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

David McGrew <mcgrew@cisco.com> Wed, 13 April 2011 13:51 UTC

Return-Path: <mcgrew@cisco.com>
X-Original-To: cfrg@ietfc.amsl.com
Delivered-To: cfrg@ietfc.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfc.amsl.com (Postfix) with ESMTP id 7B7D9E0709 for <cfrg@ietfc.amsl.com>; Wed, 13 Apr 2011 06:51:28 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -108.599
X-Spam-Level:
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 mail.ietf.org ([208.66.40.236]) by localhost (ietfc.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id PGpDRWCQV+rL for <cfrg@ietfc.amsl.com>; Wed, 13 Apr 2011 06:51:27 -0700 (PDT)
Received: from sj-iport-2.cisco.com (sj-iport-2.cisco.com [171.71.176.71]) by ietfc.amsl.com (Postfix) with ESMTP id ACAE5E066B for <cfrg@irtf.org>; Wed, 13 Apr 2011 06:51:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=mcgrew@cisco.com; 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 mtv-core-2.cisco.com ([171.68.58.7]) by sj-iport-2.cisco.com with ESMTP; 13 Apr 2011 13:51:26 +0000
Received: from stealth-10-32-254-214.cisco.com (stealth-10-32-254-214.cisco.com [10.32.254.214]) by mtv-core-2.cisco.com (8.14.3/8.14.3) with ESMTP id p3DDpOBl022910; Wed, 13 Apr 2011 13:51:24 GMT
Message-Id: <ABA04206-63B9-4B0D-A8BC-5C454CB22EC5@cisco.com>
From: David McGrew <mcgrew@cisco.com>
To: Jim Schaad <ietf@augustcellars.com>, pornin@bolet.org
In-Reply-To: <009a01cbf993$fbb34650$f319d2f0$@augustcellars.com>
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$@augustcellars.com>
X-Mailer: Apple Mail (2.936)
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Comments Requested on Deterministic DSA and ECDS draft
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=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  
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:
>
>   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
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg