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

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

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