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 [email protected]
