Re: [Hash] randomized hashes and DSA

"D. J. Bernstein" <djb@cr.yp.to> Thu, 18 August 2005 08:46 UTC

Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E5g37-0001z8-CO; Thu, 18 Aug 2005 04:46:57 -0400
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E5g35-0001z0-OB for hash@megatron.ietf.org; Thu, 18 Aug 2005 04:46:55 -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 EAA20016 for <hash@ietf.org>; Thu, 18 Aug 2005 04:46:53 -0400 (EDT)
Received: from stoneport.math.uic.edu ([131.193.178.160]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1E5gcn-0000g4-3O for hash@ietf.org; Thu, 18 Aug 2005 05:23:50 -0400
Received: (qmail 25949 invoked by uid 1016); 18 Aug 2005 08:47:12 -0000
Date: Thu, 18 Aug 2005 08:47:12 -0000
Message-ID: <20050818084712.25948.qmail@cr.yp.to>
Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html.
From: "D. J. Bernstein" <djb@cr.yp.to>
To: hash@ietf.org
Subject: Re: [Hash] randomized hashes and DSA
References: <20050803232043.6BF2E3BFFEA@berkshire.machshav.com> <Pine.GSO.4.44_heb2.09.0508041849230.5504-100000@ee.technion.ac.il>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 0bc60ec82efc80c84b8d02f4b0e4de22
Cc:
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

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

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