[Cryptography] "Death Note" elimination for hashes

[John Kelsey]

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.  (Though you are then stuck supporting that hash function forever at least for this one feature.  Though you could concatenate hashes and require the preimage for *all* of them.)  You could give that preimage to a dozen trusted parties, and *any* of them could send out the death note, which would then spread in a viral fashion.  

(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.  Then, a death note for any one of them still leaves you a lot of choices.  

--John