Deterministic ECDSA and EdDSA Signatures with Additional Randomness
draft-mattsson-cfrg-det-sigs-with-noise-01

Abstract

Deterministic elliptic-curve signatures such as deterministic ECDSA and EdDSA have gained popularity over randomized ECDSA as their security do not depend on a source of high-quality randomness. Recent research has however found that implementations of these signature algorithms may be vulnerable to certain side-channel and fault injection attacks due to their determinism. One countermeasure to such attacks is to re-add randomness to the otherwise deterministic calculation of the per-message secret number. This document updates RFC 6979 and RFC 8032 to recommend constructions with additional randomness for deployments where side-channel attacks and fault injection attacks are a concern.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on September 10, 2020.

Copyright Notice

Copyright (c) 2020 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 (https://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. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

• 1. Introduction
• 2. Updates to RFC 8032 (EdDSA)
• 3. Updates to RFC 6979 (Deterministic ECDSA)
• 4. Security Considerations
• 5. TODOs and Other Considerations
• 6. References
• 6.1. Normative References
• 6.2. Informative References
• Acknowledgments
• Authors' Addresses

1. Introduction

In Elliptic-Curve Cryptography (ECC) signature algorithms, the per-message secret number has traditionally been generated from a random number generator (RNG). The security of such algorithms depends on the cryptographic quality of the random number generation and biases in the randomness may have catastrophic effects such as compromising private keys. Repeated per-message secret numbers have caused several severe security accidents in practice. As stated in [RFC6979], the need for a cryptographically secure source of randomness is also a hindrance to deployment of randomized ECDSA [FIPS-186-4] in architectures where secure random number generation is challenging, in particular, embedded IoT systems and smartcards. [ABFJLM17] does however state that smartcards typically has a high-quality RNG on board, which makes it significantly easier and faster to use the RNG instead of doing a hash computation.

In deterministic ECC signatures schemes such as Deterministic Elliptic Curve Digital Signature Algorithm (ECDSA) [RFC6979] and Edwards-curve Digital Signature Algorithm (EdDSA) [RFC8032], the per-message secret number is instead generated in a fully-deterministic way as a function of the message and the private key. Except for key generation, the security of such deterministic signatures does not depend on a source of high-quality randomness. As they are presumed to be safer, deterministic signatures have gained popularity and are referenced and recommended by a large number of recent RFCs [RFC8037] [RFC8080] [RFC8152] [RFC8225] [RFC8387] [RFC8410] [RFC8411] [RFC8419] [RFC8420] [RFC8422] [RFC8446] [RFC8463] [RFC8550] [RFC8591] [RFC8624] [RFC8208] [RFC8608].

Side-channel attacks are potential attack vectors for implementations of cryptographic algorithms. Side-Channel attacks can in general be classified along three orthogonal axes: passive vs. active, physical vs. logical, and local vs. remote [SideChannel]. It has been demonstrated how side-channel attacks such as power analysis [BCPST14] and timing attacks [Minerva19] [TPM-Fail19] allow for practical recovery of the private key in some existing implementations of randomized ECDSA. [BSI] summarizes minimum requirements for evaluating side-channel attacks of elliptic curve implementations and writes that deterministic ECDSA and EdDSA requires extra care. The deterministic ECDSA specification [RFC6979] notes that the deterministic generation of per-message secret numbers may be useful to an attacker in some forms of side-channel attacks and as stated in [Minerva19], deterministic signatures like [RFC6979] and [RFC8032] might help an attacker to reduce the noise in the side-channel when the same message it signed multiple times. Recent research [SH16] [BP16] [RP17] [ABFJLM17] [SBBDS17] [PSSLR17] [SB18] [WPB19] [AOTZ19] [FG19] have theoretically and experimentally analyzed the resistance of deterministic ECC signature algorithms against side-channel and fault injection attacks. The conclusions are that deterministic signature algorithms have theoretical weaknesses against certain instances of these types of attacks and that the attacks are practically feasibly in some environments. These types of attacks may be of particular concern for hardware implementations such as embedded IoT devices and smartcards where the adversary can be assumed to have access to the device to induce faults and measure its side-channels such as timing information with low signal-to-noise ratio, power consumption, electromagnetic leaks, or sound. Fault attacks may also be possible without physical access to the device. RowHammer [RowHammer14] showed how an attacker to induce DRAM bit-flips in memory areas the attacker should not have access to and Plundervolt [Plundervolt19] showed how an attacker with root access can use frequency and voltage scaling interfaces to induce faults that bypasses even secure execution technologies. RowHammer can e.g. be used in operating systems with several processes or cloud scenarios with virtualized servers. Protocols like TLS, SSH, and IKEv2 that adds a random number to the message to be signed mitigate some types of attacks [PSSLR17].

Government agencies are clearly concerned about these attacks. In [Notice-186-5] and [Draft-186-5], NIST warns about side-channel and fault injection attacks, but states that deterministic ECDSA may be desirable for devices that lack good randomness. BSI has published [BSI] and researchers from BSI have co-authored two research papers [ABFJLM17] [PSSLR17] on attacks on deterministic signatures. For many industries it is important to be compliant with both RFCs and government publications, alignment between IETF, NIST, and BSI recommendations would be preferable.

One countermeasure to side-channel and fault injection attacks recommended by [RP17] [ABFJLM17] [SBBDS17] [PSSLR17] [SB18] [AOTZ19] [FG19] and implemented in [XEdDSA] [libSodium] [libHydrogen] is to re-introduce some additional randomness to the otherwise deterministic generation of the per-message secret number. This combines the security benefits of fully-randomized per-message secret numbers with the security benefits of fully-deterministic secret numbers. Such a construction protects against key compromise due to weak random number generation, but still effectively prevents many side-channel and fault injection attacks that exploit determinism. Deterministic ECDSA with additional randomness can be made compliant with [FIPS-186-4] but would not be compliant with the recommendations in many RFCs. Adding randomness to EdDSA is not compliant with [RFC8032].

This document updates [RFC6979] and [RFC8032] to recommend constructions with additional randomness for deployments where side-channel and fault injection attacks are a concern. Produced signatures remain fully compatible with unmodified ECDSA and EdDSA verifiers and existing key pairs can continue to be used. As the precise use of the noise is specified, test vectors can still be produced and implementations can be tested against them.

2. Updates to RFC 8032 (EdDSA)

For Ed25519ph, Ed25519ctx, and Ed25519: In deployments where side-channel and fault injection attacks are a concern, the following step is RECOMMENDED instead of step (2) in Section 5.1.6 of [RFC8032]:

   2.  Compute SHA-512(dom2(F, C) || Z || prefix || PH(M)), where M
       is the message to be signed, Z is 32 octets of random data.
       Interpret the 64-octet digest as a little-endian integer r.

For Ed448ph and Ed448: In deployments where side-channel and fault injection attacks are a concern, the following step is RECOMMENDED instead of step (2) in Section 5.3.6 of [RFC8032]:

   2.  Compute SHAKE256(dom4(F, C) || Z || prefix || PH(M), 114),
       where M is the message to be signed, and Z is 57 octets of
       random data, F is 1 for Ed448ph, 0 for Ed448, and C is the
       context to use. Interpret the 114-octet digest as a
       little-endian integer r.

3. Updates to RFC 6979 (Deterministic ECDSA)

For Deterministic ECDSA: In existing ECDSA deployments where side-channel and fault injection attacks are a concern, the following steps is RECOMMENDED instead of steps (d) and (f) in Section 3.2 of [RFC6979]:

  d.  Set:

      K = HMAC_K(V || 0x00 || Z || 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, random data Z (of the same length as int2octets(x)), 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).

  f.  Set:

      K = HMAC_K(V || 0x01 || Z || int2octets(x) || bits2octets(h1))

In new deployments, EdDSA with additional randomness as specified in Section 2 is RECOMMENDED.

4. Security Considerations

The constructions in this document follows the high-level approach in [XEdDSA] to calculate the per-message secret number from the hash of the private key and the message, but add random additional randomness into the calculation for greater resilience. This does not re-introduce the strong security requirement of randomness needed by randomized ECDSA [FIPS-186-4]. The randomness of Z does not need to be perfect, but SHALL be generated a cryptographically secure pseudo random number generator (PRNG) and SHALL be secret. Even if the same random number Z is used to sign two different messages, the security will be the same as deterministic ECDSA and EdDSA and an attacker will not be able to compromise the private key with algebraic means as in fully-randomized ECDSA [FIPS-186-4]. With the construction specified in this document, two signatures over two equal messages are different which prevents information leakage in use cases where signatures but not messages are public.

[SBBDS17] states that [XEdDSA] would not prevent their attack due to insufficient mixing of the hashed private key with the additional randomness. [SBBDS17] suggest a construction where the randomness is padded with zeroes so that the first 1024-bit SHA-512 block is composed only of the hashed private key and the random value, but not the message. This solution does however increase the number of hash function invocations and the amount of padding is dependent on the block size.

Another countermeasure to fault attacks is to force the signer to verify the signature in the last step of the signature generation or to calculate the signature twice and compare the results. These countermeasure would catch a single fault but would not protect against attackers that are able to precisely inject faults several times [RP17] [PSSLR17] [SB18]. Adding an additional sign or verification operation would also significantly affect performance, especially verification which is a heavier operation than signing in ECDSA and EdDSA.

[ABFJLM17] suggests using both additional randomness and a counter, which makes the signature generation stateful. While most used signatures have traditionally been stateless, stateful signatures like XMSS [RFC8391] and LMS [RFC8554] have now been standardized and deployed. [I-D.irtf-cfrg-randomness-improvements] specifies a PRNG construction with a random seed, a secret key, a context string, and a nonce, which makes the random number generation stateful. The generation of the per-message secret number in this document is not stateful, but it can be used with a stateful PRNG. The exact construction in [I-D.irtf-cfrg-randomness-improvements] is however not recommended in deployments where side-channel and fault injection attacks are a concern as it relies on deterministic signatures.

With the construction in this document, the repetition of the same per-message secret number for two different messages is highly unlikely even with an imperfect random number generator, but not impossible. As an extreme countermeasure, previously used secret numbers can be tracked to ensure their uniqueness for a given key, and a different random number can be used if a collision is detected. This document does not mandate nor stop an implementation from taking such a precaution.

Implementations need to follow best practices on how to protect against all side-channel attacks, not just attacks that exploits determinism, see for example [BSI].

5. TODOs and Other Considerations

• EdDSA hedge construction - It should be discussed what the best construction is for achieving protection against fault and side-channel attacks, simplicity and ease of implementation, as well as efficiency. For reference the construction in [XEdDSA] is
  
  SHA-512(dom2(F, C) || prefix || PH(M) || Z)
  
  where Z is 64 octets of random data. The construction suggested in [SBBDS17] is
  
  SHA-512(dom2(F, C) || prefix || 000… || Z || PH(M))
  
  where the number of zeroes is chosen so that the first 1024-bit block is composed only of the hashed private key and the random value, but not the message. E.g. 80 bytes of zeroes and 16 octets of random data. There might be reasons to have different constructions for Ed25519 (SHA-512) and Ed448 (SHAKE256).
• ECDSA hedge construction - The current construction for ECDSA is modelled after the construction for EdDSA. There might be reasons to have different constructions for EdDSA and deterministic ECDSA as ECDSA can be used with any hash function (e.g. SHA-2 or SHAKE) and the construction in [RFC6979] uses HMAC. NIST is planning to approve SHAKE for use in ECDSA [Draft-186-5]. Deterministic ECDSA would then use HMAC-SHAKE instead of the more optimal KMAC, but it is not clear if an update is worth doing, or if people should be adviced to move to EdDSA instead. But, even if EdDSA is superior to ECDSA, ECDSA is widely deployed and will be used for a long time. Small changes that are compatible with existing signature verification implementations are worth doing.
• Amount of randomness - The current construction uses 32 bytes of randomness for Ed25519. XEdDSA uses 64 bytes of randomness which might be overkill. As discussed in [SBBDS17], the amount of randomness needed depends on the targeted security level. 32 bytes of randomness should be enough for Ed448 and 16 bytes of randomness should be enough for Ed25519. Even less than that is likely sufficient to prevent practical attacks.
• EdDSA hash algorithm - For protection against side-channel attacks, the use of SHA-512 may not be optimal. [SBBDS17] states that protection against side-channel attacks would be easier and more robust with a hash function like SHAKE128, but this may not matter when randomness is added. The use of SHA-512 in Ed25519 is suitable for software implementations in web servers and may not be optimal for embedded IoT devices and smart cards as it likely requires them to implement one more cryptographic hash algorithms. If CFRG decides to do an update to RFC 8032 addressing IoT devices vulnerable to fault injection and side-channel attacks it should be considered if other changes should be made as well. Currently, most embedded IoT devices implements SHA-256, but in the future they may implement a sponge function like Keccak or Gimli and use that to construct XOF, PRF, and AEAD. Ed25519 with Keccak is discussed in [I-D.moskowitz-small-crypto] and Ed25519 with Gimli is implemented in [libHydrogen]. NIST is planning to approve SHAKE for use in ECDSA [Draft-186-5]. Using a XOF like
  
  SHAKE128(…, 64)
  
  instead of SHA-512 in Ed25519 would be straightforward, while using SHA-256 would require more invocations of the hash function like
  
  SHA-256(… || 0x00) || SHA-256(… || 0x01)

6. References

6.1. Normative References

6.2. Informative References

Acknowledgments

The authors want to thank TBD for their valuable comments and feedback.

Authors' Addresses