RFC 6979
Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)
Independent Submission T. Pornin Request for Comments: 6979 August 2013 Category: Informational ISSN: 2070-1721 Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)Abstract
This document defines a deterministic digital signature generation procedure. Such signatures are compatible with standard Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) digital signatures and can be processed with unmodified verifiers, which need not be aware of the procedure described therein. Deterministic signatures retain the cryptographic security features associated with digital signatures but can be more easily implemented in various environments, since they do not need access to a source of high-quality randomness. Status of This Memo This document is not an Internet Standards Track specification; it is published for informational purposes. This is a contribution to the RFC Series, independently of any other RFC stream. The RFC Editor has chosen to publish this document at its discretion and makes no statement about its value for implementation or deployment. Documents approved for publication by the RFC Editor are not a candidate for any level of Internet Standard; see Section 2 of RFC 5741. Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc6979. Copyright Notice Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.
Table of Contents
1. Introduction ....................................................3 1.1. Requirements Language ......................................4 2. DSA and ECDSA Notations .........................................4 2.1. Key Parameters .............................................5 2.2. Key Pairs ..................................................5 2.3. Integer Conversions ........................................6 2.3.1. Bits and Octets .....................................6 2.3.2. Bit String to Integer ...............................6 2.3.3. Integer to Octet String .............................7 2.3.4. Bit String to Octet String ..........................7 2.3.5. Usage ...............................................8 2.4. Signature Generation .......................................8 3. Deterministic DSA and ECDSA ....................................10 3.1. Building Blocks ...........................................10 3.1.1. HMAC ...............................................10 3.2. Generation of k ...........................................10 3.3. Alternate Description of the Generation of k ..............12 3.4. Usage Notes ...............................................13 3.5. Rationale .................................................13 3.6. Variants ..................................................14 4. Security Considerations ........................................15 5. Intellectual Property Status ...................................17 6. References .....................................................17 6.1. Normative References ......................................17 6.2. Informative References ....................................18 Appendix A. Examples .............................................20 A.1. Detailed Example ..........................................20 A.1.1. Key Pair ..............................................20 A.1.2. Generation of k .......................................20 A.1.3. Signature .............................................23 A.2. Test Vectors ..............................................24 A.2.1. DSA, 1024 Bits ........................................25 A.2.2. DSA, 2048 Bits ........................................27 A.2.3. ECDSA, 192 Bits (Prime Field) .........................29 A.2.4. ECDSA, 224 Bits (Prime Field) .........................31 A.2.5. ECDSA, 256 Bits (Prime Field) .........................33 A.2.6. ECDSA, 384 Bits (Prime Field) .........................35 A.2.7. ECDSA, 521 Bits (Prime Field) .........................38 A.2.8. ECDSA, 163 Bits (Binary Field, Koblitz Curve) .........42 A.2.9. ECDSA, 233 Bits (Binary Field, Koblitz Curve) .........44 A.2.10. ECDSA, 283 Bits (Binary Field, Koblitz Curve) .........46 A.2.11. ECDSA, 409 Bits (Binary Field, Koblitz Curve) .........49 A.2.12. ECDSA, 571 Bits (Binary Field, Koblitz Curve) .........52 A.2.13. ECDSA, 163 Bits (Binary Field, Pseudorandom Curve) ....56 A.2.14. ECDSA, 233 Bits (Binary Field, Pseudorandom Curve) ....58 A.2.15. ECDSA, 283 Bits (Binary Field, Pseudorandom Curve) ....60
A.2.16. ECDSA, 409 Bits (Binary Field, Pseudorandom Curve) ....63
A.2.17. ECDSA, 571 Bits (Binary Field, Pseudorandom Curve) ....66
A.3. Sample Code ...............................................70
1. Introduction
DSA [FIPS-186-4] and ECDSA [X9.62] are two standard digital signature
schemes. They provide data integrity and verifiable authenticity in
various protocols.
One characteristic of DSA and ECDSA is that they need to produce, for
each signature generation, a fresh random value (hereafter designated
as k). For effective security, k must be chosen randomly and
uniformly from a set of modular integers, using a cryptographically
secure process. Even slight biases in that process may be turned
into attacks on the signature schemes.
The need for a cryptographically secure source of randomness proves
to be a hindrance to deployment of DSA and ECDSA signature schemes in
some architectures in which secure random number generation is
challenging, in particular, embedded systems such as smartcards. In
those systems, the RSA signature algorithm, used as specified in
Public-Key Cryptography Standards (PKCS) #1 [RFC3447] (with "type 1"
padding, not the Probabilistic Signature Scheme (PSS)) and ISO 9796-2
[ISO-9796-2], is often preferred, even though it is computationally
more expensive, because RSA (with such padding schemes) is
deterministic and thus does not require a source of randomness.
The randomized nature of DSA and ECDSA also makes implementations
harder to test. Automatic tests cannot reliably detect whether the
implementation uses a source of randomness of high enough quality.
This makes the implementation process more vulnerable to catastrophic
failures, often discovered after the system has been deployed and
successfully attacked.
It is possible to turn DSA and ECDSA into deterministic schemes by
using a deterministic process for generating the "random" value k.
That process must fulfill some cryptographic characteristics in order
to maintain the properties of verifiability and unforgeability
expected from signature schemes; namely, for whoever does not know
the signature private key, the mapping from input messages to the
corresponding k values must be computationally indistinguishable from
what a randomly and uniformly chosen function (from the set of
messages to the set of possible k values) would return.
This document describes such a procedure. It has the following
features:
o Produced signatures remain fully compatible with plain DSA and
ECDSA. Entities that verify the signatures need not be changed or
even be aware of the process used to generate k.
o Key pair generation is not altered. Existing private keys can be
used with deterministic DSA and ECDSA.
o Using deterministic DSA and ECDSA implies no extra storage
requirement of any secret or public value.
o Deterministic DSA and ECDSA can be applied over the same inputs as
plain DSA and ECDSA, namely a hash value computed over the message
that is to be signed, with a cryptographically secure hash
function.
Some relatively arbitrary choices were taken in the definition of
deterministic (EC)DSA as specified in this document; this was done in
order to make it as universally applicable as possible, so as to
maximize usefulness of included test vectors. See Section 3.6 for a
discussion of some possible variants.
It shall be noted that key pair generation still requires a source of
randomness. In embedded systems where quality of randomness is an
issue, it can often be arranged that key pair generation occurs
within more controlled conditions (e.g., during a special smartcard
initialization procedure or under physical control of sworn agents)
or the key might even be generated elsewhere and imported in the
device. Deterministic DSA and ECDSA only deal with the need for
randomness at the time of signature generation.
1.1. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
2. DSA and ECDSA Notations
In this section, we succinctly describe DSA and ECDSA and define our
notations. The complete specifications for DSA and ECDSA can be
found in [FIPS-186-4] and [X9.62], respectively.
2.1. Key Parameters
DSA and ECDSA work over a large group of prime size, in which the group operation is easy to compute, but the discrete logarithm is computationally infeasible with existing and foreseeable technology. The definition of the group is called the "key parameters". Key parameters may be shared between different key pairs with no ill effect on security; this is the usual case with ECDSA in particular. DSA uses the following key parameters: p a large prime number (at least 1024 bits) q a sufficiently large prime number (at least 160 bits) that is also a divisor of p-1 g a generator for the multiplicative subgroup of order q of integers modulo p The group on which DSA will be computed consists of the values 'g^j mod p', where '^' denotes exponentiation and j ranges from 0 to q-1 (inclusive). The size of the group is q. ECDSA uses the following key parameters: E an elliptic curve, defined over a given finite field q a sufficiently large prime number (at least 160 bits) that is a divisor of the curve order G a point of E, of order q The group on which ECDSA will be computed consists of the curve points jG (multiplication of point G by integer j) where j ranges from 0 to q-1. G is such that qG = 0 (the "point at infinity" on the curve E). The size of the group is q. Note that these notations slightly differ from those described in [X9.62]; we use them in order to match those used for DSA.2.2. Key Pairs
A DSA or ECDSA private key is an integer x taken modulo q. The relevant standards prescribe that x shall not be 0; hence, x is an integer in the range [1, q-1].
A DSA or ECDSA public key is computed from the private key x and the key parameters: o For DSA, the public key is the integer: y = g^x mod p o For ECDSA, the public key is the curve point: U = xG2.3. Integer Conversions
Let qlen be the binary length of q. qlen is the smallest integer such that q is less than 2^qlen. This is the size of the binary representation of q without a sign bit (note that q, being a big prime, is odd, thus avoiding any ambiguity about the length of any integer equal to a power of 2). We define five conversion functions, which work on strings of bits, octets, and integers modulo q. qlen is the main parameter for these conversions. In the following subsections, we use two other lengths, called blen and rlen. rlen is equal to qlen, rounded up to the next multiple of 8 (if qlen is already a multiple of 8, then rlen equals qlen; otherwise, rlen is slightly larger, up to qlen+7). Note that rlen is unrelated to the value r, the first half of a generated signature. blen is the length (in bits) of an input sequence of bits and may vary between calls. blen may be smaller than, equal to, or larger than qlen.2.3.1. Bits and Octets
Formally, all operations are defined on sequences of bits. A sequence is ordered; the first bit is said to be leftmost, while the last bit is rightmost. On most software systems, bits are grouped into octets (sequences of eight bits). Binary data, e.g., the output of a hash function, is available as a sequence of octets. Whenever applicable, we consider that bits within an octet are ordered from most significant to least significant: the first (leftmost) bit within an octet has numerical value 128, while the last (rightmost) has numerical value 1.2.3.2. Bit String to Integer
The bits2int transform takes as input a sequence of blen bits and outputs a non-negative integer that is less than 2^qlen. It consists of the following steps:
1. The sequence is first truncated or expanded to length qlen:
* if qlen < blen, then the qlen leftmost bits are kept, and
subsequent bits are discarded;
* otherwise, qlen-blen bits (of value zero) are added to the
left of the sequence (i.e., before the input bits in the
sequence order).
2. The resulting sequence is then converted to an integer value
using the big-endian convention: if input bits are called b_0
(leftmost) to b_(qlen-1) (rightmost), then the resulting value
is:
b_0*2^(qlen-1) + b_1*2^(qlen-2) + ... + b_(qlen-1)*2^0
The bits2int transform can also be described in the following way:
the input bit sequence (of length blen) is transformed into an
integer using the big-endian convention. Then, if blen is greater
than qlen, the resulting integer is divided by two to the power
blen-qlen (Euclidian division: the remainder is discarded); in many
software implementations of arithmetics on big integers, that
division is equivalent to a "right shift" by blen-qlen bits.
2.3.3. Integer to Octet String
An integer value x less than q (and, in particular, a value that has
been taken modulo q) can be converted into a sequence of rlen bits,
where rlen = 8*ceil(qlen/8). This is the sequence of bits obtained
by big-endian encoding. In other words, the sequence bits x_i (for i
ranging from 0 to rlen-1) are such that:
x = x_0*2^(rlen-1) + x_1*2^(rlen-2) + ... + x_(rlen-1)
We call this transform int2octets. Since rlen is a multiple of 8
(the smallest multiple of 8 that is not smaller than qlen), then the
resulting sequence of bits is also a sequence of octets, hence the
name.
2.3.4. Bit String to Octet String
The bits2octets transform takes as input a sequence of blen bits and
outputs a sequence of rlen bits. It consists of the following steps:
1. The input sequence b is converted into an integer value z1
through the bits2int transform:
z1 = bits2int(b)
2. z1 is reduced modulo q, yielding z2 (an integer between 0 and
q-1, inclusive):
z2 = z1 mod q
Note that since z1 is less than 2^qlen, that modular reduction
can be implemented with a simple conditional subtraction:
z2 = z1-q if that value is non-negative; otherwise, z2 = z1.
3. z2 is transformed into a sequence of octets (a sequence of rlen
bits) by applying int2octets.
2.3.5. Usage
It is worth noting that int2octets is not the reverse of bits2int,
even for input sequences of length qlen: int2octets will add some
bits on the left, while bits2int will discard some bits on the right.
int2octets is the reverse of bits2int only when qlen is a multiple of
8 and bit sequences already have length qlen.
bits2int is used during signature generation and verification in
standard DSA and ECDSA to transform a hash value (computed over the
input message) into an integer modulo q. That is, the integer
obtained through bits2int is further reduced modulo q; since that
integer is less than 2^qlen, that reduction can be performed with at
most one subtraction.
int2octets is defined under the name "Integer-to-OctetString" in
Section 2.3.7 of SEC 1 [SEC1]. It is used in the specification of
the encoding of an ECDSA private key (x) within an ASN.1-based
structure.
bits2octets is not used in standard DSA or ECDSA. We will use it in
the specification of deterministic (EC)DSA.
2.4. Signature Generation
Signature generation uses a cryptographic hash function H and an
input message m. The message is first processed by H, yielding the
value H(m), which is a sequence of bits of length hlen. Normally, H
is chosen such that its output length hlen is roughly equal to qlen,
since the overall security of the signature scheme will depend on the
smallest of hlen and qlen; however, the relevant standards support
all combinations of hlen and qlen.
The following steps are then applied:
1. H(m) is transformed into an integer modulo q using the bits2int
transform and an extra modular reduction:
h = bits2int(H(m)) mod q
As was noted in the description of bits2octets, the extra modular
reduction is no more than a conditional subtraction.
2. A random value modulo q, dubbed k, is generated. That value
shall not be 0; hence, it lies in the [1, q-1] range. Most of
the remainder of this document will revolve around the process
used to generate k. In plain DSA or ECDSA, k should be selected
through a random selection that chooses a value among the q-1
possible values with uniform probability.
3. A value r (modulo q) is computed from k and the key parameters:
* For DSA:
r = g^k mod p mod q
(The exponentiation is performed modulo p, yielding a number
between 0 and p-1, which is then further reduced modulo q.)
* For ECDSA: the point kG is computed; its X coordinate (a
member of the field over which E is defined) is converted to
an integer, which is reduced modulo q, yielding r.
If r turns out to be zero, a new k should be selected and r
computed again (this is an utterly improbable occurrence).
4. The value s (modulo q) is computed:
s = (h+x*r)/k mod q
The pair (r, s) is the signature. How a signature is to be
encoded is not covered by the DSA and ECDSA standards themselves;
a common way is to use a DER-encoded ASN.1 structure (a SEQUENCE
of two INTEGERs, for r and s, in that order).
3. Deterministic DSA and ECDSA
Deterministic (EC)DSA is the process of generating an (EC)DSA signature over an input message m by using the standard (EC)DSA signature generation process (discussed in the previous section), except that the value k, instead of being randomly generated, is obtained through the process described in this section. We use the notations described in Section 2.3.1. Building Blocks
3.1.1. HMAC
HMAC [RFC2104] is a construction of a Message Authentication Code using a hash function and a secret key. Here, we use HMAC with the same hash function H as the one used to process the input message prior to signature generation or verification. We denote the process of applying HMAC with key K over data V by: HMAC_K(V) which returns a sequence of bits of length hlen (the output length of the underlying hash function H).3.2. Generation of k
Given the input message m, the following process is applied: a. Process m through the hash function H, yielding: h1 = H(m) (h1 is a sequence of hlen bits). b. Set: V = 0x01 0x01 0x01 ... 0x01 such that the length of V, in bits, is equal to 8*ceil(hlen/8). For instance, on an octet-based system, if H is SHA-256, then V is set to a sequence of 32 octets of value 1. Note that in this step and all subsequent steps, we use the same H function as the one used in step 'a' to process the input message; this choice will be discussed in more detail in Section 3.6.
c. Set:
K = 0x00 0x00 0x00 ... 0x00
such that the length of K, in bits, is equal to 8*ceil(hlen/8).
d. Set:
K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))
where '||' denotes concatenation. In other words, we compute
HMAC with key K, over the concatenation of the following, in
order: the current value of V, a sequence of eight bits of value
0, the encoding of the (EC)DSA private key x, and the hashed
message (possibly truncated and extended as specified by the
bits2octets transform). The HMAC result is the new value of K.
Note that the private key x is in the [1, q-1] range, hence a
proper input for int2octets, yielding rlen bits of output, i.e.,
an integral number of octets (rlen is a multiple of 8).
e. Set:
V = HMAC_K(V)
f. Set:
K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))
Note that the "internal octet" is 0x01 this time.
g. Set:
V = HMAC_K(V)
h. Apply the following algorithm until a proper value is found for
k:
1. Set T to the empty sequence. The length of T (in bits) is
denoted tlen; thus, at that point, tlen = 0.
2. While tlen < qlen, do the following:
V = HMAC_K(V)
T = T || V
3. Compute:
k = bits2int(T)
If that value of k is within the [1,q-1] range, and is
suitable for DSA or ECDSA (i.e., it results in an r value
that is not 0; see Section 3.4), then the generation of k is
finished. The obtained value of k is used in DSA or ECDSA.
Otherwise, compute:
K = HMAC_K(V || 0x00)
V = HMAC_K(V)
and loop (try to generate a new T, and so on).
Please note that when k is generated from T, the result of bits2int
is compared to q, not reduced modulo q. If the value is not between
1 and q-1, the process loops. Performing a simple modular reduction
would induce biases that would be detrimental to signature security.
3.3. Alternate Description of the Generation of k
The process described in the previous section is actually derived
from the "HMAC_DRBG" pseudorandom number generator, described in
[SP800-90A] and Annex D of [X9.62]. Using the terminology from
[SP800-90A], the generation of k can be described as such:
a. Instantiate HMAC_DRBG using HMAC parameterized with the same hash
function H as the one used for processing the message that is to
be signed. Instantiation parameters are:
requested_instantiation_security_strength
Set this parameter to any value that the HMAC_DRBG
implementation will accept, when using H as base hash
function.
prediction_resistance_flag
Set this parameter to "false".
personalization_string
Set this parameter to "Null" (the empty bit sequence).
entropy_input
Use int2octets(x) as entropy string.
nonce
Use bits2octets(H(m)) as nonce.
Note that the last two parameters are not parameters to the
HMAC_DRBG instantiation function per se; instead, those values
are requested from the internal Get_entropy_input function during
instantiation. For deterministic (EC)DSA, we want HMAC_DRBG to
run with the entropy string and nonce that we specify, without
accessing an actual entropy source.
b. Generate a candidate value for k by requesting qlen bits from
HMAC_DRBG and converting the resulting bits into an integer with
the bits2int transform. Repeat this step until a value is
obtained, which is non-zero, less than q, and suitable for
(EC)DSA (see Section 3.4).
Note that we instantiate a new HMAC_DRBG instance for each signature
generation process. There is no "personalization string" and no
"additional input" when generating bits. The reseed function of
HMAC_DRBG is never invoked, neither externally nor as a consequence
of the internal HMAC_DRBG processing.
As shown above, we use the encoding of the private key as "entropy
string" and the hashed message (truncated and expanded by
bits2octets) as "nonce". In HMAC_DRBG, the entropy string and nonce
are simply concatenated into the initial seed; hence, the split
between "entropy" and "nonce" is quite arbitrary. Using qlen bits
for each ought to be compatible with most HMAC_DRBG implementation
input requirements.
3.4. Usage Notes
With DSA or ECDSA, the value k is used to compute the first half of
the signature, dubbed r (see Section 2.4). The DSA and ECDSA
standards mandate that, if r is zero, then a new k should be
selected. In that situation, this document specifies that the value
k is "unsuitable", and the generation process shall keep on looping.
This occurrence is utterly improbable. Actually, it would require
considerable computational effort (similar to breaking preimage
resistance of the hash function) to find a private key and a message
that lead to a zero value for r; hitting such a case by pure chance
is thus deemed implausible, and an attacker cannot force it with
carefully crafted messages. In practice, such a code path will not
be triggered and thus can be implemented with little optimization.
3.5. Rationale
The process described in the previous sections mimics the "Approved"
generation process of k described in Annex D of [X9.62], with the
"HMAC_DRBG" pseudorandom number generator. The main difference is
that we use the concatenation of the private key x and the hashed message H(m) as the pseudorandom number generator (PRNG) seed. If using a "security level" of n bits, then HMAC_DRBG should be used with seed entropy at least n+64 bits; however, the key x should also have been generated with that much entropy, and the length of x is qlen, which is at least equal to 2*n and thus larger than n+64 (DSA and ECDSA, as specified by the standards, require qlen >= 160). It can then be argued that deterministic ECDSA fulfills the entropy requirements of Annex D of [X9.62]. We use bits2octets(H(m)) instead of H(m) in order to ease integration. Indeed, many existing signature systems offload the message hashing; the signature engine (which has access to the private key) receives only H(m). In some applications, where data bandwidth is constrained, only the first qlen bits of H(m) are transferred to the signature engine, on the basis that the bits2int transform will ignore subsequent bits anyway. Possibly, in some systems, the truncated H(m) could be externally reduced modulo q, since that is the first thing that (EC)DSA performs on the hashed message. With the definition of bits2octets, deterministic (EC)DSA can be applied with the same input.3.6. Variants
Many parts of the specification of deterministic (EC)DSA are quite arbitrary. It is possible to define variants that are NOT "deterministic (EC)DSA" but that may nonetheless be useful in some contexts: o It is possible to use H(m) directly, instead of bits2octets(H(m)), as part of the HMAC input. As explained in Section 3.5, we use bits2octets(H(m)) in order to ease integration into systems that already use an (EC)DSA signature engine by sending it an already- truncated hash value. Using the whole H(m) does not introduce any vulnerability. o Additional data may be added to the input of HMAC, concatenated after bits2octets(H(m)): K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k') A use case may be a protocol that requires a non-deterministic signature algorithm on a system that does not have access to a high-quality random source. It suffices that the additional data k' is non-repeating (e.g., a signature counter or a monotonic clock) to ensure "random-looking" signatures are indistinguishable, in a cryptographic way, from plain (EC)DSA signatures. In [SP800-90A] terminology, k' is the "additional
input" that can be set as a parameter when generating pseudorandom
bits. This variant can be thought of as a "strengthening" of the
randomness of the source of the additional data k'.
o Instead of using x (the private key) as input to HMAC, it is
possible to use additional secret data, stored along with the
private key with the same security measures. The entropy of that
additional data SHALL be at least n bits, preferably n+64 bits or
more, where n is the target security level. Having additional
secret data may help in formally proving the security of
derandomization, but it implies an extra storage cost and
incompatibility with already-generated (EC)DSA private keys.
o Similarly, the private key could be a value z, from which both x
(the "private key" in the plain (EC)DSA sense) and another value
x', to be used as input to HMAC in the generation of k, would be
derived through a suitable Pseudorandom Function (PRF) (such as
HMAC_DRBG). This would keep private key storage requirements to a
minimum while providing a more easily proven security, but it
would impact private key generation and would not be compatible
with already-generated key pairs.
o In this document, we use the same hash function H for processing
the input message and as a parameter to HMAC. Two distinct hash
functions could be used, provided that both are adequately secure.
The overall security will be limited by the weaker of the two hash
functions, i.e., the one with the smaller output. Using a
specific, constant hash function for HMAC may be useful for
constrained implementations that accept externally hashed
messages, regardless of what hash function was used for that, but
have resources for implementing only one hash function for HMAC.
The main disadvantage of any variant is that it ceases to be
verifiable against the test vectors published in this document.
4. Security Considerations
Proper implementation and usage of a cryptographic signature
algorithm require taking into account many parameters. In
particular, private key generation, storage, access control, and
disposal are sensitive operations, which this document does not
address in any way. Deterministic (EC)DSA shows how to achieve the
security characteristics of a standard DSA or ECDSA signature scheme
while removing the need for a source of strong randomness, or even
any source of randomness, during signature generation.
Private key generation, however, absolutely requires such a strongly random source. In situations where deterministic (EC)DSA is to be used due to the lack of an appropriate source of randomness, one must assume that the private key has been generated externally and imported into the signature generation system or was generated in a context where randomness was available. For instance, one can imagine a smartcard that generates its private key while still in the factory under controlled environmental conditions, but for which random data generation cannot be guaranteed once deployed in the field, when physically in the hands of potential attackers. Both removal of the random source requirement and the ability to test an implementation against test vectors enhance security of DSA and ECDSA signer implementations, in that they help avoid hard-to-test failure conditions. 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. As a rule of thumb, deterministic DSA or ECDSA can be used in lieu of the genuine DSA or ECDSA, with no additional security issues, if the overall protocol would tolerate another deterministic signature scheme, in particular RSA as specified in PKCS #1 [RFC3447] (with "type 1" padding, not PSS) or ISO 9796-2 [ISO-9796-2]. The list of protocols in which deterministic DSA or ECDSA is appropriate includes Transport Layer Security (TLS) [RFC5246], the Secure SHell (SSH) Protocol [RFC4251], Cryptographic Message Syntax (CMS) [RFC5652] and derivatives, X.509 public key infrastructures [RFC5280], and many others. The construction described in this document is known as a "derandomization". This has been proposed for various signature schemes. 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 (Pseudorandom Function). For details on the security of HMAC and HMAC_DRBG, please refer to [H2008] and [B2006]. For a more formal treatment of derandomization, see [LN2009]. One remaining issue with deterministic (EC)DSA, as presented in this document, is the "double use" of the private key x, both as the private key in the signature generation algorithm itself and as input to the HMAC_DRBG-based pseudorandom 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 logarithms, this seems a reasonable assumption. Side-channel attacks are an important consideration whenever an attacker can accurately measure aspects of an implementation such as the length of time that it takes to perform a signing operation or the power consumed at each point of a signing operation. The determinism of the algorithms described in this note may be useful to an attacker in some forms of side-channel attacks, so implementations SHOULD use defensive measures to avoid leaking the private key through a side channel.5. Intellectual Property Status
To the best of our knowledge, deterministic (EC)DSA is not covered by any active patent. The paper [BDLSY2011] points to two independent publications of the idea of derandomization by Barwood and Wigley, both in early 1997, and also to a patent application by Naccache, M'Raihi, and Levy-dit-Vehel a few months later [NML1997], but the application was withdrawn in 2003. We are not aware of any other patent on the subject.
(page 17 continued on part 2)
