Re: [Hash] randomized hashes and DSA

Hugo Krawczyk <hugo@ee.technion.ac.il> Thu, 04 August 2005 16:06 UTC

Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0iFG-00079W-Tl; Thu, 04 Aug 2005 12:06:58 -0400
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0iFF-00079H-UL for hash@megatron.ietf.org; Thu, 04 Aug 2005 12:06:58 -0400
Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA21846 for <hash@ietf.org>; Thu, 4 Aug 2005 12:06:55 -0400 (EDT)
Received: from mailgw4.technion.ac.il ([132.68.238.37]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1E0im9-0008Q9-9w for hash@ietf.org; Thu, 04 Aug 2005 12:40:59 -0400
Received: from localhost (localhost.localdomain [127.0.0.1]) by mailgw4.technion.ac.il (Postfix) with ESMTP id 09314F78C3 for <hash@ietf.org>; Thu, 4 Aug 2005 18:53:20 +0300 (IDT)
Received: from mailgw4.technion.ac.il ([127.0.0.1]) by localhost (mailgw4.technion.ac.il [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 11406-01-96 for <hash@ietf.org>; Thu, 4 Aug 2005 18:53:19 +0300 (IDT)
Received: from ee.technion.ac.il (ee.technion.ac.il [132.68.48.5]) by mailgw4.technion.ac.il (Postfix) with ESMTP id 76CDDF78E6 for <hash@ietf.org>; Thu, 4 Aug 2005 18:53:19 +0300 (IDT)
Received: from ee.technion.ac.il (localhost [127.0.0.1]) by ee.technion.ac.il (8.12.10+Sun/8.12.2) with ESMTP id j74G854A008076; Thu, 4 Aug 2005 19:08:05 +0300 (IDT)
Received: from localhost (hugo@localhost) by ee.technion.ac.il (8.12.10+Sun/8.12.2/Submit) with ESMTP id j74G84Ot008073; Thu, 4 Aug 2005 19:08:04 +0300 (IDT)
Date: Thu, 4 Aug 2005 19:08:04 +0300 (IDT)
From: Hugo Krawczyk <hugo@ee.technion.ac.il>
To: "Steven M. Bellovin" <smb@cs.columbia.edu>
Subject: Re: [Hash] randomized hashes and DSA
In-Reply-To: <20050803232043.6BF2E3BFFEA@berkshire.machshav.com>
Message-ID: <Pine.GSO.4.44_heb2.09.0508041849230.5504-100000@ee.technion.ac.il>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Brightmail-Tracker: AAAAAQAAAAQ=
X-Whitelist: TRUE
X-Virus-Scanned: by amavisd-new at technion.ac.il
X-Spam-Score: 0.0 (/)
X-Scan-Signature: b4a0a5f5992e2a4954405484e7717d8c
Cc: Hash WG <hash@ietf.org>
X-BeenThere: hash@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: hash.lists.ietf.org
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/hash>, <mailto:hash-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <http://www1.ietf.org/pipermail/hash>
List-Post: <mailto:hash@lists.ietf.org>
List-Help: <mailto:hash-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/hash>, <mailto:hash-request@lists.ietf.org?subject=subscribe>
Sender: hash-bounces@lists.ietf.org
Errors-To: hash-bounces@lists.ietf.org

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:

> 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
> Hash@lists.ietf.org
> https://www1.ietf.org/mailman/listinfo/hash
>


_______________________________________________
Hash mailing list
Hash@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/hash