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
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
