[prev in list] [next in list] [prev in thread] [next in thread] 

List:       cryptography-randombit
Subject:    [cryptography] philosophical question about strengths and
From:       jon () callas ! org (Jon Callas)
Date:       2010-10-15 20:33:55
Message-ID: 4DE54617-7D1E-4C2A-AB19-5A3C866AC9D8 () callas ! org
[Download RAW message or body]

Zooko,

Let me try to explain the rationale for some of this. Note that explaining is not the \
same thing as agreeing with.

I have to give a small ironic smile to hear you ask these questions while you've also \
advocated for hundred-year digital signatures. If you want hundred-year crypto, you \
want a 512-bit hash.

However, the real reason you want a 512-bit hash is for what's called "crypto \
balance." A system is only as strong as its weakest component, and you don't want to \
use AES-128 and a 512-bit RSA key.

The reason for the whole discussion is AES-256. To crypto-balance AES-256, you need a \
512-bit hash function. Consider the strength of a hash function to be at its birthday \
bounds, not its full width. I have ranted on this in the past and am happy to do so \
again. Permit me to merely assert it for this discussion.

One can have a good discussion about whether 256-bit security is needed at all. After \
all, there are only 2^265 particles in the universe. It's a fine discussion.

If you assume that there are Moore's-Law-Equivalent increases in compute power \
indefinitely, then 128-bit security is good until about 2050-2060, and 256-bit \
security is good until 2150 or so. On the one hand, we know that semiconductor \
improvements will peter out sometime. Best guess now is that there's not much to be \
gained after 2040 or so. So there's more to think that present things are good \
enough.

There's also the issue of quantum computers. This is another place where long rants \
are possible. My personal belief is that quantum computers will *at* *best* kick in \
at a Moore's-Law-Equivalent level. Frankly, all the quantum algorithms that are fun \
still run at O(n^3), and I don't think that's good enough.

For instance, let's suppose that in 2040 we get a quantum computer that can break an \
EC-256 public key in about a month. Well, just use an EC-2048 bit key. Heck, our \
grandparents used RSA 2048, why can't we use EC 2048? That will take 512 times the \
storage and 512 times the computes. If you manage to break a generational thing -- \
(e.g. no one has ever gotten more than 1000 qbits to do squat without decohering) \
then you have headroom. Does that bother you? Why not 4Kbit EC keys? My point is that \
n^3 is still a larger exponent than you think it is.

Okay, so let's get back to absurdly large hash functions. If you're going to ask for \
a 512-bit hash function (which NIST did, rightly or wrongly), why not have one that \
actually meets its rated specs? The point is *not* whether we can break it, but \
whether it meets its rated specifications in a well-defined way.

Let us suppose that there were a firm theoretical understanding that said that \
FooHash-512 had 400 bits of security, and here's why. I'm happy. No problems, \
whatsoever with this.

But we do *not* have a theoretical understanding of any of this. We're doing \
engineering here, not science. The theory that we have on how these things work has \
gaps we can see and gaps we can only guess at.

I am a firm believer that we have to leave some things for our grandchildren to \
solve. Some of the cryptographers who will solve the problems of 2040 are likely to \
be born in another five years, and why not let them have their fun? I don't worry too \
much about how to deal with quantum computers or whatever. They can do that.

I think, however, that when picking between FooHash and BarHash for the next 10-30 \
years, it makes sense to choose wisely. That choosing wisely is a mix between \
understanding guesswork. If we know that FooHash has a 2^230 attack against it, it \
*might* be wise to go with BarHash, which doesn't. If we understand FooHash's \
construction and do not understand BarHash's, then this might not be wise. The devil \
you know is better than the one you do not know, as the saying goes.

If you want to draw inferences from those statements to my hash function, please do. \
I argued strongly that our team operate from things we know, rather than things we do \
not know. Our design philosophy reflected that. We build our hash function so that it \
could be easily understood. Understanding is itself a security feature.

	Jon


[prev in list] [next in list] [prev in thread] [next in thread]