Merkle Signature Scheme is the most secure signature scheme possible for general-purpose use

[Jon Callas]

I want to rewind the discussion a bit.

Things being said here range from the outright true, to the true-but-irrelevant, all the way to being a canard.

There is a core question that we're not addressing at all, and that is: "How much security does a hash function have?" There is no good answer to that question.

The base rule of thumb is half the bit size. If you were in my crypto group and you said, "Hey, I'm using an N-bit symmetric key, what size hash function should I use?" I would answer 2N. So for AES-128, use SHA-256.

There are many reasons for that, the big one being the birthday bounds (for which, incidentally, N/2 is an approximation, not an exact answer).

However, there are many uses of hash functions that have a security limit greater than the birthday bounds. When someone knows what they are, and when to use them, then they can.

Picasso said "when I run out of blue, I use red instead." Once you're a good enough painter that you know why  Picasso said that, you can use red instead of blue. Until then, you should use blue for blue and red for red. 

Similarly, until you know when a hash function has security greater than the birthday bounds, you should assume that it has birthday-bound security, N/2 bits.

When NIST started the SHA3 competition, they talked to many of us, and this very issue -- security greater than the birthday bounds -- was something they said they wanted. A number of us, including me, replied that we didn't want security beyond the birthday bounds because we teach our security engineers that hash functions have a security of their birthday bounds. In other words, we want them to use red for red and blue for blue.

Moreover, if you just use a hash function that way, it only needs internal state equal to its output size. There's a term circulating now about "pipe width" to describe that, but it's frequently a misnomer. It's not a good way to describe it in many circumstances, but that's not the rant I want to go on right now. I'll save that rant for later.

NIST asked for security beyond the birthday bounds, and suggested that a reasonable internal state size would be 4/3 the output size.

From a security point of view, this is kinda reasonable. From an implementation point of view, it sucks gravel up a garden hose. From an implementation point of view, 4/3 just gets rounded up to 2.

In my particular hash function, Skein, the security parameter we gave it was internal state size; Skein can have *any* output size, even one larger than the state size (and yes, I know what you're thinking, and you're right -- if it has state S that is greater than output O, it has a security parameter of f(S) not f(O), it's still useful in main places). The primary function is Skein-512, which with an output size of 256 is "wide pipe" to use that horrid term, and with an output size of 512 is "narrow pipe."

That's the reason why there is also Skein-1024. If you want a hash function with 512 bits of output and a security bounds that it beyond the birthday limit, you need more than 512 bits of state. NIST asked for that, and that is the reason for Skein-1024, or any other large-state hash function; it gives security beyond the birthday bound. The alternative was Skein-667, The Hash Function That Lives Across The Street From The Beast.

And this is why this is something of a rant. If you presume that a hash function has N/2 bits of security, this whole discussion dissolves into the traditional greasy black smoke. If you match AES-128 with SHA-256, then it doesn't matter for your Merkle signature that it ends up with 255.33 bits of security, because you're only claiming 128 bits of security. If you want 256 bits of security, use SHA-512. 

That's using red for red and blue for blue. The problem only crops up if you want a rigorous discussion of when it's okay to use blue for red and when it's not. It's also relevant to the SHA3 discussion (which is part of how we got here) because NIST asked for security beyond the birthday bounds whenever possible, and people who have hash functions with large state are trying to count coup upon the people who have hash functions with small state. The issue is relevant only because the rule of thumb is being broken. 

So to sum up -- if you assume that a hash function has security equivalent to its birthday bounds, you escape many of these quandaries. I will assert also that this is equivalent to using large state to get beyond-birthday-bounds security and also that we'd be better off with a "narrow pipe" 1024-bit hash function that we assume has 512 bits of security than a "wide-pipe" 512-bit hash function that we try to use beyond the birthday bounds.

	Jon
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com