Wintermute was hacked for $162M on 20. September 2022. It has been one of the biggest amounts stolen from a single entity, as protocol or bridge hacks are typically spread over multiple users. This hack is extraordinary due to the concurrence of two seemingly unrelated events which only together made the exploit possible. I want to cover both of them in two separate articles starting with the off-chain one.

Introduction - two faults

The first (off-chain) fault occurred several years ago during the implementation of a tool called Profanity which is/was used for generating pretty looking (vanity) ETH addresses. As I discuss later, the space from which the private keys for ETH addresses were generated was absurdly small compared to possible ETH keys space, moreover, a deterministic approach was used to increase the speed of address generation. I will show two different approaches to how the flaw can be abused to retrieve private key of any address generated via this tool.

The second (on-chain) fault occurred shortly after publishing the existence of the first flaw. Wintermute (top tier crypto market maker) was probably using this tool in their market making on-chain setup (including both wallets and smart-contracts), so after publishing the 1inch article, they moved (within a few hours) all funds (a total of 11 ETH) from one of their vanity address somewhere else. But they forgot that this possibly compromisable address is still set as “some kind of admin” for the smart-contract which was responsible for the market making of those (at least) $162M worth of assets. I will show how the attacker probably proceeded, which tools he used and what problems he had to solve.

Off-chain vulnerability

Noticing the existence of Profanity’s vulnerability and moreover developing an attack scheme requires both advanced cryptographic knowledge and a dose of invention. I will try to get you into this process together with all related problems.

Private key, public key, ETH address

To understand where the problem lies is valuable to understand the relation between the private key, public key, and ETH address.

Private key
It all starts with the private key which is just a large integer number, it can be any positive non-zero number up to 2^256. One could use a favorite number (social security number, or credit card number), but I would not recommend it, as the usual numbers in our daily life are not even close to covering all the possibilities of mentioned range. You thought that your private key is a secret phrase you have hidden in your drawer? No, it’s not, the phrase helps us to keep the private key number in some more acceptable form than the original 78 digits string.

The private key is picked.

Public key
Once you pick the private key, you can generate a public key using elliptic curve cryptography (explained later). The public key also takes 256 bits of memory to be described, so there are 2^256 possible public keys (the same number as for private keys).

The public key is given (calculated) upon the private key choice.

ETH address
Your address (starting with 0x…) is not your public key as you may think. Ethereum needs one extra step to generate the ETH address which can be controlled with the picked private key. The process is a little bit complicated - ETH applies hash functions (keccak256) on your public key and then takes the last 40 characters of the hash function output. Since the output is hexadecimal, there are 16^40 (or 2^160) possible addresses.

The address is given (calculated) upon the public key.

Comparing the spaces
The keen one has noticed, that space of ETH addresses is much smaller than the space of Private/Public keys. Yep. This means, that one ETH address may be controlled via many private keys. This “many” is quite big, actually 2^96 (or in the decimal notation - 79228162514264337593543950336) private keys can control a single ETH address. Sounds crazy, but the probability of collision (two private keys controlling single ETH address) is still incredibly low. Don’t get messed up by the screen area taken by the different numbers in decimal notation, actually the magnitude of those spaces is not visually comparable at all.

Cryptography involved in the process

EC and ECDSA
How is the public key derived from the private one? Let’s start with the underlying framework using a mathematical technique called Elliptic Curves (EC) and a framework for their usage in signature algorithms ECDSA (Elliptic Curve Digital Signature Algorithm).

ECDSA is a mathematical “framework” that is (besides other applications) used to derive public key from private key. This framework is parameterized by an elliptic curve domain (elliptic curve/function formula, base point, finite field). Some widely used domains (so-called recommended) are described here. Recommended domains assures the expected behavior (such as trapdoor characteristic) of ECDSA will be met. Ethereum follows the secp256k1 domain standard.

EC comes with specific point operations (called EC arithmetics) - both inputs and outputs of these operations are points laying on the prescribed curve. The crucial operation is point addition add(a,b), visually the addition can be described as tangent of curve with projected slope of two points. Note, that there is no straight operation for multiplication or division. More details can be found in this great article series focused on EC operations.

Private key → Public key
Let’s return to the original problem. Public key is the base point (EC domain parameter) added N times with itself, where the N is Private key. Public key is therefore also a point on the elliptic curve. The addition of same things together multiple times can be solved with multiplication, one can say:

Public Key = BasePoint * PrivateKey

The straight operation for multiplication in EC arithmetics doesn’t exist. But there exist a few algorithms solving this problem, but is notable, that under the hood they all repeatedly use the operation of addition (in some efficient way). The most basic algorithm called “double and add” can solve any multiplication with O(2N) addition operation, where the N is the number of bits needed to binary represent the multiplier (number). The point is, that deriving the public key from the private is not computationally negligible. Also note, that deriving the private key from public key won’t work easily, because for EC division there is no efficient algorithm or even operation.

Public key → ETH address
I will also clarify the details of process for ETH address deriving. I already mentioned that public key is a single point on the elliptic curve, to describe the point at least one coordinate (x or y) and function of the curve (from EC domain) is needed. To save memory, it is practical to store only one of the coordinates, because on demand the other can be easily computed. For deriving the ETH address is needed to have both coordinates, convert them into hex form, concat them, apply the keccak256 (hash function), and take last the 40 characters from keccak256 output.

For an arbitrarily chosen private key, the outputs of described process would look like this.

Profanity

Hopefully, I let you acquire some decent knowledge about the private/public key relationship, so let’s follow with Profanity itself.

Workflow
Using a few simplifications, it can be said, that Profanity works in the following steps:

1. Let the user specify requirements (how the output ETH address should look like).

2. Random part:

   1. Pick a random private key (256 bit number) using 32 bit generator (this means, that used private key space is incredibly small compared to possible space).

   2. Derive a public key from the randomly selected private key in previous step, using algorithm like “double and add” (at most 512 EC addition operations).

   3. Set derived public and private keys as starting keys for deterministic derivation of new keys in following deterministic part.

3. Deterministic part:

   1. Check if generated public key produces address that meets the user requirements. If yes, exit. If no, continue.

   2. Increment public key by base point, increment private key by 1 (always 1 EC addition operation). Here is the trick, in 1 EC addition operation new public key was generated.

   3. Check if number of increments is less than 2 000 000. If yes, go to 3.1, if no, go to 2.1.

Once you pick the private key (in the random part) and derive public key, you appear somewhere in the private-public key space, and because of randomness, you had to calculate the public key with all those 512 EC operations (at most). Profanity then (in the deterministic part) leverages the fact, that it is computationally cheaper to reach neighborhoods (or any constantly distant keys) from the derived public key (1 EC addition operation), compared to “traveling” somewhere else and computing the public key from the scratch again.

Comparing the key spaces again

Issue and exploit approaches

The issue with Profanity implementation is the small size of random space used, and the fully deterministic kind of computation in the second part. Given to the so far described conditions of keys, ETH addresses, and Profanity workflow, two approaches of possible abuse are proposed:

Naive approach
The brute force solution could generate and store all 8 589 934 592 000 000 private keys. But as you may expect, it would require a lot of computation effort - months of computation for a solid farm of GPUs. Moreover, the result would have to be stored on more than 406 250 TB storage, assuming to store private key and ETH address pairs. Required storage is 2^32 * 2000000 * (256+160) = 3573412790272000000bits.

Diamond approach
Due to the deterministic part of Profanity workflow, there exists a different approach too. It doesn't give you a list of all keys, instead of it offers a framework, which can relatively smoothly answer a question - is a specific ETH address (respectively its corresponding public key) generated via Profanity? And if the answer is yes, then also the private key can be easily derived. The approach should look like this:

1. Reconstruct the process of generating all Profanity random keys, and store all pairs of private and public keys. Required computation time should be in a matter of hours. Required storage is 256 GB.

2. Pick a vanity ETH address worth compromising (let’s call it the given ETH address).

   1. Get the public key of the given ETH address.

   2. With public key of the given ETH address, iterate 2 000 000 times, in each iteration:

      1. Save the current public key into an array of candidate keys.

      2. Decrement (opposite operation to original Profanity flow) public key by base point (from secp256k1 standard), ie. look at given key neighborhood.

3. Try to find an intersection (should be either one or zero matches) between candidate keys and random public keys. If there is a such intersection, one can say, that the picked ETH address was generated by Profanity. To get the private key to (to handle ETH address) is needed:

   1. Get private key of intersection - simple lookup using random keys.

   2. Find the distance between intersection public key and the given ETH address public key in candidate keys array.

   3. Private key of ETH address = private key of intersection + distance.

Parts 2. and 3. of this approach should be computable in order of minutes, when optimized (ie. all data stored in RAM) it could be even seconds.

Sum up

In this article, I covered the mechanics behind key cryptography and the following process of deriving an ETH address. I also explained the logic of the Profanity tool, and its vulnerability in sense of small space size and pointed out the effective, but insecure trick the Profanity used to increase the search speed.

We know the possible process of obtaining the private key of Wintermute’s hot wallet, next time I will follow up with details of the exploit which happened on-chain.

Follow me on Twitter or reach me at Telegram.
Shout-out to Adam Chang for the cover photo.