[cryptography] philosophical question about strengths and attacks at impossible levels

Jon Callas jon at callas.org
Fri Oct 15 16:33:55 EDT 2010


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


More information about the cryptography mailing list