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

["Igoe, Kevin M." <[e-mail]>]

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.


From: David W. Kravitz [mailto:[e-mail]]
Sent: Monday, September 24, 2012 11:30 AM
To: Igoe, Kevin M.; [e-mail]
Cc: [e-mail]; [e-mail]; [e-mail]
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:[e-mail]]
Sent: Monday, September 24, 2012 10:21 AM
To: 'David W. Kravitz'; [e-mail]
Cc: [e-mail]; [e-mail]
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: [e-mail]<mailto:[e-mail]> [mailto:[e-mail]]<mailto:[mailto:[e-mail]]> On Behalf Of David W. Kravitz
Sent: Wednesday, September 19, 2012 6:40 PM
To: [e-mail]<mailto:[e-mail]>
Cc: [e-mail]<mailto:[e-mail]>; [e-mail]<mailto:[e-mail]>
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)" <[e-mail]<mailto:[e-mail]>>
Subject: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms
Date: September 13, 2012 7:40:41 AM PDT
To: "[e-mail]<mailto:[e-mail]>" <[e-mail]<mailto:[e-mail]>>

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
[e-mail]<mailto:[e-mail]>
http://www.irtf.org/mailman/listinfo/cfrg