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

From: "Shai Halevi" <[email-masked]>
Date: Sun, 20 Mar 2005 20:55:47 -0500

I am beginning to bore myself, repeating the same arguments over and over.
I'll try to clarify what I say once more, and then just sign off of this
exchange, letting Dan have the last word if he so chooses.

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

It is easy to prove the following theorem (Bellare-Rogaway, Crypto'97,
http://www.cs.ucdavis.edu/~rogaway/papers/tcr-hash-abstract.html):

  If Sig is a secure signature scheme for short messages, and H is a
  keyed target-collision-resistant hash function, then the following
  algorithm is a secure signature scheme for long messages:

  Sig'(m):
  + Choose a random key for H (call it hk)
  + Compute h = H_{hk}(m)
  + Compute s = Sig(hk,k)
  + Output (hk,s) as the signature on m

In terms of concrete security, the success probability of an attacker
against the new scheme is at most

  eps_{Sig'} = eps_{Sig} + N * eps_{TCR}

where eps_{Sig} bounds the success probability of an attacker against Sig
(the original signature scheme), eps_{TCR} bounds the success probability
of an attacker against the target-collision-resistance of H, and N is the
number of on-line signature queries that the attacker makes in the attack.

I would call the above a tight reduction, but I guess that this is a
matter of opinion.

> The attacker is _not_ faced with an uncontrolled value h and the task
> of finding m such that MD5(m) = h.

That's correct. The TCR model is this: the attacker gives you a message m,
then you choose hk at random and sends it back, and then the attacker
needs to find another m' such that H_{hk}(m) = h_{hk}(m').

I must add, however, that I don't believe the difference between "2nd
preimage" and target-collision-resistance to be that important. In
theory it is easy to get from one to the other (although I do not know
how efficient would such transformation be in practice). Actually, a
reasonably interesting work here would be to find a "really efficient"
construction of a secure signature scheme from a hash function that
is only known to be 2nd-preimage-resistant.

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

See my previous mail.

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

This argument approaches the realm of religious belief. Personally, I feel
that the case for "concrete security" and tight reductions is over-stated.
It is often the case that the reduction tightness (or lack thereof) is more
a matter of our proof techniques than anything that has to do with the
security of the scheme itself. But that's just my opinion, I know that
there are many who disagree.

-- Shai

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

---

From: John Wilkinson <[email-masked]>
Date: Mon, 21 Mar 2005 00:19:29 -0500

Most of the discussion on this list seems to be centered around 
creating a TCR hash function by keying SHA1 through the IV using the 
construction h(k || m), where k is the key (which is published, once 
chosen), m is the message, and || denotes concatenation. Keying through 
the IV is explicitly rejected in the paper [1] cited by Dr. Halevi. 
Also rejected is the "envelope" construction h(k || m || k). HMAC has 
no security guarantees if the key is not secret. It is argued in [1] 
that the TCR of these constructions may be just as easy (or even 
easier!) to break than the "any collision resistance" (ACR) of the hash 
function h.

The constructions with security reduction arguments presented in [1] 
all have very long keys (much greater than the length of the hash), and 
the authors make a comment that the common practice of stretching a 
short key into a long one using a PRF is "of no apparent use in this 
case". (If anyone can explain why, I'd love to know.) In a signature 
scheme, the hash value and the key must be signed, and then the key 
must be sent along with the signature, effectively increasing the 
length of the signature at least threefold. The authors of [1] suggest 
that since the birthday "attack" is not applicable to TCR hash 
functions, new TCR hash functions with 64- or 80-bit lengths could be 
developed to mitigate the problem of signature length expansion.

With all the caveats applied in [1] to TCR-based signature schemes, 
will anyone still prefer them to traditional ACR-based schemes using 
SHA256 or SHA512? Does anyone have an argument to make that the authors 
of [1] are overly pessimistic in their assessment of h(k || m) or HMAC 
as TCR hash functions?

[1] http://www.cs.ucdavis.edu/~rogaway/papers/tcr-hash-abstract.html
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "D. J. Bernstein" <[email-masked]>
Date: 21 Mar 2005 06:11:26 -0000

Shai Halevi writes:
> I would call the above a tight reduction

The probability ratio is approximately N, the number of signed messages,
which can easily be 2^40 or more. If a factor of 2^40 is ``tight,'' I
hate to imagine a reduction that you'd call ``loose''!

Everyone else calls this a ``loose'' reduction. See, e.g., Section 1.2
of ``The exact security of digital signatures'' by Bellare and Rogaway,
discussing the same factor of N in the FDH reduction.

Anyway, once you gave a concrete definition of feasibility (2^50
queries, 2^70 space, 2^90 operations), you were simply _wrong_ to leap
from the hypothesis ``TCR is infeasible'' to the conclusion ``forging
signatures is infeasible.'' It doesn't matter what strange terminology
you use for referring to the extra factor 2^40; neglecting that factor
was a flat-out error.

This error is important because it's a fundamental misrepresentation of
the security level of the signature system that you're advocating.
People who are misled into looking at the wrong problem, namely TCR, are
likely to be overconfident in the security of this system, and will find
themselves unpleasantly surprised when the system is ripped to shreds by
cryptanalysts.

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

---

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

>the IV is explicitly rejected in the paper [1] cited by Dr. Halevi. 

You're right.  I don't understand why that construction was rejected.
I'm at a loss to explain their reasoning.

Here is the argument given in that paper:

    Suppose, for example, that one keys MD5 through its 128-bit initial
    chaining value, IV. Denote the resulting hash function family by
    MD5*. Then breaking MD5* (in the sense of violating TCR) amounts to
    finding collisions in an algorithm which is identical to MD5 except
    that it begins with a random, known IV (as opposed to the published
    one). It seems unlikely that this task would be harder than finding
    collisions in MD5 itself. It could even be easier!

But this seems to confuse two distinct cryptanalytic tasks: (1) given the
IV, find M, M' so that MD5*(IV,M) = MD5*(IV,M'); (2) choose M before you
know the IV; then, given the IV, find M' so that MD5*(IV,M) = MD5*(IV,M').
I don't see any reason to expect these two tasks to be equivalent,
and I would certainly imagine that for some hash functions, task (2)
might be much harder than task (1).  Indeed, task (2) is basically the
TCR notion, while task (1) is just standard collision-resistance.

So I don't know why they rejected MD5*.  I don't know why that paper
considered it unlikely that breaking MD5*'s TCR property would be
any harder than breaking MD5's collision-resistance.  I don't know why
they rejected the envelope method, either.  The paragraph discussing the
envelope method seems to have made the same mistake, as far as I can tell.
I'm puzzled; I confess I don't see where those comments are coming from.

I definitely wouldn't recommend using MD5 for this purpose.  But I'm
not aware of any reason to reject SHA1(k || m) or SHA1*(k, m).

It is true that there are no security guarantees that either of these
constructions will be secure, but there is also no guarantee that these
constructions will be insecure.  There is some reason to hope that these
constructions might be secure even if collisions are found in SHA1.

>case". (If anyone can explain why, I'd love to know.)

I don't have a concrete example of what goes wrong, but this sounds
plausible to me.  The definition of security for a PRF makes no guarantees
about the pseudorandomness of its output if the key to the PRF is made
public, so using a PRF with a public key is a strange thing to do.

---

From: John Wilkinson <[email-masked]>
Date: Mon, 21 Mar 2005 10:02:42 -0500

> I'm at a loss to explain their reasoning.

I couldn't understand their out-of-hand rejection either. I thought it 
might either be something trivial that I was overlooking, or something 
that someone who had intently studied the attacks on hash functions 
would intuit.

> public, so using a PRF with a public key is a strange thing to do.

The thing that strikes me as odd about this reasoning is that, in any 
case, the TCR hash function (TCRHF) key must eventually be made public. 
Users are likely to generate the TCRHF key using a PRNG of some sort, 
such as /dev/urandom. What does it matter if you publish the state of 
your computer's internal PRNG after you have published its output? 
(Assuming you aren't foolish enough to use that same state to generate 
any further data you wish to keep secret.)

The authors exact comment in [1] is in a footnote on page 5:

"It may be worth remarking that the obvious idea for reducing key size 
is to let the key be a seed to a pseudorandom number generator and 
specify longer keys by stretching the seed to any desired length. The 
problem is that our keys are public (they are available to the 
adversary) and pseudorandom generators are of no apparent use in such a 
context."

If the authors believe that the keys to the TCRHF must be truly random 
for their security reductions to hold, then that's a huge barrier to 
implementation. I don't know of any system that can easily generate the 
required amount of truly random key material. If the security 
reductions only require that the keys be apparently random to the 
attacker (such that the details of the PRNG that generated them cannot 
be published), then we are back to the problem of having extremely long 
keys, which must be signed and transmitted with every signature.

While the practicality of the construction SHA1(k || m) relative to 
SHA256(m) could be debated, it seems unlikely that any of the 
constructions presented in [1] would be considered for implementation 
over SHA256(m) or even SHA512(m).

---

From: david jacobson <[email-masked]>
Date: Mon, 21 Mar 2005 09:55:34 -0800

> On Mar 21, 2005, at 1:55 AM, David Wagner wrote:
[snip]

> keys, which must be signed and transmitted with every signature.

A Broadcom 5821 chip will produce over 1 megabit per second of true
random output, and this chip is several years old now.  I don't believe
that random number generation (yes, cryptography quality random number
generation) is all that hard.

> ------------------------------------------------------------------------
> 

  -- David Jacobson

---

From: Adam Back <[email-masked]>
Date: Mon, 21 Mar 2005 13:42:13 -0500

Re. the comments about RNG cost (hardware or software) isn't it usual
for such output to be whitened through a hash function, such as eg
SHA1.

(Thinking eg of the Intel RNG that Paul Kocher/Cryptography Research
reviewed.)

/dev/urandom implementation also involves hash functions as do many
other CPRNG.

This to me somewhat calls into doubts the claims that CPRNGs as
suitable for creating bits for input to strengthen hash functions
have negligible cost.

(Of course the cost is amortized across large messages, but not all
messages are large).

Adam

---

From: csjutla <[email-masked]>
Date: Mon, 21 Mar 2005 13:59:59 -0500 (EST)

Lot of confusion is arising from comparing apples and oranges.
In the collision resistant model (also called ACR) the adversary is
given the IV (or the key say) and then must find M and M'. Clearly,
the adversary could try a random M and the  magic differential to get
M', and would succeed with prob say epsilon. Or, he could  spend 1/eps
time and actually succeed with high prob.

In the TCR model, the adversary chooses M first, and then is given IV
(or key) and so he again tries the magic differential to get M'
and will succeed with prob epsilon. This ASSUMES that the magic
differential works equally well on all IV, and there is good reason to
believe this is indeed the case.

Hence the rejection of MD5*. In fact, MD5 could have chosen
IV in a very samrt way and fixed it for ever. And hence, a random IV
may actually cause weakness.

-Charanjit

---

From: Greg Rose <[email-masked]>
Date: Mon, 21 Mar 2005 15:48:06 -0800

>believe this is indeed the case.

I'm unaware of any such good reason. In fact Phil Hawkes' paper 
<http://eprint.iacr.org/2004/264> pretty much says the opposite. Given an 
IV, you can choose messages that cause the right conditions to occur, but 
the chances of tweaking an arbitrary message to get a collision are very small.

Greg.

Greg Rose                                    INTERNET: [email-masked]
Qualcomm Incorporated     VOICE: +1-858-651-5733   FAX: +1-858-651-5766
5775 Morehouse Drive                    http://people.qualcomm.com/ggr/
San Diego, CA 92121   232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C

---

From: csjutla <[email-masked]>
Date: Mon, 21 Mar 2005 19:05:05 -0500 (EST)

> the chances of tweaking an arbitrary message to get a collision are
very small.

This is not an arbitrary message. Note the adversary chose the first
message too, so he could have chosen it from the space of problematic
messages. Again, this assumes that the space of problematic messages
is independent of IV. If that is not the case, then fine, the TCR is
better off. Definitely for SHA-0, as shown by Chabaud and Joux 98,
there is a space of problematic messages independent of IV. What the
new attacks reveal, we will find out soon. Hopefully.

Charanjit Jutla

---

From: david jacobson <[email-masked]>
Date: Mon, 21 Mar 2005 16:07:51 -0800

Sure, cryptographic pseudo-random (deterministic) random number
generators use hash functions or encryption.  Cryptography true random
number generators can also use hash functions or encryption.  I was
mainly discussing true random number generators.  You seemed to be
heading off to CPRNGs.  Nevertheless, I'm going to head back to true
random number generators.  The main reason is that with a true RNG we
won't get bogged down on the argument over wether the generator is
attackable.

The Broadcom 5821 is a cryptographic quality true random number
generator.  Actually, I don't want to talk about that as I'm under an
NDA agreement, and don't know for sure what I can say and what I can't
say.

But a spec sheet for the slightly older 5820 is available on the
Broadcom web site (registration required).  So I think there could be no
problem with me discussing that.

The 5820 has a thermal noise generator, the output of which Broadcom
claims is good enough to pass the FIPS 140-1 and FIPS 140-2 requirements
for self testing. (I presume that was before FIPS 140-2 was updated to
remove almost all RNG self testing requirements.)  These bits are
collected into chunks of 512 bits, and each chunks is run through SHA-1,
resulting in 160 bits.

This requires one hash for every 160 cryptographic-quality bits.

One of the random number generators approved by FIPS 140-2 is that one
in FIPS 186-2 appendix 3.2 with the mod q step (for DSA) elided.
(Eliding the mod q step is allowed by Implemetation Guidance for FIPS
PUB 140-1 and Crytpographic Module Validation Program section 8.9, if
the numbers are not for use by DSA.)  It uses a combination of the guts
of SHA-1 combined with 160-bit arithemetic to generate random numbers.
(Details below.)  It has provision for additional entropy to be stirred
in at each round.  So, with no entropy, it is a CPRNG. Or you can add
160 bits each round and have a cryptographic quality true random number
generator.

The exact algorithm for one round is this.  All UPPERCASE variables are
160 bits wide.  So "+" is 160-bit arithmetic. The value of X is the
random data that is returned to the caller.

The state is kept in a variable called XKEY, which is initialized with
seed matrial.  XSEED is just zero in the PRNG case.

XSEED = <<<new entropy or zero>>>;
XVAL = XKEY + XSEED;
X = SHA1star(XVAL || 352ZeroBits)
XKEY = (XKEY + 1 + X) mod 2**160.  /* no explicit mod; carries just get
lost */

SHA-1star is steps (a)-(e) of the SHA-1 spec.  It is just SHA-1 but
leaving out all the stuff you need for multiple blocks, fractional
blocks, and making the length contribute to the hash.  (This stuff about
the how steps (a)-(e) differ from the whole SHA-1 is from memory; I
might have it slightly wrong.) I'm quite sure full SHA-1 is just as secure.

Again 1 hash for 160 bits of random data.

One approved algorithm that will appear in the new ANSI X9.82 standard
will just hash old state to new state.  It will also have an "output
function" to obfuscate the state.  I think it will allow new entropy to
be stirred in. I'm not sure whether the standard will call for the new
entropy to be concatentated to the state, or combined with XOR.  (I
doubt it matters.)  Other people on this list are closer to the workings
of the committee on this.

I'm not quite sure what the output function will be.  Presuming it is
also a hash, this costs two hashes for 160 bits.

Bottom line, you can get cryptographic quality random numbers at a cost
of about 1 hash for every hash-block-sized chunk of output.

  -- David Jacobson

-- 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
NOTICE: This email message is for the sole use of the intended
recipient(s) and may contain confidential and privileged
information. Any unauthorized review, use, disclosure or distribution
is prohibited. If you are not the intended recipient, please contact
the sender by reply email and destroy all copies of the original
message.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

---

From: [email-masked] (David Wagner)
Date: Tue, 22 Mar 2005 00:20:09 +0000 (UTC)

Charanjit Jutla writes:
> Hence the rejection of MD5*.

That assumption doesn't sound like a good one to me.

After reading the paper on cryptanalysis of MD5 by Wang and Yu, it does
not look to me like their attack works in this way.  I think they rely
crucially on knowledge of the IV.  In particular, they choose a magic
differential.  However, their differential has a very low probability,
and it only works if a whole bunch of conditions on the message bits are
satisfied.  Then they pick a message which satisfies these conditions.
Even this still has too low a probability, so they derive some ways to
start with such a message and modify it to bypass a round or two for free.
See their section on multi-message modifications.

To put it another way, their attack seems to succeed at breaking the
collision-resistance, but they don't claim that it breaks the second
preimage resistance of the hash function.  If there were a magic
differential that worked for all messages (and didn't require their
constraints and message modification techniques), then second preimage
resistance would be broken.  Second preimage resistance is indeed a
necessary condition for TCR security.

In previous work, Dobbertin has a successful second pre-image attack
on MD4.  This means that there is no hope for MD4 to be TCR-secure.
Reading the paper by Wang, Lai, Feng, Chen, and Yu on MD4, they say
that they applied their techniques to MD4, and got a different second
pre-image attack on MD4.  However, their attack only works for a 2^-122
fraction of messages M.  They report briefly in the conclusion that there
is an improvement due to Yu, Wang, et al which improves this to 2^-72,
and that for SHA-0, it is 2^-107.

I don't see any other discussion of the possibility of second pre-image
attacks on MD5 or SHA1 in their paper, and I don't see any discussion
of the TCR property.  Presumably this will require some analysis.

It could well turn out that their techniques generalize to also find
second pre-images and break the TCR property, but I don't think it follows
trivially from the existence of collisions.  Likewise, I don't think we
can reject SHA1* out of hand based merely on the existence of collisions
(even ones based on differential analysis).

http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf
http://www.infosec.sdu.edu.cn/paper/md4-ripemd-attck.pdf
http://www.infosec.sdu.edu.cn/people/wangxiaoyun.htm

---

From: Adam Back <[email-masked]>
Date: Mon, 21 Mar 2005 19:30:25 -0500

Yep.  Coincidentally I implemented this same FIPS 186-2 RNG variant
for someone needing CC certification.  (SHA1 based G function, variant
with no mod q step).

This RNG could be considered either a CPRNG or a RNG depending on how
you use it.  (The way I used it it was a CPRNG, pure software).

Confirms the aspect that even the hardware "true" RNGs in practice use
hash functions on output.  (And I guess sometimes the hash is hw also
sometimes in software).

Adam

On Mon, Mar 21, 2005 at 04:07:51PM -0800, david jacobson wrote:
> number generators can also use hash functions or encryption.  
>

---

From: [email-masked] (David Wagner)
Date: Fri, 25 Mar 2005 08:14:25 +0000 (UTC)

Charanjit Jutla wrote:
> Again, this assumes that the space of problematic messages
> better off.

Yes, what I am saying is that this does not seem to be the case
for the recent attacks on MD5 and SHA1.  That's as far as I can tell,
anyway -- I don't entirely understand the attacks, so I could be wrong,
but that is my current working understanding.

It is always possible that those attacks could be extended so that
the space of problematic messages is independent of IV; I don't know
the attacks well enough to know how plausible this might be.