Dec 8, 2022
Profanity: Clarifications
Hi all! I have been asked several times about how Authors derived private key from public and started searching for information on this attack and found a very interesting discussion with its creators — I have compiled everything in this article, I hope no one has any questions! I found this dialogue very enlightening — here is the original link to the discussion but for your convenience I will bring it down without cuts and keeping the Author’s punctuation and spelling!
Since the disclosure of accurate information can lead to hacking other projects, you will only see generalized data here. In other words, we will tell you everything except what the deterministic function G is.
- Check out before reading: github.com/johguse/profanity/issues/61 ❕
Question:
How does one decrement a public key? (In the efficient manner section, it mentions “Repeatedly decrement them until they reach the seed public key.”)
Assuming, I have two private keys A and A’, where A’ is a single increment from A (e.g: A is [u8]: […, 0] and A’ is [u8]: […, 1]).
PublicKey(A) and PublicKey(A’) would be vastly different, right? How do I apply a decrement to PublicKey(A’) to get PublicKey(A)?
From what I understand from the blogpost:
Profanity does:
1. Generate a random seed N from set of 2**32 (problem here, small set)
2. Generate private key from seed N
3. Apply some deterministic function on generated private key to generate 2 million other private keys
4. Generate public keys for 2 million other private keys
5. Check addresses from public keys for vanity match
6. If no match, increment each of the 2 million private keys by 1
7. Repeat steps 3–5
To break, you want to find seed N, since you can compute the exact private/public keypair in the same time it took to generate (e.g using Profanity itself).
The efficient manner would require:
Pre-generation:
1. I can collect the public keys of all 2**32 (seed) * 2 million (deterministic) combinations ahead of time, with fairly little compute
Then:
1. I get the public key from the vanity address that has a transaction
2. I apply some deterministic function to get 2 million other public keys (I assume to match with the 2 million derived private keys; ignoring how this works for now)
3. I decrement these public keys over and over until one matches with one that I generated during Pre-generation (telling me the origin seed needed to re-compute the private key)
The part I don’t get is (3) — how can I decrement the public key to produce a match when two private keys (A and A’) produce vastly different public keys.
Answer from Anton Bukov (1inch team):
Subtracting point G. Need to build table of 4b public keys, expansion to 2m keys was done by:
privateKey + (task_id << 192)
So on reverse process we did:
publicKey — (task_id << 192)*G
Cool review article: mudit.blog/wintermute-muted-in-crypto-winter
This was the reason:
• telegra.ph/Profanity-Clarifications-09–16
• blog.1inch.io/a-vulnerability-disclosed-in-profanity-an-ethereum-vanity-address-tool-68ed7455fc8c
Reminds me: bitcointalk.org/index.php?topic=5076779.0
