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

"David W. Kravitz" <dkravitz@trustcentral.com> Wed, 26 September 2012 05:49 UTC

Return-Path: <dkravitz@trustcentral.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A77CB21F86E3 for <cfrg@ietfa.amsl.com>; Tue, 25 Sep 2012 22:49:23 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.907
X-Spam-Level:
X-Spam-Status: No, score=-1.907 tagged_above=-999 required=5 tests=[AWL=0.691, BAYES_00=-2.599, HTML_MESSAGE=0.001]
Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id IFa627nBI7T5 for <cfrg@ietfa.amsl.com>; Tue, 25 Sep 2012 22:49:21 -0700 (PDT)
Received: from vms173009pub.verizon.net (vms173009pub.verizon.net [206.46.173.9]) by ietfa.amsl.com (Postfix) with ESMTP id AD8B621F87B6 for <cfrg@irtf.org>; Tue, 25 Sep 2012 22:49:21 -0700 (PDT)
Received: from hatemtlaptop ([unknown] [173.66.52.63]) by vms173009.mailsrvcs.net (Sun Java(tm) System Messaging Server 7u2-7.02 32bit (built Apr 16 2009)) with ESMTPA id <0MAY0045W05RU470@vms173009.mailsrvcs.net> for cfrg@irtf.org; Wed, 26 Sep 2012 00:49:04 -0500 (CDT)
From: "David W. Kravitz" <dkravitz@trustcentral.com>
To: "'Scott Fluhrer \(sfluhrer\)'" <sfluhrer@cisco.com>, "'Dan Brown'" <dbrown@certicom.com>, "'Igoe, Kevin M.'" <kmigoe@nsa.gov>, <cfrg@irtf.org>
References: <CC7768A9.EDA64%mcgrew@cisco.com> <9745FE04-5A2C-4D38-9D34-AFF3A2EC54C6@callas.org> <002801cd96b7$b7c38c80$274aa580$@trustcentral.com> <3C4AAD4B5304AB44A6BA85173B4675CA17687160@MSMR-GH1-UEA03.corp.nsa.gov> <000601cd9a69$897d3460$9c779d20$@trustcentral.com> <3C4AAD4B5304AB44A6BA85173B4675CA176901BE@MSMR-GH1-UEA03.corp.nsa.gov> <002901cd9a99$070dc870$15295950$@trustcentral.com> <810C31990B57ED40B2062BA10D43FBF50BA17E@XMB111CNC.rim.net> <001801cd9b3d$40f6aa30$c2e3fe90$@trustcentral.com> <A113ACFD9DF8B04F96395BDEACB34042136CAF@xmb-rcd-x04.cisco.com>
In-reply-to: <A113ACFD9DF8B04F96395BDEACB34042136CAF@xmb-rcd-x04.cisco.com>
Date: Wed, 26 Sep 2012 01:49:01 -0400
Message-id: <000301cd9baa$a1da5b40$e58f11c0$@trustcentral.com>
MIME-version: 1.0
Content-type: multipart/alternative; boundary="----=_NextPart_000_0004_01CD9B89.1ACB0530"
X-Mailer: Microsoft Outlook 14.0
Thread-index: AQJZjD1WbN3mB22kfgMwgvHZe2e5lAHYBuGkAN83IhkCSTqTvgGB4PPAAV1JojICFAfetQHTGd8mAliERmcCEaUc3pYCsXLw
Content-language: en-us
Cc: john.kelsey@nist.gov, "'David McGrew \(mcgrew\)'" <mcgrew@cisco.com>, lily.chen@nist.gov
Subject: Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms
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, 26 Sep 2012 05:49:23 -0000

Hi Scott,

 

Dan Brown made that point to the Cfrg list earlier today (where I suppose
that a quick summary of the reasoning is that (-s^-1) = -(s^-1) and the
additive inverse of an elliptic curve point (x, y) is (x, -y), which both
have the same x coordinate, where r is derived by taking the x coordinate of
the point). While he suggested, in part, that ".one can choose a canonical
choice of the two candidate ECDSA signatures, say the one with smaller s
value, and define it as valid, and the other as invalid," I think that an
alternative solution would be to reject repeat 'r' values and to ignore 's'
in that determination. With a non-deterministic generation of 'k' method,
'k' should not repeat (where if it does and is used with a distinct 'm' the
private key 'x' is exposed anyway). While it is possible for 'r' to repeat
even if 'k' does not, that is highly unlikely to occur.

 

Thanks,

David

 

From: Scott Fluhrer (sfluhrer) [mailto:sfluhrer@cisco.com] 
Sent: Tuesday, September 25, 2012 11:04 PM
To: David W. Kravitz; 'Dan Brown'; 'Igoe, Kevin M.'; cfrg@irtf.org
Cc: john.kelsey@nist.gov; David McGrew (mcgrew); lily.chen@nist.gov
Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA
Digital Signature Algorithms

 

 

 

From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of
David W. Kravitz
Sent: Tuesday, September 25, 2012 12:46 PM
To: 'Dan Brown'; 'Igoe, Kevin M.'; cfrg@irtf.org
Cc: john.kelsey@nist.gov; David McGrew (mcgrew); lily.chen@nist.gov
Subject: Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA
Digital Signature Algorithms

 

Hi Dan and all,

 

I can actually see a potential non- anonymity-related downside of the
feature of having the same signature per message (which unlike the anonymity
issue applies equally to DSA and ECDSA): If a system is configured so as to
reject duplicate signatures as potential fraudulent replays, legitimate
duplicates could also be rejected. Such a system configuration might be more
than hypothetical, in that (as far as I know) an adversary without knowledge
of the private key 'x' cannot feasibly generate additional distinct
DSA/ECDSA signatures that are not in the set of signatures for that message
that the adversary already has available.

 

That last part is false for ECDSA; if (r, s) is a valid signature for a
message H and public key PK, then (r, n-s) is also a valid signature for the
message H and public key PK (where n is the order of the curve).