Tech-invite3GPPspaceIETFspace
959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 6979

Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)

Pages: 79
Informational
Errata
Part 1 of 3 – Pages 1 to 17
None   None   Next

Top   ToC   RFC6979 - Page 1
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.
Top   ToC   RFC6979 - Page 2

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
Top   ToC   RFC6979 - Page 3
       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.
Top   ToC   RFC6979 - Page 4
   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.
Top   ToC   RFC6979 - Page 5

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].
Top   ToC   RFC6979 - Page 6
   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 = xG

2.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:
Top   ToC   RFC6979 - Page 7
   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)
Top   ToC   RFC6979 - Page 8
   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.
Top   ToC   RFC6979 - Page 9
   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).
Top   ToC   RFC6979 - Page 10

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.
Top   ToC   RFC6979 - Page 11
   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
Top   ToC   RFC6979 - Page 12
       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.
Top   ToC   RFC6979 - Page 13
       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
Top   ToC   RFC6979 - Page 14
   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
Top   ToC   RFC6979 - Page 15
      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.
Top   ToC   RFC6979 - Page 16
   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
Top   ToC   RFC6979 - Page 17
   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)

Next Section