tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search     info

RFC 6979

 Errata 
Informational
Pages: 79
Top     in Index     Prev     Next
in Group Index     Prev in Group     Next in Group     Group: ~sec

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

Part 1 of 3, p. 1 to 17
None       Next RFC Part

 


Top       ToC       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       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       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       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       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       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       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       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       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       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       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       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       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       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       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       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       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 RFC Part