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

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

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:[e-mail]] 
Sent: Monday, September 24, 2012 10:21 AM
To: 'David W. Kravitz'; [e-mail]
Cc: [e-mail]; [e-mail]
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

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

 

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)" <[e-mail]>

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

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

To: "[e-mail]" <[e-mail]>

 

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
[e-mail]
http://www.irtf.org/mailman/listinfo/cfrg