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

From: "Shai Halevi" <[email-masked]>
Date: Fri, 18 Mar 2005 09:23:48 -0500

"D. J. Bernstein" <[email-masked]> wrote:
> Shai Halevi writes:
> > * Wouldn't it make sense to modify some of the standards along this
> > line?
>
> Why _would_ it make sense? Why should anyone believe that this use of
> CPU time and bandwidth is more secure than using a larger hash function?

I can think of at least three reasons:

(a) Common sense: "everybody knows" that finding a second pre-image is
harder
than finding collisions, and target collision resistance is essentially the
same as second pre-image resistance. Also, the "brute force complexity" of
breaking TCR is related to 2^n, whereas the "brute force complexity" for
finding collisions is related to 2^{n/2}.

(b) A significant body of cryptographic research suggesting that target
collision reseitance in an easier task in principle than full collision
resistance. (E.g., we have constructions of TCR fucntions from one-way
functions, but we know that there are no "black-box constructions" of fully
CR functions from one-way functions.)

(c) The cost in bandwidth and CPU time is quite small in most environments:
You have to generate and send some 20 pseudo-random bytes, which is usually
much smaller than the time and bandwidth that it takes to compute and
communicate the messge itself and the signature. (Granted, there will always
be niche environments where this cost is significant, but I am claiming that
this is not the case in general.)

> Would you really be surprised if the attack techniques are extended to
> allow some randomness in the input?

Yes, very much so. Notice that this is an "after the fact" randomness:
The attacker first supplies one message, then the randomness is drawn,
and then the attacker needs to supply another message that will collide
under the same randomness.

-- Shai

p.s. Can anyone say something about the third question from my original
post:

> * Can anyone describe a real-life application where full
> collision-resistance is really needed?

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

---

From: Shai Halevi <[email-masked]>
Date: Fri, 18 Mar 2005 10:12:34 -0500

Michael Silk <[email-masked]> wrote:

> I don't see the difference between this hashing proposal and HMAC?
> Except in this case you skip the XOR'ing part and you don't keep the
> key.. and why have you decided not to use HMAC in this case? 

I think that Hugo's proposal was meant to save a bit on computation, 
since in this case maybe you don't really need HMAC.

My opinion is that in general you should use HMAC whenever you need a
keyed hash function, unless there is a very good reason not to do so.
This is not becuase of crypto reasons, just first principles of system
design: First, it is more conveneicne to have the same construct
everywhere. Thay way we don't have to re-think every time whether or
not this form of keying is appropriate for our particular application.
More importantly, once you have a keyed hash function implemented
somewhere in your system, someone will surely find other uses for it,
and some of these uses may actually need HAMC.

> And an implementation note i'm sure we are all aware of: random
> numbers are really hard for most companies to get right; and probably
> they would (if they were allowed to) use their email, or company name,
> or something as the 'random' part.

That's a good point, so you should really use pseudo-randomness here. 
You can also have the pseudo-random bits depend on the message that
you want to sign (e.g., include also an HMAC key with your secret key,
and compute the randomness as HMAC(message)). Or keep a 160-bit counter 
and compute the randomness for the next signature as HMAC(counter++).

-- Shai

---

From: Shai Halevi <[email-masked]>
Date: Fri, 18 Mar 2005 10:44:42 -0500

> allow some randomness in the input?

On second thought, the main difference seems to be that the TCR model
forces the adversary to do on-line work, whereas in the model of full CR
the attacker can mount the attack off-line.

In particular, I will not be very surprised if we have an attack that
makes 2^{60} calls to the hash routine, getting back 2^{60} different
pieces of randomness, and then find collision to one of them. However,
I will be very surprised if you can do the same with only 2^{40} calls.

So let's say that an attack is "feasible" is it works in at most (say) 
2^{50} on-line calls, 2^{70} space and 2^{90} off-line computation time. 
I will be very surprised if you find a TCR-type attack on SHA1
with these parameters.

> I've spent time on these problems. I'm now offering a $1000 reward for
> 256-bit collisions in my Salsa10 function.

I only spent a bit of time on this, but I'll buy a bottle of wine to 
anyone that would find attack on SHA1 with the parameters from above. :)

-- Shai

---

From: "D. J. Bernstein" <[email-masked]>
Date: 18 Mar 2005 18:01:38 -0000

> I will be very surprised if you find a TCR-type attack on SHA1

Hold it---you're cheating by changing the problem!

Suppose the attacker generates 2^50 messages m_1,m_2,...; the signer, in
response, generates 160-bit strings r_1,r_2,...; the attacker somehow
exploits the structure of SHA-1 to find (i,m') with m' different from
m_1,m_2,... and with SHA-1(r_i,m') = SHA-1(r_i,m_i).

This is 100% successful as an attack on a signature system using
randomized SHA-1. It doesn't imply a feasible attack on TCR---there's a
massive 2^50 factor in the probability ratios! You can't casually use
polynomial equivalences if you're talking about constants.

Will you be surprised when someone announces an attack of this type?

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