Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in 
CSDb User Forums


Forums > C64 Coding > 8-bit homebrew ghetto cryptography
2021-08-23 13:14
Krill

Registered: Apr 2002
Posts: 2023
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 so
LOAD"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 Quiss
Huh. 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)
 
... 2 posts hidden. Click here to view all posts....
 
2021-08-23 15:19
Frantic

Registered: Mar 2003
Posts: 1537
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.
2021-08-23 15:39
Krill

Registered: Apr 2002
Posts: 2023
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). =)
2021-08-23 18:44
Groepaz

Registered: Dec 2001
Posts: 10009
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 :=)
2021-08-23 18:53
Quiss

Registered: Nov 2016
Posts: 24
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.
2021-08-23 19:00
Krill

Registered: Apr 2002
Posts: 2023
Quoting Quiss
The 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.
2021-08-23 23:44
Quiss

Registered: Nov 2016
Posts: 24
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.
2021-08-24 10:30
Krill

Registered: Apr 2002
Posts: 2023
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 Quiss
The 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 Quiss
For 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)?
2021-08-24 13:52
JackAsser

Registered: Jun 2002
Posts: 1841
You might wanna scramble the top eight bits also by:
for (int i = 0; i < TRANSWARPKEYSIZE; ++i) {
   key[i] ^= key[(i + 1) % TRANSWARPKEYSIZE];
}
2021-08-24 14:01
Krill

Registered: Apr 2002
Posts: 2023
Quoting JackAsser
You might wanna scramble the top eight bits also by:
for (int i = 0; i < TRANSWARPKEYSIZE; ++i) {
   key[i] ^= key[(i + 1) % TRANSWARPKEYSIZE];
}
This mixes in the result of the operation on the first byte, which is why i proposed that temp thingy. =)
2021-08-24 14:15
JackAsser

Registered: Jun 2002
Posts: 1841
Quote: Quoting JackAsser
You might wanna scramble the top eight bits also by:
for (int i = 0; i < TRANSWARPKEYSIZE; ++i) {
   key[i] ^= key[(i + 1) % TRANSWARPKEYSIZE];
}
This mixes in the result of the operation on the first byte, which is why i proposed that temp thingy. =)


Right, I see that now!
Previous - 1 | 2 - Next
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
curtcool
TheEnemy/Excess/THD
Freddie
iAN CooG/HVSC
Trash
JEZ
Fred/Channel 4
The Sarge/Fairlight
Acidchild/Padua
theK/ATL
Ghost/Excess
Shadow/G★P/Noice
Guests online: 72
Top Demos
1 Edge of Disgrace  (9.6)
2 Coma Light 13  (9.6)
3 Bromance  (9.6)
4 Uncensored  (9.6)
5 Memento Mori  (9.5)
6 Comaland 100%  (9.5)
7 Lunatico  (9.5)
8 Unboxed  (9.5)
9 Wonderland XII  (9.5)
10 Christmas Megademo  (9.5)
Top onefile Demos
1 Copper Booze  (9.7)
2 Daah, Those Acid Pil..  (9.5)
3 Dawnfall V1.1  (9.5)
4 Cityscape 2730  (9.5)
5 To Norah  (9.5)
6 Elite Code Mechanics  (9.4)
7 Lovecats  (9.4)
8 Barry Boomer - Trapp..  (9.4)
9 For Your Sprites Only  (9.4)
10 Quadrants  (9.4)
Top Groups
1 Booze Design  (9.4)
2 Oxyron  (9.3)
3 Censor Design  (9.3)
4 Crest  (9.3)
5 Triad  (9.3)
Top Graphicians
1 Mirage  (9.8)
2 Archmage  (9.7)
3 Mikael  (9.7)
4 Razorback  (9.7)
5 JonEgg  (9.6)

Home - Disclaimer
Copyright © No Name 2001-2021
Page generated in: 0.058 sec.