But I also wonder whether there might be advantages to ciphers with huge keys. In this post, I'll describe a big, ugly cipher I'll call Carcharias, which uses massive keys and lots of memory. Since Carcharias is a big fish, I'll talk in terms of bytes instead of bits.

**The Key**

**Carcharias is a Feistel cipher with a block size of 512 bytes and a key size of 16,777,216 bytes. The key is huge, right? But you could store hundreds of them on a modern thumb drive without any problem, and it will fit in a modern processor's memory quite easily. As with any other cipher, the ideal key is as random as possible, but the question of how to generate a good random key is outside the scope of this post.**

**The Round Function**

Since Carcharias is a Feistel cipher, it processes the block in two halves (256 bytes) using a round function. In the following pseudocode for the round function, the key is treated as a three-dimensional array of bytes (256 x 256 x 256), and the subkey, input and output are treated as arrays of bytes. This isn't the most efficient implementation...it's just meant to be illustrative.

for (i = 0; i < 0x100; ++i) {

output[i] = 0;

for (j = 0; j < 0x100; ++j) {

output[i] ^= key[i][j][input[j] ^ subkey[j]];

}

}

Mathematically, it doesn't get much simpler than this. You've got a couple XOR operations and some pointer math, but every bit of the output is dependent on every bit of the input. You throw that into a Feistel network and you have pretty good confusion and diffusion.

Incidentally, in a few years I think processors will probably carry enough memory that you could implement a 4 GB key, treated as a four-dimensional array, in which case Carcharias could be replaced by Megalodon, using this line instead:

output[i] ^= key[i][j][input[j]][subkey[j]];

It's big. It's ugly. It's brutish.

**Advantages**

Provided the key is very random and the key transmission secure, I think Carcharias and Megalodon can only be attacked by brute force. The brute force attack must use a large amount of memory, which might make it harder to farm out to a bunch of processors running in parallel.

If I have time, I'll write an implementation of Carcharias and post it on github.

Note (12/2/2013): This has some potential weaknesses if the key (which is essentially a huge S-box) is too close to a linear function. Also, it's really overkill, and there is no need for something like this in the world :)

## No comments:

## Post a Comment