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

From: Hugo Krawczyk <[email-masked]>
Date: Mon, 30 May 2005 07:00:15 +0300 (IDT)

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