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:

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

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

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

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

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