Death Notes against insecure hashes and ciphers.

SSL and similar “extensible” protocols are often plagued by a plethora of ciphers and hashes, some of which are insecure. The problem of *disabling* ciphers and hashes at a later date when they become known to be insecure is difficult.

But I think there is at least the beginnings of a way to do it. I will walk through it for hashes, but a similar logic applies to ciphers as well.

One observation is that from a practical point of view, it is very much necessary to tell naive users two things: First, what the practical result of a failure in protocol negotiation is, and second, whose FAULT it is that something that was working yesterday is no longer working and who bears responsibility for fixing it. Naive users do not care in the slightest what stage of protocol negotiation failed or why; they want to know what they can and can’t do, and who must fix it so it will work. The rest is just vaguely threatening technobabble to them.

So when a cipher or hash function is eliminated, it needs to be done in a way that makes that information absolutely detectable and provable, not just talking about a
“protocol failure.” But if we require evidence of breakage to disable a hash or cipher, that information is readily available; when a cipher or hash function has been proven invalid, the party who cannot switch to any valid hash or cipher in protocol negotiations is solely responsible for the protocol failure.

Prima Facie evidence of an insecure hash can take two forms:

1) Two texts that hash to the same value, or
2) A preimage that hashes to a known value.

Therefore, I propose that either of these forms can be used as a “death note” against hash functions. Essentially, part of any new protocol designed using a plugin hash function ought to have the ability to recognize “death notes” as a special message in hash negotiations, meaning, “I refuse to use this hash and here is why you should also refuse to use it at all points in the future — and pass the word on to others as necessary.”

So when some entity in a protocol negotiation suggests using SHA-1, the other ought to respond with a SHA-1 death note, saying, in essence, “no, here are two messages that hash to the same value using SHA-1,” or “no, here is a message that hashes to the ‘public death note’ vector for SHA-1.” The ‘public death note’ value is just a special case of a test vector whose preimage value is not published (nor, most likely, even kept after initial production of the vector).

This requires that each hash function have a ‘public death note’ vector for the preimage note, so part of protocol negotiation ought to be demonstrating knowledge of the same ‘public death note’ known by the other party to protocol negotiation. This vector would need to be distributed as part of the hash implementation, and protocol negotiation should fail if the vector is different between the two ends of the negotiation. (ie, no implementation is allowed to be a “working” implementation that can interface to deployed “working” implementations if it has a different ‘public death note’ vector for that hash).

The other case, a hash collision, doesn’t require any special value to be distributed with the hash implementation.

The point of having the ‘public death note’ vector held in common across all users of a hash is that a valid “death note” preimage once known to any client or server anywhere is reusable as a proof against use of that hash across all clients and servers that attempt to contact it. So if someone discovers a working attack, it doesn’t matter who they are or where they are or what credentials they do or don’t have; The death note is self-evidently true or false and cannot be faked, so the ability to convince others that you are right (and the trust in an authority that could be subverted in order to implement such an ability) is a nonissue.

In order to protect against DoS using false “death notes” it has to be purely a PROOF of breakage, so it has to follow all the way through to a form of evidence so solid as to be indisputable. Therefore anyone who can formulate a valid ‘death note’ against SHA-1, can use it, once, in their communication with their local ISP, and thereafter it will spread like wildfire across the Internet, every time someone attempts to use that hash function in protocol negotiation with someone who knows it’s been killed. I’m just guessing here, but I think with a widely-used insecure hash this would be essentially finished (all backbone sites and ISPs) within an hour.

So across the Internet, millions of clients and servers with this protocol extension would never use SHA-1 again, and because there are an unfortunate few who will then be left with no valid hash function at all, some people will need an error message which says something like,

“Whenever you try to do anything financial over the Internet using this browser, or attempt to change your account settings with your ISP, or anything else that requires secure Internet communications, it will fail. This is because a cryptographic function used by this browser has recently been proven to be wrong. You will need upgraded or different software to continue using secure communications.”

And some others will be looking at an error message the next day that says something like,

“Whenever you try to do anything financial over the Internet using this ISP, or attempt to change your account settings with your ISP, or anything else that requires secure Internet communications, it will fail. This is not a problem or error with your software or settings. This is something your ISP needs to fix, and you will not be able to use secure communications until your ISP fixes it. A cryptographic function used by your ISP has been proven to be invalid and your ISP now needs to upgrade servers, routers, or switches for you to be able to continue using secure communications.”

And a few others will be looking at error messages that say something like,

“The party you are trying to communicate with over the Internet is not currently able to use secure communications. You will be unable to do anything financial using their website until this is fixed. This is not a problem with your software or settings. This is something that the company hosting this website needs to fix, and you will not be able to use secure communications with them until they fix it.”

Leave a Reply