What is the entropy of a password made with pwgen?

Question

pwgen is a unix utility that generates "memorable" passwords randomly. The man page says the entropy is lower than truly random passwords with the same specification. What is the actual entropy of a password made with pwgen?

Answer 1

An exact answer would require a deeper analyzis of the pwgen source code, or a more exact measurement. But I think we can use a strong compressor to approximate the entropy. The command

pwgen 1048576|xz -9ve -|wc -c

generates an 1MB long password, compresses it with the best known flags of the best known compressor, and measures the size of the output. The result was 593412 in my case. Replayed measurements didn't show a significant dispersion.

Based on this, the entropy of a single, 8 byte-long pwgen password is 8*8*593412/1048576 = 36.2 bits of entropy.

Note: although the output was a text file, xz could compress it only with a surprisingly bad ratio. Typically, text data can be compressed to around 10% of its original size, while xz could reach only a 60% ratio. It means, that pwgen is probably quite sophistically tuned also for the high entropy, and not only to produce easily pronouncable passwords.

36 bit is not enough defense against gpu-accelerated, clustered brute force attacks. But it is far more than enough against automatized login scripts; particularly if something (like a fail2ban) causes a hard, low limit to the possible tries.

Answer 2

The actual answer to your question is too hard for me to reasonably calculate, but I can say a few useful things about this.

pwgen does not produce passwords uniformly. Some passwords are more likely than others. This is because it tries to mimic some of the frequencies we have in English. This is true of most "pronounceable" password generators. Note I discuss this in my PasswordConLV15 talk. A link to the video of the talk and the slides are here: https://blog.agilebits.com/2015/08/07/unspeakable-passwords-jeff-goldberg-talks-to-passwords15/

There is no clear answer to what notion of entropy is most appropriate when password creation schemes when the schemes do not produce uniform output. I have argued that we should be using min-entropy in such cases.

Additionally, some versions of pwgen are subject to the modulo bias. It is a relatively small bias that comes up through a common design error when trying to pick a number between 1 and N even when the underlying random number generator is good.

So between the relatively small modulo bias and the much larger deliberate bias toward more likely sounding syllables, it would require a level of analysis beyond what I am willing to do to actually calculate the min-entropy.

It is frustrating that popular password generators are hard to actually analyze in terms of strength. But for most practical purposes, if you just be sure to generate things that are a few characters longer than you otherwise might, then your gain in strength from generating a longer password will surely overwhelm the loss of strength from their non-uniform behavior.