Subject: [Cfrg] RE: Who needs collision-resistance, anyway?

From: "Shai Halevi" <[email-masked]>
Date: Sat, 19 Mar 2005 23:48:14 -0500

"D. J. Bernstein" <[email-masked]> wrote (in his usual aggressive style):

> Excuse me? [...]
> Here, once again, is the right problem. Give messages m_1, m_2, ... to
> the signer, who responds with uniform random 160-bit strings r_1, r_2,
> ...; then find a message m' and an integer i such that m' is different
> from m_1, m_2, ... while SHA-1(r_i,m_i) = SHA-1(r_i,m').

It is exactly in these "..." after m_2, r_2 that you are missing something.
The number which is hidden in these ... is the on-line cost for the
attacker.
This is usually considered a much more expensive resource than off-line
computation, and rightly so. (I don't know if you have ever taken the issue
with people who actually try to break systems in the real world, but they
would typically trade you quite a bit of off-line computation to save on
every bit of interaction.)

> Do I correctly understand that you think that this is much harder than
> merely finding SHA-1 collisions? Specifically, that you're offering a
> bottle of wine for any algorithm that does it with 2^50 messages, 2^70
> bytes of storage, and 2^90 operations of comparable complexity to SHA-1?

Yes, I tried to say it as clearly as I can. And just to be even more
specific, I consider an attack algorithm to be successful in the metric
above if it produces a valid forged signature (or a collision) with
probability at least 1/2.

> > (c) After all the brouhaha, I do not quite understand what are we
> > arguing about.
>
> The usual issues: cost and security.
>
> The cost issues are reasonably clear (although I see that some people
> are still confused). Randomization is not free. The costs of randomized
> MD5 and randomized SHA-1 are far above the costs of deterministic MD5
> and deterministic SHA-1; they're much more like the costs of
> deterministic SHA-256.

Yes, you keep saying this, and these confused people keep telling you
that this is typically wrong. Most systems have no problem coming up with
pseudo-random bits. And if push comes to shove, this is also the easiest
thing to speed-up, e.g., by producing much of it off-line, or by adding
a bit of hardware. It is certainly easier than speeding up your hash
function, which has to depend on the message. (This is the thing about
common perceptions, there are very often right on the mark :)

> I wonder how many times I'm going to have to say ``TCR is the wrong
> problem'' before it sinks in.

I guess that it doesn't really matter how many time you say it, it just
remains wrong. Using a TCR hash function for signatures has an advantage
over relying on full collision-resistance, in that it shifts much of the
cost from off-line computation to on-line interaction with the signer.

> Funny, I don't see a ``PRG'' feature in my RSA chip.

Try buying another chip? Sometimes they come with an API for (pseudo)
randomness.

> If randomized MD5 is more expensive than deterministic SHA-256, and if
> nobody is willing to claim that it's as secure as deterministic SHA-256,
> then switching to randomized MD5 is obviously silly.

Wow, I actually agree with this (with the conclusion, that is, not the
assertions). I would suggest switching to randomized <Whatever>-256.
You'd find that the overhead in randomizing is dwarfed by the overhead
in changing the standard yet again if/when some new cryptanalytic technique
finds flaws in <Whatever>-256.

> Your response might be that we should use _randomized_ SHA-256. But if
> randomized SHA-256 is more expensive than deterministic SHA-512, and if
> nobody is willing to claim that randomized SHA-256 is as secure as
> deterministic SHA-512, then switching to randomized SHA-256 is obviously
> silly.

ok, I knew it was too good to last long. Arguing that randomized SHA-256
is more expensive than deterministic SHA-512 is a very hard sell. I don't
believe it for a minute.

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "D. J. Bernstein" <[email-masked]>
Date: 20 Mar 2005 14:07:21 -0000

Shai Halevi writes:
> Arguing that randomized SHA-256 is more expensive than deterministic
> SHA-512 is a very hard sell.

Costs are supposed to be measured, not ``sold.'' When I'm fitting a
signed message into a tiny DNS packet, I can't afford the space overhead
of a big r; and PSS overhead turns out to take more cycles than SHA-512.

> remains wrong. Using a TCR hash function for signatures

Here we go again.

The signature systems that you're advocating are _not_ based on TCR.
You do _not_ have tight reductions between hash-collision forgeries and
TCR. (It shouldn't be hard to prove that no such reductions exist.) The
attacker is _not_ faced with an uncontrolled value h and the task of
finding m such that MD5(m) = h.

In short, TCR is the wrong problem. I'm still wondering how many times
I'm going to have to say this before it sinks in.

Hash-collision forgeries in your system are equivalent to a _different_
problem. That problem is, presumably, much easier than TCR, and I fully
expect it to be solved for MD5. The attacker gets to maliciously choose
(say) m_1,m_2,...,m_{2^40} to exploit the MD5 structure, and then find
m',i such that MD5(r_i,m') matches MD5(r_i,m_i), where r_1,r_2,... are
the signer's short random prefixes.

At this point you've made clear that you have a different opinion
regarding the difficulty of this problem. You've settled on a concrete
challenge for cryptanalysts; fine. But it is simply _wrong_ for you to
equate this problem with TCR. It was wrong for you to claim that a TCR
challenge was relevant, and it is wrong for you to again talk about TCR
as the foundation of a signature system. TCR is the wrong problem.

I'm reminded of the following common argument: Blum-Blum-Shub is secure
if factorization is difficult; we assume that factoring 2048-bit numbers
is difficult; we conclude that 2048-bit Blum-Blum-Shub is secure. That
argument is wrong. Breaking BBS could be much easier than factoring the
modulus. The proven equivalence disregards huge polynomial factors. If
you want to understand concrete BBS security, factorization is the wrong
problem.

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago

---

From: Jack Lloyd <[email-masked]>
Date: Sun, 20 Mar 2005 14:03:49 -0700

> of a big r; and PSS overhead turns out to take more cycles than SHA-512.

And when I'm hashing 10 gigabytes of data on my x86 box, SHA-256 with 80 bits
of r is several times faster than SHA-512.

Costs are not universal.

-Jack

---

From: [email-masked] (David Wagner)
Date: Mon, 21 Mar 2005 00:01:11 +0000 (UTC)

>the signer's short random prefixes.

You've said it several times now, and I still don't understand why TCR is
the wrong problem.  If the attacker cannot break the single-instance TCR
property with greater than \epsilon probability, then the attacker cannot
break the 2^40-instance TCR property with greater than 2^40 * \epsilon
probability.

I wouldn't use MD5.  But if you use SHA1, it may well be reasonable to
hope that SHA1 is single-instance TCR-secure with \epsilon << 2^-40, i.e.,
that it is 2^40-instance TCR-secure.  We may have to see how the latest
cryptanalytic techniques work before we can form a definitive opinion,
of course.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 21 Mar 2005 01:05:23 -0000

David Wagner writes:
> I wouldn't use MD5.

This is a curious inconsistency. You seem to believe that randomized
SHA-1 is much harder to break than deterministic SHA-1, so why don't you
believe that randomized MD5 is much harder to break than deterministic
MD5? Similarly, why is Halevi unwilling to offer a reward for a break in
randomized MD5?

Perhaps there's some magic dividing line between the 2^30ish operations
used to find an MD5 collision and the 2^66ish operations used to find a
SHA-1 collision. How far would the SHA-1 collision complexity have to
drop before you lost confidence in randomized SHA-1, the same way that
you've lost confidence in randomized MD5?

> the attacker cannot break the 2^40-instance TCR property with greater
> than 2^40 * \epsilon probability.

2^40 is a huge factor. (Also, 2^40-instance TCR is still not exactly the
right problem---even with an n-bit prefix, why are you so sure that the
n bits of output are uniform? But this is a relatively minor point.)

---

From: [email-masked] (David Wagner)
Date: Mon, 21 Mar 2005 01:31:21 +0000 (UTC)

D. J. Bernstein wrote:
>You seem to believe that randomized SHA-1 is much harder to break than
>deterministic SHA-1, so why don't you believe that randomized MD5 is
>much harder to break than deterministic MD5?  [...]  Perhaps there's
>some magic dividing line between the 2^30ish operations used to find an
>MD5 collision and the 2^66ish operations used to find a SHA-1 collision.
>[...]

It's not the collision complexity, per se.  It is that the MD5
cryptanalysis techniques seem to have penetrated quite deeply into the
structure of MD5.  It is not too far off to imagine the possibility of
second pre-image attacks on MD5, which would raise very serious doubt
about the TCR-security of MD5.

I have not seen the details of the cryptanalytic attack on SHA1, so
I don't know yet whether similar comments will apply to SHA1 or not.
If the latest announcement is just the first in a line of cryptanalytic
results against SHA1 (as turned out to be the case with MD5), then I
won't feel comfortable about SHA1, either.  At the moment, I have yet
to hear anything that sounds like it could endanger the security of SHA1
against second pre-image attacks, but I would prefer to defer judgement
until the SHA1 attack paper is published.

At the moment, the beast I know (SHA1) sounds less scary than the one
I don't (SHA256).  But that could change, if we had learn more bad things
about SHA1, or if we learn more good things about SHA256.

I certainly think it would be prudent to start a serious effort to try
to come up with some hash function that has been validated as seriously
as, say, AES.  Whether that is an existing scheme, like SHA256, or some
new one, probably matters less than the need for higher confidence in
our hash functions.