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

David McGrew <> Wed, 13 April 2011 13:51 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 7B7D9E0709 for <>; Wed, 13 Apr 2011 06:51:28 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -108.599
X-Spam-Status: No, score=-108.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_HI=-8, SARE_RAND_1=2, USER_IN_WHITELIST=-100]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id PGpDRWCQV+rL for <>; Wed, 13 Apr 2011 06:51:27 -0700 (PDT)
Received: from ( []) by (Postfix) with ESMTP id ACAE5E066B for <>; Wed, 13 Apr 2011 06:51:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple;;; l=4065; q=dns/txt; s=iport; t=1302702687; x=1303912287; h=cc:message-id:from:to:in-reply-to: content-transfer-encoding:mime-version:subject:date: references; bh=gvVo0s+pqh/YqW7TMbwzGj9yBJ01+8zjX/RTmvS38jk=; b=AtVn3w7C+xRKToRIXIWsFOnRhU8HKgC7w0nSBG2TG14G20/py2DHpmao Sd5gAIASlWyYFnGkG1wiQB1hRw+BvOe9YRHj9qaxjS9rVZTkFa0+DpkIJ x4BjOIpjG8PXjPzCu623jCxh9Jf/KO7nIKnutJ1aG4slenym88y+URrwp c=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AvsEAOqppU2rRDoH/2dsb2JhbACmF3eIb51WnHyFbgSFWogO
X-IronPort-AV: E=Sophos;i="4.64,204,1301875200"; d="scan'208";a="336241251"
Received: from ([]) by with ESMTP; 13 Apr 2011 13:51:26 +0000
Received: from ( []) by (8.14.3/8.14.3) with ESMTP id p3DDpOBl022910; Wed, 13 Apr 2011 13:51:24 GMT
Message-Id: <>
From: David McGrew <>
To: Jim Schaad <>,
In-Reply-To: <009a01cbf993$fbb34650$f319d2f0$>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
Content-Transfer-Encoding: 7bit
Mime-Version: 1.0 (Apple Message framework v936)
Date: Wed, 13 Apr 2011 06:51:24 -0700
References: <009a01cbf993$fbb34650$f319d2f0$>
X-Mailer: Apple Mail (2.936)
Subject: Re: [Cfrg] Comments Requested on Deterministic DSA and ECDS draft
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 13 Apr 2011 13:51:28 -0000

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  

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?



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:
>   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
> _______________________________________________
> Cfrg mailing list