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<mailto: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<mailto:cfrg@irtf.org>" <cfrg@irtf.org<mailto: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<mailto:Cfrg@irtf.org>
http://www.irtf.org/mailman/listinfo/cfrg