[Cryptography] NSA versus DES etc.... was: iOS 8

[Jerry Leichter]

On Sep 23, 2014, at 5:36 PM, John Denker <jsd at av8n.com> wrote:
> I never said NSA "designed" DES.  I said they weakened it.
> 
> FWIW, they're not even pretending otherwise anymore.
> See e.g. page 232 of reference [1].
A fascinating bit of history; I read through the whole thing.  Thanks for forwarding the link.

The referenced page (and all the material about DES in both papers) is ambiguous because of redaction.  For those who don't want to spend the time, the relevant portion from page 232 reads:  "(FOUO) Once that decision had been made, the debate turned to the issue of minimizing the damage. Narrowing the encryption problem to a single, influential algorithm might drive out competitors, and that would reduce the field that NSA had to be concerned about [redaction of about lines of material] they compromised on a 56-bit key.122"  Footnote 122 is just "ibid" whose exact reference is hard to determine because of a redaction in an earlier footnote.  However, it doesn't add any information to explain the text.

The reason I say this is "ambiguous" is we can't tell what the disagreement was, who compromised, and over what.

>> All NSA did was change the S boxes and drop the key from 64 to 56 bits.
> 
> Isn't that enough?
This may have been a legitimate argument to make in the 1970's, but once Shamir published his work on differential cryptography, it became rather weak.  The S-boxes that IBM chose were weak against DC.  The S-boxes NSA choose are among the strongest possible against DC.  (They show a bit of weakness - never turned into a significant attack - against linear cryptanalysis.  I don't know if any set of S-boxes is simultaneously strong against both DC and LC.)  So changing the S-boxes *absolutely, unambiguously* strengthened DES.

There's a weird side to this story, indicating that we still don't know everything.  We've always been told that "NSA changed the S boxes" and no one knew why.  On the other hand, after DC became public, Don Coopersmith of IBM was
able to reveal that the IBM designers knew about DC and had themselves chosen S-boxes secure against it.  (http://domino.research.ibm.com/tchjr/journalindex.nsf/4ac37cf0bdc4dd6a85256547004d47e1/94f78816c77fc77885256bfa0067fb98!OpenDocument)  Coopersmith makes no mention of a change to the S-boxes by anyone.

DC against DES requires about 2^47 chosen plaintext encryptions.  It's impossible to directly compare this against 2^54 expected decryptions (one factor of 2 from the complementation property) from a brute-force attack.  On a pure "work" basis, DC requires much less then 2^56 work, and *way* less than 2^64 work (based on the nominal key length).  But the information needed to mount an attack is very different.

> IBM wanted a longer key.  NSA wanted a much shorter key.
> They compromised on 56 bits.  Reference [1].  Also implied
> by reference [2].
That's an assumption everyone has made, and continues to make - but the redactions in the references - probably deliberately - make it impossible to unambiguously confirm or deny the assumption.

Reference 2 also makes it clear that "Lucifer" was a name that described a series of different encryption algorithms, where the later ones were presumably intended to be improvements over the earlier ones.  They all apparently had 128 bit keys.  At least some versions of Lucifer were published - does anyone know of an analysis of their strength using modern tools?

Reference 1 also contains an interesting paragraph (page 239):  "As for DES, the controversy quieted for a period of years.  DES chips were being manufactured by several firms and had become a profitable business.  In 1987, NSA proposed a more sophisticated algorithm, but the banking community, the prime user of DES, had a good deal of money invested in it and asked that no modifications be made for the time.  By the early 1990s it had become the most widely used encryption algorithm in the world.  Though its export was restricted, it was known to be widely used outside the United States.  According to a March 1994 study, there were some 1,952 products developed and distributed in thirty-three countries.l43"  Footnote 143 is a reference to two papers and a phone interview with David Kahn.  This is a couple of years *before* the whole Clipper business, 
so it's unclear what this "more sophisticated algorithm" was.

>  Very hypothetically and temporarily *IF* we compare DES
>  to a 64-bit cipher with random S-boxes,
Just to be clear, there are actually not that many "good" S-boxes.  You have essentially no chance of finding them unless you already know about DC.
  
>                                          DES is stronger 
>  with respect to differential cryptanalysis but weaker 
>  with respect to brute force.  Indeed according to Adi 
>  Shamir, DES is about as strong as 128-bit Lucifer.
> 
> Non-hypothetically, I don't care.  That's not the right 
> comparison to be making.  One of the most fundamental 
> principles of reasoning is to consider /all/ of the
> plausible options.  It would have been straightforward 
> to strengthen Lucifer against differential cryptanalysis 
> without shortening the key.
You know this ... how?  You just quoted Adi Shamir saying that 128-bit Lucifer was actually remarkably *weak*.  DC - discovered independently at least three times, by the NSA, but Coopersmith and a team and IBM, and by Shamir, who finally made it public - is an extraordinarily powerful attack.  Its knowledge marked the beginning of any realistic design criteria for cryptosystems.

Repeating the references, because they are valuable:
> [1]   Thomas R. Johnson
>      "American Cryptology during the Cold War; 1945-1989"
>      Center For Cryptologic History / National Security Agency (1998)
>      http://www.nsa.gov/public_info/_files/cryptologic_histories/cold_war_iii.pdf
> 
> 
> [2]   Michael Schwartzbeck
>     "The Evolution of US Government Restrictions on
>      Using and Exporting Encryption Technologies"
>      From "Studies in Intelligence"  (the secret internal CIA magazine)
>      (date not obvious;  circa 1998)
>      http://www.foia.cia.gov/sites/default/files/DOC_0006122418.pdf

                                                        -- Jerry