3
$\begingroup$

Given a master password that has a lot of entropy (similar to Bitcoin HD wallet seed words, 130 bits of entropy or more) how many bits of entropy are lost per leaked generated password?

Let's take an example of the master password hello stack exchange good to see you and some passwords generated by PBKDF2 with SHA512 with 256k iterations using a tool I wrote

foo.com   mr7i?O5til?2
bar.com   PYOT1-AOhX.D
baz.com   rk!Vxf8G_HgO

Given an attacker has these generated passwords how much easier can they guess the original master password? How many if they have 2/3, 1/3, and how it compares to 0/3 as well?

Thank you!

$\endgroup$
1
  • 1
    $\begingroup$ It might provide additional insight if you explained how master password and URL are combined. $\endgroup$
    – Paul Uszak
    Feb 6, 2018 at 14:43

4 Answers 4

6
$\begingroup$

From an information-theoretic perspective, and with an ideal password hash function, with $k=68$ possibilities for each character of derived password, each such character leaks about $\log_2(k)\approx6.1$ bit, but only as long as that remains significantly lower than the entropy in the master password. That's a leak of about $73$ bit per derived password. With $130$ bit of entropy in master password, the entropy leak would be about $73$ bit for one derived password, and just shy of $130$ bit for more.

The example password hello stack exchange good to see you is meaningful English text, uniformly-cased, properly-spaced, without digits or punctuation, with 30 non-space characters. It is doubtful that it is representative of passwords with 130-bit entropy; I'd guesstimate 40 to 90 bit, and would not be surprised if almost no entropy remained after one derived password; or/and if that password was by far the simplest for an english speaker (thus most likely) matching a single domain / derived password pair.

However, assuming that PBKDF2-HMAC-SHA512 is unbroken (as it stands), a complete entropy leak is not enough to find the master password (or a derived password for another site) for a compute-bound adversary, as real adversaries are. The entropy computation is useful only to tell how many derived passwords are necessary to carry an attack (here, two are most likely enough, and one might be enough). The best attack remains trying all the possible master passwords, from most likely to least, against one derived password hash (which will weed out most candidate master passwords), then a second selectively in case of success.

With enough derived passwords, the expected difficulty of attack is mostly dependent on the entropy in the master password, and the parametrization of PBKDF2 (which is untold): $2^n$ iterations stretch the entropy in the master password by about $n$ extra bits.


From an information-theoretic perspective, if the master password is chosen in a finite set with probability $p_i$ for each master password and $1=\sum p_i$, it initially has entropy $H=\sum(p_i\log_2(1/p_i))$. When a derived password for a known site (or a symbol of that) gets known, that makes some master passwords impossible, some probabilities $p_i$ go to zero (and are removed from the sum) and the others are increased to $p'_i$ in proportion, so that $1=\sum p'_i$ still holds. The entropy leak is the difference between initial and residual entropy.

In other words, the entropy leak is $$\sum_\text{all MPs}p_i\left(\log_2{1\over p_i}\right)\ -\ \sum_\text{remaining MPs}\left({p_i\over\displaystyle\sum_\text{remaining MPs}p_i}\log_2{\displaystyle\sum_\text{remaining MPs}p_i\over p_i}\right)$$

When only one master password remains possible, only the left sum remains, and the entropy leak is that of the master password.

If all master passwords are equally likely, the entropy leak is the base-2 logarithm of the ratio of the number of initially possible master passwords, to the remaining number of possible master passwords. When only one master password remains possible, the entropy leak is the base-2 log of the number of all initially possible master passwords.

Assuming the derivation function is a Pseudo Random Function, knowing one of its output (or a symbol thereof) will rule out passwords irrespective of their initial probability. With each output symbol about uniformly distributed among $k$, it can be shown that the entropy leak for $s$ revealed symbol is expected to be almost $s\log_2(k)$ if that's much less than the initial entropy; and is expected to be almost all the entropy in the initial password if $s\log_2(k)$ is much larger.

$\endgroup$
1
  • 2
    $\begingroup$ One more edit? What's a "leak of leak" actually leaking :-) $\endgroup$
    – Paul Uszak
    Feb 6, 2018 at 14:47
1
$\begingroup$

Without reviewing your tool, assuming it is just hashing your password mixing it with domain name, you are leaking almost all your entropy if not all of it in each password.

First, ascribing 130 bits of entropy to the password example is a bit much, Even if you assume 7 words from a 20K vocabulary you end up with 100 bits. In fact you use mostly common words and a valid sentence structure and it actually makes some sense as as sentence, all reduce entropy of such passwords even more. So in sort what is true for nearly all memorable password generation schemes, you have less entropy than it seems.

The output of PBKDF2 however is very dense, even if you truncate it you have as much entropy in the resulting password as the charset you encode in allows (up to the original entropy of course).

With infinite computing resources, even one such password and definitely two should suffice in reproducing the original password.

This is not to say this is computationally feasible. And if you do not want to store encrypted random passwords but want them to be derived from a master password I believe the approach of using a secure PBKDF mixing master password with domain name is reasonably secure(without reviewing implementation).

$\endgroup$
0
$\begingroup$

It depends on the KDF that you use. A (t,q,ε)-secure KDF produces output that is indistinguishable from a random output for attacker chosen key material (for more information and KDF properties, you can check the HKDF paper https://eprint.iacr.org/2010/264.pdf). This property is similar to IND-CPA which is equivalent to semantic security (Goldwasser, Micali). Transfer this from symmetric cryptography to KDF, and you have the property you want, you are not able to extract any information for the original master password based on the generated ones.

Regarding your example, I don't think we currently have an answer, and I'm pretty sure that even if we had, it would be dependent on the underlying hash used by your PBKDF2 implementation.

$\endgroup$
0
$\begingroup$

None. PBKDF2 does not leak entropy when using an appropriate cryptographic primitive.

The issue here is conflation between entropy consumption as in a true random number generator, and a key derivation function. They are not the same. 95% of all English consists of ~3000 words and you have used seven. That's ~81 bits which you then have to reduce somehow for collocations. It's very unlikely that the actual entropy content will be more than the 73 bits spat out every time a password is generated. I'm ignoring any additional entropy from the URLs as that's easily guessable. So if you tried using your tool as an ASCII TRNG, you'd need to input a completely new phase for each site. That kinda defeats the whole point of a tool.

But that's not what your tool is. It's effectively an ASII CSPRNG seeded with "hello stack exchange good to see you". It then produces 73 pseudo bits per iteration (with the aforementioned URL proviso). Even after megabytes of site passwords, you can't infer the original seed (master password). Otherwise all password managers and wallets would suck.

$\endgroup$

Your Answer

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

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