Last week, Ron Rivest gave a talk at MIT about Spritz, a new stream cipher by him and Jacob Schuldt. It's basically a redesign of RC4, given current cryptographic tools and knowledge.
RC4 is an example of what I think of as a too-good-to-be-true cipher. It looks so simple. It is so simple. In classic cryptographic terms, it's a single rotor machine. It's a single self-modifying rotor, but it modifies itself very slowly. Even so, it's very hard to cryptanalyze. Even though the single rotor leaks information about its internal state with every output byte, its self-modifying structure always seems to stay ahead of analysis. But RC4 been around for over 25 years, and the best attacks are at the edge of practicality. When I talk about what sorts of secret cryptographic advances the NSA might have, a practical RC4 attack is one of the possibilities.
Spritz is Rivest and Schuldt's redesign of RC4. It retains all of the problems that RC4 had. It's built on a 256-element array of bytes, making it less than ideal for modern 32-bit and 64-bit CPUs. It's not very fast. (It's 50% slower than RC4, which was already much slower than algorithms like AES and Threefish.) It has a long key setup. But it's a very clever design.
Here are the cores of RC4 and Spritz:
RC4:
1: i = i + 1
2: j = j + S[i]
3: SWAP(S[i];S[j])
4: z = S[S[i] + S[j]]
5: Return z
Spritz:
1: i = i + w
2: j = k + S[j + S[i]]
2a: k = i + k + S[j]
3: SWAP(S[i];S[j])
4: z = S[j + S[i + S[z + k]]]
5: Return z
S is an 8-bit permutation. In theory, it can be any size, which is nice for analysis, but in practice, it's a 256-element array. RC4 has two pointers into the array: i and j. Spritz adds a third: k. The parameter w is basically a constant. It's always 1 in RC4, but can be any odd number in Spritz (odd because that means it's always relatively prime to 256). In both ciphers, i slowly walks around the array, and j -- or j and k -- bounce around wildly. Both have a single swap of two elements of the array. And both produce an output byte, z, a function of all the other parameters. In Spritz, the previous z is part of the calculation of the current z.
That's the core. There are also functions for turning the key into the initial array permutation, using this as a stream cipher, using it as a hash function, and so on. It's basically a sponge function, so it has a lot of applications.
What's really interesting here is the way Rivest and Schuldt chose their various functions. They basically tried them all (given some constraints), and chose the ones with the best security properties. This is the sort of thing that can only be done with massive computing power.
I have always really liked RC4, and am happy to see a 21st-century redesign. I don't know what kind of use it'll get with its 8-bit word size, but surely there's a niche for it somewhere.
Tags: academic papers, cryptanalysis, cryptography, encryption, RC4
Posted on October 27, 2014 at 9:55 AM
•
23 Comments