ECDSA: Handle with Care

The elliptic curve digital signature algorithm (ECDSA) is a common digital signature scheme that we see in many of our code reviews. It has some desirable properties, but can also be very fragile. For example, LadderLeak was published just a couple of weeks ago, which demonstrated the feasibility of key recovery with a side channel attack that reveals less than one bit of the secret nonce.

This post will walk you through:

• the various ways in which ECDSA nonce bias can be exploited
• how simple it is to attack in practice when things go wrong, and
• how to protect yourself.

You’re probably familiar with attacks against ECDSA. Some attacks are trivial, and some involve advanced Fourier analysis and lattice math. Although these attacks can be complicated, I hope this post will demonstrate that they are easy to implement in practice. In fact, even if you don’t know anything about lattices, after reading this blog post you will be able to leverage a lattice attack to break ECDSA signatures produced with a very slightly faulty RNG using less than 100 lines of python code.

Math disclaimer: to read this post, you will need to be somewhat familiar with mathematical groups , recognizing that they have a binary operation and a group generator. You do not need to be an expert on elliptic curves; you just need to know that elliptic curves can be used to form a mathematical group (and, thus, have a concept of addition and scalar multiplication). Familiarity with other math concepts like lattices is helpful, but not required.

DSA primer

ECDSA is a specific form of the digital signature algorithm (DSA). DSA is a pretty common digital signature scheme , and is defined with three algorithms: key generation, signing, and verification. The key generation algorithm generates a private and public key; the private key is responsible for creating signatures; and the public key is responsible for verifying signatures. The signature algorithm takes as input a message and private key, and produces a signature. The verification algorithm takes as input a message, signature, and public key, and returns true or false, indicating whether the signature is valid.

DSA is defined over any mathematical group, and this scheme is secure as long as the discrete log problem is hard over this group. The group typically used is the integers modulo a prime, p . Along with this group, we will have a group generator, g , and some cryptographically secure hash function, H . We can assume that p , g , and H will all be publicly known.

Key generation works by first randomly selecting a value, x , from the integers mod p . Then the value y = g ^x mod p is computed. The private signing key is set to x , and the public key is y . The signing key must be kept secret, as this is what allows signatures to be made.

The signing algorithm produces a signature from a message, m , and the secret key, x . First, a random element of the group, k , is generated. This is known as the nonce , which is important when talking about attacks. Then, the values r = g ^k mod p and s = ( k ^-1 ( H ( m ) + xr )) mod p are computed. Here k ^-1 is the group inverse, and H ( m ) is the result of computing the hash of m and interpreting the result as an integer mod p . The signature is defined to be the pair ( r , s ). (Note: if either of the r or s values equal 0, the algorithm restarts with a new k value).

The verification algorithm receives as input the signature, ( r , s ), the message, m , and the public key, y . Let ŝ = s ^-1 , then the algorithm outputs true if and only if r , s ≠ 0 and r = ( g ^{H ( m )} y ^r ) ^ŝ . This verification check works because g ^{H ( m )} y ^r = g ^{H ( m )+ xr} = g ^ks , and so ( g ^{H ( m )} y ^r ) ^ŝ = g ^k = r .

A digital signature scheme is considered secure if it is unforgeable . Unforgeability has a formal cryptographic meaning, but on a high level it means that you cannot produce signatures without knowing the secret key (unless you have copied an already existing signature created from the secret key). DSA is proven to be unforgeable under the discrete log assumption .

ECDSA

DSA is defined over a mathematical group. When DSA is used with the elliptic curve group as this mathematical group, we call this ECDSA. The elliptic curve group consists of elliptic curve points, which are pairs ( x , y ) that satisfy the equation y ² = x ³ + ax + b , for some a , b . For this blog post, all you need to know is that, using elliptic curves, you can define a finite group, which means you obtain a group generator, g (an elliptic curve point), and addition and scalar multiplication operations just like you can with integers. Since they form a finite group, the generator, g , will have a finite order, p . This blog post will not explain or require you to know how these elliptic curve operations work, but If you’re curious, I encourage you to read more about them here .

ECDSA works the same way as DSA, except with a different group. The secret key, x , will still be a random value from the integers mod p . Now, the public key, y , is still computed as y = g ^x , except now g is an elliptic curve point. This means that y will also be an elliptic curve point (before, y was an integer mod p ). Another difference occurs in how we compute the value r . We still generate a random nonce, k , as an integer mod p , just as before. We will compute g ^k , but again, g is an elliptic curve point, and so g ^k is as well. Therefore, we can compute ( x _k , y _k ) = g ^k , and we set r = x _k . Now, the s value can be computed as before, and we obtain our signature ( r , s ), which will still be integers mod p as before. To verify, we need to adjust for the fact that we’ve computed r slightly differently. So, as before, we compute the value ( g ^{H ( m )} y ^r ) ^ŝ , but now this value is an elliptic curve point, so we take the x-coordinate of this point and compare it against our r value.

Recovering secret keys from reused nonces

Now that we understand what ECDSA is and how it works, let’s demonstrate its fragility. Again, since it’s a digital signature scheme, it is imperative that the secret key is never revealed to anyone other than the message signer. However, if a signer ever releases a signature and also releases the nonce they used, an attacker can immediately recover the secret key. Say I release a signature ( r , s ) for a message m , and I accidentally reveal that I used the nonce k . Since s = ( k ^-1 ( H ( m ) + xr )), we can easily compute the secret key:

s = ( k ^-1 ( H ( m ) + xr ))

ks = H(m) + xr

ks – H(m) = xr

x = r ^-1 ( ks – H ( m ))

Therefore, not only does a signer need to keep their secret key secret, but they also must keep all of their nonces they ever generate secret.

Even if the signer keeps every nonce secret, if they accidentally repeat a single nonce (even for different messages), the secret key can immediately be recovered as well. Let ( r , s ₁ ) and ( r , s ₂ ) be two signatures produced on messages m ₁ and m ₂ (respectively) from the same nonce, k —since they have the same nonce, the r values will be the same, so this is very easily detected by an attacker:

s ₁ = k ^-1 ( H ( m ₁ ) + xr ) and s ₂ = k ^-1 ( H ( m ₂ ) + xr )

s ₁ – s ₂ = k ^-1 ( H ( m ₁ ) – H ( m ₂ ))

k(s ₁ – s ₂ ) = H ( m ₁ ) – H ( m ₂ )

k = ( s ₁ – s ₂ ) ^-1 ( H ( m ₁ ) – H ( m ₂ ))

Once we have recovered the nonce, k , using the formula above, we can then recover the secret key by performing the previously described attack.

Let’s take a moment to digest this.

If a nonce for a signature is ever revealed, the secret key can immediately be recovered, which breaks our entire signature scheme. Further, if two nonces are ever repeated, regardless of what the messages are, an attacker can easily detect this and immediately recover the secret key, again breaking our entire scheme. That is pretty fragile, and these are just the easy attacks!

Attacking ECDSA from leaked and biased nonces

It turns out that even leaking small parts of the nonce can also be very damaging to the signature scheme. In 1999, work by Howgrave-Graham and Smart demonstrated the feasibility of using lattice attacks to break DSA from partial nonce leakage. Later, Nguyen and Shparlinski improved on their work, and were able to recover secret keys on 160-bit DSA (here 160-bit refers to p ), and later ECDSA, by knowing only three bits of each nonce from 100 signatures.

Later, Mulder et al were able to perform more attacks on partial nonce leakage. They used a different, Fourier transform-based attack derived from work by Bleichenbacher. Using these techniques, and knowing only five bits of each nonce from 4,000 signatures, they were able to recover secret keys from 384-bit ECDSA, and leveraged their techniques to break 384-bit ECDSA running on a smart card.

You may have heard of the Minerva attack : Several timing side channels were leveraged to recover partial nonce leakage, and these lattice attacks were performed on a wide variety of targets. With enough signatures, they were able to successfully attack targets even when only the size of the nonce was leaked!

Even worse, a few weeks back, the LadderLeak attack further improved on Fourier analysis attacks, and now ECDSA secret keys can be recovered if only 1 bit of the nonce is leaked! In fact, the single bit can be leaked with probability less than 1, so attackers technically need less than 1 bit. This was leveraged to attack a very small leakage in Montgomery ladders in several OpenSSL versions.

Again, let’s digest this. Even when only a few bits of the nonce are leaked—or further, even if only the size of the nonce is leaked—or further, if one bit of nonce is leaked—then, most of the time, the entire signature scheme can be broken by observing enough signatures. This is incredibly fragile!

On top of this, even if you manage to keep all of your nonces secret and never repeat a nonce, and you never leak any bits of your nonce to an attacker, you still aren’t fully protected! Work by Breitner and Heninger showed that a slightly faulty random number generator (RNG) can also catastrophically break your scheme by leveraging lattice attacks. Specifically, when using 256-bit ECDSA, if your RNG introduces a bias of just 4 bits in your nonce, your signature scheme can be broken completely by a lattice attack, even if we don’t know what those biased values are.

These attacks involve some complicated math. Like most cryptographic attacks, they formulate a series of ECDSA signatures as another hard math problem. In this case, the problem is known as the Hidden Number Problem . The Hidden Number Problem has been fairly widely studied by other researchers, so there are a lot of techniques and algorithms for solving it. This means that once we figure out how to mold a series of ECDSA signatures into an instance of the Hidden Number Problem, we can then apply existing techniques to find an ECDSA secret key.

Breaking ECDSA from bad nonces

Now, Fourier analysis, Hidden Number Problems, and lattice attacks are more complicated than your everyday cryptography, and they seem daunting. However, the fact that these attacks involve complicated math may fool some people into thinking they’re very difficult to implement in practice. This is not the case. As I mentioned in the beginning, I will teach you how to implement these attacks using fewer than 100 lines of Python code. Moreover, to perform this attack, you actually don’t need to know anything about the Hidden Number Problem or lattices. The only lattice component we need is access to the LLL algorithm . However, we can treat this algorithm as a black box; we don’t need to understand how it works or what it is doing.

We’ll be attacking signatures produced from bad nonces (i.e., bad RNG). Specifically, these nonces will have a fixed prefix, meaning their most significant bits are always the same. (The attack still works even if the fixed bits aren’t the most significant bits, but this is the easiest to follow). When using LLL, all we have to know is that we will input a matrix of values, and the algorithm will output a matrix of new values. If we use a series of ECDSA signatures to construct a matrix in a particular way, LLL will output a matrix that will allow us to recover the ECDSA private key. More specifically, because of the way we construct this matrix, one of the rows of the output of LLL will contain all of the signatures’ nonces. (It requires more complicated math to understand why, so we won’t discuss it here, but if you’re curious, see section 4 of this paper ). Once we recover the nonces, we can use the basic attack described above to recover the secret key.

To perform the attack we’ll need access to an ECDSA and an LLL library in python. I chose this ECDSA library , which allows us to input our own nonces (so we can input nonces from bad RNGs to test our attack), and this LLL library . We’ll perform this attack on the NIST P-256 elliptic curve, beginning with the easiest form of the attack: We are given two signatures generated from only 128-bit nonces. First, we generate our signatures.

import ecdsa
import random

gen = ecdsa.NIST256p.generator
order = gen.order()
secret = random.randrange(1,order)

pub_key = ecdsa.ecdsa.Public_key(gen, gen * secret)
priv_key = ecdsa.ecdsa.Private_key(pub_key, secret)

nonce1 = random.randrange(1, 2**127)
nonce2 = random.randrange(1, 2**127)

msg1 = random.randrange(1, order)
msg2 = random.randrange(1, order)

sig1 = priv_key.sign(msg1, nonce1)
sig2 = priv_key.sign(msg2, nonce2)

Now that we have our signatures, we need to craft the matrix we’ll input into the LLL algorithm:

Here N is the order of NIST P-256 (ord in code snippet above), B is the upper bound on the size of our nonces (which will be 2 ¹²⁸ in this example, because both nonces are only 128 bits in size); m ₁ and m ₂ are the two random messages; and (r ₁ , s ₁ ) and (r ₂ ,s ₂ ) are the two signature pairs. In our python code, our matrix will look like this (here modular_inv is a function for computing the inverse mod N):

r1 = sig1.r
s1_inv = modular_inv(sig1.s, order)
r2 = sig2.r
s2_inv = modular_inv(sig2.s, order)

matrix = [[order, 0, 0, 0], [0, order, 0, 0],
[r1*s1_inv, r2*s2_inv, (2**128) / order, 0],
[msg1*s1_inv, msg2*s2_inv, 0, 2**128]]

Now we’ll input this matrix into the black-box LLL algorithm, which will return a new matrix to us. For reasons that don’t matter here, one of the rows of this returned matrix will contain the nonces used to generate the two signatures. If we knew more about what the algorithm is actually doing, we could probably predict where the nonce is going to be. But since we don’t care about the details, we are just going to check every row in the returned matrix to see if we can find the secret key. Remember, we already showed how to recover the private key once we have the nonce, k . Specifically, we compute r ^-1 ( ks – H ( m )). An attacker in the real world would have access to the public key corresponding to these signatures. Therefore, to determine if we have found the correct private key, we will compute its corresponding public key and compare it against the known public key. The attack will look like this:

import olll

new_matrix = olll.reduction(matrix, 0.75)
r1_inv = modular_inv(sig1.r, order)
s1 = sig1.s

for row in new_matrix:
    potential_nonce_1 = row[0]
    potential_priv_key = r1_inv * ((potential_nonce_1 * s1) - msg1)

    # check if we found private key by comparing its public key with actual public key
    if ecdsa.ecdsa.Public_key(gen, gen * potential_priv_key) == pub_key:
        print("found private key!")

I should mention that there is a noticeable failure rate for this basic attack. If you run the code presented to you, you will notice this as well. But again, for the purposes of this post, don’t worry about these specifics. Also, this failure rate should decrease if you perform this same attack with more signatures.

Hopefully at this point I’ve shown why these attacks aren’t so complicated. We were able to recover the secret key from just two signatures, and we didn’t do anything overly complicated. That said, some of you would probably argue that being able to attack signatures with only 128-bit nonces isn’t that interesting. So let’s move on to more realistic attacks.

Exploiting real-world ECDSA bugs

You may have heard of a recent bug in the randomness generated in Yubikeys . Essentially, bad randomness caused as many as 80 bits of the nonce to be fixed to the same value. Attacking this real-world bug will not be much more difficult than the attack we just performed above, except we don’t know what the fixed 80-bit values are (in the previous example, we knew the fixed 128 bits were all set to 0). To overcome this, we need to add a trick to our attack.

Imagine we receive a collection of signatures whose nonces have 80 fixed bits. For ease of explanation, we will assume these 80 bits are the most significant bits (the attack is still feasible if this is not the case; you simply shift the fixed bits to the most significant bits by multiplying each signature by a power of 2). Even though we don’t know what these 80 bits are, we know that if we subtract any two nonces, the 80 most significant bits of their difference will all be zeros. Therefore, we are going to perform the same attack as above, except with our signature values subtracted. Specifically, given a set of n signatures and messages, we will build the following matrix:

This time, we will again input this matrix into LLL and receive a new matrix back. However, since we subtracted the n ^th value from every entry in this matrix, instead of receiving a row full of nonces, we will actually receive a row with the difference between each nonce and the n ^th nonce. In other words, the matrix returned from LLL will give us the value k ₁ – k _n , the difference between the nonces for signatures 1 and n . It takes some algebraic manipulation, but we can still recover the secret key from this value using the following formula:

s ₁ = k ₁ ^-1 ( m ₁ + xr ₁ ) and s _n = k _n ^-1 ( m _n + xr _n )

s ₁ k ₁ = m ₁ + xr ₁ and s _n k _n = m _n + xr _n

k ₁ = s ₁ ^-1 ( m ₁ + xr ₁ ) and k _n = s _n ^-1 ( m _n + xr _n )

k ₁ – k _n = s ₁ ^-1 ( m ₁ + xr ₁ ) – s _n ^-1 ( m _n + xr _n )

s ₁ s _n (k ₁ – k _n ) = s _n ( m ₁ + xr ₁ ) – s ₁ ( m _n + xr _n )

s ₁ s _n (k ₁ – k _n ) = xs _n r ₁ – xs ₁ r _n + s _n m ₁ – s ₁ m _n

x ( s ₁ r _n – s _n r ₁ ) = s _n m ₁ – s ₁ m _n –   s ₁ s _n (k ₁ – k _n )

Secret key = x = (r _n s ₁ – r ₁ s _n ) ^-1 (s _n m ₁ – s ₁ m _n – s ₁ s _n (k ₁ – k _n ))

With all of that context, let’s exploit the Yubikey bug. If signatures are produced from nonces with 80 fixed bits, we only need five signatures to recover the secret key. We will build the matrix above with n = 6 to reduce the error rate:

# generate 80 most significant bits, nonce must be less than order
yubikey_fixed_prefix = random.randrange(2**176, order)

msgs = [random.randrange(1, order) for i in range(6)]
nonces = [random.randrange(1, 2**176) + yubikey_fixed_prefix for i in range(6)]
sigs = [priv_key.sign(msgs[i],nonces[i]) for i in range(6)]

matrix = [[order, 0, 0, 0, 0, 0, 0],
[0, order, 0, 0, 0, 0, 0],
[0, 0, order, 0, 0, 0, 0],
[0, 0, 0, order, 0, 0, 0],
[0, 0, 0, 0, order, 0, 0]]

row, row2 = [], []
[msgn, rn, sn] = [msgs[-1], sigs[-1].r, sigs[-1].s]
rnsn_inv = rn * modular_inv(sn, order)
mnsn_inv = msgn * modular_inv(sn, order)

# 2nd to last row: [r1(s1^-1) - rn(sn^-1), ... , rn-1(sn-1^-1) - rn(sn^-1), 2^176/order, 0 ]
# last row: [m1(s1^-1) - mn(sn^-1), ... , mn-1(sn-1^-1) - mn(sn^-1), 0, 2^176]
for i in range(5):
    row.append((sigs[i].r * modular_inv(sigs[i].s, order)) - rnsn_inv)
    row2.append((msgs[i] * modular_inv(sigs[i].s, order)) - mnsn_inv)

# add last elements of last two rows, B = 2**(256-80) for yubikey
row.append((2**176) / order)
row.append(0)
row2.append(0)
row2.append(2**176)

matrix.append(row)
matrix.append(row2)

new_matrix = olll.reduction(matrix, 0.75)

for row in new_matrix:
    potential_nonce_diff = row[0]

    # Secret key = (rns1 - r1sn)-1 (snm1 - s1mn - s1sn(k1 - kn))
    potential_priv_key = (sn * msgs[0]) - (sigs[0].s * msgn) - (sigs[0].s * sn * potential_nonce_diff)
    potential_priv_key *= modular_inv((rn * sigs[0].s) - (sigs[0].r * sn), order)

    # check if we found private key by comparing its public key with actual public key
    if ecdsa.ecdsa.Public_key(gen, gen * potential_priv_key) == pub_key:
        print("found private key!")

That’s it! We just exploited a real-world bug in about 50 lines of python.

Some might further argue that although this was an actual bug, systems producing 80 fixed bits are rare. However, this attack can be much more powerful than shown in this one example! For 256-bit elliptic curves, this attack will work even if only 4 bits of the nonce are fixed. Moreover, the attack does not become more complicated to implement. You simply need to increase the dimension of your lattice—i.e., in the matrix figure above, just increase the value of n and repeat the attack—nothing else! This will increase the running time of your attack, but not the complexity to implement. You could copy that code snippet and recover ECDSA secret keys generated from nonces with as little as 4 bits of bias. On top of that, the attack against nonce leakage is a similar level of difficulty.

Hopefully, I’ve now convinced you of the fragility of ECDSA and how easily it can be broken in practice when things go wrong.

By the way, some of you may be wondering how we determine the value n . Remember, n is the number of signatures we need to recover the secret key. When the nonce had the first 128 bits fixed to 0, this value was 2 (this value is 3 when 128 bits are fixed, but we don’t know to what value they are fixed). When the nonce had 80 randomly fixed bits, this value was 5. If you consult the relevant publications around these attacks, you can find the exact formula and derivation of this value for a given number of fixed bits. For simplicity, I derived these values empirically by attempting this attack with different numbers of signatures on different amounts of fixed bits. I’ve compiled the results into the figure below:

Protecting your ECDSA signatures

If ECDSA is so fragile, how can users protect themselves? Ideally, we recommend that you use EdDSA instead of ECDSA, which handles nonce generation much more safely by eliminating the use of RNGs. Further, Ed25519, which is EdDSA over Curve25519 , is designed to overcome the side-channel attacks that have targeted ECDSA, and it is currently being standardized by NIST .

If you’re required to use ECDSA, proceed with caution and handle with care! ECDSA is fragile, but it is not broken. As we saw, it is imperative that nonces used for ECDSA signatures are never repeated, never revealed (even partially), and generated safely.

To protect yourself from nonce leakage, the mitigation strategy is to write the implementation to operate in “constant time.” However, guaranteeing this can be very difficult, as we saw with OpenSSL . For instance, code can appear to be constant time, but then an optimizing compiler can introduce non-constant time behavior. Further, some assembly instructions are constant time in some architectures or processor models, but not in others. (Read more about this here ).

Another technique for mitigating nonce leakage is known as blinding , where random numbers are included in your arithmetic to randomize timing information. However, evaluating the security of your blinding implementation can be tricky, and slightly weak blinding schemes can be problematic.

With both of these mitigations, keep in mind that the amount of nonce leakage is on the order of a single bit, so even the slightest changes by an optimizing compiler or the slightest leakage from your blinding technique can be catastrophic to your signature scheme.

To ensure that nonces are generated safely, most people recommend using RFC 6979 , which specifies a way to securely generate nonces deterministically (i.e., without an RNG), using the message and secret key as entropy. This protocol to generate nonces eliminates the problem of bad RNGs, which can be problematic for devices such as Yubikeys where generating randomness securely is difficult. The signature scheme EdDSA actually uses a similar nonce generation method by default to avoid bad RNGs.

If you are using ECDSA in your system, I encourage you to consider all of those recommendations. Hopefully, with enough care, your signature scheme won’t end up like this:

We’re always experimenting and developing tools to help you work faster and smarter. Need help with your next project?Contact us!