Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

"Blumenthal, Uri - 0668 - MITLL" <uri@ll.mit.edu> Mon, 24 September 2012 17:54 UTC

Return-Path: <prvs=06142bf100=uri@ll.mit.edu>
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 87C4C21F8797 for <cfrg@ietfa.amsl.com>; Mon, 24 Sep 2012 10:54:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.201
X-Spam-Level:
X-Spam-Status: No, score=-5.201 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, HTML_MESSAGE=0.001, MIME_QP_LONG_LINE=1.396, RCVD_IN_DNSWL_MED=-4, UNPARSEABLE_RELAY=0.001]
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 ydlnpXOimztX for <cfrg@ietfa.amsl.com>; Mon, 24 Sep 2012 10:53:55 -0700 (PDT)
Received: from mx2.ll.mit.edu (MX2.LL.MIT.EDU [129.55.12.46]) by ietfa.amsl.com (Postfix) with ESMTP id D63FA21E8048 for <cfrg@irtf.org>; Mon, 24 Sep 2012 10:53:54 -0700 (PDT)
Received: from LLE2K7-HUB02.mitll.ad.local (LLE2K7-HUB02.mitll.ad.local) by mx2.ll.mit.edu (unknown) with ESMTP id q8OHrmL7000423; Mon, 24 Sep 2012 13:53:48 -0400
From: "Blumenthal, Uri - 0668 - MITLL" <uri@ll.mit.edu>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Date: Mon, 24 Sep 2012 13:53:45 -0400
Thread-Topic: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms
Thread-Index: Ac2afYy3R80ffKgWQrij9JxeDb/PNA==
Message-ID: <CC8613F0.104B8%uri@ll.mit.edu>
In-Reply-To: <3C4AAD4B5304AB44A6BA85173B4675CA176901BE@MSMR-GH1-UEA03.corp.nsa.gov>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/14.12.0.110505
acceptlanguage: en-US
Content-Type: multipart/signed; protocol="application/pkcs7-signature"; micalg=sha1; boundary="B_3431339625_26774936"
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:5.7.7855, 1.0.431, 0.0.0000 definitions=2012-09-24_04:2012-09-24, 2012-09-24, 1970-01-01 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 ipscore=0 suspectscore=2 phishscore=0 bulkscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=6.0.2-1203120001 definitions=main-1209240220
Cc: "john.kelsey@nist.gov" <john.kelsey@nist.gov>, David McGrew <mcgrew@cisco.com>
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 17:54:01 -0000

> 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.
Would this reference http://www.springerlink.com/content/j7340u8162582044/
shake your confidence? (David K., thanks for pointing me at it.) Its
abstract says (again, thanks, David):

> 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.

For their distinguisher they computed prf-advantage as 2^-12 with 4 queries.
Advantage increases with the number of queries, as should be expected.

HMAC is pseudorandom only if the underlying compression function is
pseudorandom. SHA2 may not be pseudorandom.

> 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.

A good alternative IMHO would be using a block cipher-based compression
function.

Tnx!



> From: David W. Kravitz [mailto:dkravitz@trustcentral.com]
> Sent: Monday, September 24, 2012 11:30 AM
> To: Igoe, Kevin M.; 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
>  
> Kevin,
>  
> One effect of the use of ³internal state² is the prevention of HMAC_DRBG from
> producing repeat outputs, where ³HMAC_DRBG Internal State² is defined in
> section 10.1.2.1 of SP 800-90A. By stating that ³Note that we instantiate a
> new HMAC_DRBG instance for each signature generation process,² the draft is
> indicating that internal state is not carried over (which is what I meant by
> ³null²). Consequently, given a repeat message Œm¹ (i.e., repeat seed (= x ||
> H(m) )), the output repeats. While this is not a problem in this particular
> application, it violates a fundamental property of a good DRBG. Furthermore,
> with regard to the next-output-bits-given-previous-output-bits- uncertainty
> property of a good DRBG, if the output for a single message Œm¹ becomes known,
> all other outputs are not only distinguishable from the output of a truly
> random function, but are actually computable. This is due to the ³double use²
> of the private key Œx¹ for generation of Œk¹ and for generation of Œs¹ from
> Œk¹. Since we don¹t require the use of a DRBG in this (EC)DSA application, we
> can use HMAC directly (with Œx¹ as the HMAC key, and H(m)||Counter as the
> HMAC¹ed data, where Counter is used in conjunction with FIPS PUB 186-3 B.2.1
> or B.2.2).
>  
> Note that the use of deterministic generation of Œk¹ (whether done as in the
> current draft, or the suggested simplified version, or based on a block cipher
> instead of HMAC) has an additional potential non-repudiation advantage not
> previously explicitly mentioned: It could make it more difficult to plausibly
> disavow signatures on the basis of leakage of Œx¹ due to low entropy Œk¹.
>  
> Thanks,
> David
>  
> 
> From: Igoe, Kevin M. [mailto:kmigoe@nsa.gov]
> Sent: Monday, September 24, 2012 10:21 AM
> To: 'David W. Kravitz'; cfrg@irtf.org
> Cc: john.kelsey@nist.gov; mcgrew@cisco.com
> Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA
> Digital Signature Algorithms
>  
> David:
>  
>   I¹m having a hard time parsing the last two sentences of the first
> paragraph.  Would you be kind
> enough to rephrase them for me?
>  
> 1) As far as I can see this draft instantiates the HMAC_DRBG using the seed (=
> x || H(M) ) in 
> precisely the correct manner.  I miss where they have strayed from the
> standard.  
>  
> 2) I¹m not  sure what you mean by ³null internal state².
>  
> Clearly I am misinterpreting what you are trying to say.
>  
> 
> From:cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of David
> W. Kravitz
> Sent: Wednesday, September 19, 2012 6:40 PM
> To: cfrg@irtf.org
> Cc: john.kelsey@nist.gov; mcgrew@cisco.com
> Subject: Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA
> Digital Signature Algorithms
>  
> Hi all,
>  
> Comments below.
>  
> Thanks,
> Jon Callas, David W. Kravitz, and Phil Zimmermann
>  
> The required security attributes for the safe use of HMAC in this draft are
> more nuanced than the description currently conveys.  Consider the following
> two excerpts of the draft from the Security Considerations (section 5):
> ³Security relies on whether the generation of 'k' is indistinguishable from
> the output of a Random Oracle.  Roughly speaking, HMAC_DRBG is secure in that
> role as long as HMAC behaves as a PRF (Pseudo-Random Function).²   ³One
> remaining issue with deterministic (EC)DSA, as presented in this document, is
> the "double use" of the private key 'x', both as private key in the signature
> generation algorithm itself, and as input to the HMAC_DRBG-based pseudo-random
> oracle for producing the 'k' value.  This requires HMAC_DRBG to keep on being
> a random oracle, even when the public key (which is computed from 'x') is also
> known.  Given the lack of common structure between HMAC and discrete
> logarithm, this seems a reasonable assumption.² Any discussion in the
> literature of ³random oracle² is typically with respect to ³a publicly
> accessible random function² (as, for example, in ³Indifferentiability,
> Impossibility Results on Reductions, and Applications to the Random Oracle
> Methodology,² by U. Maurer, R. Renner, and C. Holenstein,
> ftp://ftp.inf.ethz.ch/pub/crypto/publications/MaReHo04.pdf). But as HMAC_DRBG
> is specified in the draft document (with null internal state per ³Note that we
> instantiate a new HMAC_DRBG instance for each signature generation process,²
> and ³double use² of the private key Œx¹), given any single output of
> HMAC_DRBG, all other outputs are completely distinguishable from the output of
> an arbitrary truly random function. In other words, given a single Œk¹ value
> that was generated using HMAC_DRBG as specified, any other Œk¹ value(s)
> recovered from Œs¹ by using Œr¹, ŒH(m)¹ and the no-longer-private value of Œx¹
> can be determined as having been generated using HMAC_DRBG as specified. Note
> that even if no values of Œk¹ are disclosed, the use of null internal state
> would be problematic in an application relying on a DRBG where repeated
> outputs are unacceptable.
>  
> So, given that neither (pseudo-)random oracle nor the
> next-output-bits-given-previous-output-bits- uncertainty property of DRBG is
> achieved within the context of the actual (EC)DSA application, we can use a
> simpler formulation here. An example of such is HMAC(Œx¹, H(m)||Counter),
> where Counter is reinitialized for each signature generation process instance
> and potential bias is addressed by deriving Œk¹ using  a single Counter value
> as in [FIPS PUB 186-3] B.2.2 (Per-Message Secret Number Generation by Testing
> Candidates), or multiple Counter values are used as in B.2.1 (Per-Message
> Secret Number Generation Using Extra Random Bits).
>  
> Note that in the case where multiple entities have knowledge of Œx¹ (which may
> complicate non-repudiation), deterministic generation of Œk¹ has the effect
> that the potential subliminal/covert channel is replaced by a MAC property.
> That is, any entity with knowledge of Œx¹ can verify the integrity of Œm¹
> using Œs¹ while ignoring both the transmitted value of Œr¹, and Œy¹ or ŒU¹
> (where y = g^x mod p in DSA or U = xG in ECDSA).
>  
> It might also be prudent to indicate in the Security Considerations section
> that the use of wholly deterministic generation of Œk¹, while not adversely
> affecting the security of (EC)DSA itself and enabling an implementation to be
> safely tested using dummy values of Œx¹, may have a deleterious effect against
> resistance to side-channel attacks such as DPA (as opposed to ³masking² using
> a true RNG).
>  
>  
> 
> From: "David McGrew (mcgrew)" <mcgrew@cisco.com>
> 
> Subject: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital
> Signature Algorithms
> 
> Date: September 13, 2012 7:40:41 AM PDT
> 
> To: "cfrg@irtf.org" <cfrg@irtf.org>
>  
> 
> Hi,
> 
>  
> 
> Thomas has updated his individual submission on deterministic [EC]DSA.   I
> think this is useful work that deserves to move forward to RFC, and that the
> research group should support it (based on my own opinion and the positive
> feedback on the list regarding version ­00).   Please take a look at the draft
> if you have an opinion on digital signatures, and let Thomas know if you have
> constructive criticism.   Verification of the test cases, and review of the
> security considerations, would be especially helpful.
> 
>  
> 
> Thanks,
> 
>  
> 
> David
> 
>  
> 
> <http://tools.ietf.org/html/draft-pornin-deterministic-dsa-01>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>