Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms
"David W. Kravitz" <dkravitz@trustcentral.com> Mon, 24 September 2012 21:11 UTC
Return-Path: <dkravitz@trustcentral.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7DFD61F0425 for <cfrg@ietfa.amsl.com>; Mon, 24 Sep 2012 14:11:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.265
X-Spam-Level:
X-Spam-Status: No, score=-1.265 tagged_above=-999 required=5 tests=[AWL=0.133, BAYES_00=-2.599, HTML_MESSAGE=0.001, J_CHICKENPOX_41=0.6, J_CHICKENPOX_42=0.6]
Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id FCMvwp76tvDv for <cfrg@ietfa.amsl.com>; Mon, 24 Sep 2012 14:11:00 -0700 (PDT)
Received: from vms173011pub.verizon.net (vms173011pub.verizon.net [206.46.173.11]) by ietfa.amsl.com (Postfix) with ESMTP id 59E711F041D for <cfrg@irtf.org>; Mon, 24 Sep 2012 14:11:00 -0700 (PDT)
Received: from hatemtlaptop ([unknown] [173.66.52.63]) by vms173011.mailsrvcs.net (Sun Java(tm) System Messaging Server 7u2-7.02 32bit (built Apr 16 2009)) with ESMTPA id <0MAV00FMFHH75ZG1@vms173011.mailsrvcs.net> for cfrg@irtf.org; Mon, 24 Sep 2012 16:10:31 -0500 (CDT)
From: "David W. Kravitz" <dkravitz@trustcentral.com>
To: "'Igoe, Kevin M.'" <kmigoe@nsa.gov>, cfrg@irtf.org
References: <CC7768A9.EDA64%mcgrew@cisco.com> <9745FE04-5A2C-4D38-9D34-AFF3A2EC54C6@callas.org> <002801cd96b7$b7c38c80$274aa580$@trustcentral.com> <3C4AAD4B5304AB44A6BA85173B4675CA17687160@MSMR-GH1-UEA03.corp.nsa.gov> <000601cd9a69$897d3460$9c779d20$@trustcentral.com> <3C4AAD4B5304AB44A6BA85173B4675CA176901BE@MSMR-GH1-UEA03.corp.nsa.gov>
In-reply-to: <3C4AAD4B5304AB44A6BA85173B4675CA176901BE@MSMR-GH1-UEA03.corp.nsa.gov>
Date: Mon, 24 Sep 2012 17:10:19 -0400
Message-id: <002901cd9a99$070dc870$15295950$@trustcentral.com>
MIME-version: 1.0
Content-type: multipart/alternative; boundary="----=_NextPart_000_002A_01CD9A77.7FFD8800"
X-Mailer: Microsoft Outlook 14.0
Thread-index: AQJZjD1WbN3mB22kfgMwgvHZe2e5lAHYBuGkAN83IhkCSTqTvgGB4PPAAV1JojKWQxjaAA==
Content-language: en-us
Cc: john.kelsey@nist.gov, mcgrew@cisco.com, lily.chen@nist.gov
Subject: Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 24 Sep 2012 21:11:04 -0000
Kevin and all, In the (EC)DSA application, unlike a DRBG considered in isolation, we need k^-1 mod q and (H(m) + xr) mod q to effectively hide each other when multiplied modulo q and the resultant modular product 's' and r = (g^k mod p) mod q and y = g^x mod p and 'm' are public (as is g^k mod p through reconstruction during signature verification). Unlike applications that actually require a DRBG: (1) it is not a security weakness if k's repeat for the same m's; and (2) we don't need to reconsider the case where an adversary gains a k value through compromise (as opposed to cryptanalysis) since this is (equally) deadly regardless of how k is generated. So within this particular application (as opposed to DRBG in general) how is the use of HMAC_DRBG in the draft document http://tools.ietf.org/html/draft-pornin-deterministic-dsa-01 any more secure than the direct use of HMAC(x, H(m)||Counter), where (for bias handling) Counter increments by one, is reinitialized for each 'm', and its values are completely determined by either FIPS PUB 186-3 B.2.1 (Per-Message Secret Number Generation Using Extra Random Bits)or B.2.2 (Per-Message Secret Number Generation by Testing Candidates)? As "data points" regarding the security of HMAC: http://cseweb.ucsd.edu/~mihir/papers/hmac-new.html , New Proofs for NMAC and HMAC: Security without Collision-Resistance, has the following "Abstract: HMAC was proved by Bellare, Canetti and Krawczyk (1996) to be a PRF assuming that (1) the underlying compression function is a PRF, and (2) the iterated hash function is weakly collision-resistant. However, recent attacks show that assumption (2) is false for MD5 and SHA-1, removing the proof-based support for HMAC in these cases. This paper proves that HMAC is a PRF under the sole assumption that the compression function is a PRF. This recovers a proof based guarantee since no known attacks compromise the pseudorandomness of the compression function, and it also helps explain the resistance-to-attack that HMAC has shown even when implemented with hash functions whose (weak) collision resistance is compromised. We also show that an even weaker-than-PRF condition on the compression function, namely that it is a privacy-preserving MAC, suffices to establish HMAC is a secure MAC as long as the hash function meets the very weak requirement of being computationally almost universal, where again the value lies in the fact that known attacks do not invalidate the assumptions made." Although I realize "SHA-3" is coming, with regard to whether/which existing SHA compression functions are PRFs, this is what I found so far: http://www.springerlink.com/content/j7340u8162582044/ , Pseudorandom-Function Property of the Step-Reduced Compression Functions of SHA-256 and SHA-512, Abstract: "Applications of an iterated hash function such as HMAC require that the compression function of the hash function is a pseudorandom function. However, the pseudorandom-function property of the compression function was not analyzed up to now. This paper shows that it is easy to distinguish between the 22 step-reduced SHA-512 compression function with the key-via-IV strategy and a random function. This is the first result on the pseudorandom-function property of the SHA-512 compression function with the key-via-IV strategy. A similar distinguishing attack is applicable to the SHA-256 compression function with the key-via-IV strategy." As we know, HMAC is used in http://csrc.nist.gov/publications/nistpubs/800-108/sp800-108.pdf, SP 800-108 Recommendation for Key Derivation Using Pseudorandom Functions, which indicates "For key derivation, this Recommendation approves the use of either the keyed-hash Message Authentication Code (HMAC) specified in [8] or the cipher-based Message Authentication Code (CMAC) specified in [7] as the pseudorandom function." Presumably, the reason why that Special Pub does not recommend the use of a keyed hash function directly (instead of HMAC) is because, in particular, the length-extension property of Merkle-Damgard- based hash functions implies such hash functions do not behave as PRFs even if the underlying compression function behaves as a PRF. Thanks, David From: Igoe, Kevin M. [mailto:kmigoe@nsa.gov] Sent: Monday, September 24, 2012 1:17 PM To: 'David W. Kravitz'; cfrg@irtf.org Cc: john.kelsey@nist.gov; mcgrew@cisco.com; pornin@bolet.org Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms Hi David: Thanks for the clarifications. I have heard reports that some applications (I think it was BGPsec related, but I could easily be wrong), like the "feature" that Alice's signature will be the same each time she signs the same message. (Hopefully someone more familiar with BGPsec can verify this). I believe your main concern is the double use of the signer's secret "x" value. As you point out, we are "betting the farm" that ALL of the "k"'s produced by the HMAC_DRBG are strong. I've not seen any reason to doubt the strength of HMAC_DRBG. It is unlikely that we will ever be able to prove this double usage doesn't introduce any security problems . But I agree with the author that given the extensive analysis of the primitive's involved, the only risk is that somehow combining the two leads to an exploitable weakness. I agree with you and the author that this is double usage unlikely to lead to an exploitable weakness, but would like more feedback from the list on this point. You're probably right that the use of full blown HMAC_DRBG is overly conservative, but it has the virtue of having withstood many years of examination. In an effort to get a design finished in a timely fashion I suggest that we continue with the existing design. But I also would strongly encourage you and your co-authors to put forth a more daring and an efficient alternative design, one that will require more extensive analysis before it is ready for adoption.
- [Cfrg] call for review: Deterministic Usage of DS… David McGrew (mcgrew)
- Re: [Cfrg] call for review: Deterministic Usage o… David W. Kravitz
- Re: [Cfrg] call for review: Deterministic Usage o… Igoe, Kevin M.
- Re: [Cfrg] call for review: Deterministic Usage o… David W. Kravitz
- Re: [Cfrg] call for review: Deterministic Usage o… Igoe, Kevin M.
- Re: [Cfrg] call for review: Deterministic Usage o… Blumenthal, Uri - 0668 - MITLL
- Re: [Cfrg] call for review: Deterministic Usage o… Dan Brown
- Re: [Cfrg] call for review: Deterministic Usage o… David W. Kravitz
- Re: [Cfrg] call for review: Deterministic Usage o… David W. Kravitz
- Re: [Cfrg] call for review: Deterministic Usage o… Dan Brown
- Re: [Cfrg] call for review: Deterministic Usage o… David W. Kravitz
- Re: [Cfrg] call for review: Deterministic Usage o… David W. Kravitz
- Re: [Cfrg] call for review: Deterministic Usage o… Dan Brown
- Re: [Cfrg] call for review: Deterministic Usage o… Scott Fluhrer (sfluhrer)
- Re: [Cfrg] call for review: Deterministic Usage o… David W. Kravitz
- Re: [Cfrg] call for review: Deterministic Usage o… David W. Kravitz