[Cryptography] "Death Note" elimination for hashes

Ray Dillinger bear at sonic.net
Mon Oct 28 20:53:05 EDT 2013


John Kelsey Wrote:
>>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.

True.  Is this a bug?  After all, if DES and RC4 are both broken, then
the fact is that something which has no other choices really and truly
DOESN'T work.  If it continues to give the impression that it works,
and other parts of the system continue to deign to interact with it as
though it works, then those other parts of the system are also broken.

>> 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?

It looks like a trust issue, unfortunately.  That is a 'break' which is
in terms visible to an average user only hypothetical.  If you can find
a way to formulate an unambiguous machine-checkable proof of this break
that the software clients out there can reliably evaluate as true or
false, then more power to you.  But if not, then you have to appeal to
some recognized authority - and that puts the authority, whoever they
may be, in the line of attack and also at risk of issuing a death note
that is in fact wrong.  I very intentionally framed the proposal in
terms of "prima facie evidence" or the kind of proof that ANYONE can
verify is correct.  If anyone can verify that something is correct, then
it doesn't matter who points it out or whether that person is trusted.

That kind of very simple proof we can handle in software, and we can
reliably implement a robust proof checker for it.  But as the breaks
get less total that kind of simple proof is less applicable.  By the
time you've gotten as far as the attack you describe, I despair of having
a trustworthy non-buggy automaton capable of checking that your proof
is correct, and that puts us on shifting ground where people debate things
and reach conclusions for reasons that most of those who depend on them
don't understand, and ignore things that most most who depend on them
cannot tell whether they ought to be ignoring or not.  The trust issue
becomes much murkier.

If you require humans to verify the correctness of the proof, then
as far as most people are concerned it has become a matter of opinion
anyway.  That is, the IT professional can't tell the difference between
a death note that is true and a false death note that has a con job
behind it good enough to fool the pros. Nor can he tell the difference
between a death note that is false and a death note and one that the
pros simply aren't treating seriously enough to even bother checking.

Jerry Leichter wrote:

> 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.

Aaand this.  This is one of the reasons why you really can't place trust
in the hands of a few authorities with regard to this kind of thing.  It
makes them into targets.

That's completely aside from the equally difficult question of whether
they are in fact trustworthy, and whether they and their heirs in the
position will remain trustworthy over a long period of time.

So, yes, "death notes" as I see them are very much limited to cases
where there is a truly unambiguously broken primitive such that everyone
can verify that it is broken.  I would love for them to be more widely
applicable, but I don't know how to do that.

	Bear



More information about the cryptography mailing list