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 

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 

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.

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Reply via email to