[Cryptography] Fwd: OPENSSL FREAK

Jerry Leichter leichter at lrw.com
Sat Apr 4 15:35:35 EDT 2015


On Apr 4, 2015, at 2:53 PM, Ray Dillinger <bear at sonic.net> wrote:
>> So in the last 50 years or so, can you give an example in which a Death Note would have actually been published?
> Every variety of "export mode" encryption could and
> should have received a Death Note long before now.
> They had been deprecated but, despite being a clear
> and present danger, were still in use. A timely
> Death Note could have stopped them.
This completely misses my understanding of what a Death Notice is supposed to be.  A Death Notice is a machine-checkable proof that some cryptographic primitive has been broken.  To be useful, the check has to be reasonably easily checkable.  For example, it's trivial to prove that a cryptographically secure hash function is not second-preimage resistant:  Simply provide at least one pair of distinct values that hash to the same thing.  The cost of checking this is essentially the cost of computing the hash function twice.  Proving that there's a way to compute pre-images of the hash function can be done by publishing an algorithm to do just that.  Checking this may be much harder, however.  Suppose that the published algorithm requires a computation equivalent to 10^8 hash computations.  This would clearly be a bad break of the hash function, but it's not a useful Death Notice, as hardly any implementation of the hash function will be in a position to check the assertion in that Notice.

The same goes for the export mode encryptions.  Yes, all of them fall to brute force today.  But an independent machine-checkable proof of that fact would require checks that are, even today, outside the bounds of practicality *for most if not all implementations that actually use those primitives*.

Since it's impractical for all instances of implementations to verify these alleged proofs for themselves - and were they to try, there would be subjecting themselves to trivial denial-of-service attacks - you're left with some central authority certifying that, yes, they've received a Death Notice and checked it and found it valid.  How exactly that's different from what we do (very badly) today isn't clear.

> Some whistleblower like Snowden or Manning inside
> the NSA who actually knows the magic numbers behind
> the Dual-EC DRBG and feels that it is a crime against
> society (and would be right to believe so) ought to
> have been able to publish a Death Note against that.
They could also have just published the magic numbers.  And yet no one has.  There's little reason to believe Snowden or Manning would have ever been close to having access to that level of detail - the actual "magic numbers", from the point of view of an attacker his keys - would be held very tightly, as there's simply no reason to make them widely known.  Unlike the stuff that Snowden and Manning have released - which had to be circulated to be useful - the "magic numbers" only need to be known to those who build the attack code that uses them.  Assuming those numbers exist, they might be known to a handful of people in the world; and, frankly, many of them might have known them at one time - as they were working on code - but would have had not reason to remember them after.  I'd rate the chance that these numbers ever leak as effectively 0.

The non-existence of Death Notices is irrelevant here.  We have to rely on a proof that, given the algorithm used, such "magic numbers" *could* exist; and the *human* judgement that the way the constants were chosen *could have allowed* for someone in the right place at the right time to siphon off the relevant values.  (Short of the numbers leaking, there's no way to *prove* that anyone actually did.)

> Mobile phone and wi-fi encryption that somebody
> can break with a laptop in seconds?  That's not
> an implementation flaw, that is a dead cipher.
> Send it a Death Note and bury it.
This may be your best examples, as some of these are so weak that, indeed, implementations might, in principle, run published attack algorithms to check them with reasonable resources.  Of course, these algorithms were implemented in secret by organizations with no reason to want to have them tested for strength after the fact - and every reason to want them *not* to be tested.  Further, they were in implementations that offered no alternative algorithms.  The right solution here wasn't Death Notices (which no one involved would have dreamed of including support for); it's not letting critical systems rely on untested, secret algorithms developed by people with little expertise in the field.  Fortunately, we seem to have moved away from this kind of thing.  All recent breaks of this sort are of algorithms developed and fielded years ago, living on only because of backwards compatibility requirements.  And, indeed, such systems need to be retired.

It's not that Death Notices aren't a cool theoretical concept; it's that they appear to have almost no *practical* application.
                                                        -- Jerry

 



More information about the cryptography mailing list