From hash-bounces@lists.ietf.org Thu Aug 04 03:21:26 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0a2g-0001WK-Df; Thu, 04 Aug 2005 03:21:26 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0a2e-0001W3-5y for hash@megatron.ietf.org; Thu, 04 Aug 2005 03:21:24 -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 DAA07065 for ; Thu, 4 Aug 2005 03:21:20 -0400 (EDT) Received: from machshav.com ([147.28.0.16]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1E0aZP-0001Ro-CH for hash@ietf.org; Thu, 04 Aug 2005 03:55:18 -0400 Received: by machshav.com (Postfix, from userid 512) id 79F68FB27F; Thu, 4 Aug 2005 03:21:10 -0400 (EDT) Received: from berkshire.machshav.com (localhost [127.0.0.1]) by machshav.com (Postfix) with ESMTP id 0CFCBFB262 for ; Thu, 4 Aug 2005 03:21:09 -0400 (EDT) Received: from cs.columbia.edu (localhost [127.0.0.1]) by berkshire.machshav.com (Postfix) with ESMTP id 6BF2E3BFFEA for ; Thu, 4 Aug 2005 01:20:43 +0200 (CEST) X-Mailer: exmh version 2.6.3 04/04/2003 with nmh-1.0.4 From: "Steven M. Bellovin" To: Hash WG Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Wed, 03 Aug 2005 19:20:43 -0400 Message-Id: <20050803232043.6BF2E3BFFEA@berkshire.machshav.com> X-Spam-Score: 0.6 (/) X-Scan-Signature: 08170828343bcf1325e4a0fb4584481c Cc: Subject: [Hash] randomized hashes and DSA X-BeenThere: hash@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: hash.lists.ietf.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: hash-bounces@lists.ietf.org Errors-To: hash-bounces@lists.ietf.org 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 From hash-bounces@lists.ietf.org Thu Aug 04 03:26:28 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0a7Y-0003Mq-JT; Thu, 04 Aug 2005 03:26:28 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0a7X-0003Mg-IP for hash@megatron.ietf.org; Thu, 04 Aug 2005 03:26:27 -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 DAA07325 for ; Thu, 4 Aug 2005 03:26:25 -0400 (EDT) Received: from open-28-19.ietf63.ietf.org ([86.255.28.19] helo=delta.rtfm.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1E0aeL-0001dw-Tw for hash@ietf.org; Thu, 04 Aug 2005 04:00:24 -0400 Received: from networkresonance.com (localhost.rtfm.com [127.0.0.1]) by delta.rtfm.com (Postfix) with ESMTP id 060AEB813; Thu, 4 Aug 2005 00:26:10 -0700 (PDT) To: "Steven M. Bellovin" Subject: Re: [Hash] randomized hashes and DSA In-reply-to: Your message of "Wed, 03 Aug 2005 19:20:43 EDT." <20050803232043.6BF2E3BFFEA@berkshire.machshav.com> X-Mailer: MH-E 7.4.3; nmh 1.0.4; XEmacs 21.4 (patch 17) Date: Thu, 04 Aug 2005 00:26:10 -0700 From: Eric Rescorla Message-Id: <20050804072610.060AEB813@delta.rtfm.com> X-Spam-Score: 0.0 (/) X-Scan-Signature: 79899194edc4f33a41f49410777972f8 Cc: Hash WG X-BeenThere: hash@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: hash.lists.ietf.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: hash-bounces@lists.ietf.org Errors-To: hash-bounces@lists.ietf.org 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. -Ekr _______________________________________________ Hash mailing list Hash@lists.ietf.org https://www1.ietf.org/mailman/listinfo/hash From hash-bounces@lists.ietf.org Thu Aug 04 04:29:38 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0b6g-00032R-HR; Thu, 04 Aug 2005 04:29:38 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0b6b-000323-Ob for hash@megatron.ietf.org; Thu, 04 Aug 2005 04:29:36 -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 EAA11937 for ; Thu, 4 Aug 2005 04:29:31 -0400 (EDT) Received: from fmr14.intel.com ([192.55.52.68] helo=fmsfmr002.fm.intel.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1E0bdR-00051C-Ga for hash@ietf.org; Thu, 04 Aug 2005 05:03:30 -0400 Received: from fmsfmr101.fm.intel.com (fmsfmr101.fm.intel.com [10.253.24.21]) by fmsfmr002.fm.intel.com (8.12.10/8.12.10/d: major-outer.mc,v 1.1 2004/09/17 17:50:56 root Exp $) with ESMTP id j748TAQh003910; Thu, 4 Aug 2005 08:29:10 GMT Received: from fmsmsxvs043.fm.intel.com (fmsmsxvs043.fm.intel.com [132.233.42.129]) by fmsfmr101.fm.intel.com (8.12.10/8.12.10/d: major-inner.mc,v 1.2 2004/09/17 18:05:01 root Exp $) with SMTP id j748T9UG028641; Thu, 4 Aug 2005 08:29:10 GMT Received: from fmsmsx331.amr.corp.intel.com ([132.233.42.156]) by fmsmsxvs043.fm.intel.com (SAVSMTP 3.1.7.47) with SMTP id M2005080401291024438 ; Thu, 04 Aug 2005 01:29:10 -0700 Received: from fmsmsx312.amr.corp.intel.com ([132.233.42.227]) by fmsmsx331.amr.corp.intel.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 4 Aug 2005 01:29:09 -0700 Received: from hdsmsx402.amr.corp.intel.com ([10.127.2.62]) by fmsmsx312.amr.corp.intel.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 4 Aug 2005 01:29:09 -0700 Received: from pysmsx401.amr.corp.intel.com ([146.152.3.156]) by hdsmsx402.amr.corp.intel.com with Microsoft SMTPSVC(6.0.3790.211); Thu, 4 Aug 2005 04:29:08 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.5.7226.0 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Subject: RE: [Hash] randomized hashes and DSA Date: Thu, 4 Aug 2005 04:25:19 -0400 Message-ID: <3DEC199BD7489643817ECA151F7C592901971A7B@pysmsx401.amr.corp.intel.com> Thread-Topic: [Hash] randomized hashes and DSA Thread-Index: AcWYxT2Desyk82JcTbKe1hk0rj6qYAACMULg From: "Blumenthal, Uri" To: "Steven M. Bellovin" , "Hash WG" X-OriginalArrivalTime: 04 Aug 2005 08:29:08.0205 (UTC) FILETIME=[9518E9D0:01C598CE] X-Scanned-By: MIMEDefang 2.44 X-Spam-Score: 0.0 (/) X-Scan-Signature: e5ba305d0e64821bf3d8bc5d3bb07228 Content-Transfer-Encoding: quoted-printable Cc: X-BeenThere: hash@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: hash.lists.ietf.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: hash-bounces@lists.ietf.org Errors-To: hash-bounces@lists.ietf.org Steve, I share your concerns, and dislike the idea.=20 -----Original Message----- From: hash-bounces@lists.ietf.org [mailto:hash-bounces@lists.ietf.org] On Behalf Of Steven M. Bellovin Sent: Thursday, August 04, 2005 1:21 AM To: Hash WG Subject: [Hash] randomized hashes and DSA At the hash BoF, Ran Canetti suggested using the same random number for=20 the hash as for the DSA signature. That left me feeling very uneasy. =20 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=20 number used for signing must remain confidential; the random number for=20 hashing need only be unpredictable. If I receive a signed message, in=20 order to verify it I need to have the random number to feed to the hash=20 function. But before this, the hash module did not need to have any=20 confidentiality properties. With this scheme, it does. This imposes a=20 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 From hash-bounces@lists.ietf.org Thu Aug 04 04:36:11 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0bD1-0005Mz-8d; Thu, 04 Aug 2005 04:36:11 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0bCz-0005Mu-Au for hash@megatron.ietf.org; Thu, 04 Aug 2005 04:36:09 -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 EAA12167 for ; Thu, 4 Aug 2005 04:36:07 -0400 (EDT) Received: from machshav.com ([147.28.0.16]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1E0bjp-0005Iy-Cy for hash@ietf.org; Thu, 04 Aug 2005 05:10:06 -0400 Received: by machshav.com (Postfix, from userid 512) id 9DEF5FB27C; Thu, 4 Aug 2005 04:36:02 -0400 (EDT) Received: from berkshire.machshav.com (localhost [127.0.0.1]) by machshav.com (Postfix) with ESMTP id 6B0CAFB24A; Thu, 4 Aug 2005 04:36:01 -0400 (EDT) Received: from cs.columbia.edu (localhost [127.0.0.1]) by berkshire.machshav.com (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." <20050804072610.060AEB813@delta.rtfm.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Date: Thu, 04 Aug 2005 04:35:58 -0400 Message-Id: <20050804083559.342453BFD72@berkshire.machshav.com> X-Spam-Score: 0.0 (/) X-Scan-Signature: b19722fc8d3865b147c75ae2495625f2 Cc: Hash WG X-BeenThere: hash@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: hash.lists.ietf.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: hash-bounces@lists.ietf.org Errors-To: hash-bounces@lists.ietf.org In message <20050804072610.060AEB813@delta.rtfm.com>, 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, http://www.cs.columbia.edu/~smb _______________________________________________ Hash mailing list Hash@lists.ietf.org https://www1.ietf.org/mailman/listinfo/hash From hash-bounces@lists.ietf.org Thu Aug 04 04:43:05 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0bJh-0007J3-O4; Thu, 04 Aug 2005 04:43:05 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E0bJf-0007Is-N0 for hash@megatron.ietf.org; Thu, 04 Aug 2005 04:43:03 -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 EAA12538 for ; Thu, 4 Aug 2005 04:43:01 -0400 (EDT) Received: from open-28-19.ietf63.ietf.org ([86.255.28.19] helo=delta.rtfm.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1E0bqV-0005bV-UV for hash@ietf.org; Thu, 04 Aug 2005 05:17:01 -0400 Received: from networkresonance.com (localhost.rtfm.com [127.0.0.1]) by delta.rtfm.com (Postfix) with ESMTP id 23201B848; Thu, 4 Aug 2005 01:43:01 -0700 (PDT) To: "Steven M. Bellovin" Subject: Re: [Hash] randomized hashes and DSA In-reply-to: Your message of "Thu, 04 Aug 2005 04:35:58 EDT." <20050804083559.342453BFD72@berkshire.machshav.com> X-Mailer: MH-E 7.4.3; nmh 1.0.4; XEmacs 21.4 (patch 17) Date: Thu, 04 Aug 2005 01:43:01 -0700 From: Eric Rescorla Message-Id: <20050804084301.23201B848@delta.rtfm.com> X-Spam-Score: 0.0 (/) X-Scan-Signature: 39bd8f8cbb76cae18b7e23f7cf6b2b9f Cc: Hash WG X-BeenThere: hash@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: hash.lists.ietf.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: hash-bounces@lists.ietf.org Errors-To: hash-bounces@lists.ietf.org Steven M. Bellovin wrote: > In message <20050804072610.060AEB813@delta.rtfm.com>, 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. Totally agree.. -Ekr _______________________________________________ Hash mailing list Hash@lists.ietf.org https://www1.ietf.org/mailman/listinfo/hash From hash-bounces@lists.ietf.org Thu Aug 04 12:06:58 2005 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 ; 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 ; 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 ; 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 ; 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 To: "Steven M. Bellovin" Subject: Re: [Hash] randomized hashes and DSA In-Reply-To: <20050803232043.6BF2E3BFFEA@berkshire.machshav.com> Message-ID: 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 X-BeenThere: hash@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: hash.lists.ietf.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 From hash-bounces@lists.ietf.org Fri Aug 05 16:59:51 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E19IF-0003I1-EC; Fri, 05 Aug 2005 16:59:51 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E19I9-0003Hi-7E for hash@megatron.ietf.org; Fri, 05 Aug 2005 16:59:45 -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 QAA03833 for ; Fri, 5 Aug 2005 16:59:42 -0400 (EDT) Received: from above.proper.com ([208.184.76.39]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1E19pG-0003ME-UV for hash@ietf.org; Fri, 05 Aug 2005 17:34:01 -0400 Received: from [10.242.21.248] (m975f36d0.tmodns.net [208.54.95.151]) (authenticated bits=0) by above.proper.com (8.12.11/8.12.9) with ESMTP id j75KxYZx082181 for ; Fri, 5 Aug 2005 13:59:36 -0700 (PDT) (envelope-from paul.hoffman@vpnc.org) Mime-Version: 1.0 Message-Id: Date: Fri, 5 Aug 2005 14:13:02 -0400 To: Hash WG From: Paul Hoffman Content-Type: text/plain; charset="us-ascii" ; format="flowed" X-Spam-Score: 2.9 (++) X-Scan-Signature: ec7c6dab5a62df223002ae71b5179d41 Cc: Subject: [Hash] Preliminary minutes from the BoF X-BeenThere: hash@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: hash.lists.ietf.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: hash-bounces@lists.ietf.org Errors-To: hash-bounces@lists.ietf.org Many thanks to Pasi Eronen and Rich Graveman for taking notes! This is my combination of the two. Hash BoF IETF 63, Paris Monday August 1st, 1815-1945, room 341 Chair: Paul Hoffman Notes taken by Pasi Eronen and Rich Graveman, edited by Paul Hoffman 1. Paul Hoffman: Introduction (see slides) Introduced the BOF and rationale for it This deals only with collision resistance, not preimage resistance. 2. Bill Burr: NIST workshop NIST is organizing hash workshop on October 31 - November 1 If you want to attend you have to pre-register Expecting about 20 talks; the agenda will be posted in a couple of weeks Results of this workshop will help in us deciding whether to run a competition for hash functions, and policies regarding SHA-256 URL: http://www.nist.gov/hash-function 3. Russ Housley: Preprocessing to strengthen current hash functions (presenting on Michael Szydlo's behalf) (see slides) Eric Rescorla: As a defense, how specific this is to current techniques of attacking hash functions? Russ: This defeats the currently-known attacks, but not all unknown attacks. Basically we don't know how wide class of attacks this defeats. The paper has some more details. 4. Ran Canetti: Randomized hashing in signatures (see slides) Eric Rescorla: One concern people often have about if attacker can control initial value, it makes forgeries easier. Ran: You need to incorporate randomness in some other way than IV. Eric: 2nd thing, how much randomness you need? Ran: Any amount is better than none, at most 512 bits (the function's block size). Uri Blumenthal: Are there any calculations to prove this randomized is any better than non-randomized? Ran: With current SHA-1 attacks, randomness helps in transforming off-line brute-force attack to on-line. Uri: In some cases it is a problem to come up with even 128 bits of randomness for every signature or hash. Also questioned how to calculate how much randomness you need and how much it helps. 5. Steven Bellovin: Analyzing hash agility in IETF protocols (see slides) Stephen Kent: When looking at this, did you consider handling this with configuration of trust anchors? Bellovin: If IPsec is used in relatively closed environment, it might work. But for things like TLS, probably not. 6. Tim Polk: Hash truncation at NIST (see slides) Donald Eastlake: Why not put the truncation length every 12 bytes, like the "whitening" earlier? Tim Polk: Currently, we only put it in IV. But I'll take this idea to the editors 7. Paul Hoffman: Charter discussion (see slides) Paul: Let's start with the charter from the list but feel free to amend it. Also, let's discuss if this should be in the IETF or the IRTF. Wes Hardaker: I haven't read the charter. I'm confused what exactly is within the scope. We have 4000 RFCs and someone needs to grep for hash functions. Paul: That's not included right now. Wes: It seems the output would be guidance to the rest of IETF, mandated reading. Uri: Designing a hash function is not appropriate for either IETF or IRTF. Collecting requirements, or designing modes like truncated hashes, or recommendations on how to use a hash function, could belong here. Larry Masinter: IETF should do things are needed and only IETF will do, not things that are needed but someone else is likely to do. Designing hash algorithms is the latter, going through through IETF protocols is clearly former, so maybe it should be in the charter. Paul: draft-hoffman-has-attacks-04 concludes that in most IETF protocols the attacks don't really matter. The main exception is certificates, and the attacks are not yet useful. Jon Callas: Randomized hashing or whitening is interesting, we could implement it in OpenPGP in a couple of hours. But what should we doing? There are workshops coming soon. If I have an objection to making a charter, it's only that we should wait for Vancouver to have more information. Gregory Lebovitz: I think doing all protocol work here is not a good idea, rather produce coaching to other WGs that can then update their protocols. Ran: I agree that IETF or IRTF should not design hash functions. Standardizing modes of operation for hash functions, yes. IETF is sometimes more agile than other organizations, for instance HMAC started here, and was then used elsewhere. Paul: Talking about BCPs, we also need to decide whether we want to have a one recommendation/answer for the next hash function, or several. Several gives flexibility, but may confuse the audience. Uri: Our job is not designing modes of operation, but standardizing modes designed and thoroughly peer-reviewed elsewhere. I don't think we're at that point yet with things like randomized hashing. We also need to collect input from not only protocol people, but also hardware; it would not be good if our design is 10x slower than SHA-1. Paul: Some people are implementing SHA1 in hardware, are we making that hardware obsolete? Steven Bellovin: We could do an informational RFC based on the paper by Eric and I, e.g. how to design protocol for hash function agility. Second thing that is needed is analyzing more protocols than Eric and I did to see what works and what not. Eric: We currently have partial information. We know some things we have are weak. In the first stage, we can patch things and provide input/requirements to people designing new hash functions. In stage two, we would replace things with things that come out from standardization process elsewhere, like new hash functions. David Black: I also support producing BCPs, one important thing to decide is to when to publish that BCP, when we're sufficiently confident to recommend something. This is important also outside the IETF. On the hardware issue, SHA-1 is pain in hardware, being as fast as SHA-1 might not be sufficient requirement. Wes Hardaker: People need guidance in rollover and algorithm negotiation. Paul: If we do some work, is it BCPs? (Some nodding and humming) Yes, it looks like most people are. Aaron Falk (IRTF chair): BCP does not sound like research to me, so this sounds more like IETF than IRTF. The IRTF is mostly about doing our own research before handing it off to the IETF. It depends on how you want to scope the work. Shorter-term protocol work would better fit in IETF, longer-term work maybe in CFRG research group? Ran: As CFRG co-chair, some of this is clearly within scope of CFRG. But also would make sense to have a focused IETF working group. Christian Huitema: I would like to see IETF WG working at least on negotiation mechanisms. Jim Touch: We seem to be talking mainly about hashes within scope of signatures, but signature algorithms are out of scope. Is this a good idea? Paul: More needs to be discussed on the mailing list. (end) --Paul Hoffman, Director --VPN Consortium _______________________________________________ Hash mailing list Hash@lists.ietf.org https://www1.ietf.org/mailman/listinfo/hash From hash-bounces@lists.ietf.org Thu Aug 11 13:39:42 2005 Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E3H1q-0001eS-GP; Thu, 11 Aug 2005 13:39:42 -0400 Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1E3H1o-0001eI-NW for hash@megatron.ietf.org; Thu, 11 Aug 2005 13:39:40 -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 NAA15946 for ; Thu, 11 Aug 2005 13:39:40 -0400 (EDT) Received: from above.proper.com ([208.184.76.39]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1E3HaA-0003Cl-CB for hash@ietf.org; Thu, 11 Aug 2005 14:15:11 -0400 Received: from [10.20.30.249] (dsl2-63-249-92-231.cruzio.com [63.249.92.231]) (authenticated bits=0) by above.proper.com (8.12.11/8.12.9) with ESMTP id j7BHdXT4095571 for ; Thu, 11 Aug 2005 10:39:34 -0700 (PDT) (envelope-from paul.hoffman@vpnc.org) Mime-Version: 1.0 Message-Id: Date: Thu, 11 Aug 2005 10:39:52 -0700 To: Hash WG From: Paul Hoffman Content-Type: text/plain; charset="us-ascii" ; format="flowed" X-Spam-Score: 0.0 (/) X-Scan-Signature: 8ac499381112328dd60aea5b1ff596ea Cc: Subject: [Hash] Slides from the meeting X-BeenThere: hash@lists.ietf.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: hash.lists.ietf.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: hash-bounces@lists.ietf.org Errors-To: hash-bounces@lists.ietf.org A temporary pointer of the proceedings with the slides from the BoF last week can be found at --Paul Hoffman, Director --VPN Consortium _______________________________________________ Hash mailing list Hash@lists.ietf.org https://www1.ietf.org/mailman/listinfo/hash From hash-bounces@lists.ietf.org Thu Aug 18 04:46:57 2005 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 ; 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: 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" To: hash@ietf.org Subject: Re: [Hash] randomized hashes and DSA References: <20050803232043.6BF2E3BFFEA@berkshire.machshav.com> 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: , List-Archive: List-Post: List-Help: List-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