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

"David W. Kravitz" <dkravitz@trustcentral.com> Tue, 25 September 2012 18:28 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 F138621F8594 for <cfrg@ietfa.amsl.com>; Tue, 25 Sep 2012 11:28:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.2
X-Spam-Level:
X-Spam-Status: No, score=-1.2 tagged_above=-999 required=5 tests=[AWL=-0.022, BAYES_00=-2.599, HTML_MESSAGE=0.001, SARE_GIF_ATTACH=1.42]
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 5ojaiZol3aA7 for <cfrg@ietfa.amsl.com>; Tue, 25 Sep 2012 11:28:18 -0700 (PDT)
Received: from vms173019pub.verizon.net (vms173019pub.verizon.net [206.46.173.19]) by ietfa.amsl.com (Postfix) with ESMTP id 127C61F0421 for <cfrg@irtf.org>; Tue, 25 Sep 2012 11:28:18 -0700 (PDT)
Received: from hatemtlaptop ([unknown] [173.66.52.63]) by vms173019.mailsrvcs.net (Sun Java(tm) System Messaging Server 7u2-7.02 32bit (built Apr 16 2009)) with ESMTPA id <0MAX002AX4N0I570@vms173019.mailsrvcs.net> for cfrg@irtf.org; Tue, 25 Sep 2012 13:28:15 -0500 (CDT)
From: "David W. Kravitz" <dkravitz@trustcentral.com>
To: "'Igoe, Kevin M.'" <kmigoe@nsa.gov>, "'Dan Brown'" <dbrown@certicom.com>, <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> <3C4AAD4B5304AB44A6BA85173B4675CA17695419@MSMR-GH1-UEA03.corp.nsa.gov>
In-reply-to:
Date: Tue, 25 Sep 2012 14:28:10 -0400
Message-id: <001801cd9b4b$857f3010$907d9030$@trustcentral.com>
MIME-version: 1.0
Content-type: multipart/related; boundary="----=_NextPart_000_0019_01CD9B29.FE71FCE0"
X-Mailer: Microsoft Outlook 14.0
Thread-index: AQJZjD1WbN3mB22kfgMwgvHZe2e5lAHYBuGkAN83IhkCSTqTvgGB4PPAAV1JojICFAfetQHTGd8mAU9Hh/EBdgmtJ5YPHaCA
Content-language: en-us
Cc: john.kelsey@nist.gov, 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: Tue, 25 Sep 2012 18:28:22 -0000

Kevin,

 

Regarding ".but a priori I think I'd  want a timestamp of some sort to
prevent replay", as I pointed out to the list a little while ago*, I don't
think you need a timestamp to prevent successful replay to the same
destination if you don't use fully deterministic DSA/ECDSA. Of course, the
differing signatures over the same message would each have to be
individually verified unless you use some sort of batch verification method.

 

*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.

 

Thanks,
David

 

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

 

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?  

 

I'll give this a shot.  Warning: this is all based on a side comment thrown
into a 

conversation concerning obstacles to the adoption of ECDSA signatures.  It
concerns 

BGPsec, which I believe falls under the SIDR WG.

 

BGP will often get duplicate reports from a given neighbor  because the
local configuration 

hasn't changed since the last report.  If the report is signed with an RSA
signature, even the

signature stays constant, so it's simple to see this is the same message is
the same as the last one

& there is no need to verify any signature.  But using ECDSA, the signature
field will (potentially) 

change even if nothing else has, forcing a signature verification.

 

One way to side step the issue is to use deterministic ECDSA.  Another would
be for the sender to 

keep track of the last signed report it sent and, if nothing has changed,
resend the same report.   

 

(I haven't paid much attention to the current state of the BGPsec
discussions and its threat models, but 

a priori I think I'd  want a timestamp of some sort to prevent replay. That
would mean that the report 

would always be changing and a signature verification would always need to
be done).

 

Again, this is all of this is second or third hand,  a quick glance at the
SIDR mailing list didn't provide any 

relevant information.

 

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

 

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