<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">On 22/09/2014 14:48, Jerry Leichter
wrote:<br>
</div>
<blockquote cite="mid:D4DC5180-BB89-44CC-84F5-4E48C88CD29C@lrw.com"
type="cite">
<pre wrap="">On Sep 21, 2014, at 9:54 PM, Jonathan Thornburg <a class="moz-txt-link-rfc2396E" href="mailto:jthorn@astro.indiana.edu"><jthorn@astro.indiana.edu></a> wrote:
</pre>
<blockquote type="cite">
<blockquote type="cite">
<pre wrap="">When it was approved
in 1976, it's not clear even NSA could muster the hardware for a
brute force attack; in fact, I'd guess not. The first *public*
attack wouldn't come until 1999 - 23 years later.
</pre>
</blockquote>
<pre wrap="">
Actually, Diffie and Hellman published their design for a
custom-hardware DES-cracker in 1977:
Whitfield Diffie and Martin E. Hellman
"Exhaustive Cryptanalysis of The NBS Data Encryption Standard"
IEEE Computer, June 1977, pages 74-84,
<a class="moz-txt-link-freetext" href="http://www.computer.org/csdl/mags/co/1977/06/01646525.pdf">http://www.computer.org/csdl/mags/co/1977/06/01646525.pdf</a>
Their paper makes fascinating reading even today.
Their design could search the entire 2^56 DES keyspace in about a
day (mean time to solution about 12 hours), at a capital cost which
they estimated at about $20 Million (using 1976 hardware technology).
</pre>
</blockquote>
<pre wrap="">Since no one actually did more than a back-of-the-envelope design, much less an implementation of even a small part of the machine, it's hard to know exactly how to approach the estimates. What made the EFF DES cracker valuable was that it was a real, working machine - there was no longer any place of argument about what was *possible*.
Then again, the EFF DES cracker came in at $250,000 with a design goal of a mean crack time of 4.5 days (though hardware problems make it roughly 3 times slower), roughly 20 years after the Diffie/Hellman paper was published. That paper estimates that *10* years after publication, their machine would cost $200,000 for a 12-hour crack time. Since we're assuming exponential drops in cost, there's a *huge* difference between 10 years and 20 years. Even the paper's "within an order of magnitude" estimates won't cover that.
So, yes, it's fascinating reading after all these years; and it's "directionally correct", to use that horrible bit of business-speak; but the fact is, on the important details, they got it wrong. Estimation of costs for unbuilt hardware should be taken with large grains of salt. (BTW, the EFF reports that they *budgeted* $210,000, which prove too low by $40,000 - about 20%. It's not easy getting accurate cost estimates even fairly close in to actual design/build time.)
(None of these numbers are adjusted for inflation, but it wasn't wildly high in that period.)
The paper argues that going to 128 or even 256 bits would not increase the cost of encryption hardware by much. What I remember hearing from hardware guys around that time was that 64-bit internals of a DES chip were about at the limit of practical (cost/yield/etc.) hardware technology at the time.
There's also the question of *what algorithm to use*. People keep repeating the story that the NSA "weakened" DES by reducing the key to 56 bits; but in fact we now know, and have known for years, that given the basic DES algorithm (a) the S-boxes NSA specified are the strongest possible against differential cryptography; (b) the inherent strength of the DES algorithm against DC is only about 56 bits.
If the NSA, at that moment in time, had wanted to reserve the ability to break DES to itself, it could have simply left the 64-bit keys in place. Everyone else would be looking at strength against brute force attack, and would conclude that with a 64 bit key (well, 63 because of the complement property) things were safe for a while; but NSA could use DC and get a roughly 55-bit attack. (A few years later, when NSA had begun to see the degree of penetration public use of encryption was starting to have, I have no doubt they would have done just that - at least in a hypothetical world where DC was not yet publicly known. But I think they just missed what was coming down the road - they though that crypto would move from the realm of spies to big banks and some of the largest corporations, which they could penetrate easily enough in other ways. So at that moment in time, my guess is they really wanted to get a strong system fielded for those giants.)
</pre>
</blockquote>
<br>
Assuming that guess to be right, what about the inconvenience for
the NSA if not only the banks and other corporations used their
strong system, but also the NSA's adversaries in the military and
diplomatic systems of their SIGINT targets? Many of them were
probably using rotor machines, and only gradually at best coming to
appreciate the implications of the British and American penetration
of Enigma and other World War II systems, which had come into public
view not many years before.<br>
<br>
What the NSA would have needed was subtle measures to stir up doubts
in the minds of their adversaries about the true strength of the
DES. After all, in the US the banks and other corporations could
happily just take the word of the authorities, but the NSA's
adversaries might think twice about that if given a reason to do so.<br>
<br>
Perhaps what would have served was for the NSA to have made changes
to the S boxes while remaining ostentatiously tight-lipped about
their reasons, and to have coupled that with apparently (and perhaps
ostentatiously) reducing the strength of the fielded system while
refusing again to explain why in the face of objections. 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.<br>
<br>
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.<br>
<br>
Nicholas Bohm<br>
<div class="moz-signature">-- <br>
<style type="text/css">
A:link
{ text-decoration: none; color:#0000bb; }
A:visited
{ text-decoration: none; color:#990099; }
A:active
{ text-decoration: none; color:#bb0000; }
A:hover
{ text-decoration: underline; color:#bb0000; }
</style><span style="font-family: monospace;"><a
href="http://www.ernest.net/contact/index.htm">Contact
and PGP key here</a></span><br>
</div>
</body>
</html>