4. Security Considerations

Proper implementation and usage of a cryptographic signature algorithm require taking into account many parameters. In particular, private key generation, storage, access control, and disposal are sensitive operations, which this document does not address in any way. Deterministic (EC)DSA shows how to achieve the security characteristics of a standard DSA or ECDSA signature scheme while removing the need for a source of strong randomness, or even any source of randomness, during signature generation.

Private key generation, however, absolutely requires such a strongly random source. In situations where deterministic (EC)DSA is to be used due to the lack of an appropriate source of randomness, one must assume that the private key has been generated externally and imported into the signature generation system or was generated in a context where randomness was available. For instance, one can imagine a smartcard that generates its private key while still in the factory under controlled environmental conditions, but for which random data generation cannot be guaranteed once deployed in the field, when physically in the hands of potential attackers.

Both removal of the random source requirement and the ability to test an implementation against test vectors enhance security of DSA and ECDSA signer implementations, in that they help avoid hard-to-test failure conditions. Deterministic signature schemes may also help in other situations, e.g., to avoid spurious duplicates, when the same data element is signed several times with the same key: with a deterministic signature scheme, the same signature is generated every time, making duplicate detection much easier.

Conversely, lack of randomization may have adverse effects in some advanced protocols, e.g., related to anonymity in some voting schemes. As a rule of thumb, deterministic DSA or ECDSA can be used in lieu of the genuine DSA or ECDSA, with no additional security issues, if the overall protocol would tolerate another deterministic signature scheme, in particular RSA as specified in PKCS #1 [RFC3447] (with "type 1" padding, not PSS) or ISO 9796-2 [ISO-9796-2]. The list of protocols in which deterministic DSA or ECDSA is appropriate includes Transport Layer Security (TLS) [RFC5246], the Secure SHell (SSH) Protocol [RFC4251], Cryptographic Message Syntax (CMS) [RFC5652] and derivatives, X.509 public key infrastructures [RFC5280], and many others.

The construction described in this document is known as a "derandomization". This has been proposed for various signature schemes. Security relies on whether the generation of k is indistinguishable from the output of a random oracle. Roughly speaking, HMAC_DRBG is secure in that role as long as HMAC behaves as a PRF (Pseudorandom Function). For details on the security of HMAC and HMAC_DRBG, please refer to [H2008] and [B2006]. For a more formal treatment of derandomization, see [LN2009].

One remaining issue with deterministic (EC)DSA, as presented in this document, is the "double use" of the private key x, both as the private key in the signature generation algorithm itself and as input to the HMAC_DRBG-based pseudorandom oracle for producing the k value. This requires HMAC_DRBG to keep on being a random oracle, even when the public key (which is computed from x) is also known. Given the lack of common structure between HMAC and discrete logarithms, this seems a reasonable assumption.

Side-channel attacks are an important consideration whenever an attacker can accurately measure aspects of an implementation such as the length of time that it takes to perform a signing operation or the power consumed at each point of a signing operation. The determinism of the algorithms described in this note may be useful to an attacker in some forms of side-channel attacks, so implementations SHOULD use defensive measures to avoid leaking the private key through a side channel.