From: Eugene Leitl (Eugene.Leitl@lrz.uni-muenchen.de)
Date: Tue Dec 31 1996 - 06:34:29 MST
On Mon, 30 Dec 1996, Eliezer Yudkowsky wrote:
John wrote:
> > 2) In an algorithm that is large, complex and messy, it's very easy to make a
> > blunder. When you add yet another wheel within a wheel you may think you're
> > making it more secure, but you may be doing the opposite, it's hard to
> > know how the change will react with all the other parts of a very messy
> > algorithm. You may have actually have created a small hole in the system
> > through which an attacker can extract a little piece of information,
> > information he shouldn't have, information he can use to expand the hole
> > until he can drive a truck through it.
Agreed. This certainly happens, and all the introductory crypto
literature is riddled with remarks that one should not mess with a given
algorithm, trying to "improve" it (apart from developing an algorithm from
scratch, while having zero cryptoanalytical experience), but I was trying to
sell something else.
Clearly, a huge algorithm which is trivial to break can exist. However,
I was trying to argument about a clear-cut algorithm family, with several
parameters, and an easy way to benchmark them, both in theory and
practice. I've looked up IDEA, and indeed, it does not contain lookup
tables, while DES, GOST, Blowfish, etc. do. Little wonder, as IDEA
substitutes opaque tables with magical code.
Consider a hypothetical computer, with code being about as succinct as an
average modern machine. Clearly, encryption cannot be done by a program
consisting of one instruction. Otoh a program the size of the entire
physical memory consisting of NOPs won't accomplish much, as well. A space
of all possible programs of given length will contain duds as well as
brilliant algorithms. The longer the program, the larger the space, the
more the absolute number of brilliant algorithms. A brilliant algorithm
can use opaque code with little data, or tiny code with a lot of magic
cookies in tables -- I'd say both can provide equally good encryption.
But while data can be created by a physical methods/automatisms, code
currently cannot. Data can be changed in the course of system evolution,
while code currently cannot, both SMC being a strong no-no, and the code
brittleness preventing this. So cryptosystems with opaque tables should win.
What does it mean, if the data encoding the Hamiltonian is changed during
the system evolution? It can be thought executing a walk in the space of
possible Hamiltonians, or being a Hamiltonian of a higher order. I
conjecture it makes it much harder to break, as SMC is typically mightier
than plain code, albeit banned (but due to its complexity!).
> In the German "Enigma", they added a little "improvement" which made it
> impossible for any letter to be encoded as itself. That, essentially,
> is how the Allies cracked it.
It was a bit more complicated than that. In the excellent book by Andrew
Hodges "Alan Turing -- the enigma" the life and works of this, sadly,
little-known scientist, is described nicely. (Hint: Andrew Hodges has
created a web site, as well).
ciao,
'gene
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:35:56 MST