| Relay-Version: version B 2.10.1 6/24/83; site decvax.UUCP
Posting-Version: version B 2.10.1 6/24/83; site allegra.UUCP
Path: decvax!decwrl!Glacier!oliveb!allegra!don
From: [email protected] (Don Mitchell)
Newsgroups: net.crypt
Subject: bad S boxes
Message-ID: <[email protected]>
Date: Sat, 17-Aug-85 15:18:28 EDT
Article-I.D.: allegra.4956
Posted: Sat Aug 17 15:18:28 1985
Date-Received: Mon, 19-Aug-85 04:50:24 EDT
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 5
To answer various people's questions, consider the S boxes in DES.
They take six input bits and give four output bits. I understand
that Shamir has found that there are strong correlations between
the xor of the four output bits and simple functions of the input
bits.
|
| There has always been suspicion about the S boxes. Regardless of this
discovery, the DES was not designed to last until 1985 and it was time
to seek a new algorithm anyways. Arrays of special purpose micros can crack
at DES encrypted message for around $25,000 (assuming you can keep them
busy enough with messages to amortize your costs).
/Bevin
PS: I can't wait to see what Cryptologia has to say about this...
|
| Here's more about des from allegra!don (copied from Usenet).
Several people have asked me question about DES. Here is a brief
review of what it does.
The heart of it is a hashing function that hashes 32 bits. The 16
stages of DES (which encrypts a 64 bit block) are just "hash the right
32 bits and xor them with the left", then "hash the left 32 bits and
xor them with the right", etc.
The hash function has three components, E boxes, S boxes, and P boxes.
In the E box stage, the 32 bit input is expanded to 48 bits by taking
groups of four bits and just copying two of them to get a pattern of
six. Just a table lookup. This 48 bit quantity is xor'ed with 48 bits
of the key then. (48 bits selected in a complex way from the 56 bit
key.)
Eight S boxes map this 48 bits into 32. Each S box takes 6 bits and
spits out four. It's just a table lookup again, 64 numbers from 0 to
15 index by the six input bits. This is the nonlinear part.
Finally, the 32 bits coming out of the S boxes are shuffled around,
permuted by the P box. Thus successive stages of hashing diffuses (P
box) and confuses (S box). I don't now why the E box step is used, but
stages of P and S boxes is called an SP network.
|
| I wonder why a certain company cancelled a certain project and is now
reviving it with, you guessed it, des.
If one were to put security on a net, what would you use?
Ed.
|
| Remember a few months ago when somebody in Washington (NSA?) proposed
buying a few hundred thousand "secure phones" for the government?
They proposed mass-producing phones with DES built in, and putting
them all over the place, so government calls couldn't be wiretapped.
This was posted on internet Telecom digest, and immediately got the
rejoinder that NSA must have cracked DES wide open. Certainly they
wouldn't have encouraged its widespread deployment if they couldn't
see right through it.
So no surprises here!
|