[Cryptography] NSA versus DES etc....

[John Denker]

On 09/23/2014 02:36 PM I wrote:

>>   Hint: GOST.

On 09/23/2014 05:35 PM, Richard Outerbridge replied:

> The 1st paragraph of that paper sez the full design of GOST
> wasn’t published until 1994, 20 years later.

I hope we don't need to quibble over the definition
of what "was" was.

There is a big distinction between
 -- /was/ in existence, and
 -- was /visible/ in the published literature.

Note that Soviet spies were not obliged to publish
their crypto designs.

> There was nothing before.  Maybe Bookcodes & Testkeys.

Really?  Nothing in existence?  How do you know?  
How sure are you?

> In 1974?  Both the USA and the USSR were both still using 1950s
> era rotor machines!  What better (digital) ciphers at that time
> did you have in mind?

I have in mind GOST, at some point in the 1970s, for 
multiple reasons.

For starters, it is reported by Schneier that the GOST 
cipher was developed and deployed in the 1970s.  I'm
not sure what is source is on that.  See also:
  https://en.wikipedia.org/wiki/GOST_%28block_cipher%29

Also, it's obvious from the design that GOST was optimized
to run on 1970s-style hardware.

Furthermore ... even in the absence of direct evidence 
I would be almost certain that the Soviets had something 
like GOST.  Any self-respecting cryptographer who looked
at DES and the public discussions thereof would say
  a) That's a nifty architecture.
  b) The key is too short.
  c) There's something sketchy about the S-boxes.
  d) There's barely enough rounds.

About 60 seconds later the guy would come to some
conclusions:
  a) Let's keep the Feistel architecture.  It 
   generalizes to any blocksize and any keysize.
  b) Let's use a much longer key.
  c) Let's change the S-boxes.
  d) Let's use more rounds.

I very much doubt that the GOST 28147-89 cipher was 
the best they came up with.  It's just the best they 
deigned to publish.

In particular, GOST has an astonishingly small hardware
footprint.  It stands to reason that they came up with 
other versions optimized for board-level and/or software 
implementation.  For starters, adding more rounds increases 
the cost only linearly in software, but increases the 
attacker's cost exponentially.  Using 128-bit block size 
costs practically nothing, except insofar as it might 
require more rounds to ensure full diffusion, yet it 
makes things very much more unpleasant for the adversary.
Similarly, expanding the S-boxes to 8 bits in and 16 or 
even 64 bits out costs practically nothing in software, 
increases diffusion, yet raises the workload enormously
for the adversary.

If nothing else, the triple DES idea has been around
since the late 1970s, as a way of getting around the
short-key problem.

I know first-hand that people in the US were playing
with scaled-up DES variants in the 1970s.  They didn't
talk much about it.  If the Soviets didn't do something
similar, I would consider it inexplicable, to say the
least.

I stand by the point of my previous message:  The idea
that the NSA could talk about DES in a way that tricked
the Soviets into making a cryptographic mistake does
not withstand scrutiny.

The entirely foreseeable result of putting out a 
weakened cipher standard was that friends would use
the weakened version and enemies would very rapidly
come up with a non-weakened version.

If the NSA couldn't foresee this, they were really,
really dumb.  Assuming they did foresee it, it tells
you a lot about their priorities.