Demystifying Ethereum Vanity Generator Profanity Private Key Cracking Vulnerability

2022-09-22 15:44

Read this article in 12 Minutes

This article summarizes the causes of Profanity's vulnerabilities and analyzes the possibility of cracking such random problems.

Original title: " Demystifying Ethereum Vanity Generator Profanity Private Key Cracking Vulnerability "

Original author: Johan, Slow Mist Security Team

Recently, the Wintermute wallet was attacked and lost about 160 million US dollars. ), after decentralized exchange aggregator 1inch published a security disclosure report claiming that certain Ethereum addresses created through a tool called Profanity have serious vulnerabilities. The SlowMist security team conducted an in-depth analysis of this incident and shared it with you.

Elliptic Curve Cryptography (ECC) is the most commonly used encryption algorithm in the blockchain field, ECC is an encryption algorithm Large category, which includes a variety of different curves and encryption algorithms, such as secp256k1/secp256r1/ed25519/schnorr, etc. Both Bitcoin and Ethereum use secp256k1 encryption.

When using Ethereum, we will first generate a private Account number (starting with 0x + 40 letters), the specific process is as follows:

(1) Generate an unpredictable random number seed, usually based on the system's /dev/ urandom random generator;

(2) Use a random seed to generate a private key (256 bits, 32 bytes)

(3) Generate a public key (64 bytes) from the private key

(4) Use the keccak-256 hash algorithm for the public key , take the last 40 letters of the hash value hexadecimal string, add 0x at the beginning to generate the final Ethereum address.

Specially remember the size of these public and private keys, because it is related to the amount of calculation we will do later.

A key formula that needs to be mentioned here:

Q = kG

This is the core algorithm for deriving the public key from the private key. It is very simple to deduce the public key from the private key, but it is almost impossible to deduce it in reverse.

Q is the public key, k is the private key, k is composed of large integers in a finite field, so large that it is almost impossible to guess, G is A point on the elliptic curve is a fixed value by default, and kG is the addition of k G points (the addition of points on the elliptic curve is not a simple addition of real numbers, and the calculation method will not be discussed here).

If we want to enumerate the Ethereum accounts and find Vitalik's private key, then after knowing his public key, we need to perform up to 2^256 (2 The 256th power) calculation of Q = kG is naturally insensitive to large numbers, so I convert it into workload, that is, the current rate of an Apple M1 computer is about 40M/s, so the approximate year required is 8 followed by 62 zeros. ten thousand years is too long, fight for now.

There are some wrong private key generation methods, which will cause the value range of the private key to become a value within a smaller range and become guessable. Common reasons are:

(1) The random number seed is not random enough, for example, if a timestamp is used as the random number seed, then we only need to exhaustively enumerate the past period of time All the time stamps can find the seed and private key used to generate the public key;

(2) The software algorithm is flawed, resulting in insufficient random strength (Profanity is exactly There are such defects);

The design purpose of Profanity is to help people generate an account with special visual effects, such as accounts starting or ending with special characters, On the other hand, some developers use it to generate accounts with many 0s at the beginning, such as 0x00000000ae347930bd1e7b0f35588b92280f9e75, which can save Gas when calling smart contracts.

In order to blast out the Vanity Address faster, Profanity only obtained a random number at the beginning of the program, and all subsequent private keys are iterated based on this random number Extended, let's take a look at its random number generation algorithm:

random_device is used here to obtain the random number provided by the system. This random number source meets the strength required by encryption. But when we noticed the variable type, we found that rd() returns a 32-bit random value. We mentioned above that a private key is 256-bit long, so the process of obtaining random numbers cannot be filled The entire private key, so Profanity uses mt19937_64 to generate random numbers to fill the entire private key. The random algorithm of mt19937_64 and random_device is essentially different. mt19937_64 is deterministic, its randomness depends on the input random number, and does not produce new randomness.

That is to say, if the value passed to mt19937_64 by rd() is within a certain range, then distr(eng) ; The value is also in a corresponding range, and the r value returned by the createSeed function is naturally also in a certain range.

The key point is here: all possibilities of rd() are 2^32, which is different from the security of the private key (2^256) 224 orders of magnitude, but the order of 2^32 is also quite large, so how much calculation does it need to crack the private key?

After obtaining the first private key SeedPrivateKey, in order to collide with the required account address, Profanity will continuously update the private key through a fixed algorithm. Up to 2 million times (the value comes from the article disclosed by 1inch), the calculation method of this public key can be expressed as:

PublicKey = kG = (SeedPrivateKey + Iterator) *G

Iterator is an increasing number. When PublicKey is known, we can get SeedPrivateKey by enumerating SeedPrivateKey and Iterator exhaustively. The amount of calculation is about 2^ 32 multiplied by 2 million times, it takes more than 60 years on 1 M1 computer, it seems that there is hope in this life :D. If I use a large number of graphics cards with larger computing power for parallel computing, it is perfectly fine to collide with the desired result in a few days or even a few hours.

It just so happened that the Ethereum-to-PoS consensus has been transferred recently, and there is a large amount of idle graphics card computing power. If the miners use the graphics card to crack the private key, it will not be possible in minutes success? Of course, this conspiracy theory is meaningless, we just want to study the possibility of cracking. We would prefer to be able to unlock the private key with a less brute force method.

Let's move the two sides of the equation a little and transform the above formula, we can get:

< p>SeedPrivateKey*G = PublicKey - Iterator*G

We can think about another attack method, if we pre-calculate SeedPrivateKey*G first, we need up to 256 G The memory space to store calculation results can be done on an ordinary server, and the required calculations are 2^32 times, which can be completed in about tens of minutes. Then we substitute the PublicKey that needs to be cracked into the right side of the equation, and then collide with the Iterator. The amount of calculation required is about 2 million times, and there are 2 million table lookup times. The time required is in seconds. This is interesting. It turns out that the 32-bit random number is so insignificant that anyone can restore the private key within tens of minutes.

So far, we have concluded that the cause of the Profanity vulnerability is that the 256-bit private key is not sufficiently randomly seeded, resulting in a serious reduction in the value range of the private key. At the same time, the possibility of cracking this kind of randomness problem is also analyzed, hoping to give you some inspiration.