Subject: [Cfrg] Comments Requested on Deterministic DSA and ECDS draft

From: "Jim Schaad" <[email-masked]>
Date: Tue, 12 Apr 2011 21:33:47 -0700

I am currently in the process of reviewing the document draft-pornin-deterministic-dsa-00.txt which has been submitted as independent submission.  As part of this process I am soliciting for comments from the cryptographic community about the soundness of the concept presented.  The abstract for the document is as follows:

   This document defines a deterministic digital signature generation
   procedure.  Such signatures are compatible with standard DSA and
   ECDSA digital signatures, and can be processed with unmodified
   verifiers, which need not be aware of the procedure described
   therein.  Deterministic signatures retain the cryptographic security
   features associated with digital signatures, but can be more easily
   implemented in various environments since they do not need access to
   a source of high quality randomness.

As the document points out there are potential attacks on DSA in the event that k is not randomly chosen and this document  then outlines a way to choose k deterministically and hopefully free from that problem.

Comments are requested so that we can complete our review process.

Thanks

Jim

---

From: David McGrew <[email-masked]>
Date: Wed, 13 Apr 2011 06:51:24 -0700

Hi Jim,

thanks for forwarding; I copied Thomas as well.

Hi Thomas,

this is a well-written and interesting draft.  I have some questions  
on the motivations.   As I understand it, there are two claimed  
advantages for deterministic DSA/ECDSA over the usual vanilla-flavored  
DSA/ECDSA: it requires fewer bits of random data to be provided as  
input, and it is easier to validate an implementation.   I don't quite  
understand how it requires fewer bits of random data, though.  If an  
implementation of DSA/ECDSA can instantiate a strong pseudorandom  
source (such as a DRBG from SP 800-90) using a single random seed, it  
can use that source to generate private keys and k-values.  For that  
implementation, the use of deterministic DSA/ECDSA would not be  
significantly different than the usual DSA/ECDSA, since no additional  
random data is needed. On the other hand, an implementation that has  
no random source whatsoever can only generate DSA/ECDSA signatures if  
it imports a private key.  If that implementation could import a  
random seed for use in a pseudorandom source, it could perform the  
usual DSA/ECDSA signatures; otherwise, deterministic DSA/ECDSA would  
be useful.

On validation, it seems like a nice property that implementations of  
deterministic signature algorithms are amenable to known-answer tests,  
and thus can be easily and directly tested.  To my thinking this is an  
appealing property in a design, but as I see it more analysis that  
showed that this is a real advantage would be needed to warrant  
recommending the adoption of this variant over the existing standard,  
which is already well established.  The questions that come to my  
mind: are deterministic signatures demonstrably more robust against  
implementation failure?  Does the known-answer-test of a deterministic  
signature algorithm provide a higher assurance level than the testing  
that can be done on a randomized algorithm?   I think these questions  
are worth some consideration (in the context of your draft, and in  
general).

Security wise, the assumption that deterministic DSA/ECDSA relies on  
is that the HMAC_DRBG is a random oracle.   The reference [LN2009]  
"stresses the importance of studying the actual security of schemes  
proven in the ROM [random oracle model]".  Has this sort of study been  
performed for deterministic DSA/ECDSA?

An attacker in a chosen-message model can control more aspects of the  
internal computation during signature generation.  Does that have an  
impact on the efficacy of fault-injection attacks, say?

regards,

David

On Apr 12, 2011, at 9:33 PM, Jim Schaad wrote:

> I am currently in the process of reviewing the document draft-pornin- 
> deterministic-dsa-00.txt which has been submitted as independent  
> submission.  As part of this process I am soliciting for comments  
> from the cryptographic community about the soundness of the concept  
> presented.  The abstract for the document is as follows:
>
> As the document points out there are potential attacks on DSA in the  
> event that k is not randomly chosen and this document  then outlines  
> a way to choose k deterministically and hopefully free from that  
> problem.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Jon Callas <[email-masked]>
Date: Wed, 13 Apr 2011 13:11:59 -0700

Jim,

I'm basically supportive of this. In PGP 5.0, we did something analogous to this -- we hashed together the private key, the hash of the message, and I think a couple other things like a time stamp (as a form of sequence number). We were very concerned about the quirk of DSA that losing the random number loses the private key. Certainly, we've seen that as a break of DSA in a couple places since.

There is a lot of discussion of this in the code comments on rationale etc., but the idea was that even if your random number generator was broken in ways that you didn't understand, your private key would still be safe. We noted that strictly speaking, a completely broken random number generator wouldn't spill the keys, which is pretty much the same point that this draft has.

We've encouraged people to use this basic technique. Obviously, today you'd use an HMAC instead of a hash (we did this in the days when dinosaurs roamed the earth and there were no HMACs), etc. Also, back in those days, hardly anyone used DSA. But with DSA coming back through ECDSA, a safety net using steps like these.

This would have saved Sony, and there are others for whom this is a good safety net on the crypto.

However, I raise an eyebrow at turning the virtue of a safety net into a necessity. Despite having been proud of this safety net being so good that it protects against a broken RNG, I wouldn't recommend determinism to *anyone*. It seems to me that it's skating on very thin ice to go completely deterministic.

These techniques make basic DSA better, because if there is weakness in the RNG, you're protected to the degree to which your mixing function resembles a random oracle. It's a huge leap of faith then pin all your security on that. I fear that the basic very good idea might be lost by this final leap of faith.

	Jon