#33819 - LOst? - Sun Jan 09, 2005 5:58 pm
A lot of people talk about XOR encryption in the DS forum.
I wonder how to code XOR enctyption for my hi-score data (so that no one can edit it with a hexeditor).
How does it work?
An idea of mine: byte ^= magic_number?
C++ explanation would be great. I hope it is simple to code.
#33820 - Soccr743 - Sun Jan 09, 2005 6:10 pm
XOR encryption is definitely not the best way to go since it can be easily broken compared to other forms.
You have a key of a certain length that you use to xor byte by byte against your data. Then you get the encrypted data from that output.
So a quick mockup would be:
char key [8] = "aIm0z9c2";
char data [18] = "Hello how are you?";
char xor_data [18];
int data_place = 0;
int key_place = 0;
while(data_place++ < sizeof(data)){
xor_data[data_place] = data[data_place] ^ key[key_place];
key_place++;
key_place = (key_place < sizeof(key)) ? key_place : 0;
}
I think that would be what you are looking for. But remember that this isnt the most secure method at all...
-----Soccr743-----
_________________
http://www.cubedstudios.com
#33821 - LOst? - Sun Jan 09, 2005 6:21 pm
| Quote: |
I think that would be what you are looking for. But remember that this isnt the most secure method at all...
-----Soccr743----- |
Thank you for the help! Yea I know it isn't thje safest form, but it is safer than plane ascii :P
#33822 - poslundc - Sun Jan 09, 2005 6:21 pm
For simple storing of something like high score data, if all you want to do is make it tamper-resistant, then XOR-encryption is probably plenty. (More than most games bother with, anyway.)
The importance of XOR for encryption is that you can encrypt a value by XORing it against a magic number, and then XOR it against that same magic number to obtain the original value. In other words,
C = A ^ B to encrypt, and then
A = C ^ B to decrypt.
Dan.
#33823 - LOst? - Sun Jan 09, 2005 6:24 pm
| poslundc wrote: |
For simple storing of something like high score data, if all you want to do is make it tamper-resistant, then XOR-encryption is probably plenty. (More than most games bother with, anyway.)
The importance of XOR for encryption is that you can encrypt a value by XORing it against a magic number, and then XOR it against that same magic number to obtain the original value. In other words,
C = A ^ B to encrypt, and then
A = C ^ B to decrypt.
Dan. |
Yea, that's what I thought. Now Soccr743 also reminded me that you can use more than just one byte as a magic number.
Interesting to see XOR being useful for something else other than turning a flag on and off.
#33833 - Soccr743 - Sun Jan 09, 2005 8:06 pm
Yea definitely use more then one of what you call "a magic number" if you are going to use XOR to encrypt bytes of data.
Because if you use only one then you have a message Hello that goes into something like y9jj4 (hypothetically) because both l's xored with the same byte become the same thing. If you have a key of a longer length, it will not repeat the same letters as often.
-----Soccr743-----
_________________
http://www.cubedstudios.com
#33840 - LOst? - Sun Jan 09, 2005 9:13 pm
| Soccr743 wrote: |
Yea definitely use more then one of what you call "a magic number" if you are going to use XOR to encrypt bytes of data.
Because if you use only one then you have a message Hello that goes into something like y9jj4 (hypothetically) because both l's xored with the same byte become the same thing. If you have a key of a longer length, it will not repeat the same letters as often.
-----Soccr743----- |
Yea. I mostly want to hide repeated letters and numbers so thank you for sharing your code example and your ideas!
I will probably XOR the hi-score, and then compress it with LZSS >=D
It will not compress any good, but it with make the crypted data harder to mess with.
#33851 - bertsnks - Sun Jan 09, 2005 11:42 pm
| LOst? wrote: |
| Soccr743 wrote: | Yea definitely use more then one of what you call "a magic number" if you are going to use XOR to encrypt bytes of data.
Because if you use only one then you have a message Hello that goes into something like y9jj4 (hypothetically) because both l's xored with the same byte become the same thing. If you have a key of a longer length, it will not repeat the same letters as often.
-----Soccr743----- |
Yea. I mostly want to hide repeated letters and numbers so thank you for sharing your code example and your ideas!
I will probably XOR the hi-score, and then compress it with LZSS >=D
It will not compress any good, but it with make the crypted data harder to mess with. |
Not quite. A high score number, split into bytes will mostly have different bytes. LZSS cannot compress different bytes, and thus your highscore would show up uncompressed in a hex editor.
#33872 - LOst? - Mon Jan 10, 2005 5:29 am
| bertsnks wrote: |
| LOst? wrote: | | Soccr743 wrote: | Yea definitely use more then one of what you call "a magic number" if you are going to use XOR to encrypt bytes of data.
Because if you use only one then you have a message Hello that goes into something like y9jj4 (hypothetically) because both l's xored with the same byte become the same thing. If you have a key of a longer length, it will not repeat the same letters as often.
-----Soccr743----- |
Yea. I mostly want to hide repeated letters and numbers so thank you for sharing your code example and your ideas!
I will probably XOR the hi-score, and then compress it with LZSS >=D
It will not compress any good, but it with make the crypted data harder to mess with. |
Not quite. A high score number, split into bytes will mostly have different bytes. LZSS cannot compress different bytes, and thus your highscore would show up uncompressed in a hex editor. |
Yea I just saw that x.x;;
#33874 - tepples - Mon Jan 10, 2005 5:37 am
If you want to compress and encrypt, it's usually wise to compress first, as encryption covers up the correlations that compression relies on. Besides, why would you need to compress a high score table?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#33875 - LOst? - Mon Jan 10, 2005 5:58 am
| tepples wrote: |
| If you want to compress and encrypt, it's usually wise to compress first, as encryption covers up the correlations that compression relies on. Besides, why would you need to compress a high score table? |
It was before I knew XOR crypto. I thought it would be a way to hide the score by compressing it with someting as high as LZSS. But when I tried it, it just added bytes more than compressing it, and the names and score weren't hidden.
#33891 - denopqrihg - Mon Jan 10, 2005 9:14 pm
Even the save in Pokemon R/S uses only XOR encryption (and not too good :-)
#33893 - sgeos - Mon Jan 10, 2005 9:36 pm
You could seed an RNG to create a weak one time key:
| Code: |
void xor_encrypt(char *p_data, int p_size, unsigned long p_seed)
{
unsigned long old_seed;
unsigned char xor_mask;
int i;
/* Save current RNG state
*/
old_seed = get_rng_seed();
/* Seed one time key
*/
seed_rng(p_seed);
/* Encrypt data
*/
for (i = 0; i < p_size; i++) {
xor_mask = (unsigned char) rng_range(0, 255);
data[i] ^= xor_mask;
}
/* Restore old RNG state
*/
seed_rng(old_seed);
} |
Call it once to encrypt, call it again to decrypt.
-Brendan
#33927 - LOst? - Tue Jan 11, 2005 5:18 am
| sgeos wrote: |
You could seed an RNG to create a weak one time key:
| Code: | void xor_encrypt(char *p_data, int p_size, unsigned long p_seed)
{
unsigned long old_seed;
unsigned char xor_mask;
int i;
/* Save current RNG state
*/
old_seed = get_rng_seed();
/* Seed one time key
*/
seed_rng(p_seed);
/* Encrypt data
*/
for (i = 0; i < p_size; i++) {
xor_mask = (unsigned char) rng_range(0, 255);
data[i] ^= xor_mask;
}
/* Restore old RNG state
*/
seed_rng(old_seed);
} |
Call it once to encrypt, call it again to decrypt.
-Brendan |
One problem. I don't know what a RNG is.
#33930 - poslundc - Tue Jan 11, 2005 5:30 am
#33938 - phantom-inker - Tue Jan 11, 2005 9:38 am
Rather than using an external RNG, I tend to prefer just hacking together a simple linear-congruential-feedback generator. The code's insanely simple, and compiles to very efficient assembly, even if it's not super-random. It certainly saves having to have an external set of RNG functions.
Here's how to convert the code above, using the classic 69069 multiplier, and 1234567 (any interesting nonzero number will do) for c:
| Code: |
void xor_encrypt(char *data, int size, unsigned long seed)
{
int i;
/* Make the seed more stable, so that zero seeds don't produce bad results.
Could use an XOR or add here instead if speed was vital. */
seed = seed * 69069 + 1234567;
/* Encrypt data */
for (i = 0; i < size; i++) {
seed = seed * 69069 + 1234567;
data[i] ^= (char)((seed >> 24) & 0xFF);
}
}
|
In this example, seed will cycle with 2^32 period. Not too shabby for a one-line PRNG. The lack of function calls alone will usually make this many times faster than the other version above. Note that we shift down the high bits of seed when we XOR, because they cycle with longer periods than the low bits.
If 69069 doesn't make you feel good enough, you could try 1664525, which is known to be an even better multiplier for LCGs like this that have period 2^32. (Note: Don't just pick any old number for a multiplier; you're best off using one that's known to be good. See Knuth 3.3.4 for more details, if you dare.)
You can speed this up and shrink it a little by switching to pointers, too. Here's a version that's faster, smaller, and more random:
| Code: |
void xor_encrypt(char *data, int size, unsigned long seed)
{
/* Make the seed more stable, so that zero seeds don't produce bad results. */
seed ^= 0xDEADBEEF;
/* Encrypt data */
while (size--) {
seed = seed * 1664525 + 1234567;
*data++ ^= (char)((seed >> 24) & 0xFF);
}
}
|
Nice, huh?
_________________
Do you suppose if I put a signature here, anyone would read it? No? I didn't think so either.
#33949 - poslundc - Tue Jan 11, 2005 2:46 pm
| phantom-inker wrote: |
| Rather than using an external RNG, I tend to prefer just hacking together a simple linear-congruential-feedback generator. |
LCG's aren't really an "alternative" to random-number generators; for all intents and purposes a good LCG is a random-number generator (pseudo-random, of course). In fact, the Unix rand() function is an LCG, I believe.
While I wouldn't want to use it for statistical applications, real-money gambling, or serious cryptography or anything, I am hard-pressed to think of a handheld console videogame where an LCG would be insufficient as a random-number generator, especially given the efficiency they provide.
Dan.
#33966 - Miked0801 - Tue Jan 11, 2005 7:29 pm
It's suprising how these types of generators do fail though. We used a very similiar routine on Heroes of M&M - GBC (turn based strategy game) and were very suprised at how non-random it could become depending on timing. Nothing like losing 5 fights in a row where you had a 75% chance (on paper) of winning. We ended up generating a table of 256 entries, each 8-bit number occuring once, and prime number stepping through it. Only 256 different combos I know, but it felt much better :)
Mike
#33969 - poslundc - Tue Jan 11, 2005 7:41 pm
That's a good point that I left out, and especially in a turn-based game there are more opportunities to fall into a pattern than an action-based game.
LCGs are also heavily affected by the parameters used for them. I don't suppose you'd remember what you used back on M&M, would you? I've been using BCPL and it's performed pretty well for me so far in practice (at least I never have noticed any suspicious patterns emerging), but it would be good to know if it's less reliable for turn-based apps.
Thanks,
Dan.
#33975 - LOst? - Tue Jan 11, 2005 9:24 pm
I don't even know what a seed is.
And I don't know how you can make the XOR mask by a random number when you need the same number the next time (probably after a restart of the GBA) to encrypt the data.
#33980 - phantom-inker - Tue Jan 11, 2005 10:42 pm
| LOst? wrote: |
I don't even know what a seed is.
And I don't know how you can make the XOR mask by a random number when you need the same number the next time (probably after a restart of the GBA) to encrypt the data. |
A seed is just some number you pick for it to start with. Zero will work.
To encrypt your data, call the function I gave above like this:
| Code: |
| xor_encrypt(my_data, size_of_my_data, 0); |
To decrypt your data, call the function like this:
| Code: |
| xor_encrypt(my_data, size_of_my_data, 0); |
Notice that it's the same to encrypt or decrypt... distressingly symmetric, but good enough for simple information hiding. ;)
| Mike0801 wrote: |
| We used a very similiar routine on Heroes of M&M - GBC (turn based strategy game) and were very suprised at how non-random it could become depending on timing. |
Were you using the high bits of the seed, or the low ones? The low bits have very poor behavior in an LCG, having relatively short periods. The high bits, though, are usually pretty random, with very long periods (the top bit of the RNGs I gave above only cycles with period 2^32, for example). I've had very little problems with just sampling off the top four bits of every iteration and using those --- of course, that requires a lot more multiplies, and does shorten the overall period to 2^29. But that's good enough for most "predictable" RNGs.
_________________
Do you suppose if I put a signature here, anyone would read it? No? I didn't think so either.
#34021 - Miked0801 - Wed Jan 12, 2005 8:02 pm
Lol again - GBC == software multiply and 2Mhz CPU. Our random calls tended to be pretty simple. I'm looking at the original Z80 code right now and, it burnzzzes! It burnnnzzzes! Stop the pain! Argh! Ok, now that I remember how to read Z80....
We stepped through the table sequentially and did a software mod to get our number.
We tried taking the seed, indexing into the table, take that value / 8, xor the value there to the index and add the system clock to that. Then rotate the whole seed weird. Dunno where we got that. I'd post the Z80, but no one would be able to read it.
We also tried the Twister? algorithm at one point, but again for the GBC, the simple table/mod function worked best.
Wow that was fun :)
#34073 - LOst? - Thu Jan 13, 2005 5:33 am
Z80 will be the very last processor I will look into. I hate it. How can you produce a game using it anyway? I don't like 8-bit games to begin with. I have own a Sega Master System so I know the result of Z80.
#34075 - tepples - Thu Jan 13, 2005 7:08 am
| LOst? wrote: |
| Z80 will be the very last processor I will look into. I hate it. How can you produce a game using it anyway? |
First of all, you need an F2A and a GB Bridge.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#34091 - poslundc - Thu Jan 13, 2005 2:53 pm
| LOst? wrote: |
| Z80 will be the very last processor I will look into. I hate it. How can you produce a game using it anyway? I don't like 8-bit games to begin with. I have own a Sega Master System so I know the result of Z80. |
God, it makes me feel old that I find this quote so upsetting. Get off your high horse, boy; I've done some Z80 programming in the past and I'm frankly amazed by what has been done with it on platforms like the GB. Your predecessors have spun straw into gold, and paved the way for the technology you take for granted.
Dan.
#34127 - Miked0801 - Thu Jan 13, 2005 10:28 pm
| Quote: |
Z80 will be the very last processor I will look into. I hate it. How can you produce a game using it anyway? I don't like 8-bit games to begin with. I have own a Sega Master System so I know the result of Z80.
|
You're making me feel old as well. The Z80 in many ways is superior to the 8086/8088 intruction set. More registers, less arbitrary reliance on certain registers needed for certain commands, did I mention more registers (shadow). Alas, the GB had a bastardized Casio chip in it emulating a Z80 missing 60% of the register space and 50% of the cool ops. Grumble.
And the Sega master system "results" have more to do with the word Sega than Z80...
#34139 - phantom-inker - Fri Jan 14, 2005 4:07 am
| Miked0801 wrote: |
| Lol again - GBC == software multiply and 2Mhz CPU. |
True. I forgot the architecture. But, still, coding up a simple LCG for a low modulus (16 bits?) wouldn't be too hard, and it'd be easy to perform an exhaustive search for a "good" multiplier for a small modulus (based on the spectral test). Once you've found your multiplier, coding up a good 8-bit assembly implementation of a fixued multiplication is probably only about 100-ish instructions (least, that's what I'd expect on a 6502; it's probably a similar order on a Z80).
| LOst? wrote: |
| Z80 will be the very last processor I will look into. I hate it. How can you produce a game using it anyway? |
You'd be surprised what you can do on an 8-bit processor. I cut my teeth on a 6502 at 1 MHz twenty years ago (yay for the Apple ][!). You can learn a lot from simpler computers if you take a little time to study them.
_________________
Do you suppose if I put a signature here, anyone would read it? No? I didn't think so either.
#34141 - LOst? - Fri Jan 14, 2005 4:27 am
| Miked0801 wrote: |
| Quote: |
Z80 will be the very last processor I will look into. I hate it. How can you produce a game using it anyway? I don't like 8-bit games to begin with. I have own a Sega Master System so I know the result of Z80.
|
You're making me feel old as well. The Z80 in many ways is superior to the 8086/8088 intruction set. More registers, less arbitrary reliance on certain registers needed for certain commands, did I mention more registers (shadow). Alas, the GB had a bastardized Casio chip in it emulating a Z80 missing 60% of the register space and 50% of the cool ops. Grumble.
And the Sega master system "results" have more to do with the word Sega than Z80... |
Wow, I just made a huge mistake. I had no idea Gameboy used the Z80 unil this very moment. Now I see why I shouldn't have said that on a Gameboy messageboard.
Of course Z80 is okay. But Gameboy sucks man *shot*
Okay enough of the jokes. I'm not a very big fan of 8 bit or the old Gameboy. Some of you have worked a lot with it so of course I made you upset. I'm 16 bit all the way. I even see GBA as 16 bit. As long as you can jump 32-bit/24-bit. I kinda hate 286 for 16 bit segment/offset jumps.