Both the ECDSA and DSA signature algorithms are known to have a problematic feature: during the signature generation, they require the generation of a random value k. If the same value of k ever is used in two signing processes for the same private key, or k can be predicted to some extent, then an attacker gains sufficient information to recover the private key. One prominent and rather recent failure where this design flaw in conjunction with an entropy problem in the random number generator lead to an actual exploitation was in the context of a Bit Coin App on Android platforms. Already about 20 years ago this shortcoming of these standards has lead to critizism and to two types of reactions: ad hoc countermeasures and a new standard. In the following we will only speak of ECDSA, which is much more widely used today than DSA, but note that all the following equally applies to DSA.

ad hoc countermeasures

The straightforward countermeasure is to use the values available during signature creation to ensure that k is both unique and unpredictable. Obviously, this measure is so straightforward that it was reinvented a number of times, as Daniel Bernstein summarizes. The solution is to use both the private ECDSA key and the message (or a hash of it) to seed a (pseudo) random number generator, which is then used to produce k. The ECDSA private key is a high entropy secret, and thus brings the random number generator into a state which an attacker cannot guess, even given the total absence of any other entropy source. But it alone does not suffice, since then for repeated signature generation, still the same value of k could be generated, causing disclosure of the private ECDSA key as explained above. For this reason, also the message needs to be used to seed the random number generator. As a result, the signature generation routine will produce different values of k for different messages.

a new standard

The second reaction is the standard of deterministic ECDSA laid down in RFC 6979. It basically boils down to the previous countermeasure, where it is specified that k is to be derived purely based on the deterministic seed input values to the random number generator (which must thus be a pseudo random number generator, i.e. not collect any additional external entropy). The algorithm is deterministic in the sense that if the same message is signed twice, it will output the same signature for both messages. There is nothing wrong with this approach, deterministic signatures are in fact something that we are used to from RSA PKCS#1 v1.5 signatures. They have the advantage of being able to be tested by test vectors which contain expected values for signatures, which is not the case for classic ECDSA.

Confronted with the problem of how to hedge ECDSA signature generation in a given implementation against a low-entropy state of the employed random number generator, from the above we might conclude that it is actually straightforward to implement one of the two countermeasures.

However, things are not quite so simple. In itself, there is no problem with deterministic ECDSA according to RFC 6979, but if we silently replace a classical ECDSA implementation with a deterministic one, we take the risk of subverting schemes which build on the probabilistic nature of classical ECDSA. One example would be a scheme where ECDSA signatures are published without the signed message (which must be of high entropy for this example to make sense) to function as a commitment to a message which might be revealed later. With ECDSA, the same message signed twice by the same user will lead to different signatures. With deterministic ECDSA, the information that a user committed himself to the same message multiple times would be leaked. Of course that is a rather contrived example, but it shows us the principal possibility that this approach may lead to problems. There may be other uses we cannot think of right now where the difference between classical and deterministic ECDSA matters.

The same considerations apply to some proposed approaches for ad hoc countermeasures, since they also drop the random inputs to the generation of k.

Having understood that we should avoid rendering ECDSA deterministic where users expect classical ECDSA, it is basically straightforward to specify how to actually achieve an implementation with optimal security with respect to the generation of k: We have to combine the classical approach of using a random number generator, but make sure that in case of its failure due to being in a low entropy state, k is still unpredictable and unique for each signature.

This approach again provides the possibility of making a suboptimal choice. Namely, to seed the default random number generator used by the legacy ECDSA implementation we are about to fix, which is typically a global object maintained by the cryptographic library throughout the program's lifetime, with the message and the ECDSA private key. There are two potential problems.

The first is in relation to the ECDSA private key. If we feed it to the random number generator, it is not necessarily clear that this object handles such sensitive data appropriately. Note that cryptographic libraries often allow the user to choose between different types random number generators, often at runtime. Users might also define their own random number generator implementations and use them for ECDSA. Furthermore, even if the current version of the cryptographic library at hand uses a specific generator, this might change in future versions. As security engineers, it is our task to provide solutions which maintain security with as little assumptions about the environment and circumstance in which they are used as possible. Accordingly, when considering our case, not knowing for sure which concrete random number generator will be used, we have to be prepared to deal with its possible deficiencies. There are random number generators, such as that of OpenSSL, which fail to appropriately "digest" high entropy seed data when they are in a low entropy state. As a result, traces of the ECDSA key might linger in memory for a longer time than necessary, subverting forward security, i.e. the security against future compromise of the system.

The second is in relation to the message. We may be tempted not to consider the message a potential secret. However, it may well be one. If the global random number generator is actually in a low entropy state (i.e. exactly the case which we are hedging against), then feeding the message (or a hash of it) alone, would cause future output of that random number generator to leak the message, given that it is a low entropy message, i.e. all its probable values can be iterated over efficiently in a brute force search. The further feeding of the ECDSA private key prevents the vulnerability in that form, but still leaves a minimal leakage behind: The generator's output now still potentially leaks whether the same message is signed again after a system restart when it gets into the same state before. This potential leakage about the message is clearly a minor problem and rather improbable to manifest itself, but as we see shortly, we can easily do better.

Having explored all wrong paths, we come to the solution which circumvents all the above pitfalls:

• In the ECDSA signature generation routine, instantiate a pseudo random number generator.
• Draw a random seed from the library's default random number generator of at least the bit size of k.
• Seed the pseudo random number generator with the random seed, the message (hash) and the ECDSA private key.
• Generate k using the pseudo random number generator.
• Cleanup the memory used by the random number generator properly (NOT using memset if programming in C).

Note that OpenSSL (I checked version 1.1.0) follows exactly this approach in the function BN_generate_dsa_nonce, but does not get the last point right: the memory allocated on the stack locally in that function for the ECDSA private key is not attempted to be cleaned at all. OpenSSL will fix this lapse in future releases.