CDR: RE: Musings on AES and DES

[Trei, Peter]

> ----------
> From: 	Vin McLellan[SMTP:vin at shore.net]
> Reply To: 	Vin McLellan
> Sent: 	Monday, October 09, 2000 3:22 AM
> To: 	Ray Dillinger; cypherpunks at cyberpass.net
> Subject: 	Re: Musings on AES and DES
> 
>          Ray Dillinger <bear at sonic.net> wrote:
> ><snip>
> 
> >[As the DES,] Dataseal/Demon/Lucifer was pretty good.  It may not 
> >have  been the *most* secure algorithm of its time, but neither was it a 
> >transparent and useless "cipher" with obvious flaws  other than the
> 56-bit 
> >keyspace.  However, the important part of building up trust (or lack 
> >thereof) in the cipher came after it was chosen as the DES.
> 
>          I suggest that you give insufficient weight to the importance of 
> the NSA imprimatur on the DES.
> 
>          The DES became the standard we know today -- for years, 
> universally accepted in US commerce, banking, and trade -- largely because
> 
> the US National Security Agency (NSA) issued, upon the designation of the 
> DES by NIST, a statement that the NSA's cryptanalysts knew of no attack on
> 
> the DES algorithm more effective than a brute force search of all possible
> 
      56-bit keys.
[...]
>          DES was pretty much what they said it was (even down to that
> tweak 
> in the S-boxes to block differential analysis, which the academic crypto 
> researchers didn't discover for many years.) The NSA was/is really very 
> good at what they did, and -- particularly in the US computer industry 
> (which until 1960 had been pretty much guided by NSA R&D contracts) -- 
> their cryptanalytic expertise was wholly unchallenged.
> 
> 
If you read the ostensible charter of the NSA, its duties include assisting
in 
the securing of US civilian communications. While I expect this mainly means
making sure that Boris & Natasha aren't tapping US internal comm links 
without permission, it can also be interpreted to make sure we aren't
using snakeoil ciphers. Making DES not suck seems well within the NSA
charter. 

In 1986, when the second recertification came up, I remember considerable
consternation over the key-length reduction to 56 bits, and the unexplained
tweaking of the S-boxes. There was serious discussion at the time that one
or both of these changes were done to introduce backdoors. You'd probably 
have to find a usenet archive from the period to confirm this. I seem to
recall
reading somewhere that the extra (8?) bits in the original were shown not to
add to the security of the cipher. Clearly 56 was too short - Diffie &
Hellman
published a paper to that effect in 1977. 

In the end, we now know that the tweaking prevented differential
cryptanalysis,
but not linear cryptanalysis. DCA had apparently been discovered internally
at IBM (and presumably at NSA). LCA was not then known within IBM 
(whether it was known inside NSA is an interesting question :-)

I would not be suprised if 30 or 50 years down the road, we find out that
NSA
did its level best to ensure that the AES selection process picked the best
candidate. Equally, I would not be suprised to find that they already have 
some black cryptanalytic technique which can defeat it.  On the balance
I favor the former: the NSA is as aware as the rest of us of the huge cost
(both financial and security) of embedding a broken cipher in the
infrastructure of the nation.

Peter Trei