5

The explanation in question is given here and reproduced below as well:

Electrum currently use the same wordlist as BIP39 (2048 words). A typical seed has 12 words, which results in 132 bits of entropy in the choice of the seed.

Following BIP39, 2048 iterations of key stretching are added for the generation of the master private key. In terms of hashes, this is equivalent to adding an extra 11 bits of security to the seed (2048=2^11).

From the point of view of an attacker, the constraint added by imposing a prefix to the seed version hash does not decrease the entropy of the seed, because there is no knowledge gained on the seed phrase. The attacker still needs to enumerate and test 2^n candidate seed phrases, where n is the number of bits of entropy used to generate the seed.

However, the test made by the attacker will return faster if the candidate seed is not a valid seed, because the attacker does not need to generate the key. This means that the imposed prefix reduces the strength of key stretching.

Let n denote the number of entropy bits of the seed, and m the number of bits of difficulty added by key stretching: m = log2(stretching_iterations). Let k denote the length of the prefix, in bits.

On each iteration of the attack, the probability to obtain a valid seed is p = 2^-k

The number of hashes required to test a candidate seed is: p * (1+2^m) + (1-p)*1 = 1 + 2^(m-k)

Therefore, the cost of an attack is: 2^n * (1 + 2^(m-k))

This can be approximated as 2^(n + m - k) if m>k and as 2^n otherwise.

With the standard values currently used in Electrum, we obtain: 2^(132 + 11 - 8) = 2^135. This means that a standard Electrum seed is equivalent, in terms of hashes, to 135 bits of entropy.

Is the assumption that 2048 rounds of key stretching add 11 bits to the security of the seed correct? Is the overall explanation correct?

1

Yes it is correct. Bruteforcing n bits with 2048 rounds of hmac for each attempt is equivalent to bruteforcing n + 11 bits but only requiring one round of hmac for each attempt. They are equivalent because the rounds of work required to determine each secret (n bits vs n + 11 bits) are identical.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.