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

[John Denker]

On 09/23/2014 09:50 AM, ianG remarked:

> I think it is important to keep mining this 'event' because how the
> threat actor acted with DES gives us a window on how they will act in
> the future. 

Agreed.  See further "mining" below.



On 09/21/2014 06:13 AM, Jerry Leichter wrote:

> NSA always claimed that they didn't design DES - IBM did. 

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].

>  All NSA did was change the S boxes and drop the key from 64 to 56 bits.

Isn't that enough?

IBM wanted a longer key.  NSA wanted a much shorter key.
They compromised on 56 bits.  Reference [1].  Also implied
by reference [2].

  Very hypothetically and temporarily *IF* we compare DES
  to a 64-bit cipher with random S-boxes, 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.

As it says in reference [1], quoting none other than Frank
Rowlett,
  "in the long run it is more important to secure one's own 
  communications than to exploit those of the enemy."
Alas the NSA seems to get this wrong again and again and 
again.

On 09/23/2014 05:29 AM, Nicholas Bohm wrote:

>> With any luck their adversaries would have picked up on these 
>> hints, and been successfully bluffed into retaining their existing systems 
>> rather than moving to the new ones.
>>
>> It could be that those who still maintain that the NSA undermined the DES for 
>> their own advantage are the evidence of the success of a well-executed bluff.

Well executed?  I very much doubt it.  It sounds like an 
awfully foolish gambit to me.  I attribute to the NSA an 
immense budget and some highly skilled cryptologists, but
I don't give them credit for being able to predict the 
actions of other people.

At the time, any sane person would have expected such 
a gambit to backfire ... and all available evidence 
suggests that it did backfire.  The ones who were most 
hurt by weakening DES were outfits like US banks who felt 
constrained by regulation to use DES, who trusted NSA to 
get it right, and were too clueless to superencrypt.

In contrast, when playing chess or doing high-stakes 
crypto, you should not assume that your main adversary 
is clueless.

Specifically, at the time (mid 1970s) the microelectronics
revolution was in full swing.  DES was allegedly constrained
to "just barely" fit on a single chip.  So in accordance with
Moore's law, all you needed to do is wait a couple of years 
and then implement a scaled-up version on a single chip ... 
or implement the algorithm in software on a microprocessor.

This is more-or-less what happened.  Hint: GOST.  Soviet 
chip fabrication was years behind the US, but there was 
nothing to prevent them from buying microprocessors by
the bagful.  The last time I checked, GOST (very unlike 
DES) was unbreakable in practice even today.
  http://www.iacr.org/workshops/fse2012/FSEpreproceedings/PDF/total.pdf

Then superencrypt with bog-standard DES on the off chance
that the NSA was actually adhering to Rowlett's dictum
for once ... and so you can say to the banking regulators 
yeah, sure, I used the approved DES.

Also superencrypt with whatever you were using before,
be it a fancy rotor machine or whatever, on the off 
chance that there might be a systematic weakness in 
all Feistel ciphers.

To summarize:  The claim that DES was superior to this-
or-that straw man is irrelevant and deceptive.  Better 
ciphers were available at the time.  Proof by construction.

=====================================
Useful references:

[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