3
$\begingroup$

Andreas Antonopoulos effectively states: an input of 256bits of entropy into PBKDF2-HMAC-SHA512 will ONLY output a 64 byte hash containing ~128 bits of entropy. He states the algorithm essentially ignores the extra entropy going in, and it is "wasted" entropy.

IS THIS TRUE? Can anyone explain why?

Source: (starts at 14:10 mark and goes for a few minutes)

https://www.youtube.com/live/U0T49duRt74?feature=share&t=850

Background to avoid confusion: The subject of the video is on bitcoin key generation. Bip39 uses PBKDF2-HMAC-SHA512 - 64 byte output. 24 word seed phrases contain 256 bits of entropy. 12 word seed phrases contain 128 bits of entropy.

$\endgroup$
6
  • $\begingroup$ Is this the entropy halves every hash thing again..? $\endgroup$
    – Paul Uszak
    Commented Jul 7, 2023 at 15:11
  • $\begingroup$ Never heard of that. A myth of some sort? $\endgroup$
    – George
    Commented Jul 7, 2023 at 15:18
  • $\begingroup$ not quite - crypto.stackexchange.com/a/107084/23115 :-) $\endgroup$
    – Paul Uszak
    Commented Jul 7, 2023 at 15:42
  • $\begingroup$ That actually helps. Not sure it is exactly the answer to my question, but it helps me on this quest to find out. Thank you. $\endgroup$
    – George
    Commented Jul 7, 2023 at 16:26
  • $\begingroup$ I don't think it is true, but in any case, if your input is 128 bits or more then there is no need to worry anyway. Actually, at that point, you might not even need PBKDF2. I'd be more worried about the generation and especially storing part, because remember it you won't. $\endgroup$
    – Maarten Bodewes
    Commented Jul 7, 2023 at 18:07

1 Answer 1

4
$\begingroup$

TLDR: No, PBKDF2‑HMAC‑SHA‑512 does not limit the output entropy to 128‑bit. It's output entropy is nearly the input entropy with a cap of about 510 bit for input with at least 0.2 bit of entropy per byte. As far as I can tell this also applies in the context of BIP‑0039, and the video is wrong at least in it's justification to use 128 bits of entropy.

The recommendation does not practically endanger an individual user's security when generating secp256k1 keys. However, from a system perspective, when we consider attack against millions of public keys generated per this recommendation (with a standard word set and no password), that recommendation makes it a rational choice for adversaries trying to break any one of the public keys to attack BIP‑0039 by brute force rather than trying to attack secp256k1 with Pollard's rho or similar. The attack simply enumerates mnemonics sentences, apply BIP‑0039 (which likely dominates the cost), derive the private key, then the public key (which also has sizable cost), and compare against the million public keys (which has rather lesser cost).

BIP‑0039 is specified as:

To create a binary seed from the mnemonic, we use the PBKDF2 function with a mnemonic sentence (in UTF‑8 NFKD) used as the password and the string "mnemonic" + passphrase (again in UTF‑8 NFKD) used as the salt. The iteration count is set to 2048 and HMAC‑SHA512 is used as the pseudo-random function. The length of the derived key is 512 bits (= 64 bytes).

mnemonic sentence and passphrase are different inputs. passphrase defaults to empty.

Preliminary: per the definition of SHA‑512 and this heuristic, the entropy in the output of SHA‑512 is near it's input entropy capped to $c$ bits, for some $c$ in $[512-\ln(r),512)$ where $r$ is the number of rounds, with $r=\lfloor(\ell+137)/128\rfloor$ where $\ell$ is the length of the input in bytes. When the input has less than $c$ bits of entropy, the output entropy is close to the input entropy. When the input is full entropy, $c$ is very near $512$, except that $c\approx511.2$ when $\ell\bmod 128=119$ (because then no entropy enters the last SHA‑512 round). The minimum for $c$ is reached when all the entropy is in the first 128 bytes of input. When there is at least 0.2 bit of entropy per input byte, and for all purposes in this answer, $c$ is in $[504,512)$ and $c\approx510$ is a fair approximation.

Per the definition of PBKDF2HMAC‑SHA-512, the password input is hashed when it is more than 128 bytes. In the context of BIP-0039, that's likely when mnemonic sentence has 256 bits of entropy. This hashing reduces the entropy in mnemonic sentence, but not by a sizable amount below 504 bit of input entropy.

If a passphrase is used in BIP‑0039, it goes into the PKKDF2 salt, which entropy is capped to some $c$ by the first of the HMAC round(s) in PBKDF2.

Then the structure of PBKDF2-HMAC is such that the entropy in it's password and salt inputs (after each has been capped as aforementioned) essentially ass with a cap by some $c$. More rounds do not lower the output entropy, because the PBKDF2 results at each round are XORed.

$\endgroup$
1
  • $\begingroup$ Excellent reply! Thank you so much for taking the time to explain all of this! $\endgroup$
    – George
    Commented Jul 8, 2023 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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