Suggestion for Attributes: Shannon & Brute Force Thresholds Revisited

[bwbug]

Your treatment of entropy per letter in the attributes (and as explained in your blogs) is interesting, but I think that to ensure a passphrase will not be too short, one must consider the number of words in the passphrase (as Reinhold did when he came up with a 19-letter minimum for a 6-word passphrase). Basically, the character-based entropy must be at least as large as the word-based entropy. This leads to a required lower bound for the minimum average word length in a given passphrase, from which one can determine the minimum number of letters required in a passphrase that has a specified number of words (by multiplying the minimum average word length by the number of words). So my suggestion is that the attributes table should report this lower bound for the required average word length.

If the actual entropy per letter is E (e.g., 2.62 bits for Shannon, 4.70 bits for brute-force), and the number of entries in the word list is W (e.g., 7776 for a diceware list using 5 dice), then it can be shown that the required lower bound for the average word length in a generated passphrase is given by the expression (log₂W)/E.

The above expression is for the case of no separators, but if separators are included, the resulting increase in the character-based entropy relative to the word-based entropy will be minimal. The calculation becomes much more complex, so I think it would make most sense to just report the conservative value obtained for the assumption of no separators.

One could compare the average word length for the entire word list to the computed minimum required average word length, but to guarantee that none of the generated passphrases have an insufficient number of characters, the shortest word length in the word list would have to be greater than or equal to the lower bound for the average word length.

It may be possible to compute or estimate the overall entropy reduction caused by rejecting passphrases that are too short, but I would have to think more about how this could be done.

[sts10]

Ah, I did this work a few years, so this is a bit of test for me. Very cool to have someone interested in this stuff!

Basically, the character-based entropy must be at least as large as the word-based entropy.

Agree.

I think you're suggesting the attributes table include a value called "minimum average word length". Let's assume 4.7 bits of entropy for a moment (putting Shannon aside for now). I think the meaning of this value would be saying to the user "Hey, whenever you generate passphrase using this list, make sure the average length of the words in your passphrase is above X". Do I have that right?

If so, I object to that metric for a few reasons. First of all, for the EFF long list, this new "minimum average word length" would be 12.925/4.7 or 2.75. Since the shortest word is 3 characters, there's no possible way to generate a passphrase below the minimum length.

But secondly, I have intended to make Tidy a tool to make word lists that are good and safe with wide room for user error. By this I mean, I do not want to pass caveats to the user. "Ensure your passphrase's average word length is above X" would be one of these caveats. Basically, I want to encourage list-makers to make lists that are as "fool-proof" as possible. (Making it easy to remove prefix or suffix words is another example of this: that way, the passphrase generator need not require separators between words).

My method for preventing these caveats is to take conservative approaches.

Let's look at the metrics that Tidy currently displays. Here they are for the EFF long list:

List length               : 7776 words
Mean word length          : 6.99 characters
Length of shortest word   : 3 characters (aim)
Length of longest word    : 9 characters (zoologist)
Free of prefix words      : true
Free of suffix words      : false
Entropy per word          : 12.925 bits
Efficiency per character  : 1.849 bits
Assumed entropy per char  : 4.308 bits
Above brute force line    : true
Above Shannon line        : false

The key lines for our discussion are the last three. I'll use W as word list length (7,7776 in the case of the EFF long list).

"Assumed entropy per char(acter)" is log₂(W) divided by length of the shortest word on the list (here's the code). For the EFF list, it's log₂(7776)/3 which is 4.308.

I use the shortest word on the list to be conservative. Users could get a passphrase completely made up of words that are of the shortest length.

Once we've calculated "assumed entropy per character", we compare it to two constants to make the metric more human-understandable to users. If "assumed entropy per character" <= 4.7, Tidy reports that the list is "above" the "brute force line". For the EFF list, 4.308 is indeed less than 4.7, so we're safely "above" the brute force line (reported in the attribute table as "Above...": "true"). If it's less than 2.62, we're under the "Shannon line". Since 4.308 is greater the 2.62, the EFF list does not clear this line.

In general, I want Tidy to encourage the creation of lists that are as safe as possible, with as few caveats as possible. I hope that makes sense in connection to your comment.

[bwbug]

Thank you for your thoughtful response. Your reasoning makes sense, and it's easy enough to compute the the "minimum required average word length" just using a calculator, if one is interested in this metric.

There is a benefit delving into a more in-depth analysis when one wants to optimize the trade-off between passphrase entropy and length (for example, for a 7776-word list to clear the "Shannon line" using your conservative approach, the minimum word length would have to be 5, so a user will have to type a large number of characters to enter their passphrase; the more nuanced analysis would allow shorter words on the list, as long as the generated words have an average length of 4.9).

[sts10]

Yep, I gotcha. The "lines" are admittedly strict/unforgiving in the current set-up... maybe too strict to be useful? Haha I also haven't gotten much feedback from tidy users who are not me, so this is a good discussion.

I guess we could do like "Chance that a 6-word passphrase is below the 'Shannon line'", expressed as a percentage? For the EFF list, we'd count the number of words with fewer than 5 characters and go from there?

[bwbug]

I guess we could do like "Chance that a 6-word passphrase is below the 'Shannon line'", expressed as a percentage?

Yes, something like this is what I meant when I wrote "It may be possible to compute or estimate the overall entropy reduction caused by rejecting passphrases that are too short", although I was thinking of some kind of metric in terms of entropy (e.g., perhaps an effective entropy per word, taking into account passphrases that would be rejected for being too short).

However, I believe that whether this is expressed as a probability (percentage) or effective entropy, the result will be dependent on the number of words assumed for the passphrase. Thus, it may not be possible to calculate a universal metric for this, unless you are open to using a 6-word passphrase as representative benchmark.

For the EFF list, we'd count the number of words with fewer than 5 characters and go from there?

I have a feeling that the calculation will not be trivial. My initial thought is that it may involve a 6-dimensional joint probability distribution...

[sts10]

I have a feeling that the calculation will not be trivial. My initial thought is that it may involve a 6-dimensional joint probability distribution...

Ah, maybe you're right. If you want to work out some kind of formula, I might be able to implement it for Tidy in Rust. Maybe we could create a sort of general 0 to 100 "score"?

[bwbug]

I'll think about how to do this. But the bottom line is that the "score" (whether expressed as a 0-100 score, or in terms of some entropy metric) will be different depending on the assumed number of words in the passphrase. So unless you are OK with presenting the results in a tabular form (e.g., for word counts in the range 4-8), we would have to see whether a conservative (worst-case) metric can provide meaningful/actionable information, or else, abandon the idea.

[sts10]

Not exactly on-topic, but I did add two formulas and two tables to the bottom of the readme that might be of interest here (and would welcome a double-check of my math).

Maximum word list lengths to clear the Brute Force Line

Formula:

Where S is the length of the shortest word on the list, 26 is the number of letters in the English alphabet, and M is max list length: 2^{S * log₂(26)} = M

(or in Python: max_word_list_length = 2**(S*4.7))

shortest word length	max list length
2	675
3	17559
4	456419
5	11863283

Maximum word list lengths to clear the Shannon Line

Formula:

Where S is the length of the shortest word on the list and M is max list length: 2^{S * 2.62} = M

(or in Python: max_word_list_length = 2**(S*2.62))

shortest word length	max list length
2	37
3	232
4	1428
5	8779
6	53974

Before creating this table, I hadn't realized just how "strict" the Shannon line is. Makes me wonder if it's so strict as to not be helpful.

[bwbug]

would welcome a double-check of my math

For the first table, your max list length values are only accurate to 2-3 significant digits, as a result of rounding errors in taking the logarithm. You can make the max list length values more accurate by taking advantage of the fact that S·log₂(26) = log₂(26^S ) and that for any base B, by definition of the logarithm, we get B^log_BX = X. As a result, we get M = 26^S, which can be exactly evaluated without rounding errors; thus, your table entries should be 676, 17576, 456976, and 11881376.

The Shannon entropy was apparently computed based on an empirically estimated "entropy per word" of 11.82 bits, and dividing that by 4.5 letters/word, which Shannon calls "the average word length in English" without documenting any source for this claim. Now, 11.82/4.5 = 2.6266666..., so rounded to 3 significant digits, it would actually be more appropriate to call it 2.63 than 2.62. However, since the claimed average word length is only given to 2 significant digits, the ratio can also be known only to 2 significant digits — i.e., 2.6 bits/letter. A more detailed uncertainty propagation analysis based on assumed Type B uncertainties of ±0.005 in the 11.82 value and ±0.05 in the 4.5 value indicates that the confidence interval for the ratio corresponds to the range 2.60-2.66 (i.e., 2.63±0.03 bits/letter). Thus, the corresponding values of the maximum list length should not be given to a precision greater than 2 or 3 digits.

Footnote:
I found some oddities in the math of that 1951 Shannon paper. For example, in deriving the value of 11.82 bits/word, he claims that the critical word rank n for which the sum p₁ + p₂ + p₃ + ... + p_n =1 (where each term p_k=0.1/k) is n=8727. However, by my calculations, the sum of the first 8727 terms of this harmonic series is only 0.9651, and that one must include words up to rank n=12366 in order for the sum to evaluate to unity. Second, my attempts to reproduce the calculation of Equation (7) did not yield a value of 11.82 (instead, the summation was found to equal 9.14 for n=8727 and 9.72 for n=12366). Admittedly, the linked PDF contains some scanning/OCR artefacts, so some of the mathematical expressions may not be correctly represented. I should probably check out the original version of the 1951 article, and also read the 1948 Shannon paper that is cited as Reference 1. But the methods described in the 1951 paper do not appear to be so complex, so I was very surprised that I could not reproduce the published numbers!

[sts10]

For the first table, your max list length values are only accurate to 2-3 significant digits, as a result of rounding errors in taking the logarithm. You can make the max list length values more accurate by taking advantage of the fact that S·log₂(26) = log₂(26^S ) and that for any base B, by definition of the logarithm, we get B^log_BX = X. As a result, we get M = 26^S, which can be exactly evaluated without rounding errors; thus, your table entries should be 676, 17576, 456976, and 11881376.

AMAZING! I've updated the brute force table in the readme.

Fixing the actual brute force computation in the code itself is a bit trickier, thanks to some rounding tomfoolery in Rust.

2.0_f64.powf(26_f64.log2()) // evaluates to 25.999999999999993, rather than 26
26_f64.log2() // evaluates to 4.700439718141092 ; I think it should be 4.700439718141093

(Code playground, for those interested.)

So, unless you object, I'm just going to hard-code the decimal in the test: assumed_entropy_per_character <= 4.700439718141093

However, since the claimed average word length is only given to 2 significant digits, the ratio can also be known only to 2 significant digits — i.e., 2.6 bits/letter... Thus, the corresponding values of the maximum list length should not be given to a precision greater than 2 or 3 digits.

Fascinating work! Going to change the Shannon test to 2.6 for now. Maybe we should just... do a bit of our own analysis with some more modern word corpus?

I found some oddities in the math of that 1951 Shannon paper... Admittedly, the linked PDF contains some scanning/OCR artefacts, so some of the mathematical expressions may not be correctly represented. I should probably check out the original version of the 1951 article, and also read the 1948 Shannon paper that is cited as Reference 1.

Again, super impressed you went this far here. Hope it's just a scanning issue? Let me know if I can help. The PDF I linked to was just a first search result. I should read more of those papers myself at some point.

[bwbug]

Ha! Thank you for the kind words, but I was really just trying to figure out if I could get a little better precision on the "2.62" value. Either there's something screwy with Shannon's numbers (not impossible -- this is what an electronic calculator looked like in 1951!), or I have completely misunderstood the methods used in his paper.

Maybe we should just... do a bit of our own analysis with some more modern word corpus?

I think we may have to either look for a different analysis in the literature, or come up with our own. It seems to me that Shannon's value is derived entirely from data on frequency of words in grammatically correct written text (sentences, paragraphs, etc.). What we need instead is some kind of analysis based on the frequency of letters appearing in those words. Perhaps the act of dividing the "entropy per word" by the average word length does give an appropriate value, but that seems like mathemagic to me, so I would like to understand the reasoning behind the analysis before I trust it. In addition, it is not yet clear to me that Shannon's use of the word entropy is identical to our own use of this term. Thus, I would personally take the Shannon entropy value with a grain of salt until I have better understood the underpinnings of his methods.

Fixing the actual brute force computation in the code itself is a bit trickier, thanks to some rounding tomfoolery in Rust.

Can you explain why the limited precision of Rust's floating point calculation causes a problem in the code? Not sure I understand why there is a need to calculate 2^log26 in the code, or why an error on the order of 10^-15 will cause issues.

[sts10]

Can you explain why the limited precision of Rust's floating point calculation causes a problem in the code? Not sure I understand why there is a need to calculate 2log26 in the code, or why an error on the order of 10-15 will cause issues.

I was confused as well until just now -- have resolved the rounding issue.

Think the culprit was this function:

pub fn calc_entropy_per_word(list_size: usize) -> f64 {
    (list_size as f64).ln() / (2_f64.ln() as f64)
}

If I change it to

pub fn calc_entropy_per_word(list_size: usize) -> f64 {
    (list_size as f64).log2()
}

the rounding issue I found resolves itself.

Here's a Rust code playground the shows the original issue:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=e8234d2494140adf09272282a7c1ee20

[bwbug]

I think you can simplify the evaluation of

assumed_entropy_per_character <= brute_force_line_max_entropy_per_character

by first calculating a value G that represents the number of letter guesses required, if given an entropy per letter:

G = 26 (randomly drawn letters from [a-z])
G = 2^2.6 = 6.1 (randomly drawn letters from written English)

If W is the length of the word list, and M is the number of letters in the shortest word, then your boolean test above becomes equivalent to checking whether

W ≤ G^M

For the brute force case, this should require no floating-point arithmetic, and therefore would be expected to yield a more precise result.

[sts10]

For the brute force case, this should require no floating-point arithmetic, and therefore would be expected to yield a more precise result.

Very smart. Got it working and haven't gotten any surprises yet.

G = 2^2.6 = 6.1 (randomly drawn letters from written English)

Just want to confirm you like 6.1 here, rather than having more digits. Guessing we're set on limiting Shannon's calculations to two significant digits, but just checking.

NOTE: Using your new method of calculating the Shannon line disrupts the table in the readme, as it's currently calculated. Now, a list with shortest_word-length of 3 can be 226 words and still be above the Shannon line. Does that sound right?

[sts10]

For Shannon line max length:
Using 6.1^M, then rounding down to nearest integer (can't have fractions of words on the list), I get

shortest word length	max list length
2	37
3	226
4	1384
5	8445
6	51520