Subject: Re: [Cfrg] new i-d: randomized hashing

From: John Wilkinson <[email-masked]>
Date: Thu, 2 Jun 2005 19:51:07 -0400

Hugo, thank you for the link, I read your draft with great interest.  
My only contribution, minor though it is, is to point out that in  
section 3.1, you refer to an "integrated hash function a-la-Merkle- 
Damgard", when I believe you meant an "iterated hash function".

Regards,
John

On May 30, 2005, at 12:00 AM, Hugo Krawczyk wrote:

> Shai Halevi and I wrote an internet draft on the subject of randomized
> hashing and its use for strengthening current and future hash  
> functions in
> the context of digital signatures.
>
> The draft can be downloaded from
> http://www.ietf.org/internet-drafts/draft-irtf-cfrg-rhash-00.txt
>
> Our proposal is to define a "mode-of-operation" for hash functions
> by which any hash function (existing or yet-to-be-designed) is  
> converted
> into a randomized hash that, when used appropriately with digital
> signatures, is plaussible to make the life of a forger much harder.
> In particular, simple deterministic collisions (as recent  
> cryptanalysis
> helps finding) are not enough to attack a signature scheme using a
> randomized hashing algorithm. This application of randomized  
> hashing is
> well-known in the literature (where such families of hash functions  
> are
> called UOWHF or TCR) but not used in practice. We believe that we  
> should
> armor our digital signature schemes as much as possible against  
> known and
> future weaknesses and this is precisely what randomized hashing can  
> buy us.
>
> If you read, you will see that in order to incorporate these  
> mechanisms
> into real use there are two things to do:
>
> (1) Define a specific randomized hashing mode of operation: the  
> idea is to
> use the deterministic hash functions without any need to change their
> implementations (a la HMAC); randomization is to be achieved via  
> the input
> to the function.
>
> (2) Define how signature schemes (especially RSA and DSS) will  
> transport
> the randomness required when using randomized hashing. This calls for
> changes to the existing signature formatting and processing standards
> (such as PKCS #1).
>
> In the draft we offer some specific candidates for (1) that serve to
> illustrate the approach and as a basis for discussion of what the best
> method of randomizing a hash function may be.
>
> As for (2), this may be the more important part for standardization  
> bodies
> to tackle ASAP. The needed changes (discussed in the draft) are quite
> straightforward and can be defined even before agreement is reached  
> on the
> exact mode of randomization.
>
> Pleas read the draft, comment on it, propose alternatives, etc.
> BUT LET THE IETF AND OTHER ORGANIZATIONS GET STARTED ON THESE  
> IMPORTANT
> CHANGES TO OUR CRYPTO PRACTICES. We believe that the tradeoff between
> security, complexity and performance favors these changes.
>
> Hugo
>
> PS: this is not a proposal to abandon the study, design and  
> adoption of
> new deterministic hash functions (such as SHA2 and new to-be-designed
> ones). Deterministic hashing has other applications and is the  
> basis for a
> randomized mode of operation of the type we propose. The important  
> point
> to realize is that randomized hashing may extend significantly the  
> life of
> the function, in particular by providing more time between the moment
> weaknesses are discovered (as the case of SHA-1 now) and the time  
> that the
> randomized version cannot be used anymore in the context of  
> signatures.
>
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg
>

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

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 3 Jun 2005 22:31:04 +0300 (IDT)

You are certainly right about the typo, thanks.

In light of Russ posting about a hashing BoF at the Paris meeting,
it would be helpful to have opinions of people about the
randomized hashing approach and its use in digital signature
applications  as discussed in the draft. In particular, whether
this group feels that a standardization effort in this direction
is worth pursuing (deciding on the exact mechanisms seems
less important at this point).

Hugo

---

From: [email-masked] (David Wagner)
Date: Mon, 6 Jun 2005 06:40:49 +0000 (UTC)

Hugo Krawczyk  wrote:
>hashing and its use for strengthening current and future hash functions in

I think this is great stuff, and very much worth pursuing further.
Providing advice on which TCR constructions to use and how to use them
seems like a good service to the IETF, and I think the draft you and Shai
have put together is an excellent starting point.

Maybe one topic that might be worth discussing is which constructions
are most worthy of consideration, perhaps on grounds of both security and
performance.

---

From: Ben Laurie <[email-masked]>
Date: Tue, 07 Jun 2005 14:53:30 +0100

> http://www.ietf.org/internet-drafts/draft-irtf-cfrg-rhash-00.txt

It seems to me that life would be generally easier if you defined a 
modified hash function H_r(m) and then constructed H'(m)=(r,H_r(m)). 
This way transport of r happens automatically, but the hash gets wider. 
This means that protocols will normally only need to be modified (if at 
all) to cope with the wider hash.

What's unfortunate is that it isn't going to be generally possible to 
make software changes that are equally simple, since the usual mode for 
verifying a hash is to do the hash again and compare the result.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: Jack Lloyd <[email-masked]>
Date: Tue, 7 Jun 2005 11:11:58 -0400

> all) to cope with the wider hash.

I agree that this is generally a better system, and much easier to implement,
however it's worth pointing out that defining H' like this would only work for
signature systems with message recovery (RSA, RW, NR), but would not work with
DSA, ElGamal, etc. I think it is superior, changing PKCS #1 would be a pretty
substantial amount of effort and would affect even implementors who had no
interest in randomized hashes, while the method Ben proposes instead puts the
work soley on people who choose to implement randomized hashing instead of or
in addition to larger hashes.

> verifying a hash is to do the hash again and compare the result.

That's true. It is possible to design the software to support either method
(randomized or not) cleanly, but I doubt it's anyones first inclination. Though
anyone who has implemented PSS will have already encountered many of the same
issues, so it might not be that bad, assuming your toolkit of choice already
handles PSS.

-Jack

---

From: Hal Finney <[email-masked]>
Date: Sat, 11 Jun 2005 22:33:22 -0700

> http://www.ietf.org/internet-drafts/draft-irtf-cfrg-rhash-00.txt

In informal discussion of ideas along these lines I have seen the
objection raised that the randomization might allow the signer to
create hash collisions more easily. This could allow a dishonest
signer to exhibit a pair of messages with the same hash, then claim
that he only meant to sign one of them and that he is the victim of a
successful forgery. Maybe you can rule this out by defining the
security properties to be such that any such collision goes against
the signer, but it might still muddy the waters in an actual legal
dispute. It would be good if the randomized hash could be proven safe
against collisions even by someone who could choose the random value.
You might want to consider including discussion of this failure or
attack mode in your paper.

Hal Finney

---

From: "D. J. Bernstein" <[email-masked]>
Date: 12 Jun 2005 19:16:01 -0000

> This way transport of r happens automatically, but the hash gets wider. 

Even better, use the extra space for a longer _deterministic_ hash. For
example, instead of using 96 bits for r and 160 bits for SHA-1 output,
simply use SHA-256.

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

---

From: Ben Laurie <[email-masked]>
Date: Mon, 13 Jun 2005 15:18:35 +0100

> example, instead of using 96 bits for r and 160 bits for SHA-1 output,

That assumes we're confident SHA-256 won't have similar flaws.

-- 
 >>>ApacheCon Europe<<<                   http://www.apachecon.com/

---

From: Jon Callas <[email-masked]>
Date: Mon, 13 Jun 2005 15:38:10 -0700

> That assumes we're confident SHA-256 won't have similar flaws.

Ben brings up a good point, but I side with Dan Bernstein. I think 
SHA-256 is the right way to go, and we don't need anything else until 
we get new hash functions that have the attributes we want.

I am quite confident that SHA-256 has similar flaws to SHA-1 and all 
the others, but I think the right thing to do for the time being is to 
just use it. This is what we've done in PGP.

Here's my reasoning why:

SHA-1 is supposed to have 80 bits of security. Our present knowledge of 
it has it around 69. (I will handwave what this means, because yes, I 
know that this isn't pre-image collision, it doesn't apply to hmacs or 
similar constructions, etc.) It's thus missing 11 bits of security.

SHA-256 is supposed to have 128 bits of security. If we assume a 
similar flaw, SHA-256 should be missing about 17.6 bits of security. 
(That's (11/80) * 128.)

Let's take that 17.6 and round it up to 38. Yup, thirty-eight. Not 
twenty-eight, not eighteen. I have a cynical rounding function. That 
gives us 90 bits of security.

At 90 bits of security, I'm happy to live with SHA-256 for a while. I 
believe that the hash function we *want* to be using hasn't been 
written yet. (My guess is that it will be announced around the time of 
Asiacrypt '06, and papers published in FSE '07. We're not going to be 
comfortable with it until early '08, but will still whine and mutter 
about it until September '09. The FIPS for it won't appear -- sorry, 
I'm not going to make that cheap joke; NIST will actually make a FIPS 
before the whining stops.)

At 90 bits of security, we can live with it for another five years. And 
this assumes my rounding function, which scopes the "similar" flaw in 
SHA-256 to actually be a million times more devastating than the SHA-1 
one. If my rounding function should round 17.6 to 28 instead, then 
SHA-256 will last for another 15 years just fine. I think that factor 
of 1024 takes into account a additional decade of semiconductor 
improvements adequately. If my rounding function should round 17.6 to 
18, then SHA-256, while flawed, can live out its natural life. Normal 
engineering improvements can dispose of it sometime in the indefinite 
future -- probably around '09. (Oh, and if it were 80, then we could 
use it for all the same things we expect SHA-1 to do at the mere cost 
of being slow and big.)

We also know that there's no real mathematical insight that Wang and 
others have. It is true that attacks don't get worse, they only get 
better, but there's no reason to think that the attacks on any of the 
hash functions are going to get different in kind, merely in degree. I 
believe that SHA-256 has at least 100 bits of security in it. That's 
why my gedankenexperiment backs it down to 90.

Any number of people have observed that we have taken one basic 
construction for hash functions has been a bunch of tweaks, rather than 
a design change. Everything we have has at some level the same 
architecture. My concern about randomized hashing is that I see it as 
another tweak. Yes, it's a tweak in a higher level construct, but it's 
still a tweak. It's a tweak that requires more fundamental changes to 
the protocols and systems that *use* hash functions than merely 
swapping in a new function. That one is bad enough. I also see no 
reason why this is going to change our core mechanisms of operating. If 
we learn how to make a good hash function sometime between 2010 and 
2020, then that's within the pragmatic safety considerations of 
SHA-256. If something extraordinary happens, then gosh darnit, SHA-512 
should work. I can't believe that SHA-512 will have less than 128 bits 
of security. I'm sorry, I don't. If I'm proved wrong, then we really, 
really don't know what we're doing, and there are many dramatic things 
in information security we have to change.

So to sum up -- this is all interesting, to make randomized hashing, 
but why should I trust it, why should I convert to it? Why am I not 
jumping from the frying pan into another frying pan? Especially when my 
present plan is to use SHA-256, and if that is unacceptable, SHA-512. 
Does anyone believe that they're really that broken? Or to sum up my 
summary, in waiting for the right hash function, am I waiting for 
Godot?

	Jon

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 21 Jun 2005 02:28:51 +0300 (IDT)

see below

> That assumes we're confident SHA-256 won't have similar flaws.

That is exactly a main point in the consideration of randomized hashing:
There is no way, with our current understanding of hash constructions,
to have such confidence in SHA-256 or other existing hash candidates.

And DJB's argument that it is better to use the extra bits to increase the
output size of the hash function rather than using them for randomization,
does not really apply to the digital signature setting that we are
discussing here. At least in the case of the two schemes used in practice,
RSA and DSS, there is either plenty room for extra bits or no need for
them at all. As explained in the I-D, in the case of RSA (with 1024 or
more bits of modulus) we have plenty room to transport both the hash value
and the random bits (so you can easily accomodate 256-bit, or even
512-bit, hash functions PLUS the random bits). In the case of DSS, the
randomization costs zero additional bits since the random bits already
exist as part of the signature.

(BTW, in the case of DSS long hashes will be effectively truncated modulo
the order of the group, and randomized hashing handles truncation more
securely since it avoids trivial birthday attacks).

Hugo

---

From: "D. J. Bernstein" <[email-masked]>
Date: 21 Jun 2005 06:48:28 -0000

The user has limited resources (CPU time, bandwidth) to devote to
cryptography. We need to stay within those limits. For example, people
experimenting with DNSSEC are whimpering about the cost of RSA-1024,
even though RSA-1024 is clearly breakable by today's botnets.

Comments such as ``you can easily accomodate 256-bit, or even 512-bit,
hash functions PLUS the random bits'' show a basic lack of understanding
of these real-world performance constraints. We can't just blithely toss
the kitchen sink into a cryptographic protocol, making it ridiculously
big and slow in the name of security; we have to ask how the same
conjectured security level can be achieved most efficiently.

People who say ``Use randomized MD5 because we conjecture that it's more
secure than MD5!'' are ignoring the fact that randomized MD5 is _more
expensive_ than MD5. We could spend the same resources in other ways;
why should anyone believe that randomized MD5 is the best way?

In particular, SHA-256 has comparable cost to randomized MD5---maybe
more, maybe less, depending on the application, but certainly something
to consider if we can afford something bigger than MD5. Does anyone
seriously believe that randomized MD5 provides a higher level of
security than SHA-256?

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 21 Jun 2005 23:10:13 +0300 (IDT)

> even though RSA-1024 is clearly breakable by today's botnets.

The only real computational cost associated with randomized hashing
is the generation of the random bits. However, since this will be done
pseudo-randomly the cost is negligible relative to 1024-RSA operations
(even if you only do a signature verification with low exponent).
In the case of DSS even this cost does not exist.
And as said previously, there is no real cost in bandwidth either, at
least in the context of RSA and DSS.

The only real cost of supporting randomized hashing is the need to change
existing standards and practices. But since some changes will be required
anyway when moving to different hash algorithms and different hash
lengths, then it is well worth to take one step further and build support
for randomized hashing in these applications. This support may well prove
to last longer than the next to-be-adopted hash functions

> conjectured security level can be achieved most efficiently.

As said, there is nothing big or slow here.
And let's stay cool here and not resort to any expressions of ridicule,
fear and the like which are only needed when we ran out of rationale
arguments.

> People who say ``Use randomized MD5 because we conjecture that it'smore

It is very hard to provide well-founded claims about the relative
strengths of these constructions. I do not think I can provide them
myself (and maybe not even you). But when considering resistance to
collisions, MD5 with randomized hashing is more secure than plain MD5,
and SHA-256 with randomized hashing is more secure than plain SHA-256.
Randomization may not be a cure to some fundamental weaknesses of a given
construction but it may change the economics of an attack from borderline
practical to impractical.

As long as we do not gain some fundamental confidence in SHA-256 or any
other hash function we do need the safety net provided by randomized
hashing.

What needs to be done now is to build the mechanisms for supporting
randomization in signature standards as well as to study what are the best
ways to design a randomized hashing mode of operation.

Hugo

---

From: "D. J. Bernstein" <[email-masked]>
Date: 21 Jun 2005 23:20:28 -0000

Here's the question that matters for each user: In light of that user's
performance constraints, how strong a security conjecture can we
provide? Equivalently: What combinations (p,s) can we achieve, where p
is performance and s is conjectured security level?

The statement ``We can achieve a higher conjectured security level at
higher cost,'' even if true, doesn't provide even the slightest bit of
help in answering this question. A competent designer of cryptographic
protocols doesn't waste time with this sort of comparison.

On the other hand, the statement ``We can achieve a higher conjectured
security level at lower cost,'' if true, is quite useful. For example,
if SHA-256 is better than randomized MD5 from both a price perspective
and a security perspective, then randomized MD5 is bad design. But the
proponents of randomization refuse to make this comparison.

Hugo Krawczyk writes:
> MD5 with randomized hashing is more secure than plain MD5

Perhaps it's noticeably stronger; perhaps not. Even if it _is_ stronger,
that has no relevance to cryptographic design.

> least in the context of RSA and DSS.

The fastest RSA/Rabin-type signature verification, under 10000 CPU
cycles (hashing being a major part of that cost), requires randomizers
to be transmitted separately. Yes, PSS compresses the randomizer, but
PSS is incompatible with high-speed signature verification.