CRYPTO: Small Cryptosystems

John K Clark (
Tue, 31 Dec 1996 23:16:45 -0800 (PST)


On Tue, 31 Dec 1996 Eugene Leitl <> Wrote:

>I've looked up IDEA, and indeed, it does not contain lookup


>while DES, GOST, Blowfish, etc. do.

Yes, but with Blowfish and RC4 an attacker does not know what the lookup
tables are.

>cryptosystems with opaque tables should win.

DES was made public by the National Security Agency (NSA) in 1975 and it
certainly has lookup tables, but until 1990 nobody outside of the NSA
understood why the table, called the S box, had the numbers in it that it did.
They were truly opaque.

In 1990 Biham and Shamir discovered Differential Cryptanalysis, rediscovered
it really, because it was found that the S box in DES was optimized to make
Differential Cryptanalysis difficult. Clearly somebody at the NSA knew about
Differential Cryptanalysis in 1975 and probably much earlier, but the rest of
the world didn't know about it till 1990.

In 1993 Matsui discovered Linear Cryptanalysis and it was found that the
S box in DES was NOT optimized to defend against it, in fact, if you picked
numbers at random to fill the S box there is only a 9% chance it would work
as poorly against a Linear Cryptanalysis attack as the one the NSA gave us.
Either the NSA didn't know about Linear Cryptanalysis in 1975 or they
deliberately gave it a weakness.

Blowfish has something like an S box, but it is key dependent so is unknown
to an attacker. The very simple RC4 algorithm generates a lookup table from
the key too, and then constantly mutates it as you use it, this makes using
Cryptanalysis much more difficult, perhaps impossible.

John K Clark

Version: 2.6.i