How do save/load codes keep track of code integrity?

[Flux]

Do save/load codes use checksum (CRC?) or do they use a hashing algoritm (MD5)?

Example, let's say my save/load code is "L7%" which when converted to binary, let's say the result is (each character is 7 bits)
0001010 1100100 0110111 and the first 10 bits refer to the player's total gold while the remaining 11 bits refers to the player's kill count.
The problem is, if players intentionally changes the code to "L8%", then the player's kill count changes to a significantly higher value. Question is, what's the best way to detect if the code is valid. Are checksums good enough? If yes, what checksum should I use? I don't like CRC due to the high computation requirement. Also, it feels like checksums would fail at intentional changes in the code. Just look at Longitudinal Parity for example, if players change the code to "L%7" then it would fail to detect the error.

TL;DR I need help in making save/load codes that can detect the validity of itself.
EDIT: I need a way to implement a digital signature.

 

[LeP]

You are pretty much free to use anything you want.
Using something like md5 adds a lot of overhead when it's not really usefull imo.
Luckily wc3 provides us with some pseudorandom functions which should be enough for our honest wc3 needs.
GetRandomInt and StringHash

 

[Flux]

You are pretty much free to use anything you want.
Using something like md5 adds a lot of overhead when it's not really usefull imo.
Luckily wc3 provides us with some pseudorandom functions which should be enough for our honest wc3 needs.
GetRandomInt and StringHash

So what you're saying is, use hashing with StringHash as the hash value? Haven't check it yet but is StringHash case sensitive? If it is not, then players can edit the cpde to "l7%" and the system would not be able to detect the error. Also, how reliable is StringHash in terms of collision?

 

[LeP]

Yes StringHash is case insensitive. but you can easily derive a case sensitive version from it. and the good thing is that we know how StringHash works in contrast to GetRandomInt.

 

[Flux]

Yes StringHash is case sensitive. but you can easily derive a case sensitive version from it.

Wait, if it is case sensitive, why would I derive a case sensitive version??
Maybe you got a typo there, do you mean to say StringHash is case insensitive?

 

[Zwiebelchen]

Most Save/Loads simply use name encryption and apply a single simple checksum to a code to check integrity.
Nestharus' Save/Load has some extra plugins that apply CRC and MD5 if you are into extra security. Might aswell check those out.
As always, his systems are a huge mess of depencies, but it's definitely the best Save/Load in terms of compression and modularity, so in this case he deserves a big nod.

Just use it and don't think about it too much. It's night impossible to get valid results with it when entering random digits.

 

[Dr Super Good]

Do save/load codes use checksum (CRC?) or do they use a hashing algoritm (MD5)?

Simple checksums are just not enough. They are cheap to compute and often can be computed 1 bit at a time so are great for transmission protocols but are too weak for actual security needs. Hence some form of cryptographic hashing algorithm is recommended (MD5/SHA-1 etc).

Such cryptographic hashing algorithms are very secure, to the point that no one will be able to perform modifications manually or randomly. The problem is they are also very long, with ones like SHA-1 being 160 bits long so impractical for use in WC3 codes (it might be longer than your code data). I have used SHA-1 in StarCraft II banks for added security, since there code length is practically a non-issue when dealing with banks.

In WC3 you need to trade security for usability. You will probably have to come up with a simpler algorithm (as computing bitwise operations are slow) for a significantly shorter output hash (sensible code length). About 5-6 code characters is more than enough, although certainly no longer as secure as 180 bits would be.

Maybe you got a typo there, do you mean to say StringHash is case insensitive?

It is case insensitive. Which makes it perfect for player names (which are also case insensitive, just try changing your BattleNet login case and logging in).

The idea is that you combine the hash of the player name with your cryptographic hash of code data to produce the final code hash. This means that if either the code data or the player account name changes then the code hash will mismatch allowing the load to be failed. This combination of hashes saves on code length while providing similar levels of security.

 

[Nestharus]

For non-codeless, I start the code off with a value of 1 and then append all of the values. At the end, I append a knuth checksum of any size, usually taking 6 characters.

The 1 at the start is for length validation. The checksum is for content validation.

In codeless, I use MD5 and I think I still start with the 1 at the beginning.



Player uniqueness is part of the encryption process ; ).

 

[Flux]

Ok, I'll stick to a hashing since the save/load code is gonna get stored to an Save File anyway so code length isn't that big of a problem. Maybe I'll use MD5 since it is only 128 bits. Thanks!

EDIT: Hmm, MD5 was reported to be non-collision resistant. Though it must very unlikely that random changes in the code would produce the same Hash value.


Got another question somehow related to save/load systems. Are there enough (>=255) string characters for warcraft such that a single character is composed of 8 bits?

 

[Dr Super Good]

so code length isn't that big of a problem

It is a big problem because you can only enter a chat string of a certain length and apparently it is impossible/not viable to read from files automatically.

Are there enough (>=255) string characters for warcraft such that a single character is composed of 8 bits?

Yes and no. WC3 does seem to support 8 bit characters however many of them are control characters, and probably will not encode properly in files or chat. I would recommend using 7-6 bit per character at most.

Nestharus and people created systems to allow non-bit aligned characters if I recall. The approach involves base conversion techniques to convert from one base to another. This can allow you to use encoding schemes such as 100 characters with all benefits this brings which is not possible with bit-aligned character encoding. The main problem with this technique is how slow the mathematics to do the conversions are when written with JASS.

 

[Flux]

It is a big problem because you can only enter a chat string of a certain length and apparently it is impossible/not viable to read from files automatically.

Nestharus' FileIO does that. Coupled with his Network Library fo sync data to all players.

Yes and no. WC3 does seem to support 8 bit characters however many of them are control characters, and probably will not encode properly in files or chat. I would recommend using 7-6 bit per character at most.

Yeah that's the problem, control characters won't encode properly. I guess I'll have to use 7 bits per character.

 

[Dr Super Good]

Nestharus' FileIO does that. Coupled with his Network Library fo sync data to all players.

According to a conversation I had with him about 2 years ago it has a transmission rate of a few baud (1 byte a second or so if lucky)... Hence it is not viable.

 

[Nestharus]

Well, I mentioned the synchronization to Flux. The problem with Network is that it is spamming TriggerSyncReady, which floods the game with packets. We need an asynchronous solution to synchronizing, like polling every interval on a timer. This should fix the transmission rate.

 

[Flux]

So using your Network Library is not viable?

Or in general? Codeless Save/Load is not feasible?

 

[Nestharus]

It's feasible. There just isn't a library written yet. There is an experimental one that shows how fast it can be. Somebody just needs to translate the current lib over.

 

[Zwiebelchen]

So using your Network Library is not viable?

I use Network in Gaias Retaliation to broadcast a single boolean state per player (basicly a simple flag if the user has some local files or not).

Up until ~4 players this syncing happens within several seconds. With more than 4 players broadcasting a single boolean can take up to 5 minutes (making the game unable to process any player orders during the sync process).

So, currently, I'd say it's not viable until he rewrites Network.

Codeless Save/Load is not feasible?

It is feasable in 2 player co-op maps, I think (and for small amounts of data). More than 2 players? Not so much.

 

[Flux]

Wait, so this is a lie?

This uses specialized algorithms to maximize the sync speed, allowing players to synchronize even 10,000 integers from multiple players in the game to every other player in the game at the exact same time in a little over a minute.

 

[Zwiebelchen]

Wait, so this is a lie?

Not really. It doesn't say anything about what number "players" is and what average ping between players was the basis for this calculation.

From my tests in "real" Bnet sessions with the typical pings around 80-100ms (europe and american players in the same game), syncing an integer happens in a couple of seconds until you have more than 4 players in which things get painfully slow (up to 5 minutes for 6 players).

On the bright side: Network in it's current state is extremely reliable. I never encountered faulty or asynchronous data with it. So if you only want to broadcast a small amount of data for a small amount of players, it is currently your safest bet.

 

[Flux]

So if I would let's say sync 250 integers in a map consisting of only two players, based on your experience using Network Library, how much is the estimated time the sync will take?

 

[Zwiebelchen]

So if I would let's say sync 250 integers in a map consisting of only two players, based on your experience using Network Library, how much is the estimated time the sync will take?

I never tested this, tbh, as I only used it to sync one single integer.

But my guts tell me that this heavily depends on the pings between these players. Somewhere between a couple of seconds and several minutes? Probably short enough to be able to cover it up neatly with an intro cinematic.

 

[Nestharus]

Well, as I mentioned, the current reason Network is so slow is because it spams TriggerSyncReady : ). I think that we can get it to acceptable speeds for up to 12 players if we can remove the spam, which involves a partial rewrite of the library.

I'm still going on the route of using gamecache. Someone else was experimenting with ForceUIKey and events.

 

[Zwiebelchen]

Well, as I mentioned, the current reason Network is so slow is because it spams TriggerSyncReady : ). I think that we can get it to acceptable speeds for up to 12 players if we can remove the spam, which involves a partial rewrite of the library.

Well, you wrote it in the first place, so if anyone is going to rewrite it, it should probably be you.

I'm still going on the route of using gamecache. Someone else was experimenting with ForceUIKey and events.

ForceUIKey is much faster from my tests, but the downside is that it needs a checksum for data plausibility in case a player interferes with the unit. So unlike gamecache, there is no maximum to sync times and a player could theoretically delay the syncing process infinitely to annoy other players by just smashing random buttons.

 

[Nestharus]

We won't know if ForceUIKey is faster or not until I purge the network spam : P.


As for the rewrite.. haha... if someone else could that understands the lib, that'd be awesome.

 

[Zwiebelchen]

We won't know if ForceUIKey is faster or not until I purge the network spam : P.

ForceUIKey is basicly 3bit/latency when using 8 abilities plus some variable overhead depending on how often you check data integrity via the checksum.

So to sync a 32 bit integer would take between 0.2 (~20ms ping) and 2.0 (~200ms ping) seconds on average.

That seems a lot faster than gamecache, considering that SyncStoredInteger alone even without any TriggerSyncReady calls can take well over 3 seconds to sync in multiplayer sessions.

The only advantage of gamecache (and I'm not even sure about that) is that you can sync more than one integer in parallel?

 

[Nestharus]

Well Zwiebelchen, it's a little more complicated than that.

You can sync things with a gamecache in parallel in bursts. Both ForceUIKey and gamecache have limits. For ForceUIKey, it's an order limit. For gamecache, it's a packet limit. Once this limit is surpassed, the stuff gets throttled hard. While staying under this limit, things can be sync'd in parallel.

ForceUIKey can send orders, but these orders are executed linearly because of how orders work. I'm not sure what's synchronized in the background. Probably the orders themselves.

gamecache can send integers and these integers can all be sent in parallel. I sent a lot of integers in parallel in single bursts at very, very high speeds. The burst rate is probably dependent upon the number of players in the map. I think TriggerSyncReady also impacts it. This is why it slows down considerably for more players. If I can figure out the burst rate for 12 players and remove TriggerSyncReady, say hello to superspeed ; P.

edit
What might work best is a ForceUIKey from each of the players to signify that they have received the entirety of the burst : O. The broadcasting player could also use ForceUIKey when the burst has finished. This use would allow us to put the stuff to sleep until the stuff's ready to go again, rather than using a synchronous network poll. I think this is the answer : ). I'll probably work on updating Network on Friday or later today because I'm interested in seeing how it works. If I could get someone to test it with 2, 3, 4, 5, etc up to 12 players, that'd be excellent. We could work together to see if the "bandwidth" cap raises as there are more players or if we need to account for more players and lower how many bytes we burst.

 

[Zwiebelchen]

Hmm, so you mean like this?
- set gamecache integer for player 0-11 to zero
- sync gamecache integer for player 0-11 to the value you want
- periodically check if the gamecache integer of player(0-11) is non-zero --> send a "ready" response via the UIkey associated with the sending player(0-11)
- if all players sended an order: repeat with the next integer

Obviously, "integer" should actually be a set of integers (like 32? 64?) to make this time-efficient.

The only problem would be that we still need some kind of sanity check after a package of data, just to find out if the player tried to interfere by smashing buttons.

EDIT: Maybe that isn't even needed. If we use the SelectUnit native and just move the camera of the player onto black mask so that he can't select anything, we can effectively prevent the player from interferring by just doing select-ForceUIKey-Unselect. Selecting is instant if we don't have to sync the selection, right?

 

[Nestharus]

Hmm, so you mean like this?
- set gamecache integer for player 0-11 to zero
- sync gamecache integer for player 0-11 to the value you want
- periodically check if the gamecache integer of player(0-11) is non-zero --> send a "ready" response via the UIkey associated with the sending player(0-11)
- if all players sended an order: repeat with the next integer

Obviously, "integer" should actually be a set of integers (like 32? 64?) to make this time-efficient.

It's' way, way more complex than that, but you get the idea. You send bursts of data. There are several buffers as well that get filled up. These buffers are then transferred into local caches. So it's like synchronizing 500 integers at once, split across the 12 players. The buffer fills up to complete the burst. The buffer can overflow (players keep dumping to it), but only x amount of bytes are going to be sent out per burst.

In order to determine when you do the next burst, you'd have your event that notifies you. So you'd have one of these per burst.

Beyond this, you aren't actually synchronizing integers.. you are repacking the integers into groups of 4 bytes and synchronizing that, like a packet. When the packet is received, the thing is broken up and the original information is reconstructed. One burst is maybe 500 packets. One packet is 4 bytes.