| |
Krill
Registered: Apr 2002 Posts: 2982 |
8-bit homebrew ghetto cryptography
After the Transwarp crypto challenge was so swiftly and thoroughly beaten, i decided to put in some effort and make it as hard as i can (while still not considerably slowing down loading nor sacrificing checksumming) for the next release.
Request for comments: I'm posting this here because i might have missed some weaknesses (or more devious encryption ideas), and because the secret is supposed to lie entirely with the key, not the algorithm.
Both the encryption and decryption routines will be released in source.
The key is now ~229.32 bits (~28.67 bytes, rounded to 29 bytes) large instead of a puny 40 bits (5 bytes).
To make a key this large somewhat practical to use, encrypted files are now loaded with a pass-phrase, like soLOAD"SECRET",8,1,"THE REAL PARTY IS OUTSIDE" The pass-phrase isn't the key. Instead, the key is generated from the pass-phrase using some kind of cryptographic hash function derived from this answer to a very similar problem.
The idea is to make reconstructing the pass-phrase from discovered parts of the key as hard as possible (while still limiting complexity to sensible 8-bit/1 MHz constraints). Note that longer pass-phrases are more secure, as usual, but more than 29 characters are ignored.
The key is then split up into smaller parts and applied like this:
1. 11 bytes (88 bits)
8 bytes are used as a simple EOR mask on the 8-byte Transwarp file metadata in the directory (load and end addresses, start track, number of blocks, checksums).
3 bytes are used as initial values for various decoding/transfer loops.
2. ~11.62 bytes (~92.99 bits)
File data bytes are transferred in bitpairs. Individual bit positions and bitpair values (0..3) are scrambled with this part of the key. As one of the 4 bitpairs in a byte is fixed both in position and values, there remain 6 arbitrary bit positions, with 4 different values for each of those 3 bitpairs, in 4 "types" of transferred bytes. This yields ((6!)*(4!^3))^4 (a little less than 10^28) different permutations for the data scrambling.
3. ~6.04 bytes (~48.3 bits)
A track consists of 17 to 21 sectors depending on density zone. The order of the first 17 sectors on all (but the last) file tracks (where those blocks go to in C-64 memory) is scrambled. This yields 17! (more than 355 million million) different permutations for the block position scrambling.
Quoting QuissHuh. I'll be curious to see what kind of 4k effect you need these kinds of cryptographic shenanigans for. :) from Long division/modulo with byte-size divisor
There. =) (8K, though. =D) |
|
| |
Frantic
Registered: Mar 2003 Posts: 1648 |
Is this a useful feature to begin with? :) |
| |
Krill
Registered: Apr 2002 Posts: 2982 |
Quoting FranticIs this a useful feature to begin with? :) Yes, useful for fun. =)
But it could also be used to delay cracking a (linear) game somewhat, but then the pass-phrase for each successive level must be well-hidden or derived from the expected game-state at that point or something.
Still, asking for usefulness in the demoscene...? =D |
| |
Frantic
Registered: Mar 2003 Posts: 1648 |
Doing things for fun is certainly reason enough to do it. I was just asking myself whether there was some obvious use for this feature, but couldn't think of any. |
| |
Krill
Registered: Apr 2002 Posts: 2982 |
It's just an optional file encryption feature, with the usual reasons for why you would want to have or distribute encrypted files (or not). =) |
| |
chatGPZ
Registered: Dec 2001 Posts: 11391 |
change the on disk format slightly so it does NOT work in d64 anymore, then make some properly obfuscated startup code which derives the passphrase while it executes.... and you have a tough nut for all those "crackers" of today :=) |
| |
Quiss
Registered: Nov 2016 Posts: 43 |
I'm glad you're adding secret part tooling into your loaders. :)
The perm32() "hash" from the stackexchange post looks invertible. Not sure whether that means your version is, too. |
| |
Krill
Registered: Apr 2002 Posts: 2982 |
Quoting QuissThe perm32() "hash" from the stackexchange post looks invertible. Shouldn't be, at least not trivially.
Quote:alternating bitwise eXclusive-OR and addition modulo 2^32 results in non-linearity. The non-linearity should make inversion (without brute-forcing) pretty hard.
This is my version:#define TRANSWARPKEYSIZE 29 /* 232 bits */
#define TRANSWARPKEYHASHROUNDS 33
for (int round = TRANSWARPKEYHASHROUNDS; round > 0; --round) {
for (int i = 0; i < (TRANSWARPKEYSIZE - 1); ++i) {
key[i] ^= key[i + 1];
}
for (int i = TRANSWARPKEYSIZE - 1; i >= 0; --i) {
int product = key[i] * 0x6b;
key[i] = product;
int msb = product >> 8;
for (int j = i + 1; j < TRANSWARPKEYSIZE; ++j) {
msb += key[j];
key[j] = msb;
msb >>= 8;
}
}
int sum = round;
for (int i = 0; i < TRANSWARPKEYSIZE; ++i) {
sum += key[i];
key[i] = sum;
sum >>= 8;
}
} The same hashing algorithm (in a 6502 assembly incarnation) is executed on the C-64. This is the most expensive part of the encryption scheme, luckily only executed once before loading. |
| |
Quiss
Registered: Nov 2016 Posts: 43 |
Hmmm, pretty sure that's invertible, too.
The first inner loop leaves key[TRANSWARPKEYSIZE - 1] alone, with you can then use to deduce key[TRANSWARPKEYSIZE - 2], etc.
For the second inner loop, note that 0x6b6b6b...6b has a multiplicative inverse modula 2^232.
For the third inner loop, note that the new key[0] is just the old key[0] plus the round, so subtract round and jot down the carry, which is needed for key[1] etc.
Of course, you'll need to do those blocks (and the rounds) in reverse order. |
| |
Krill
Registered: Apr 2002 Posts: 2982 |
Okay, yes, the function is trivially reversible if you know the entire key* (it's more like a block cipher than a cryptographic hash function). Hope is that when only knowing parts of the key, the function is not reversible.
* The entire key plus the few extra bits to fill up the final byte.
Maybe the "virtual" key should be much larger than the bits used for encryption, such that a large portion of the key to be reversed would have to be guessed/bruteforced. This would be like using a truncated block-cipher encrypted block as a hash value.
Quoting QuissThe first inner loop leaves key[TRANSWARPKEYSIZE - 1] alone, with you can then use to deduce key[TRANSWARPKEYSIZE - 2], etc. True. What about something more like rotation, as in char temp = key[0];
for (int i = 0; i < (TRANSWARPKEYSIZE - 1); ++i) {
key[i] ^= key[i + 1];
}
key[TRANSWARPKEYSIZE - 1] ^= temp; Quoting QuissFor the second inner loop, note that 0x6b6b6b...6b has a multiplicative inverse modula 2^232. It's BIGNUM *= 0x6b, however. But yes, the top 8 bits falling out of the resulting bignum can be reconstructed by dividing the truncated result plus a tentative top byte (0..255) by $6b until the result is an integer (and thus the reconstructed value prior to multiplication).
So then, what about using temp again (or some other byte of the initial key for this round) to EOR a byte of the value prior to multiplication, or to use as fractional part (such as BIGNUM.temp *= 0x6b)? |
| |
JackAsser
Registered: Jun 2002 Posts: 2014 |
You might wanna scramble the top eight bits also by:
for (int i = 0; i < TRANSWARPKEYSIZE; ++i) {
key[i] ^= key[(i + 1) % TRANSWARPKEYSIZE];
}
|
... 2 posts hidden. Click here to view all posts.... |
Previous - 1 | 2 - Next |