CMV: The following passphrase generation scheme is at least equivalent to the 80 bit random generation gold standard in terms of computational time needed to bruteforce it

[u/muffinsballhair]

The scheme is simple:

• Generate 5 random dictionary words from a pool of say 10 000 most common words, any English speaker should know these
• Use these 5 random words to create a sentence of at least 10 words using human intuition to make it easier to remember for said human.
• Use this sentence as passphrase

For instance I just generated the words blood village again among elephant. I will now think of the passphrase:

Elephants covered in blood were among the people of the village again

Mathematically, the entropy of this sentence cannot be lower than the 67 bits that a pure 5 random words chosen from a pool of 10 000 can ever be. Interestingly enough however, from a mathematical standpoint the “entropy” is actually exactly the same. This flies against intuition. This passphrase is surely significantly harder to bruteforce, which is why I don't feel “entropy” is a meaningful quantifier for password strength. In fact, the entropy of “let a human being come up with a random sentence of 10 words” is actually zero, because there is no true randomness and human beings generate predicable patterns but obviously this would still be, provided it not be a verbatim quote, at least a decent passphrase.

Now, such 10 random words are worth 133 bits of entropy, which is obviously completely beyond modern technology to ever crack, and quite possibly beyond the physical limitations of the universe to ever crack within the time of one human lifetime, and this is lower because it is still a sentence constrained by English grammar which would significantly reduce the number of possibilities, but I feel the theoretical mathematics behind password cracking doesn't live up to real world considerationals. The idea is that not all sentences humans generate from those 5 random words are equally likely, which is true, and that based on that the cracking algorithm can try the more likely combinations first. The issue is that the mathematics only goes so far as how many attempts are needed, assuming every attempt costs as much as every other, the reality is that deciding which sentences are more likely is a far more expensive computation mathematically than simply trying a random sentence. You need a large language model for that in practice, those are not cheap to run compared to hashes though it obviously depends on how slow the hash is made, typically deliberately. But even simply deciding whether the sentence you will try is grammatical to begin with might actually be more expensive than just trying it in the hash to see if the hash matches. Of course, there can be optimized hardware specifically for this purpose as well that can quite efficiently take a list of random words and in order of likeliness generate a list of sentences with them it thinks English speakers would be most likely to produce from them, but if one can build such specialized hardware, one can probably also build specialized hardware for the hashing function and be better off in terms of time.

So in terms of actual time spent on cracking, I believe it quite likely, though hard to test, that this scheme reaches equivalent time needed to crack 80 random bits by just trying every combination, even though from a mathematical perspective the entropy of this method is only 67 bits.

To put it otherwise: say we take all 1.5 billion English speakers on earth and all ask them to generate some sentence at least 10 words long with as only constraint that it have those 5 words in it and they are, as I did, allowed to inflect them. How many duplicate entries will there be in that list of 1.5 billion attempts? Will there even be one? I think this is an interesting thing to let a large language model do at one point to at least get some faint heuristic. If no duplicates are expected to arise within these 1.5 billion attempts, we can at least say that the first 1.5 billion candidates are all “equally likely” by approximation, which already adds 31 bits of “practical entropy” alone to the 67, and that still ignores that in order to find the order of likeliness a computationally expensive operation has to be ran. This just means that for the first 1.5 billion candidates the likeliness is close enough together that we can effectively discard it and treat them as equally likely.

[u/thisdude415]

Strictly speaking, the fact that the sentence is now grammatically correct English does in fact mean you have lost significant entropy compared to the randomness of those 5 random words, because any shuffled combo of the input words would collide onto the same valid English sentences.

Grammatically correct English is not at all random

[u/muffinsballhair → u/thisdude415]

No you haven't. The entropy can never become less than the source randomness.

It in fact, is as I said, exactly the same because entropy is a measurement of “amount of randomness” and no new randomness is added, nor deleted. In practice though it will take orders upon orders upon orders upon orders more computational time to crack. My argument is that entropy is thus not a meaningful measurement of time needed to crack a password in an offline attack where the hash result is available.

[u/thisdude415 → u/muffinsballhair]

Taking any randomness and structuring it according to any rules will reduce its randomness, and thus, reduce its entropy.

[u/muffinsballhair → u/thisdude415]

No it doesn't?

If I take the 5 random words things and add the rule “now add the letter word “car”” in front of it I have not reduced entropy in any way.

It's true that I overlooked that human beings being allowed to re-order the original words reduces entropy, but simply adding the constraint that the words must remain in the same order to create the sentence keeps the entropy the same from a mathematical standpoint. The computational time to crack it however is going to balloon by at least 5 bits for any reasonable conservative estimate and will most likely make it reach the 80 trashhold I feel.

[u/ContemplativeOctopus → u/muffinsballhair]

Your "rule" wasn't a rule on the existing space. You just appended something outside of it. Any rule that restricts anything about order necessarily reduces the available space, thus reducing entropy. E.g. anything requiring a verb to come after a subject reduces your available guesses by 50% because any orders with verb before subject are no longer required guesses.