[Cryptography] An Open Source Analysis of NSA Cryptologic Capabilities

Ryan Carboni ryacko at gmail.com
Wed Sep 16 17:27:14 EDT 2015

Timeline of Events of Note

1992 - DES is broken cryptanalytically, although with an attack greater
than the birthday bound
1993 - SHA released, based on MD4/MD5
1995 - SHA-1 revised, original SHA now called SHA-0
1998 - Skipjack Released
1999 - Impossible Differential Analysis breaks 31 of 32 rounds
2001 - SHA-2 released, by Threefish's standards, a 256-round hash function
2005 - SHA-1 is broken by a non-practical attack, spurs SHA-3 competition
2010 - Xie and Feng announce a one block collision on MD5, which they
cannot release for _security reasons._

The occasional cryptanalytic success implies that the NSA is generally more
advanced, but not always. Cryptanalytic success seems to be a random
process, but it requires previous successes to exist. The NSA seems to be
more advanced than the Chinese, and the Chinese vaguely more advanced than
the remaining cryptographic community. This can probably be attributed to
the fact that the NSA has more money, has the support of other SIGINT
agencies in cryptanalysis, and thus probably have half the world's
mathematicians. Thus perhaps the NSA has a 42% chance of getting a
genuinely new cryptanalytic success, the Chinese a 33%, and the rest of the
world a 25% chance.

The evidence to support such a claim is that impossible differential
analysis nearly broke Skipjack, although maybe the NSA was aware of it and
had less concerns about security margins than we think. Further attacks on
SHA-1 and SHA-2 spurred the SHA-3 competition. While it was reasonable for
the civilian cryptographic community to be concerned, the fact that the NSA
was concerned is telling. It was a result they did not predict, and they
possibly thought further cryptanalysis could break those two hash functions.

Fortunately there is a large body of research on the cost efficiency of
research programs. While one may conclude that the NSA must perpetually be
making leaps and bounds ahead of everyone through the virtues of compound
interest, the answer is pleasanter. There is a diseconomy of scale when it
comes to research. For instance, the Moon program or the Manhattan project
could have been cheaper if more time was allotted for its completion.
Given that the nature of research changes over time as the easiest results
are exhausted, and that large organizations do have waste, it is safe to
say that any gap between NSA and civilian cryptography will shrink by a
small extent, year over year.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150916/2c5eb4e8/attachment.html>

More information about the cryptography mailing list