Subject: [Cfrg] Re: Is target-collision-resistance really harder than full collision-resistance?

From: Shai Halevi <[email-masked]>
Date: Fri, 18 Mar 2005 16:38:43 -0500

"D. J. Bernstein" <[email-masked]> wrote:
> Shai Halevi writes:
>> 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.
> 
> 
> Hold it---you're cheating by changing the problem!

I would argue that it is you who is changing the model. Regardless, 
changing the model is never cheating. This is what we do.

> Suppose the attacker generates 250 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 250 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?

I'll try to be a specific as I can:

(a) Yes, I will be very surprised if someone announced such an attack 
within the parameters that I specified above (<= 2^50 signatures, 2^70 
space, and 2^90 time). I even committed myself to buying wine in this case..

(b) I claim that if the problem with SHA1 would have only effected 
systems that grant more than 2^40 signatures, you would not see so
much excitement about it (and you would see very little effort on the 
part of anyone to change the standards). And for a good reason: in most 
systems such an attack is not a real threat.

Hence, it seems a good idea to design the next signature standards so 
that "these types of attacks" on their hash functions would indeed only 
result in theoretical attacks on the signature, not real attacks.

(c) After all the brouhaha, I do not quite understand what are we 
arguing about. It it just that my definition from above of "feasible" 
attacks precludes things that DJB would consider legitimate attacks?

-- Shai

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 19 Mar 2005 09:32:21 -0000

Shai Halevi writes:
> I would argue that it is you who is changing the model.

Excuse me? I've consistently focused on the probability of a successful
forgery in these systems. That's what users care about. In particular,
forgery by hash collision is a multiple-input version of TCR. You
oversimplified the problem by switching to traditional TCR---which is a
single-input problem, and which therefore ignores a factor of 2^20 if
there are 2^20 signed messages, a factor of 2^40 if there are 2^40
signed messages, etc.

Theoreticians often gloss over this point because, hey, it's just a
polynomial factor. But if you're going to make concrete predictions then
you have to stop switching problems.

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').

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?

> 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.

The security argument hasn't been settled but I think we've boiled it
down to a simple question for the cryptanalysts. Two people are claiming
that randomized MD5 and SHA-1 are much stronger than deterministic MD5
and SHA-1 (although nobody seems willing to claim that they're as strong
as deterministic SHA-256). I think this position will be shredded by
cryptanalysis of randomized MD5.

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