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

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

Hi all,

With regard to Dan Brown's  point 5 below ("Regarding Anonymity"), the
reconstruction of y = g^x mod p from g^k mod p, r, s, and H(m) is very
similar to the reconstruction of g^k mod p from y, r, s, and H(m) that
actually occurs during signature verification. But without knowledge of y,
the recovery of g^k mod p from its highly compressed form r = (g^k mod p)
mod q appears to be computationally infeasible. For ECDSA, the analogous
recovery of the integer representation of the X coordinate of kG from its
reduced form r is not analogous in difficulty (and is, in fact, trivial),
due to the small cofactor of 1,2 or 4 per the NIST Recommended Curves in
FIPS PUB 186-3, D.1. The difficulty of the DSA case was exploited in U.S.
Patent 5,832,089, D. Kravitz, P. Gemmell, E. Brickell, Off-line Compatible
Electronic Cash Method and System, issued November 3, 1998, and Y. Zheng,
Signcryption or How to Achieve Cost(Signature & Encryption) <<
Cost(Signature) + Cost(Encryption), Crypto '97
http://www.signcryption.org/publications/. Kravitz, et al., states that "
... unlike the El Gamal signature scheme, the Digital Signature Algorithm
apparently does not transmit enough information in its signatures to allow
recovery of the public key. ...the functionality of the Digital Signature
Algorithm may be efficiently extended beyond a straight forward digital
signature mechanism in order to provide (1) sender anonymity, (2)
transaction security, and (3) database security." Zheng essentially achieves
encryption for confidentiality at the same time as signing by "Alice" to
intended recipient "Bob" by replacing generator 'g' in DSA by Bob's public
key g^b mod p. Bob can recover the shared secret (g^b)^k mod p from (g^b)^a
mod p, ((g^b)^k mod p) mod q, s and H(m), but others (besides Alice) cannot
derive the shared secret. 

With regard to Uri Blumenthal's suggestion with respect to the use of a
block cipher (and Dan Brown's point 6 below), there is an issue similar to
the one raised about a "non-compliant" version of HMAC_DRBG vs. the direct
use of HMAC with Counter. Namely, can we use a simpler / more efficient
block cipher- based form that is not prone to potential misuse as an actual
DRBG, as would be a downgraded/"non-compliant" version of CTR_DRBG? The
reference for CTR_DRBG (and HMAC_DRBG) is NIST SP 800-90A.

Thanks,
David

Date: Mon, 24 Sep 2012 18:37:43 +0000
From: Dan Brown <[e-mail]>
To: "'David McGrew (mcgrew)'" <[e-mail]>, "[e-mail]"
	<[e-mail]>
Subject: Re: [Cfrg] call for review: Deterministic Usage of DSA and
	ECDSA Digital Signature Algorithms
Message-ID: <[e-mail]>
Content-Type: text/plain; charset="us-ascii"

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

I-D Reference: http://tools.ietf.org/html/draft-pornin-deterministic-dsa-01