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

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

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.

 

For reference, this is what the current draft of the I-D
http://tools.ietf.org/html/draft-pornin-deterministic-dsa-01 says on this
specific topic:

   "Deterministic signature schemes may also help in

   other situations, e.g. to avoid spurious duplicates, when the same

   data element is signed several times with the same key: with a

   deterministic signature scheme, the same signature is generated every

   time, making duplicate detection much easier. Conversely, lack of
randomization may have adverse effects in some

   advanced protocols, e.g. related to anonymity in some voting schemes."

 

Thanks,
David

 

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