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

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Thu, 13 Sep 2012 14:40:41 +0000

Hi,

Thomas has updated his individual submission on deterministic [EC]DSA.   I think this is useful work that deserves to move forward to RFC, and that the research group should support it (based on my own opinion and the positive feedback on the list regarding version –00).   Please take a look at the draft if you have an opinion on digital signatures, and let Thomas know if you have constructive criticism.   Verification of the test cases, and review of the security considerations, would be especially helpful.

Thanks,

David

<http://tools.ietf.org/html/draft-pornin-deterministic-dsa-01>

---

From: "David W. Kravitz" <[email-masked]>
Date: Wed, 19 Sep 2012 18:40:01 -0400

Hi all,

Comments below.

Thanks,

Jon Callas, David W. Kravitz, and Phil Zimmermann

The required security attributes for the safe use of HMAC in this draft are
more nuanced than the description currently conveys.  Consider the following
two excerpts of the draft from the Security Considerations (section 5):
"Security relies on whether the generation of 'k' is indistinguishable from
the output of a Random Oracle.  Roughly speaking, HMAC_DRBG is secure in
that role as long as HMAC behaves as a PRF (Pseudo-Random Function)."   "One
remaining issue with deterministic (EC)DSA, as presented in this document,
is the "double use" of the private key 'x', both as private key in the
signature generation algorithm itself, and as input to the HMAC_DRBG-based
pseudo-random oracle for producing the 'k' value.  This requires HMAC_DRBG
to keep on being a random oracle, even when the public key (which is
computed from 'x') is also known.  Given the lack of common structure
between HMAC and discrete logarithm, this seems a reasonable assumption."
Any discussion in the literature of "random oracle" is typically with
respect to "a publicly accessible random function" (as, for example, in
"Indifferentiability, Impossibility Results on Reductions, and Applications
to the Random Oracle Methodology," by U. Maurer, R. Renner, and C.
Holenstein, ftp://ftp.inf.ethz.ch/pub/crypto/publications/MaReHo04.pdf). But
as HMAC_DRBG is specified in the draft document (with null internal state
per "Note that we instantiate a new HMAC_DRBG instance for each signature
generation process," and "double use" of the private key 'x'), given any
single output of HMAC_DRBG, all other outputs are completely distinguishable
from the output of an arbitrary truly random function. In other words, given
a single 'k' value that was generated using HMAC_DRBG as specified, any
other 'k' value(s) recovered from 's' by using 'r', 'H(m)' and the
no-longer-private value of 'x' can be determined as having been generated
using HMAC_DRBG as specified. Note that even if no values of 'k' are
disclosed, the use of null internal state would be problematic in an
application relying on a DRBG where repeated outputs are unacceptable.

So, given that neither (pseudo-)random oracle nor the
next-output-bits-given-previous-output-bits- uncertainty property of DRBG is
achieved within the context of the actual (EC)DSA application, we can use a
simpler formulation here. An example of such is HMAC('x', H(m)||Counter),
where Counter is reinitialized for each signature generation process
instance and potential bias is addressed by deriving 'k' using  a single
Counter value as in [FIPS PUB 186-3] B.2.2 (Per-Message Secret Number
Generation by Testing Candidates), or multiple Counter values are used as in
B.2.1 (Per-Message Secret Number Generation Using Extra Random Bits).

Note that in the case where multiple entities have knowledge of 'x' (which
may complicate non-repudiation), deterministic generation of 'k' has the
effect that the potential subliminal/covert channel is replaced by a MAC
property. That is, any entity with knowledge of 'x' can verify the integrity
of 'm' using 's' while ignoring both the transmitted value of 'r', and 'y'
or 'U' (where y = g^x mod p in DSA or U = xG in ECDSA). 

It might also be prudent to indicate in the Security Considerations section
that the use of wholly deterministic generation of 'k', while not adversely
affecting the security of (EC)DSA itself and enabling an implementation to
be safely tested using dummy values of 'x', may have a deleterious effect
against resistance to side-channel attacks such as DPA (as opposed to
"masking" using a true RNG).

From: "David McGrew (mcgrew)" <[email-masked]>

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

Date: September 13, 2012 7:40:41 AM PDT

To: "[email-masked]" <[email-masked]>

Hi,

Thomas has updated his individual submission on deterministic [EC]DSA.   I
think this is useful work that deserves to move forward to RFC, and that the
research group should support it (based on my own opinion and the positive
feedback on the list regarding version -00).   Please take a look at the
draft if you have an opinion on digital signatures, and let Thomas know if
you have constructive criticism.   Verification of the test cases, and
review of the security considerations, would be especially helpful.

Thanks,

David

_______________________________________________
Cfrg mailing list
[email-masked]
http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Mon, 24 Sep 2012 14:21:10 +0000

David:

  I'm having a hard time parsing the last two sentences of the first paragraph.  Would you be kind
enough to rephrase them for me?

1) As far as I can see this draft instantiates the HMAC_DRBG using the seed (= x || H(M) ) in
precisely the correct manner.  I miss where they have strayed from the standard.

2) I'm not  sure what you mean by "null internal state".

Clearly I am misinterpreting what you are trying to say.

From: [email-masked] [mailto:[email-masked]] On Behalf Of David W. Kravitz
Sent: Wednesday, September 19, 2012 6:40 PM
To: [email-masked]
Cc: [email-masked]; [email-masked]
Subject: Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

Hi all,

Comments below.

Thanks,

The required security attributes for the safe use of HMAC in this draft are more nuanced than the description currently conveys.  Consider the following two excerpts of the draft from the Security Considerations (section 5): "Security relies on whether the generation of 'k' is indistinguishable from the output of a Random Oracle.  Roughly speaking, HMAC_DRBG is secure in that role as long as HMAC behaves as a PRF (Pseudo-Random Function)."   "One remaining issue with deterministic (EC)DSA, as presented in this document, is the "double use" of the private key 'x', both as private key in the signature generation algorithm itself, and as input to the HMAC_DRBG-based pseudo-random oracle for producing the 'k' value.  This requires HMAC_DRBG to keep on being a random oracle, even when the public key (which is computed from 'x') is also known.  Given the lack of common structure between HMAC and discrete logarithm, this seems a reasonable assumption." Any discussion in the literature of "random oracle" is typically with respect to "a publicly accessible random function" (as, for example, in "Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology," by U. Maurer, R. Renner, and C. Holenstein, ftp://ftp.inf.ethz.ch/pub/crypto/publications/MaReHo04.pdf). But as HMAC_DRBG is specified in the draft document (with null internal state per "Note that we instantiate a new HMAC_DRBG instance for each signature generation process," and "double use" of the private key 'x'), given any single output of HMAC_DRBG, all other outputs are completely distinguishable from the output of an arbitrary truly random function. In other words, given a single 'k' value that was generated using HMAC_DRBG as specified, any other 'k' value(s) recovered from 's' by using 'r', 'H(m)' and the no-longer-private value of 'x' can be determined as having been generated using HMAC_DRBG as specified. Note that even if no values of 'k' are disclosed, the use of null internal state would be problematic in an application relying on a DRBG where repeated outputs are unacceptable.

So, given that neither (pseudo-)random oracle nor the next-output-bits-given-previous-output-bits- uncertainty property of DRBG is achieved within the context of the actual (EC)DSA application, we can use a simpler formulation here. An example of such is HMAC('x', H(m)||Counter), where Counter is reinitialized for each signature generation process instance and potential bias is addressed by deriving 'k' using  a single Counter value as in [FIPS PUB 186-3] B.2.2 (Per-Message Secret Number Generation by Testing Candidates), or multiple Counter values are used as in B.2.1 (Per-Message Secret Number Generation Using Extra Random Bits).

Note that in the case where multiple entities have knowledge of 'x' (which may complicate non-repudiation), deterministic generation of 'k' has the effect that the potential subliminal/covert channel is replaced by a MAC property. That is, any entity with knowledge of 'x' can verify the integrity of 'm' using 's' while ignoring both the transmitted value of 'r', and 'y' or 'U' (where y = g^x mod p in DSA or U = xG in ECDSA).

It might also be prudent to indicate in the Security Considerations section that the use of wholly deterministic generation of 'k', while not adversely affecting the security of (EC)DSA itself and enabling an implementation to be safely tested using dummy values of 'x', may have a deleterious effect against resistance to side-channel attacks such as DPA (as opposed to "masking" using a true RNG).

From: "David McGrew (mcgrew)" <[email-masked]<mailto:[email-masked]>>
Subject: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms
Date: September 13, 2012 7:40:41 AM PDT
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>

Hi,

Thomas has updated his individual submission on deterministic [EC]DSA.   I think this is useful work that deserves to move forward to RFC, and that the research group should support it (based on my own opinion and the positive feedback on the list regarding version -00).   Please take a look at the draft if you have an opinion on digital signatures, and let Thomas know if you have constructive criticism.   Verification of the test cases, and review of the security considerations, would be especially helpful.

Thanks,

David

<http://tools.ietf.org/html/draft-pornin-deterministic-dsa-01>
_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
http://www.irtf.org/mailman/listinfo/cfrg

---

From: "David W. Kravitz" <[email-masked]>
Date: Mon, 24 Sep 2012 11:30:27 -0400

Kevin,

One effect of the use of "internal state" is the prevention of HMAC_DRBG
from producing repeat outputs, where "HMAC_DRBG Internal State" is defined
in section 10.1.2.1 of SP 800-90A. By stating that "Note that we instantiate
a new HMAC_DRBG instance for each signature generation process," the draft
is indicating that internal state is not carried over (which is what I meant
by "null"). Consequently, given a repeat message 'm' (i.e., repeat seed (= x
|| H(m) )), the output repeats. While this is not a problem in this
particular application, it violates a fundamental property of a good DRBG.
Furthermore, with regard to the next-output-bits-given-previous-output-bits-
uncertainty property of a good DRBG, if the output for a single message 'm'
becomes known, all other outputs are not only distinguishable from the
output of a truly random function, but are actually computable. This is due
to the "double use" of the private key 'x' for generation of 'k' and for
generation of 's' from 'k'. Since we don't require the use of a DRBG in this
(EC)DSA application, we can use HMAC directly (with 'x' as the HMAC key, and
H(m)||Counter as the HMAC'ed data, where Counter is used in conjunction with
FIPS PUB 186-3 B.2.1 or B.2.2).

Note that the use of deterministic generation of 'k' (whether done as in the
current draft, or the suggested simplified version, or based on a block
cipher instead of HMAC) has an additional potential non-repudiation
advantage not previously explicitly mentioned: It could make it more
difficult to plausibly disavow signatures on the basis of leakage of 'x' due
to low entropy 'k'.

Thanks,

David

From: Igoe, Kevin M. [mailto:[email-masked]] 
Sent: Monday, September 24, 2012 10:21 AM
To: 'David W. Kravitz'; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA
Digital Signature Algorithms

David:

  I'm having a hard time parsing the last two sentences of the first
paragraph.  Would you be kind

1) As far as I can see this draft instantiates the HMAC_DRBG using the seed
(= x || H(M) ) in 

precisely the correct manner.  I miss where they have strayed from the
standard.  

From: [email-masked] [mailto:[email-masked]] On Behalf Of
David W. Kravitz
Sent: Wednesday, September 19, 2012 6:40 PM
To: [email-masked]
Cc: [email-masked]; [email-masked]
Subject: Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA
Digital Signature Algorithms

Hi all,

Comments below.

Thanks,

 

Hi,

Thanks,

David

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Mon, 24 Sep 2012 17:17:08 +0000

Hi David:

Thanks for the clarifications.

I have heard reports that some applications (I think it was BGPsec related, but I could easily be wrong),
like the "feature" that  Alice's signature will be the same each time she signs the same message.  (Hopefully
someone more familiar with BGPsec can verify this).

I believe your main concern is the double use of the signer's secret "x" value.   As you point out, we are
"betting the farm" that ALL of the "k"'s produced by the HMAC_DRBG are strong.  I've not seen any reason
to doubt the strength of HMAC_DRBG.

It is  unlikely that we will ever be able to prove this double usage doesn't introduce any security problems .
But I agree with the author that given the extensive analysis of the primitive's involved, the only risk is that
somehow combining the two leads to an exploitable weakness.   I agree with you and the author that this
is double usage unlikely to lead to an exploitable  weakness,  but would like more feedback from the list
on this point.

You're probably right that the use of full blown HMAC_DRBG is overly conservative, but it has the virtue of
having withstood many years of examination.  In an effort to get a design finished in a timely fashion I
suggest that we continue with the existing design.  But I also would strongly encourage you and your co-authors
to put forth a more daring and an efficient alternative design, one that will require more extensive analysis
before it is ready for adoption.

From: David W. Kravitz [mailto:[email-masked]]
Sent: Monday, September 24, 2012 11:30 AM
To: Igoe, Kevin M.; [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

Kevin,

One effect of the use of "internal state" is the prevention of HMAC_DRBG from producing repeat outputs, where "HMAC_DRBG Internal State" is defined in section 10.1.2.1 of SP 800-90A. By stating that "Note that we instantiate a new HMAC_DRBG instance for each signature generation process," the draft is indicating that internal state is not carried over (which is what I meant by "null"). Consequently, given a repeat message 'm' (i.e., repeat seed (= x || H(m) )), the output repeats. While this is not a problem in this particular application, it violates a fundamental property of a good DRBG. Furthermore, with regard to the next-output-bits-given-previous-output-bits- uncertainty property of a good DRBG, if the output for a single message 'm' becomes known, all other outputs are not only distinguishable from the output of a truly random function, but are actually computable. This is due to the "double use" of the private key 'x' for generation of 'k' and for generation of 's' from 'k'. Since we don't require the use of a DRBG in this (EC)DSA application, we can use HMAC directly (with 'x' as the HMAC key, and H(m)||Counter as the HMAC'ed data, where Counter is used in conjunction with FIPS PUB 186-3 B.2.1 or B.2.2).

Note that the use of deterministic generation of 'k' (whether done as in the current draft, or the suggested simplified version, or based on a block cipher instead of HMAC) has an additional potential non-repudiation advantage not previously explicitly mentioned: It could make it more difficult to plausibly disavow signatures on the basis of leakage of 'x' due to low entropy 'k'.

Thanks,
David

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

David:

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]]<mailto:[mailto:[email-masked]]> On Behalf Of David W. Kravitz
Sent: Wednesday, September 19, 2012 6:40 PM
To: [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

Hi all,

Comments below.

Thanks,

Hi,

Thanks,

David

---

From: "Blumenthal, Uri - 0668 - MITLL" <[email-masked]>
Date: Mon, 24 Sep 2012 13:53:45 -0400

> I believe your main concern is the double use of the signer¹s secret ³x²
> value.   As you point out, we are
> ³betting the farm² that ALL of the ³k²¹s produced by the HMAC_DRBG are strong.
> I¹ve not seen any reason
Would this reference http://www.springerlink.com/content/j7340u8162582044/
shake your confidence? (David K., thanks for pointing me at it.) Its
abstract says (again, thanks, David):

> Applications of an iterated hash function such as HMAC require that the
> compression function of the hash function is a pseudorandom function. However,
> the pseudorandom-function property of the compression function was not
> analyzed up to now. This paper shows that it is easy to distinguish between
> the 22 step-reduced SHA-512 compression function with the key-via-IV strategy
> and a random function. This is the first result on the pseudorandom-function
> property of the SHA-512 compression function with the key-via-IV strategy. A
> similar distinguishing attack is applicable to the SHA-256 compression
> function with the key-via-IV strategy.

For their distinguisher they computed prf-advantage as 2^-12 with 4 queries.
Advantage increases with the number of queries, as should be expected.

HMAC is pseudorandom only if the underlying compression function is
pseudorandom. SHA2 may not be pseudorandom.

> But I also would strongly encourage you and your co-authors

A good alternative IMHO would be using a block cipher-based compression
function.

Tnx!

> One effect of the use of ³internal state² is the prevention of HMAC_DRBG from
> producing repeat outputs, where ³HMAC_DRBG Internal State² is defined in
> section 10.1.2.1 of SP 800-90A. By stating that ³Note that we instantiate a
> new HMAC_DRBG instance for each signature generation process,² the draft is
> indicating that internal state is not carried over (which is what I meant by
> ³null²). Consequently, given a repeat message Œm¹ (i.e., repeat seed (= x ||
> H(m) )), the output repeats. While this is not a problem in this particular
> application, it violates a fundamental property of a good DRBG. Furthermore,
> with regard to the next-output-bits-given-previous-output-bits- uncertainty
> property of a good DRBG, if the output for a single message Œm¹ becomes known,
> all other outputs are not only distinguishable from the output of a truly
> random function, but are actually computable. This is due to the ³double use²
> of the private key Œx¹ for generation of Œk¹ and for generation of Œs¹ from
> Œk¹. Since we don¹t require the use of a DRBG in this (EC)DSA application, we
> can use HMAC directly (with Œx¹ as the HMAC key, and H(m)||Counter as the
> HMAC¹ed data, where Counter is used in conjunction with FIPS PUB 186-3 B.2.1
> or B.2.2).
>  
> Note that the use of deterministic generation of Œk¹ (whether done as in the
> current draft, or the suggested simplified version, or based on a block cipher
> instead of HMAC) has an additional potential non-repudiation advantage not
> previously explicitly mentioned: It could make it more difficult to plausibly
> disavow signatures on the basis of leakage of Œx¹ due to low entropy Œk¹.
>  
> Thanks,
> David
>  
> 
>   I¹m having a hard time parsing the last two sentences of the first
> 2) I¹m not  sure what you mean by ³null internal state².
>  
> From:[email-masked] [mailto:[email-masked]] On Behalf Of David
> W. Kravitz
> ³Security relies on whether the generation of 'k' is indistinguishable from
> the output of a Random Oracle.  Roughly speaking, HMAC_DRBG is secure in that
> role as long as HMAC behaves as a PRF (Pseudo-Random Function).²   ³One
> remaining issue with deterministic (EC)DSA, as presented in this document, is
> the "double use" of the private key 'x', both as private key in the signature
> generation algorithm itself, and as input to the HMAC_DRBG-based pseudo-random
> oracle for producing the 'k' value.  This requires HMAC_DRBG to keep on being
> a random oracle, even when the public key (which is computed from 'x') is also
> known.  Given the lack of common structure between HMAC and discrete
> logarithm, this seems a reasonable assumption.² Any discussion in the
> literature of ³random oracle² is typically with respect to ³a publicly
> accessible random function² (as, for example, in ³Indifferentiability,
> Impossibility Results on Reductions, and Applications to the Random Oracle
> Methodology,² by U. Maurer, R. Renner, and C. Holenstein,
> ftp://ftp.inf.ethz.ch/pub/crypto/publications/MaReHo04.pdf). But as HMAC_DRBG
> is specified in the draft document (with null internal state per ³Note that we
> instantiate a new HMAC_DRBG instance for each signature generation process,²
> and ³double use² of the private key Œx¹), given any single output of
> HMAC_DRBG, all other outputs are completely distinguishable from the output of
> an arbitrary truly random function. In other words, given a single Œk¹ value
> that was generated using HMAC_DRBG as specified, any other Œk¹ value(s)
> recovered from Œs¹ by using Œr¹, ŒH(m)¹ and the no-longer-private value of Œx¹
> can be determined as having been generated using HMAC_DRBG as specified. Note
> that even if no values of Œk¹ are disclosed, the use of null internal state
> would be problematic in an application relying on a DRBG where repeated
> outputs are unacceptable.
>  
> simpler formulation here. An example of such is HMAC(Œx¹, H(m)||Counter),
> where Counter is reinitialized for each signature generation process instance
> and potential bias is addressed by deriving Œk¹ using  a single Counter value
> as in [FIPS PUB 186-3] B.2.2 (Per-Message Secret Number Generation by Testing
> Candidates), or multiple Counter values are used as in B.2.1 (Per-Message
> Secret Number Generation Using Extra Random Bits).
>  
> Note that in the case where multiple entities have knowledge of Œx¹ (which may
> complicate non-repudiation), deterministic generation of Œk¹ has the effect
> that the potential subliminal/covert channel is replaced by a MAC property.
> That is, any entity with knowledge of Œx¹ can verify the integrity of Œm¹
> using Œs¹ while ignoring both the transmitted value of Œr¹, and Œy¹ or ŒU¹
> (where y = g^x mod p in DSA or U = xG in ECDSA).
>  
> that the use of wholly deterministic generation of Œk¹, while not adversely
> affecting the security of (EC)DSA itself and enabling an implementation to be
> safely tested using dummy values of Œx¹, may have a deleterious effect against
> resistance to side-channel attacks such as DPA (as opposed to ³masking² using
> a true RNG).
>  
>  
> 
> feedback on the list regarding version 00).   Please take a look at the draft
> if you have an opinion on digital signatures, and let Thomas know if you have
> constructive criticism.   Verification of the test cases, and review of the
> security considerations, would be especially helpful.
> 
>  
> 
> Thanks,
> 
>  
> 
> David
> 
>  
>

---

From: Dan Brown <[email-masked]>
Date: Mon, 24 Sep 2012 18:37:43 +0000

Dear CFRG subscribers,

0. Summary of this email (because it is rather long, sorry)

The I-D that is the topic of this thread addresses a major issue in using (EC)DSA, and provides a good solution, but there is a simpler and more standards compliant solution, which is described below.  This I-D also addresses a minor issue in using (EC)DSA, and provides a good solution.  Though addressing a minor issue, it is worth an RFC, but perhaps with greater coordination with other standards.

1. The Issues

A general issue is that ephemeral private keys (EC)DSA must be secret (and must not even possess certain kinds of bias) and also must not repeat for distinct messages, (even show other weaker types of interdependence). Otherwise, known attack algorithms can be used to learn the static private key.

A major issue, which can be viewed a special case of the general issue, is how to handle an (EC)DSA instantiation with no live entropy source for generating secret ephemeral keys.

A minor issue is to purposely make (EC)DSA operate in a mode that generates a constant signature per message.   Firstly, this mode avoids certain attacks (on repeated keys per message), but is not the only way to do so.  Secondly, this mode makes certain security proofs work.  Thirdly, perhaps some unknown attacks exploit a small leakage per each different (but unbiased) ephemeral key per message, in which case this mode would resists those attacks.

2. A Simpler and More Compliant Solution to the Major Issue

A solution (simpler than in the I-D) to the major issue is to generate the (EC)DSA static and ephemeral keys with a pre-seeded DRBG, the first being the static private key, and the remaining being ephemeral keys.  Just to be clear: the initial DRBG must be seeded with enough entropy.

Alternatively, and along the lines of the I-D, all ephemeral keys could be generated using a single DRBG instance seeded with the static private key.  This is not very compliant for two reasons: (1) the static private key is being use for another purpose, and (2) standards such as NIST Draft Special Publication 800-90C defined an entropy as inside an RBG boundary and not accessible to the application using it, such as the (EC)DSA implementation, so the general RBG API does not allow the external control the entropy.

If there is some risk that this single DRBG is multi-threaded and could possibly supply the same key to two different threads (which it should never ever do, and this would be a major implementation error), then one could add the message hash as an additional input the message digest.  This would help avoid the fatal problem of a repeated ephemeral across different messages.  In other words, the (EC)DSA implementation could try to be very robust and overcome a potential deficiency in a (faulty) DRBG implementation.

Perhaps another I-D explaining this simpler solution would help the IETF.

By the way, I agree with that using HMAC_DRBG may well be quite helpful in getting it deployed, because current ANSI/NIST compliant implementation should already use HMAC_DRBG (or another the SP 800-90A DRBGs).  I also agree, that using HMAC_DRBG helps with compliance, but with the following reservation.    I also agree that although this I-D may not comply with various standards, it is probably a harmless violation.

3. Solving the Minor Issue

On the minor issue, which may be main motivation for the I-D, of generating a constant signature per message, there is only a small benefit.  It would nice if a solution, unlike the I-D, could be strictly compliant to the other RBG standards.

I am reviewing SP 800-90C, but so far I haven't found any way to use it, in strict compliance, to achieve an (EC)DSA with constant signature per message.  Again, by strict compliance, I mean the (EC)DSA is not allowed to see, touch, or influence the entropy inputs, and also the entropy inputs cannot be replicated.  The closest I could get is as follows.  First, instantiate an initial DRBG with real entropy.  It serves as a source of entropy input SEI for further DRBGs, using the notion of an "RBG chain" from NIST's Draft Special Publication 800-90C, subsequent DRBGs can be instantiated using this SEI.  As in the I-D, one DRBG instance could be instantiated per signature.   Note that this requires that this per-signature DRBG be seeded using the output of the initial DRBG, which generates some new random bits for the purposes of the seeding.  The message digest, could be fed in as additional input (or nonce).  However, in order to have a constant-signature-per-message, the (EC)DSA would have to maintain a database of message to ephemeral key values.

Perhaps, I'm interpreting 90C too strictly, and it does allow entropy-input replication.  But I would be surprised if it did, because in general, that could be very bad if not carefully handled.  In that case, the initial DRBG could be called once as SEI, to obtain an initial seed, then this since can be replicated in the sense that is used to instantiate multiple other DRBGs.

4.  Question about deterministic modes

I am also not totally confident that running (EC)DSA with no new entropy per ephemeral key does not lose any security.  For example, it may cause the security of (EC)DSA to rely more heavily on the properties of the hash functions, than it would normally.  Any thoughts?

5. Regarding Anonymity

The security consideration section of the I-D mentions anonymity.  A message and its ECDSA signature (r,s) can be used to reconstruct the public key (or a small set of possible candidates for the keys), and should probably not be regarded as anonymous.  (Doing so for DSA seems to be hard problem.)  So, the security consideration could perhaps be clarified, to avoid giving the wrong impression.  (At this point, I don't have a suggested re-wording, but I could probably be

6. Regarding some of David Kravitz's Comments

My reservations about compliance are also related to David Kravitz's concern, which I agree with. The danger may be that this non-compliant way of using the DRBG in this I-D is mistakenly ported from (EC)DSA over to some other applications, with some potentially bad consequences.  David Kravitz's counter proposal is also not compliant with the current (EC)DSA standards, which that the keys be generated using an approved RNG.

7. Modifying other (EC)DSA standards

So, if a deterministic mode of (EC)DSA is really desired, and deemed secure, should the (EC)DSA standards be amended to loosen this requirement on the key generation, such as in the manner of the I-D, or as in Kravitz's alternative solution?

I can take this question to ANSI X9F1 working group for the next revision of ANS X9.62 (ECDSA), which I am currently editing.

Best regards,

Daniel Brown

Research In Motion Limited

From: [email-masked] [mailto:[email-masked]] On Behalf Of David McGrew (mcgrew)
Sent: Thursday, September 13, 2012 10:41 AM
To: [email-masked]
Subject: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

Hi,

Thanks,

David

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

---

From: "David W. Kravitz" <[email-masked]>
Date: Mon, 24 Sep 2012 17:10:19 -0400

Kevin and all,

In the (EC)DSA application, unlike a DRBG considered in isolation, we need
k^-1 mod q and (H(m) + xr) mod q to effectively hide each other when
multiplied modulo q and the resultant modular product 's' and r = (g^k mod
p) mod q and y = g^x mod p and 'm' are public (as is g^k mod p through
reconstruction during signature verification). Unlike applications that
actually require a DRBG: (1) it is not a security weakness if k's repeat for
the same m's; and (2) we don't need to reconsider the case where an
adversary gains a k value through compromise (as opposed to cryptanalysis)
since this is (equally) deadly regardless of how k is generated.

So within this particular application (as opposed to DRBG in general) how is
the use of HMAC_DRBG in the draft document
http://tools.ietf.org/html/draft-pornin-deterministic-dsa-01 any more secure
than the direct use of HMAC(x, H(m)||Counter), where (for bias handling)
Counter increments by one, is reinitialized for each 'm', and its values are
completely determined by either FIPS PUB 186-3 B.2.1 (Per-Message Secret
Number Generation Using Extra Random Bits)or B.2.2 (Per-Message Secret
Number Generation by Testing Candidates)?

As "data points" regarding the security of HMAC:

http://cseweb.ucsd.edu/~mihir/papers/hmac-new.html , New Proofs for NMAC and
HMAC: Security without Collision-Resistance, has the following "Abstract:
HMAC was proved by Bellare, Canetti and Krawczyk (1996) to be a PRF assuming
that (1) the underlying compression function is a PRF, and (2) the iterated
hash function is weakly collision-resistant. However, recent attacks show
that assumption (2) is false for MD5 and SHA-1, removing the proof-based
support for HMAC in these cases. This paper proves that HMAC is a PRF under
the sole assumption that the compression function is a PRF. This recovers a
proof based guarantee since no known attacks compromise the pseudorandomness
of the compression function, and it also helps explain the
resistance-to-attack that HMAC has shown even when implemented with hash
functions whose (weak) collision resistance is compromised. We also show
that an even weaker-than-PRF condition on the compression function, namely
that it is a privacy-preserving MAC, suffices to establish HMAC is a secure
MAC as long as the hash function meets the very weak requirement of being
computationally almost universal, where again the value lies in the fact
that known attacks do not invalidate the assumptions made."

Although I realize "SHA-3" is coming, with regard to whether/which existing
SHA compression functions are PRFs, this is what I found so far:
http://www.springerlink.com/content/j7340u8162582044/ ,
Pseudorandom-Function Property of the Step-Reduced Compression Functions of
SHA-256 and SHA-512, Abstract: "Applications of an iterated hash function
such as HMAC require that the compression function of the hash function is a
pseudorandom function. However, the pseudorandom-function property of the
compression function was not analyzed up to now. This paper shows that it is
easy to distinguish between the 22 step-reduced SHA-512 compression function
with the key-via-IV strategy and a random function. This is the first result
on the pseudorandom-function property of the SHA-512 compression function
with the key-via-IV strategy. A similar distinguishing attack is applicable
to the SHA-256 compression function with the key-via-IV strategy."

As we know, HMAC is used in
http://csrc.nist.gov/publications/nistpubs/800-108/sp800-108.pdf, SP 800-108
Recommendation for Key Derivation Using Pseudorandom Functions,  which
indicates "For key derivation, this Recommendation approves the use of
either the keyed-hash Message Authentication Code (HMAC) specified in [8] or
the cipher-based Message Authentication Code (CMAC) specified in [7] as the
pseudorandom function." Presumably, the reason why that Special Pub does not
recommend the use of a keyed hash function directly (instead of HMAC) is
because, in particular, the length-extension property of Merkle-Damgard-
based hash functions implies such hash functions do not behave as PRFs even
if the underlying compression function behaves as a PRF.

Thanks,

David

Sent: Monday, September 24, 2012 1:17 PM

Hi David:

I have heard reports that some applications (I think it was BGPsec related,
but I could easily be wrong),

like the "feature" that  Alice's signature will be the same each time she
signs the same message.  (Hopefully
someone more familiar with BGPsec can verify this).   

I believe your main concern is the double use of the signer's secret "x"
value.   As you point out, we are 

"betting the farm" that ALL of the "k"'s produced by the HMAC_DRBG are
strong.  I've not seen any reason  

It is  unlikely that we will ever be able to prove this double usage doesn't
introduce any security problems .  

But I agree with the author that given the extensive analysis of the
primitive's involved, the only risk is that

somehow combining the two leads to an exploitable weakness.   I agree with
you and the author that this

is double usage unlikely to lead to an exploitable  weakness,  but would
like more feedback from the list 

on this point.   

You're probably right that the use of full blown HMAC_DRBG is overly
conservative, but it has the virtue of 

having withstood many years of examination.  In an effort to get a design
finished in a timely fashion I

suggest that we continue with the existing design.  But I also would
strongly encourage you and your co-authors 

to put forth a more daring and an efficient alternative design, one that
will require more extensive analysis

---

From: Dan Brown <[email-masked]>
Date: Tue, 25 Sep 2012 15:23:59 +0000

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

From: [email-masked] [mailto:[email-masked]] On Behalf Of David W. Kravitz
Sent: Monday, September 24, 2012 5:10 PM
To: 'Igoe, Kevin M.'; [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

Kevin and all,

In the (EC)DSA application, unlike a DRBG considered in isolation, we need k^-1 mod q and (H(m) + xr) mod q to effectively hide each other when multiplied modulo q and the resultant modular product 's' and r = (g^k mod p) mod q and y = g^x mod p and 'm' are public (as is g^k mod p through reconstruction during signature verification). Unlike applications that actually require a DRBG: (1) it is not a security weakness if k's repeat for the same m's; and (2) we don't need to reconsider the case where an adversary gains a k value through compromise (as opposed to cryptanalysis) since this is (equally) deadly regardless of how k is generated.

So within this particular application (as opposed to DRBG in general) how is the use of HMAC_DRBG in the draft document http://tools.ietf.org/html/draft-pornin-deterministic-dsa-01 any more secure than the direct use of HMAC(x, H(m)||Counter), where (for bias handling) Counter increments by one, is reinitialized for each 'm', and its values are completely determined by either FIPS PUB 186-3 B.2.1 (Per-Message Secret Number Generation Using Extra Random Bits)or B.2.2 (Per-Message Secret Number Generation by Testing Candidates)?

http://cseweb.ucsd.edu/~mihir/papers/hmac-new.html , New Proofs for NMAC and HMAC: Security without Collision-Resistance, has the following "Abstract: HMAC was proved by Bellare, Canetti and Krawczyk (1996) to be a PRF assuming that (1) the underlying compression function is a PRF, and (2) the iterated hash function is weakly collision-resistant. However, recent attacks show that assumption (2) is false for MD5 and SHA-1, removing the proof-based support for HMAC in these cases. This paper proves that HMAC is a PRF under the sole assumption that the compression function is a PRF. This recovers a proof based guarantee since no known attacks compromise the pseudorandomness of the compression function, and it also helps explain the resistance-to-attack that HMAC has shown even when implemented with hash functions whose (weak) collision resistance is compromised. We also show that an even weaker-than-PRF condition on the compression function, namely that it is a privacy-preserving MAC, suffices to establish HMAC is a secure MAC as long as the hash function meets the very weak requirement of being computationally almost universal, where again the value lies in the fact that known attacks do not invalidate the assumptions made."

Although I realize "SHA-3" is coming, with regard to whether/which existing SHA compression functions are PRFs, this is what I found so far: http://www.springerlink.com/content/j7340u8162582044/ , Pseudorandom-Function Property of the Step-Reduced Compression Functions of SHA-256 and SHA-512, Abstract: "Applications of an iterated hash function such as HMAC require that the compression function of the hash function is a pseudorandom function. However, the pseudorandom-function property of the compression function was not analyzed up to now. This paper shows that it is easy to distinguish between the 22 step-reduced SHA-512 compression function with the key-via-IV strategy and a random function. This is the first result on the pseudorandom-function property of the SHA-512 compression function with the key-via-IV strategy. A similar distinguishing attack is applicable to the SHA-256 compression function with the key-via-IV strategy."

As we know, HMAC is used in http://csrc.nist.gov/publications/nistpubs/800-108/sp800-108.pdf, SP 800-108 Recommendation for Key Derivation Using Pseudorandom Functions,  which indicates "For key derivation, this Recommendation approves the use of either the keyed-hash Message Authentication Code (HMAC) specified in [8] or the cipher-based Message Authentication Code (CMAC) specified in [7] as the pseudorandom function." Presumably, the reason why that Special Pub does not recommend the use of a keyed hash function directly (instead of HMAC) is because, in particular, the length-extension property of Merkle-Damgard- based hash functions implies such hash functions do not behave as PRFs even if the underlying compression function behaves as a PRF.

Thanks,
David

Hi David:

---

From: "David W. Kravitz" <[email-masked]>
Date: Tue, 25 Sep 2012 12:46:03 -0400

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:[email-masked]] 
Sent: Tuesday, September 25, 2012 11:24 AM
To: 'David W. Kravitz'; 'Igoe, Kevin M.'; [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA
Digital Signature Algorithms

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

---

From: "David W. Kravitz" <[email-masked]>
Date: Tue, 25 Sep 2012 14:28:10 -0400

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

Thanks,
David

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

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.

To: 'David W. Kravitz'; Igoe, Kevin M.; [email-masked]

Best regards,

Daniel Brown

---

From: Dan Brown <[email-masked]>
Date: Tue, 25 Sep 2012 18:53:59 +0000

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

From: David W. Kravitz [mailto:[email-masked]]
Sent: Tuesday, September 25, 2012 2:28 PM
To: 'Igoe, Kevin M.'; Dan Brown; [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
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:[email-masked]]<mailto:[mailto:[email-masked]]>
Sent: Tuesday, September 25, 2012 2:12 PM
To: 'Dan Brown'; 'David W. Kravitz'; [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

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:[email-masked]]<mailto:[mailto:[email-masked]]>
Sent: Tuesday, September 25, 2012 11:24 AM
To: 'David W. Kravitz'; Igoe, Kevin M.; [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: RE: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

Best regards,

Daniel Brown

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 26 Sep 2012 03:03:36 +0000

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

---

From: "David W. Kravitz" <[email-masked]>
Date: Wed, 26 Sep 2012 01:49:01 -0400

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

Hi Dan and all,

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

---

From: "David W. Kravitz" <[email-masked]>
Date: Thu, 27 Sep 2012 12:27:48 -0400

Kevin,

Regarding "If the report is signed with an RSA signature, even the signature
stays constant.," this gets us back to the issue I mentioned in my initial
comments on the I-D regarding side-channel attacks. See, for example,
"Weaknesses in Current RSA Signature Schemes," Juliane Kramer Dmitry
Nedospasov Jean-Pierre Seifert, ICISC 2011, http://nedos.net/icisc2011.pdf,
which exploits constant (and therefore fixed-per-message-) RSA signature
padding. Also, http://www.rsa.com/rsalabs/node.asp?id=2005 mentions that
"Another advantage of RSA-PSS is that, due to the randomization, an attacker
does not know in advance what the encoded message EM will be. This makes
"fault analysis" attacks of the sort proposed by Bellcore a few years ago
more difficult to mount (see the RSA Laboratories' Bulletin No. 5)."

Thanks,
David

relevant information.