[145843] in cryptography@c2.net mail archive
Re: Merkle Signature Scheme is the most secure signature scheme possible for general-purpose use
daemon@ATHENA.MIT.EDU (Jon Callas)
Mon Sep 13 20:38:35 2010
From: Jon Callas <jon@callas.org>
In-Reply-To: <AANLkTikTVTg=r4NgPOELHGVmMAp-o2WrU3Unb2uzUafx@mail.gmail.com>
Date: Mon, 13 Sep 2010 16:33:34 -0700
To: Cryptography List <cryptography@metzdowd.com>
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.=20
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.
=46rom a security point of view, this is kinda reasonable. =46rom an =
implementation point of view, it sucks gravel up a garden hose. =46rom =
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 =46rom 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.=20
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.=20
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@metzdowd.com
