How to hack a vanity address generated with Profanity #NFT #NFTCollection #nftart #nftcollector #Crypto

On September 15, 2022, I decided to generate a vanity address for my daily-use hot wallet. #NFT #NFTCollection #nftart #nftcollector #Crypto

Something easily recognizable, like 0x0000…aced. A friend of mine, Alex, told me that he used Profanity, an Ethereum vanity address tool, to generate his one. #NFT #NFTCollection #nftart #nftcollector #Crypto

When I opened their GitHub repo, I found a README file that says that a critical bug was found. #NFT #NFTCollection #nftart #nftcollector #Crypto

Moreover, on the same day, an article was posted on 1inch’s blog with some ideas on exploiting the bug. #NFT #NFTCollection #nftart #nftcollector #Crypto

I had some free time, so I decided to dive deep into the topic and hack it by myself. #NFT #NFTCollection #nftart #nftcollector #Crypto

In this blog post, I’ll explain how addresses generated with Profanity can be hacked and how I was able to brute-force my friend’s private key on my MacBook M1 Pro (16 Gb) in 26 minutes. Let’s go! #NFT #NFTCollection #nftart #nftcollector #Crypto

How to get a public key? If you have your private key k (256-bit long random number), you need to apply some elliptic curve cryptography to derive your public key #NFT #NFTCollection #nftart #nftcollector #Crypto

More specifically, your public key K = k * G, where G is a generator point on the elliptic curve. #NFT #NFTCollection #nftart #nftcollector #Crypto

Then you take 5 least significant bytes of keccak256 hash of the public key to attain the public address. #NFT #NFTCollection #nftart #nftcollector #Crypto

As you can guess, you cannot reverse that process. So the only way to get a beautiful address with many leading zeros is to try many different private keys. #NFT #NFTCollection #nftart #nftcollector #Crypto

How does profanity work? Profanity uses OpenCL kernels to run many GPU threads in parallel that generate millions of addresses per second using a simple algorithm: #NFT #NFTCollection #nftart #nftcollector #Crypto

Profanity generates a random seed S that is used to sample a private key k. #NFT #NFTCollection #nftart #nftcollector #Crypto

Then it creates about 4 million work items, where the i-th worker takes K[i, 0] = (k + i * 2¹⁹²) * G as the initial public key. #NFT #NFTCollection #nftart #nftcollector #Crypto

After that, each worker increases its public key by G until the address derived from it meets the user’s requirements. #NFT #NFTCollection #nftart #nftcollector #Crypto

When it is found, you can easily calculate the private key given the number of the worker that found it and how many iterations it did. #NFT #NFTCollection #nftart #nftcollector #Crypto

So what is wrong with that? The method described is simple and effective, but there is a small issue in its implementation that has significant implications. #NFT #NFTCollection #nftart #nftcollector #Crypto

he random seed S that is used to generate a private key k is a 32-bit number instead of 64-bit. #NFT #NFTCollection #nftart #nftcollector #Crypto

Notice that if you know S, that Profanity used during the generation process, you know all private keys that it generated. #NFT #NFTCollection #nftart #nftcollector #Crypto

We are going to exploit the fact that a set of potential seeds is only 2³². #NFT #NFTCollection #nftart #nftcollector #Crypto

How to exploit the bug? Algorithm Idea If you have a public address that was generated using Profanity, you can find the corresponding private key by reversing the generation process: #NFT #NFTCollection #nftart #nftcollector #Crypto

First, you need to restore the corresponding public key K_t from the address. #NFT #NFTCollection #nftart #nftcollector #Crypto

You can do this if there is any transaction signed by the victim using their key. For example, you can easily look it up on Etherscan. #NFT #NFTCollection #nftart #nftcollector #Crypto

If the public key K_t was generated given some initial public key K by adding the needed amount of G (+2¹⁹² * G for each row and +G for each column). #NFT #NFTCollection #nftart #nftcollector #Crypto

you can initialize your workers in a way that the i-th worker starts with a public key K_t - i * 2¹⁹² * G, and then decrease it by G on each iteration until K is finally found by any of them. #NFT #NFTCollection #nftart #nftcollector #Crypto

If you know what private key corresponds to K, you can calculate the target private key (again, because you know the row and the column where it was found). #NFT #NFTCollection #nftart #nftcollector #Crypto

It looks simple! There is one challenge, though. We don’t know the initial public key. #NFT #NFTCollection #nftart #nftcollector #Crypto

Vulnerability Yes, we don’t know what initial public key K was used during the generation. #NFT #NFTCollection #nftart #nftcollector #Crypto

But we know that it was derived from one of the 2³² seeds (about 4 billion). Thus, we can iterate through all of them and precompute all corresponding private and public keys. #NFT #NFTCollection #nftart #nftcollector #Crypto

Now, when we run the generation process backward, we need to check on each iteration whether a new public key belongs to our precomputed set. #NFT #NFTCollection #nftart #nftcollector #Crypto

If we find any key that is in the set, we are done! #NFT #NFTCollection #nftart #nftcollector #Crypto

If the seed is a 64-bit random number, we need to precompute 2⁶⁴ public keys. That’s a lot of keys! 4 billion times more! #NFT #NFTCollection #nftart #nftcollector #Crypto

Search Problem This part of the algorithm is the trickiest one. #NFT #NFTCollection #nftart #nftcollector #Crypto

Once again, you need a way to check whether an element belongs to a set of 2³² public keys. #NFT #NFTCollection #nftart #nftcollector #Crypto

Ideally, you want each worker to do it on GPU, so your CPU is not a bottleneck. #NFT #NFTCollection #nftart #nftcollector #Crypto

There are 2³² public keys. It indeed doesn’t look like a huge amount for modern computers. But each public key takes 32 bytes in compressed form. #NFT #NFTCollection #nftart #nftcollector #Crypto

So if you decide to store 2³² of them on the disk, it will require 128GB of memory. #NFT #NFTCollection #nftart #nftcollector #Crypto

Moreover, it is not likely that your computer has 128Gb of RAM to upload them into the memory. #NFT #NFTCollection #nftart #nftcollector #Crypto

Put simply, 128GB is too much. If we use only 12 bytes for each public key, it will require 48GB to store them, and the probability of collisions will be low. #NFT #NFTCollection #nftart #nftcollector #Crypto

When I used only 8 bytes, collisions did occur. #NFT #NFTCollection #nftart #nftcollector #Crypto

Partitioning If you have a GPU with at least 48GB of memory, you can upload all keys into the memory, so each worker can search them using a binary search or utilizing some other data structure. #NFT #NFTCollection #nftart #nftcollector #Crypto

I wanted to hack Alex using my MacBook Pro M1 with 16GB of memory, so I chose 8GM as a memory limit and tested a few approaches. #NFT #NFTCollection #nftart #nftcollector #Crypto

Binary Search I divided the set of all public keys into 4 parts of 2³⁰ public keys each. #NFT #NFTCollection #nftart #nftcollector #Crypto

Then I took only 8 bytes of each public key, sorted them, and uploaded into the memory. That’s exactly 8GB of GPU memory. #NFT #NFTCollection #nftart #nftcollector #Crypto

Now each GPU worker can run a binary search to check whether its public key belongs to the set. #NFT #NFTCollection #nftart #nftcollector #Crypto

As you can remember, I already told you that collisions occur when only 8 bytes are used. #NFT #NFTCollection #nftart #nftcollector #Crypto

But it is not a big deal because they are rare, and when they happen, I check those public keys on the CPU using 12 bytes. #NFT #NFTCollection #nftart #nftcollector #Cryptoa

Hash Table Binary search is a great algorithm, but is there a way to search for an element even faster? Sure. #NFT #NFTCollection #nftart #nftcollector #Cryptoa

We can use a hash table instead. However, there is one caveat. You cannot use all slots allocated for it. Generally, typical load factors with most open addressing methods are 50%. #NFT #NFTCollection #nftart #nftcollector #Cryptoa

Thus, if we have 8GB allocated for the hash table, we can only store 2²⁹ public keys (8 bytes each). So we need to split our set into 8 parts instead of 4. #NFT #NFTCollection #nftart #nftcollector #Cryptoa

Is it worth it? On the one hand, when we have more parts, we are wasting more computational resources iterating through the same keys repeatedly. #NFT #NFTCollection #nftart #nftcollector #Cryptoa

On the other hand, the hash table requires O(1) lookups instead of O(log N) for binary search. #NFT #NFTCollection #nftart #nftcollector #Cryptoa

Comparison It took 64 minutes to complete 10k iteratinons using the hash table, and almost 4 hours using a binary search. #NFT #NFTCollection #nftart #nftcollector #Cryptoa

Even with extra work wasted on 8 parts instead of 4, the former approach performs much better. #NFT #NFTCollection #nftart #nftcollector #Cryptoa

Hack The fun part! It took me 7.5 hours to precompute the public keys using my Macbook Pro, and 26 minutes to hack Alex’s private key. That’s insane! #NFT #NFTCollection #nftart #nftcollector #Cryptoa

Profanity is almost 5 years old, and that vulnerability was there waiting to be discovered. #NFT #NFTCollection #nftart #nftcollector #Cryptoa

I wonder how many more small bugs and typos are hidden in the crypto world that can have significant implications. #NFT #NFTCollection #nftart #nftcollector #Cryptoa

#NFT #NFTCollection #nftart #nftcollector #cryptocurrency #Crypto #CryptoNews

##### Follow us on Twitter

to be informed of the latest developments and updates!

Follow @tivitikothreadYou can easily use to @tivitikothread bot for create more readable thread!