CRYPTO: Small Cryptosystems

John K Clark (johnkc@well.com)
Tue, 31 Dec 1996 23:16:45 -0800 (PST)


-----BEGIN PGP SIGNED MESSAGE-----

On Tue, 31 Dec 1996 Eugene Leitl <Eugene.Leitl@lrz.uni-muenchen.de> Wrote:

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

True.

>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 johnkc@well.com

-----BEGIN PGP SIGNATURE-----
Version: 2.6.i

iQCzAgUBMsoOan03wfSpid95AQHvfwTw6jzSh2Pj6QoL8EUz9OJkwiNO/Vv9q0Hl
0m8Q9fi4szHhs8moZppb8sgkgS1k2RbOtiEsr9CXq1t/oT7J9A+F9Ql0YngbwjTJ
MfNakEa6ejqZPLNBQaBs34ZLUqqRLVPaYPtr0mLJ/nYqKoVk226HQFwjgMo9o0Ix
nwAPl79JRN/CSF3XpMkeba6R+uz8nrZcDQjEMRozgZ/nOqaUnpw=
=/Zrr
-----END PGP SIGNATURE-----