[Cryptography] "Death Note" elimination for hashes

[Jerry Leichter]

On Oct 24, 2013, at 10:54 AM, John Kelsey <crypto.jmk at gmail.com> wrote:
> I like the idea of death notes for crypto primitives, but to make them practical, you need a couple of things:
> 
> a.  An alternative primitive you can switch to in your system.  If your choices are DES and RC4, and you''ve already sent out the DES death note, then you *can't* send out the RC4 death note without ceasing to work.  
> 
> b.  A more efficient mechanism than needing to show the break, which is only workable for some algorithms.  What does the death note look like for an adaptive chosen plaintext attack on AES that breaks it with 2^{50} texts and 2^{100} work?  
> 
> (b) is easy with a TTP or a set of trusted parties--each crypto primitive has an identifier that's a hash value, and the preimage of the hash is the death note....
Who's the "you" in this process?  Some collection of parties, during the entire useful lifetime of the hash, is in possession of information that can disrupt the entire system.  Those parties will be marked for attack by anyone interested in causing trouble.  Alternatively, they will be targets for anyone interesting in *blocking* attempts to kill off the hash - perhaps because they themselves have found a break.

It's easy to imagine such a system if your time horizon is a year or two.  But for time horizons measured in decades, things are much, much harder.  Either individuals have to pass along their responsibilities to others - so you have a transitive trust issue; I may have trusted the guy I originally nominated, but do I trust the guy who replaced the guy who replace him? - or you have to trust an organization, which over a couple of years may no longer even resemble the organization I put my trust in at the beginning.

> (a) is really hard once a couple of primitives/modes are broken.  One reason so many sites are using RC4 only for encryption is because of the reaction attacks on AES-CBC encryption.  I guess the way to do this would be to *require* support for a bunch of ciphers/modes up front that were as different as possible--CAST128 in CFB-mode + HMAC-SHA256, Twofish-CCM, AES-GCM, SHA3 in duplex mode, and Salsa20 + Poly1305, say.
Actually, the reaction attacks highlight an entirely different issue:  Just what is it you are signing the death-note on?  The problem here isn't AES - it's CBC.    Suppose your entire suite consisted of XXX-CBC, for a 15 different XXX ciphers, all of them good.  The problem in CBC has now killed them all.  The obvious response is, "sure, but why would I use CBC mode for everything?" - but without knowing where the next attack might come from, how can you guess what dimensions you need to vary along?  Maybe the next attack is some clever timing attack that hits all the ciphers, regardless of mode, rather than one mode, regardless of cipher.

There is a fundamental problem with getting existing software upgraded.  There are two fundamental approaches you can take:

1.  Pre-load the system with a bunch of alternatives, marking one at a time as the primary.
2.  Allow for the distribution of updates to add new alternatives as required.

Method 2 is what we do today, except that the way we do it is to replace the entire piece of software within which the crypto lives.  Our success rate in doing this isn't particularly notable.  Stepping back, the products that *do* see rapid updates do so through some form of brute force:  Chrome updates itself, giving you little choice in the matter; iOS updates directly from Apple, bypassing all the intermediaries - and Apple has been very successfully in getting end users to update quickly, through a variety of mechanisms.  Microsoft has gotten more rapid updates in place through pushing them really hard, but there even today its penetration rates for new versions are nowhere near Chrome or iOS.

Method 1 is what is being proposed here.

There's little difference in principle between the two methods.  If there were a way to push out updates *just to the crypto algorithms*, the two would come even closer together - and there would be much less reluctance to update because the product itself presumably would have no visible changes, it would just use new crypto to do what it had always done.

The details of possible attacks differ.  With Method 2, a evil push of a new algorithm could remove all the security.  With Method 1, the evil algorithm would have had to be present from the start.  How different this is, in practice, is hard to say.  The corresponding attack for Method 1 - as I noted above - is a denial of service attack, which knocks out the good algorithms until the system is forced to use a bad one which slipped into the set, or just plain runs out - and must fall back on Method 2.  (Note that this would be very good for a clever attacker:  Unlike a system that used Method 2 on an everyday basis, a system based on Method 1 is likely to be pushed into quickly throwing together a way to keep the system running.  This provides the perfect environment for "helpers" to come along and slip stuff in to an update.)

Method 1 in "easy" cases - where one can publish a checkable witness to a break - seems to avoid needing to trust the party that says "OK, go change things now".  But that's a bit of an illusion.  You'd think that a pre-image would be such a witness for a hash, but anyone can generate a hash/pre-image pair - they just start from the pre-image!  The only way such a pair is a witness is if there's some way of being sure that the process started with the hash - and that's not so easy.  The only methods I can think of are (a) publish the actual cracking algorithm - which likely will require too many resources to be practical as a witness; (b) publish a pre-image that was kept secret until now, which requires trusting someone to have *held* that secret.

While clever, I just don't see what problem death notices actually solve.

                                                        -- Jerry