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

[Dan Brown <[e-mail]>]

Hi David and CFRG subscribers,

Regarding David's question comparing the security of the HMAC_DRBG method from the I-D to David's simpler HMAC-only proposal, I don't think anybody is saying the HMAC_DRBG method is more secure (though Kevin Igoe mentions that analysis already done on HMAC_DRBG).  My intuition would be that they are about the same security, for what little my intuition is worth.

To further answer David's question, my understanding that one of the intuitive goals of HMAC_DRBG design, which I'm not sure is applicable here, was (a) to have a wider pipe than just HMAC and (b) that as long as HMAC_DRBG is fed enough input entropy the output entropy of its initial segment output is not limited by the security level of HMAC.  (The latter is the "full entropy" notion in 90C).  I'm not sure that I quite understand that goal exactly, or that HMAC_DRBG meets it, but I would hazard a bet that HMAC_DRBG could be secure on an assumption slightly milder than HMAC being PRF, which might be the only advantage of the HMAC_DRBG over the simpler HMAC-only.  Put another way, one might be able to devise a pathological condition on the hash function such that HMAC is not PRF, but HMAC_DRBG is still secure.

The I-D  and I have raised the issue of compliance. (I should clarify myself by saying that I agree the I-D probably complies with 90A. But I think it would be nice to further comply 90C and some of the boundary concepts hinted at in ANSI X9.62-2005 but unfortunately that may not be possible).  That said, given that David's solution is also secure, and more efficient, then maybe it deserves to be standardized (that was my point 7).  David's mention of the key derivation function standard suggests that it could applicable here, as an alternative well-studied method.

Can somebody please articulate the benefit of the feature of having the same signature per message?  Perhaps the I-D itself should elaborate on this point. Is it just that some protocol picked some signature scheme with this deterministic feature, and then the protocol decided to rely on this feature, e.g. by using the signature as an stable index for the message?

Curiously, a randomized ECDSA signature (r,s) can also almost provide stable index for the message m, by computing a message-index of h(m)G = sR - rQ, where R is one a just a few elliptic curve point which can be derived from r (this is similar to how the public key can almost be recovered).

Best regards,

Daniel Brown

Research In Motion Limited




[cid:image001.gif@01CD9B06.7DABC2D0]



From: [e-mail] [mailto:[e-mail]] On Behalf Of David W. Kravitz
Sent: Monday, September 24, 2012 5:10 PM
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 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:[e-mail]]
Sent: Monday, September 24, 2012 1:17 PM
To: 'David W. Kravitz'; [e-mail]
Cc: [e-mail]; [e-mail]; [e-mail]
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.

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.