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.