Introduction

If you have a public and private key, chances are you’re using ECDSA signatures for every transaction you execute. But do you know how to protect yourself from the vulnerabilities this mechanism has?

In this blog post, we want to explain how the ECDSA mechanism works, its vulnerabilities, and what you should be wary of when signing messages with your private key.

You can skip to the last chapter if you just want the spicy stories about ECDSA failing. But we strongly suggest you grab a coffee (and maybe a pen and paper) and come with us as we take you step-by-step through how ECDSA works. By the end, you’ll understand one of the most fundamental mechanisms in crypto, and you’ll be able to spot attacks before they can affect you. Are you ready? Let’s begin.

What are ECDSA signatures, and how do they work?

ECDSA stands for Elliptic Curve Digital Signature Algorithm. That might be a bit of a mouthful, so let’s break it down:

• Algorithm means a set of steps that you can repeat again and again for consistent results.

• Digital Signature means that it is used to confirm a signer has approved a message.

Just like a signature on a document verifies the signer agreed to the clauses, a digital signature confirms that the signer has agreed to some message.

• Elliptic curve means that the calculations are done using structures called elliptic curves.

This allows fast calculations in one direction and practically impossible in the other direction. We’ll explain a bit more about how they work a bit later.

Why do we use ECDSA?

ECDSA has been proven to be a very secure mechanism if correctly used (foreshadowing) while remaining efficient. There’s no point in having the most secure encryption if it takes you three days actually to encrypt the message.

How do elliptical curve calculations work?

You have a secret number called your private key (d_A). There is a publicly used shape, known as the elliptic curve, and a point on that elliptic curve called the Generator point (G).

You use a specific method to take the Generator point and “multiply” it with your secret number. The result of that “multiplication” is a point on the elliptic curve (Q_A = d_A * G), which you use as your public key.

Multiplication here means something slightly different than what you’re used to, so let’s explain that;

On an elliptic curve, when you draw a line between two points, you’ll always intersect the curve at one additional point. The “mirror image” of that intersection is considered the sum of those two points.

If you take one point and add it to itself, you’ll find a point which is considered P + P, so 2 * P. Sum that new point with the original P, and you got 2 * P + P, et voilà, 3 * P. Rinse and repeat to get any n * P you want.

Extra credit: You might wonder how you calculate 2 * P if you’re trying to draw a line through one point. In that case, you draw a line tangential to the curve, which will only intersect the curve at point P and one other point, which we’ll mirror to get P + P = 2P

If you’re confused, here’s a gif that shows how to add a point P to its sum five times to calculate a point which is considered 6 * P

One additional step in this process is that these calculations are not done in a continuous space like in the image above. But in a discrete space, every time you calculate a sum, you actually use the modulo of that number. Think about how clocks wrap around from 12 back to 1; that’s effectively a modulo of 12. Elliptic-curve cryptography does the same thing but with a huge prime number. This number is called the “order” of the curve (n).

Why is this so complicated? Because in the end, if I give you one point Q_A you know nothing about, you have no chance of calculating with which number I multiplied G to get it. And the numbers used for these multiplications are enormous. Your only option is to start trying numbers randomly until you get the number. I hope you have a lot of free time if you wanna try and guess it.

Hopefully, now you understand that if we write Q_A = d_A * G, it means that you can’t crack that equation by calculating d_A = Q_A / G. So you cannot divide elliptic curve points. But you can divide numbers. So you could calculate a d^-1, which would have the following property:

 d * d^-1 = 1

Now that we know how all this math works, let’s see how it’s used before we can find out how it can be abused.

How ECDSA works:

In this section, we’ll explain how ECDSA uses all this arithmetic to generate and verify signatures.

Generating a signature:

Note: This is a simplified explanation of the process. We won’t get into many more technical details because they’re irrelevant to the main points we want to explain.

Before we start calculating, let’s list the things we (as the message signer) know:

1. Our message, represented as the number z
2. A publicly known generator point G
3. Our private key d_A and its corresponding public key Q_A = d_A * G

We generate a signature for a message z by following these four steps:

1. Generate a random number, k.
2. Calculate a point from that number, called R ( R = k * G )
3. Extract the x coordinate of the point R, called r
4. Calculate s with the following formula s = k^-1 * ( z + r * d_A)

The pair of numbers (r,s) is considered our signature for the message z.

Verifying a signature

Now that we’ve generated a signature for a message, a verifier has to check that the signature is valid. Let’s see how that part is executed.

Before we start calculating, let’s list what a message verifier would know:

1. The original message, represented as the number z
2. A publicly known generator point G
3. The signer’s public key point, Q_A
4. The signature value pair of numbers (r, s). With r, we can determine the random point R

When we have all of these values, we verify that the signature came from the signer by using the following calculations:

1. Calculate number u₁ as u₁ = -z * r^-1
2. Calculate number u2 as u2 = s * r^-1
3. If u₁*G + u₂*R is equal to Q_A, the signature is valid

This seems super simple, but we don’t know why it works. Let’s see how and why it works by expanding the calculation from the last step.

1. Let’s expand u₁ and u₂:
   
   -z* r^-1 * G  +  s* r^-1 * R
   
2. We know that R is calculated as k * G, so we have:
   
   -z * r^-1 * G  +  s * r^-1 * k * G
   
3. Since multiplication is distributive, we can extract G from the equation:
   
   [-z* r^-1 + s * k * r^-1] * G
   
4. Now we expand on s from its original form, k^-1 * (z + r * d_A):
   
   [-z* r^-1 + r^-1 * k * k^-1 * (z + r * d_A) ] * G
   
5. Since we’re multiplying k with k^-1, we can eliminate that, leaving:
   
   [-z * r^-1 + r^-1 * (z + r * d_A) ] * G
   
6. Similarly, if we multiply the (z + r*d_A) expression with r^-1, we would get z* r^-1 + d_A, since r * r^-1 cancels out, resulting in:
   
   [-z* r^-1 + z * r^-1 + d_A] * G

7. Now the two opposite expressions eliminate each other, and we are left with:
   
   d_A * G

And this is the public address point of the signer. If it matches the signer we expect the signature from, then we consider it valid.

If you’ve made it this far, congrats; you just levelled up! You now understand how one of the most foundational signing mechanisms in crypto actually works. While we can’t upload knowledge into your brain, if you get this, you’re leagues ahead of most in understanding crypto and its underlying technology.

When ECDSA signatures fail

Now that you know how signatures work, we’ll show you how these signatures can fail and what can happen when they do.

Not using an actually random value for the signature

A significant factor in guaranteeing the safety of this algorithm is ensuring what verifiers know and what’s supposed to stay private. One important thing that the verifier should not know is the random value k that we use to generate the signature. But what’s also important is that that value is unique for every signature.

If you use the same value k for even one additional message, it could result in your private key getting revealed to an attacker.

This is what happened to multiple bitcoin wallets in 2013 when a library that was used to generate random values would generate the same value multiple times. This allowed private keys to be stolen for Bitcoin Wallet, blockchain.info, BitcoinSpinner, Mycelium wallet, and others. You can read more about it in this blog post.

A more popular attack with the same root issue was Sony using the same “random” value for all of their digital signatures. This allowed hackers to retrieve the private key used for signing code with Sony’s trusted private key, enabling any code to be loaded as officially verified. Let’s just say that was not the smartest move…

While this type of exploit is relatively uncommon nowadays, it highlights why developers should be extra careful when using a library for generating random numbers. If you’re a regular user, it serves as a reminder to only use apps with reliable track records. Ones you don’t think would be that careless to make this mistake.

Signing unsalted messages

Not using the same random value is an exploit that a developer needs to secure the users from. But signing unsalted messages is something you, as a user, might fall victim to and should know about.

The ECDSA mechanism is used for signing all kinds of messages. For us, what’s most important is that they can be used to sign transactions. When you send a transaction on the blockchain, you use your private key to verify that you agree that a particular transaction should be executed.

When using your private key to confirm something other than a transaction, most tools use something called a salt. It’s essentially just a prefix that adds a set of characters. This set of characters is added to a message you would be signing to ensure that you aren’t accidentally signing a transaction. For example, on Ethereum, it’s “\x19Ethereum Signed Message:\n” plus the length of the message.

However, some tools still allow signing without salting the message (for legacy compatibility purposes), which enables phishing attacks. You might be prompted to sign a message to confirm your wallet, but you would actually be signing a transaction that sends all of your funds to an attacker. For example, when you saw this prompt, would you know that you might be signing a transaction:

As you can see, one of the most prominent tools which still enables unsalted message signatures is Metamask. While it does provide a large warning message, a transaction in a raw format is just a string of hexadecimal values. So it could trick you into signing transactions without you knowing.

So if you receive a warning message on Metamask like the one above, be extremely careful and proceed only if you really know what you’re doing.

Oh, and definitely don’t sign stuff like this:

Conclusion

To recap, let’s look at what we’ve covered:

• We dipped into how elliptic curve cryptography works
• We learned how ECDSA actually calculates and verifies signatures
• We found out about possible exploits of ECDSA

While there’s a LOT more about ECDSA, we hope you have a fundamental understanding of how it works and how to stay safe when using it. 

If you have any thoughts or questions about this topic, let us know on our Discord server, and we’d be happy to talk more about it.