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

[Dan Brown <[e-mail]>]

Hi David,

A slight clarification to your comment about generation of additional distinct signatures: ECDSA has the possibility of admitting one "duplicate" signature because (r,s) and (r,(-s mod q)) are distinct, equally valid for a given message, and easily generated from one another.

The conventional definition of digital signature security (formally known as Goldwasser-Micali-Rivest security) only concerns whether a message has been signed, and does not consider how many distinct signatures there for a message.  Strong unforgeability is a strengthening of this notion, which says that only as many signatures per message as the signer has generated should be allowed. Strong unforgebability sounds nice to have, but I am not too persuaded of its usefulness.  For example, one can wrap any signature in some non-unique encoding scheme, such as BER encoding, and that shouldn't make it insecure.   Anyway, if one really wants this strong unforgeability, 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.  In that case, a protocol of the type you describe may be possible, and I think there are even proofs of strong unforgeability for certain probabilistic signature schemes (I forget which ones now).

Daniel Brown

Research In Motion Limited




[cid:image001.gif@01CD9B2B.C63910A0]



From: David W. Kravitz [mailto:[e-mail]]
Sent: Tuesday, September 25, 2012 2:28 PM
To: 'Igoe, Kevin M.'; Dan Brown; [e-mail]
Cc: [e-mail]; [e-mail]; [e-mail]
Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

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:[e-mail]]<mailto:[mailto:[e-mail]]>
Sent: Tuesday, September 25, 2012 2:12 PM
To: 'Dan Brown'; 'David W. Kravitz'; [e-mail]<mailto:[e-mail]>
Cc: [e-mail]<mailto:[e-mail]>; [e-mail]<mailto:[e-mail]>; [e-mail]<mailto:[e-mail]>
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:[e-mail]]<mailto:[mailto:[e-mail]]>
Sent: Tuesday, September 25, 2012 11:24 AM
To: 'David W. Kravitz'; Igoe, Kevin M.; [e-mail]<mailto:[e-mail]>
Cc: [e-mail]<mailto:[e-mail]>; [e-mail]<mailto:[e-mail]>; [e-mail]<mailto:[e-mail]>
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




[cid:image001.gif@01CD9B2B.C63910A0]




---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.