SSL and internet security news

Tag Archive: academicpapers

Auto Added by WPeMatico

Spritz: A New RC4-Like Stream Cipher

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:


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


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.

Powered by WPeMatico

Analysis of Printer Watermarking Techniques

Interesting paper: Maya Embar, Louis M. McHough IV, and William R. Wesselman, “Printer watermark obfuscation,” Proceeding
RIIT ’14: Proceedings of the 3rd annual conference on Research in information technology

Abstract: Most color laser printers manufactured and sold today add “invisible” information to make it easier to determine when a particular document was printed and exactly which printer was used. Some manufacturers have acknowledged the existence of the tracking information in their documentation while others have not. None of them have explained exactly how it works or the scope of the information that is conveyed. There are no laws or regulations that require printer companies to track printer users this way, and none that prevent them from ceasing this practice or providing customers a means to opt out of being tracked. The tracking information is coded by patterns of yellow dots that the printers add to every page they print. The details of the patterns vary by manufacturer and printer model.

Powered by WPeMatico