I am thinking about how you two are thinking about this problem in more detail. My concern is that you are intending to punish everyday users for not using “the correct software” or “not being careful enough” - when really the majority of people aren’t well versed in this topic - and just want to use a currency.
The best analogy for this argument is “You shouldn’t have clicked on that link” vs well maybe “We shouldn’t have XSS to begin with”… and please keep an open mind in this discussion - everyone on this tread wants our users to be safe as possible and to build the very best network - I know that. Math is the universal language after all, and I think it can help us all reason about this issue.
Is using keccak() alone for wallet generation more of a concern than than keccak(secp256k1)?
Is this a shortcut useful to anyone?
Let’s start of with keccak() - which is more commonly known as SHA3. This is hash function is very interesting, it is one of the few hash functions created specifically to be accelerated on 64bit architectures and in fact we are seeing phenomenal hash-rates from hardware acceleration. Keyword being accelerated, which is the exact opposite of the bcrypt(), and PBKDF2() key-derivation functions.
Let’s assume the attacker is modifying the salt with an O(1) operation. Now let’s assume the hacker has a modern 64bit machine at their disposal. The address is calculated as follows:
contract address=keccak(concatenate(sender address,nonce,code hash,salt))
So this is a sha3() hash of 1024bits. We will assume that the attacker isn’t using string-concatenation, but rather bit flipping the last 256bits of the message to search the key-space. Looking up the performance we can see keccakc256treed2 takes roughly 40 cycles per byte in order to calculate this hash.
That gives us:
40 cycles * 64 bytes = 2560 cycles per hash
Now lets assume our hackers are poor, and they purchased a used-server from eBay for a few thousand dollars. For the purposes of this lets say the attacker with with an AMD Epyc with 64 cores at 2.66ghz.
So that gives us
2.66 billion cycles * 64 cores = 170,240,000,000 cycles/second
Thus yielding a theoretical maximum of:
66,500,000 hashes per second
Now keep in mind - the same hardware that is used in Bitcoin mining, will have a higher hashrate using keccak/sha3. This is because the sha3 hash function was created to be accelerated by hardware - where as sha2 wasn’t.
That allows for an attacker to search a very large key-space without a lot of resources. Yes, of course this poor AMD chip isn’t going to hit its maximum today - but hardware only gets faster over time. So this calculation will be a low-ball estimate in just a few years.
Now the fun part! ECC key generation isn’t something that can be easily accelerated because the numbers are too large to fit in the CPU’s registries, which is an important feature of a KDF. So even if a manufacturer decided to make a hardware accelerated secp256k1, no processor has ever been created which can accelerate this calculation, where as sha3 was specifically designed to be accelerated. This means ECC-key generation isn’t cycle-bound - its memory-bound - and we can see this this limit affects the calculation times.
There is another curve-ball here: secp256k1 keys are harder to generate, in fact the link below claims that it is 10 times slower on average than some of the more performant curves used in TLS. The benchmark didn’t think to test secp256k1… but we can choose some other Weierstraß curve which should have very similar performance characteristics. By looking at the real-world benchmarks for ECC key generation. For the purposes of this calculation we will use the data from ecfp256h which is also 256bit Weierstraß curve.
So if it takes roughly 31,738 cycles to generate a single key - we still to calculate the sha3() hash for 32-bytes of data:
31,738 cycles + 40 cycles * 32 bytes
33,018 cycles per key
Meaning that we can at most generate 5,365,197.07 keys in a second… But wait, we know that this is wrong because no has ever generated 5 million secp256k1 keys in a second on any chip, thats impossible because this calculation memory-bound and not CPU-bound - which is a very useful feature to have in a KDF.
In practice, if you where to benchmark an AMD Epyc system today - I think you would get only around 40k ECC keys per second - making it 3,000 times slower than sha3() alone.
But you don’t have to take my word for it, this is all easily verifiable. In fact, here is a wonderful discussion between cryptographers about the performance differences between SHA2 and secp256k1 key generation:
In some sense you could think of this vulnerability as a KDF bypass, that allows the attacker to search the keyspace thousands of times faster. If we added some value that made the contract’s hash unpredictable (otherwise known as a ‘pepper’) - then the attacker would have to search this keyspace using secp256k1 key generation instead of simple addition or string concatenation.
Using a formal memory-hard KDF like bcrypt() would also make it more difficult to search this keyspace using any method.
A reasonable patch is as follows:
keccak(concatenate(sender address, nonce, code hash, salt ⊕ pepper))
One could make the argument that BLOCK_HASH is a suitable nonce for this purpose because it cannot be known by the attacker when the transaction is formed - and should not be influenced in a MEV-style attack because PoS validators are no longer responsible for block assembly.
Correct me if i’m wrong with any of this, I like being wrong because it gives me a opportunity to improve.