From: Peter Wayner <pcw@access.digex.net>
Date: Wed, 11 Aug 93 10:57:00 PDT
To: gnu@toad.com
Subject: Re:  Chaos harnessed for encryption / Fluctuations and Order research
Message-ID: <199308111755.AA03541@access.digex.net>
MIME-Version: 1.0
Content-Type: text/plain



There was a paper several years back in Cryptologia that came to 
the conclusion that many of the chaotic functions were unsuitable
for encryption. By this, they mean the "classic" chaotic functions
like the Lorentz attractor. DES is obviously a very nice chaotic 
generator. 

The problem with the systems has its basis in the philosophical
foundations of the field. Mathematicians have been basically
saying, "Like Wow. These very simple equations just generate
stuff that is totally out of whack." The equations are just
simple differential equations that go kablooie. In many cases,
though, the kablooie only means that a small pertubation in 
the system causes large changes in the outcome. While this
is a necessary effect for solid encryption, it is not sufficient
for a good system. What we really want to know is whether
you can recover x from f(x) where f is the encryption function. 
if f(x+small value) is wildly different from f(x), then this
is good, but not good enough. 

Now, think a minute about the "synchronization" of these two
chaotic generators. This means that both ends of the conversation
have set their scramblers to the same "key". But since this
is analog, things might not be _exactly_ the same on both 
ends. If this was a really chaotic system then the tiny differences
in the two systems should make things go kablooie. 

My guess is that they figured out some way to use a feedback
mechanism to fix small pertubations and keep things from going
kablooie in a small range. I would guess that this could lead
to a hole for attacking the system. Just a guess, though. 

This insight is similar to the holes that people found in 
linear feedback shift registers. These systems are pretty
good random number generators, but they're not secure if
the user can guess a few bits of your message. Why? Because
the equations are simple enough to be inverted. 

The only question is whether the chaotic equations can be inverted.
I think that the Cryptologia paper came to the conclusion that
it could be done. 

I'm sorry I don't have a complete reference to the Cryptologia
paper. Perhaps my memory is a bit flawed here as well. 

It would be interesting, though, to study the EE times article
in depth. I think John is right that there is a certain amount
of philosophical convergence between the work at MIT and the
work at Los Alamos.

-Peter