Fractal cryptography

There have been some discussions on sci.crypt within the past few months
on nonlinear/chaotic algorithms and their use in cryptography.  Fractal
cryptography sounds like it might be related.  The problem is that unless
an algorithm was SPECIFICALLY DESIGNED to prevent an intelligent adversary
from defeating it, the chances of it being an effective cryptosystem are
limited.  Just because nonlinear systems produce complex-looking results
does not mean that these results are unpredictable given enough data.

Now, maybe this particular fractal cryptosystem idea will actually work
well.  I don't know; I haven't seen it.  But the point is that these
complex types of systems have not provided a good foundation for crypto-
graphy in the past.

sci.crypt messages are available on (at least) ripem.msu.edu, in
/pub/crypt/sci.crypt.  In that directory there is a file "subjects",
which lists all the subject lines by message number, as well as a collection
of files each of which holds a couple of months' worth of messages.  You
can grep the subjects file to find those messages which might be i{terested.
The archives appear to go back a couple of years.

Hal

hfinney@shell.portal.com (Hal Finney) wrote:

> There have been some discussions on sci.crypt within the past few months
> on nonlinear/chaotic algorithms and their use in cryptography.  Fractal
> cryptography sounds like it might be related.  The problem is that unless
> an algorithm was SPECIFICALLY DESIGNED to prevent an intelligent
> adversary from defeating it, the chances of it being an effective
> cryptosystem are limited.  Just because nonlinear systems produce
> complex-looking results does not mean that these results are unpredictable
> given enough data.

Yeah, but how much data?  Just because something can be solved given
enough data doesn't help me break it if I need 10^37643254 bytes of data
to do it.

> Now, maybe this particular fractal cryptosystem idea will actually work
> well.  I don't know; I haven't seen it.  But the point is that these
> complex types of systems have not provided a good foundation for crypto-
> graphy in the past.

Well, here's a little test.  The following numbers were generated using
a chaotic function:

568139551155097445567935056793172821494566808655678121156334445567812121480659

Do you see a pattern?  What function did I use to generate it?  :)

(Actually, assuming you knew what function I used, you could probably
solve for the key if you had enuf raw output from the PRNG, so it's
probably not completely impossible to solve the above, but that wouldn't
necessarily help you decrypt a file which had been encoded with such a
pad, unless you knew a lot about the format of the file.)

Matthew J Ghio says:
> hfinney@shell.portal.com (Hal Finney) wrote:
> 
> > There have been some discussions on sci.crypt within the past few months
> > on nonlinear/chaotic algorithms and their use in cryptography.  Fractal
> > cryptography sounds like it might be related.  The problem is that unless
> > an algorithm was SPECIFICALLY DESIGNED to prevent an intelligent
> > adversary from defeating it, the chances of it being an effective
> > cryptosystem are limited.  Just because nonlinear systems produce
> > complex-looking results does not mean that these results are unpredictable
> > given enough data.
> 
> Yeah, but how much data?  Just because something can be solved given
> enough data doesn't help me break it if I need 10^37643254 bytes of data
> to do it.

Amateurs regularly develop systems and claim fantastic things for
them. They then turn out to be trivial to break. This has made people
who are even semi-pro like some of the folks on this list shake their
heads and say "oh no, not another one" every time someone who hasn't
read the literature claims to have come up with "the new great
cryptosystem". This is the reason that people tend to be so skeptical
of the constant stream of new proposals from such individuals. Its
nothing personal -- its just the sort of jaded attitude you get when
this sort of thing happens repeatedly.

Perry

"Perry E. Metzger" <pmetzger@lehman.com> wrote:

> Amateurs regularly develop systems and claim fantastic things for
> them. They then turn out to be trivial to break. This has made people
> who are even semi-pro like some of the folks on this list shake their
> heads and say "oh no, not another one" every time someone who hasn't
> read the literature claims to have come up with "the new great
> cryptosystem". This is the reason that people tend to be so skeptical
> of the constant stream of new proposals from such individuals. Its
> nothing personal -- its just the sort of jaded attitude you get when
> this sort of thing happens repeatedly.

This is true.  If you were specifically referring to the example I
posted, it could probably be broken from the data presented if you
really put your mind to it.  However it is a fairly clever PRNG, and it
takes quite a bit of data to get the exact pattern.

It might not be feasible to create a cryptosystem using fractals and
chaos functions, but I think the possibility could be explored a bit
further...

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


writes Hal Finney:
>
>Now, maybe this particular fractal cryptosystem idea will actually work
>well.  I don't know; I haven't seen it.  But the point is that these
>complex types of systems have not provided a good foundation for crypto-
>graphy in the past.
>

(First, sorry for bringing up an old subject, I was at SC93, and now
have 500 messages to surf through)

I read an article in Electronic Engineering Times a while back (summer, I 
think), about some researchers doing encryption with chaos...  they had
two decryption chips (I think they used DSPs) that had a synchronized 
chaotic stream going between them, which they both used to [en,de]crypt
the data...  

This seems kind of silly, since (assuming an intelligent adversary),
they could just tap the chaotic flow, and start listening...

Am I missing something?

- -nate

- -- 
+-----------------------------------------------------------------------+
| Nate Sammons  nate@VIS.ColoState.Edu  (303) 491-1578                  |
|   Colorado State University -- Computer Visualization Laboratory      |
+-----------------------------------------------------------------------+