Path: gmdzi!unido!mcvax!uunet!ginosko!gem.mps.ohio-state.edu!
tut.cis.ohio-state.edu!ucbvax!hoptoad!gnu
From: gnu@hoptoad.uucp (John Gilmore)
Newsgroups: sci.crypt
Subject: Re: theoretical foundation for S-boxes
Message-ID: <8124@hoptoad.uucp>
Date: 25 Jul 89 20:45:42 GMT
References: <3705@shlump.nac.dec.com> <11927@ulysses.homer.nj.att.com>
Organization: Grasshopper Group in San Francisco
Lines: 37
Posted: Tue Jul 25 21:45:42 1989

s...@ulysses.homer.nj.att.com (Steven M. Bellovin) wrote:
> It is very obvious that there is structure in the S-box...
>              (perhaps) ... secret keying information that makes it much
> easier to invert.  Without that information, the problem is about as
> hard as cracking DES with a random S box.

So how hard IS cracking DES with a random S box?

If that's sufficiently hard, then cracking Khufu with a random S box
will be similarly hard.

If it isn't hard, then finding out why it isn't hard will help us to design
a non-random S-box that will withstand that attack.  Perhaps we should
generate random S-boxes and subject them to tests; when one passes, that
becomes the S-box of choice until a weakness in it is detected.

>           unless you have a theory of what makes an S-box strong or
> weak, you can't reliably design one that will resist cryptanalytic
> attack.

Yes, but perhaps we can unreliably design one that will resist
attack, and then test until we are satisfied that WE can't break it.
We can never do better than this! unless for some reason our government
decides to cooperate with its citizens.

Once such ciphers are in use, we can monitor whether the information
passed under encryption with a given S-box becomes learned by folks who
might be able to break it.  They take care about this, but everybody
makes mistakes.  Our chances of keeping our info secret are better
than if we use NSA chips and NSA keys!

And the attempt will teach us things about what's weak and strong
in S-boxes, which seems a particularly useful thing to know.
-- 
John Gilmore      {sun,pacbell,uunet,pyramid}!hoptoad!gnu      g...@toad.com
      "And if there's danger don't you try to overlook it,
       Because you knew the job was dangerous when you took it"