A Wintermute wallet was recently attacked, resulting in a loss of approximately $160 million dollars. The root cause of this incident was Wintermute’s use of the Profanity tool to create a vanity wallet (beginning with 0x0000000) in an attempt to save on gas fees. This follows the recent announcement by 1inch, a DeFi exchange, that some Ethereum addresses created through Profanity contained severe vulnerabilities. We conducted a thorough investigation into this incident, and the following are our findings.
Elliptic Curve Encryption (ECC) is the most commonly used encryption algorithm in the blockchain field. ECC is a broad category of encryption algorithms that includes a wide range of curves and encryption algorithms such as secp256k1/secp256r1/ed25519/schnorr, among others. Secp256k1 is used to encrypt Bitcoin and Ethereum.
When using an Ethereum address, we first generate a private account (beginning with 0x + 40 letters), and the process is as follows:
(1). Generate a random number seed, typically using the system’s /dev/urandom random number generator
(2) Use a random seed to generate a private key (256 bits, 32 bytes)
(3) Generate the public key (64 bytes) from the private key
(4) To generate the final Ethereum address, the public key employs the keccak-256 hash algorithm, which takes the 40 letters following the hexadecimal string of the hash value and adds 0x to the beginning.
Take note of the size of these public and private keys, as this relates to the amount of computation we will need to perform in the future.
A key formula to mention here: Q = kG.
This is the main algorithm for generating the public key from the private key. It is relatively simple to extract the public key from the private key, but it is nearly impossible to reverse the process.
The public key is Q, and the private key is k. k is composed of large integers in a finite field, making guessing nearly impossible. G is an elliptic curve point, the default is a fixed value, and kG is the sum of k and G. (Because this is a complex calculation, we won’t go into specifics here.)
If we want to brute force an Ethereum accounts, for example, after knowing Vitalik’s public key, we want to find his private key, then we need to perform at most 2²⁵⁶ times Q = kG. To solve this equation using the current rate of an Apple M1 chip(~ 40M/s), it would take approximately 8 followed by 62 zeros years to solve this problem. A very longgggggggggggg time.
There are several faulty private key generation methods that will cause the private key’s value range to decrease, making it easily guessable.
Some reasons include:
(1) The random number seed is insufficiently random. For example, if we use a timestamp as the random number seed, we can check all timestamps in the past period to determine the seed and private key used to construct the public key.
(2) A flaw in the software algorithm results in insufficient random strength (Such as the Profanity bug).
Profanity is intended to assist people in creating accounts with unique visual effects, such as accounts that begin or end with special characters. Some developers also use it to generate accounts with multiple zeros, such as 0x00000000ae347930bd1e7b0f35588b92280f9e75, which can save gas when calling smart contracts.
In order to generate vanity addresses quickly, Profanity only obtains a random number at the beginning of the program. All subsequent private keys are iteratively extended based on this random number.
Let’s look at their random number generation algorithm:
Dispatcher.cpp
cl_ulong4 Dispatcher::Device::createSeed() {#ifdef PROFANITY_DEBUG cl_ulong4 r; r.s[0] = 1; r.s[1] = 1; r.s[2] = 1; r.s[3] = 1; return r;#else // Randomize private keys std::random_device rd; std::mt19937_64 eng(rd()); std::uniform_int_distribution<cl_ulong> distr; cl_ulong4 r; r.s[0] = distr(eng); r.s[1] = distr(eng); r.s[2] = distr(eng); r.s[3] = distr(eng); return r;#endif}
In this case, random_device is used to obtain the system’s random number. This random number generator is strong enough to meet the encryption requirements. However, when we examine the variable type, we see that rd() returns a random value with a length of 32 bits. Given that a private key is 256 bits long, obtaining a random number all at once cannot fill the entire private key. Profanity employs mt19937_64 to generate a random number large enough to fill the entire private key. There is a fundamental difference between mt19937_64 and the random algorithm of random_device. Since mt19937_64 is deterministic, its randomness is dependent on the random number’s input, making it not truly random.
In other words, if the value passed to mt19937_64 by rd() is within a certain range, the value of distr(eng) is also within that range, and the r value returned by the createSeed function is naturally within that range.
Here’s something to think about: The total number of rd() possibilities is 2³²; this is 224 orders of magnitude less than the security of private keys with 2²⁵⁶. But 2³² is still a large number, so how much computation is required to solve this?
To sync with the correct account address, Profanity will constantly replace the private key through a fixed algorithm up to 2 million times after obtaining the first private key SeedPrivateKey (the value comes from the article disclosed by 1inch).
The public key can be calculated using the following equation: PublicKey = kG = (SeedPrivateKey + Iterator)*G
Once the PublicKey is known, we can obtain the SeedPrivateKey by exhaustively checking the SeedPrivateKey and Iterator. This should take approximately 2³² X 2 million attempts. On an M1 computer, it will take more than 60 years, so there’s still hope in this lifetime:D. However, by deploying a large number of graphics cards as well as additional computational power, we can achieve the required results in a matter of days, if not hours.
Ethereum recently adopted the PoS consensus, and there is a lot of idle computing power looking for a new home. Miners could use their mining power to brute force a Protanity private key in minutes.
Of course, these are just theories, and there is no evidence to support them. We simply want to raise awareness of the various possibilities. We also don’t want anyone using brute force to gain access to private keys.
By shifting the equation above, attackers can use a different approach to solve for private keys: SeedPrivateKey*G = PublicKey — Iterator*G
If we first compute the SeedPrivateKey*G, we will need at least 256 G of memory space to store the results. This is entirely feasible on a standard server, and the required calculation is only 2³², which can be completed in a matter of minutes. Then, on the right side of the equation, we substitute the PublicKey to be solved, and then collide with the Iterator drop; the amount of computation required is approximately 2 million attempts, which can be completed in seconds. As it turns out, 32-bit random numbers are so insignificant that anyone with a few minutes can potentially restore the private key.
So far, we’ve determined that the Profanity vulnerability is caused by a failure to create the 256-bit private key with enough randomness, resulting in a severely limited range of private key values. While we did mention brute force attacks, it was only to shed light on the subject and in no way encouraged their use.
