the effects of a spy

[John Kelsey]

>From: leichter_jerrold at emc.com
>Sent: Nov 16, 2005 12:26 PM
>Subject: Re: the effects of a spy

...
>Remember Clipper?  It had an NSA-designed 80-bit encryption
>algorithm.  One interesting fact about it was that it appeared to be
>very aggressively designed.  Most published algorithms will, for
>example, use (say) 5 rounds beyond the point where differential
>cryptoanalysis stops giving you an advantage.  Clipper, on the other
>hand, falls to differential cryptoanalysis if you use even one less
>round than the specification calls for.

Nipick: The system was Clipper, the algorithm was Skipjack.  

>Why the NSA would design something so close to the edge has always
>been a bit of a mystery (well, to me anyway).  One interpretation is
>that NSA simply has a deeper understanding than outsiders of where
>the limits really are.  What to us looks like aggressive design, to
>them is reasonable and even conservative.

Three comments here:

a.  Maybe they really do have a good generic differential-probability
limiting algorithm.  There are algorithms like this in the public
world (they can be really computationally expensive, and they only
tell you upper bounds on a subset of possible attacks), and you'd
expect NSA to be interested, since they design a lot of algorithms.
It's not so intuitive to me that this would have applied to impossible
differentials unless they designed it to, though.  In that case,
you're looking at differentials that can't appear instead of
differentials that appear too often.

b.  Maybe they don't care that much about attacks that require some
huge number of plaintexts.  The academic world has defined the game in
terms of total work being the critical parameter in the attack, and
we're seeing a push over time to move that to total attack cost.
(That is, it's not so interesting if you have a 2^{100} attack on a
128-bit block cipher, if the attack is impossible to parallelize.)  If
someone publishes an attack on Twofish tomorrow which requires 2^{96}
plaintexts to break it faster than brute-force, we'll all agree that's
an attack.  But there's no reason NSA has to think that way--maybe
they have some other parameter like 2^{n/2} texts for n-bit block
ciphers, after which they don't care about attacks because they're not
practical.  

c.  Maybe they just got it wrong.  SHA0 and SHA1 demonstrate that this
is all too possible.  (It's quite plausible to me that they have very
good tools for analyzing block ciphers, but that they aren't or
weren't sure how to best apply them to hash functions.)  

...
>Or maybe ... the reasoning Perry mentions above applies here.  Any
>time you field a system, there is a possibility that your opponents
>will get hold of it.  In the case of Clipper, where the algorithm was
>intended to be published, there's no "possibility" about it.  So why
>make it any stronger than you have to?

Reducing Skipjack to 31 rounds wouldn't make a practical trapdoor
appear!  You're still talking about 2^{34} chosen plaintexts!

>							-- Jerry

--John Kelsey


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com