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

["David W. Kravitz" <[e-mail]>]

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:[e-mail]] 
Sent: Tuesday, September 25, 2012 11:04 PM
To: David W. Kravitz; 'Dan Brown'; 'Igoe, Kevin M.'; [e-mail]
Cc: [e-mail]; David McGrew (mcgrew); [e-mail]
Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA
Digital Signature Algorithms

 

 

 

From: [e-mail] [mailto:[e-mail]] On Behalf Of
David W. Kravitz
Sent: Tuesday, September 25, 2012 12:46 PM
To: 'Dan Brown'; 'Igoe, Kevin M.'; [e-mail]
Cc: [e-mail]; David McGrew (mcgrew); [e-mail]
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).