Subject: [Hash] randomized hashes and DSA

From: "Steven M. Bellovin" <[email-masked]>
Date: Wed, 03 Aug 2005 19:20:43 -0400

At the hash BoF, Ran Canetti suggested using the same random number for 
the hash as for the DSA signature.  That left me feeling very uneasy.  
I think I can now show that it's a very bad idea.

The problem is that the two have very different properties.  The random 
number used for signing must remain confidential; the random number for 
hashing need only be unpredictable.  If I receive a signed message, in 
order to verify it I need to have the random number to feed to the hash 
function.  But before this, the hash module did not need to have any 
confidentiality properties.  With this scheme, it does.  This imposes a 
signficant new requirement on the modularization of the total system.

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

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

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 04 Aug 2005 00:26:10 -0700

> signficant new requirement on the modularization of the total system.

I was assuming that Ran meant r, which is computed by generating
a random k and then computing: (g^k mod p) mod q
where k is random and secret. r, however, is public and part of
the signature, and random since it was derived from k.

-Ekr

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Thu, 04 Aug 2005 04:35:58 -0400

>the signature, and random since it was derived from k.

That would certainly be better, though there are still issues with 
modularization.  The signing process would no longer be a simple
pipeline of an hash operator that merely needs to be authentic and a 
signature operator that requires confidentiality.  To give a concrete 
example, in a secure email system the signature function -- DSA, RSA, 
or whatever -- should be in a separate compartment to protect the 
long-term secret key from the vast bulk of the MTA.  This scheme would 
complicate the API to the signature function, and require a different 
API for DSA than for RSA.

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 04 Aug 2005 01:43:01 -0700

> API for DSA than for RSA.

Totally agree..

-Ekr

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 4 Aug 2005 19:08:04 +0300 (IDT)

Let me clarify this very important point before more people get confused.
In general, please refer to draft-irtf-cfrg-rhash-00.txt for the details
and rationale of the proposal presented by Ran.

In reference to Steve's point below regarding the use (or re-use) of
the random component of a
DSA signature as the random "salt" in the hashing process, the intention
is to use the public value r=g^k and NOT the SECRET k. Doing the latter
would completely break the DSS scheme in which revealing a single value of
k also discloses the full value of the long-term private signing key.

Having clarified this it is also important to distinguish between two issues
(1) The cryptographic soundness of (re) using the component r for salting
the randomized hashing
(2) The engineering benefits and drawbacks of doing that.

The first point is essential and holds in this case. It is indeed secure
to reuse the value of r for the salting of the hash (with one caveat
pointed out in the above draft: the salt value r needs to be unpredictable
to the attacker so it should not be made available to the attacker before
the signature is issued)

As for (2), here we get into the business of trade-offs. Re-using r saves
bandwidth. Otoh, it changes the processing order of hash-and-sign in the
sense that the DSA component r now needs to be available before the
hashing. This may not be a problem is some cases (since r can be generated
a-priori independently of the msg being signed) and may be a problem in
others (such as allowing for the randomized hashing mode to be a drop-in
replacement for deterministic hashing in current signature code).

Whetehr bandwidth savings or processing compatibility is more important is
to be determined by purely engineering considerations (which is the ietf
expertise). The cryptography supports either way.

The details of processing and formats is of fundamental importance for the
practice of randomized hashing. But at this initial stage it is even more
important to understand the significance of the notion and the essential
role it may play now and in the future as an "insurance" against current
and future weaknesses of collision-resistant hashing.

Hugo

On Wed, 3 Aug 2005, Steven M. Bellovin wrote:

> the hash as for the DSA signature.That left me feeling very uneasy.
> The problem is that the two have very different properties.The random
> hashing need only be unpredictable.If I receive a signed message, in
> function.But before this, the hash module did not need to have any
> confidentiality properties.With this scheme, it does.  This imposes a

---

From: "D. J. Bernstein" <[email-masked]>
Date: 18 Aug 2005 08:47:12 -0000

Apparently some people think that it's a new idea to use H(r,m) instead
of H(m) in the ElGamal/Schnorr/DSA/etc. family of signature systems. In
fact, this idea was clearly stated by Schnorr in his CRYPTO 1989 paper,
page 244:

   In order to thwart the chosen message attack the function h(x,m) must
   be one-way in the argument m. ... It is not necessary that the
   function h(x,m) is collision-free with respect to m.

Every security issue for H(r,m) in this family of systems is also
present for H(m). The security bounds for H(r,m) in this context are at
least as good as the security bounds for H(m); see, in particular, the
Goh-Jarecki theorems in EUROCRYPT 2003. Nobody can seriously claim that
this use of r is a security problem.

There are problems with randomization:

   * It costs time.
   * It costs bandwidth for RSA signatures.
   * The security gains are purely speculative.
   * Nobody is willing to claim that the security gains are large (e.g.,
     that randomized MD4 is hard to break).

But it's not reasonable to claim that randomization _loses_ security.
There's nothing wrong with Schnorr's signature system.

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