[Cryptography] new wiretap resistance in iOS 8?

[Jerry Leichter]

On Sep 21, 2014, at 9:54 PM, Jonathan Thornburg <jthorn at astro.indiana.edu> wrote:
>> 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.
> 
> 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,
>  http://www.computer.org/csdl/mags/co/1977/06/01646525.pdf
> 
> 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).
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.)

                                                        -- Jerry

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4813 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140922/4df30f2a/attachment.bin>