Re: [Hash] randomized hashes and DSA

"Steven M. Bellovin" <> Thu, 04 August 2005 08:36 UTC

Received: from localhost.localdomain ([] by with esmtp (Exim 4.32) id 1E0bD1-0005Mz-8d; Thu, 04 Aug 2005 04:36:11 -0400
Received: from ([] by with esmtp (Exim 4.32) id 1E0bCz-0005Mu-Au for; Thu, 04 Aug 2005 04:36:09 -0400
Received: from (ietf-mx []) by (8.9.1a/8.9.1a) with ESMTP id EAA12167 for <>; Thu, 4 Aug 2005 04:36:07 -0400 (EDT)
Received: from ([]) by with esmtp (Exim 4.43) id 1E0bjp-0005Iy-Cy for; Thu, 04 Aug 2005 05:10:06 -0400
Received: by (Postfix, from userid 512) id 9DEF5FB27C; Thu, 4 Aug 2005 04:36:02 -0400 (EDT)
Received: from (localhost []) by (Postfix) with ESMTP id 6B0CAFB24A; Thu, 4 Aug 2005 04:36:01 -0400 (EDT)
Received: from (localhost []) by (Postfix) with ESMTP id 342453BFD72; Thu, 4 Aug 2005 10:35:59 +0200 (CEST)
X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4
From: "Steven M. Bellovin" <>
To: Eric Rescorla <>
Subject: Re: [Hash] randomized hashes and DSA
In-Reply-To: Your message of "Thu, 04 Aug 2005 00:26:10 PDT." <>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Thu, 04 Aug 2005 04:35:58 -0400
Message-Id: <>
X-Spam-Score: 0.0 (/)
X-Scan-Signature: b19722fc8d3865b147c75ae2495625f2
Cc: Hash WG <>
X-Mailman-Version: 2.1.5
Precedence: list
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>

In message <>, Eric Rescorla writes:
>Steven M. Bellovin <> wrote:
>> 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.
>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.

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.

		--Steven M. Bellovin,

Hash mailing list