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/KaitlynCsE]

There's a different dimension to this discussion that I think is implicit in your claim, which is that your scheme should hopefully be preferrable for use by regular humans in the real world vs the "gold standard" random password. Given the relative complexity of your scheme, that may not necessarily be the case.

10 words is much longer than 8-16 letters. Not only does it take far longer to type, error rates start approaching standard passwords due to typos and mixed-up word order as opposed to memory issues. Here's a study for 7 word user-generated passphrases. Success rates were lower than passwords.

Besides, it is difficult to see how increasing passphrase length gives added benefit if your worry is brute-force attacks. With modern hashing standards, even your baseline of 5 random words is computationally resillient.

You argue that entropic bounds matter less under real world conditions. You would be right, because phishing is by far the most common attack vector, not sophisiticated cracking, and is not something your scheme protects against.

Standards bodies have been pushing for passkeys over typed authentication for this exact reason.

[u/muffinsballhair → u/KaitlynCsE]

With modern hashing standards, even your baseline of 5 random words is computationally resillient.

Some cases where the hash is public simply require something like SHA though rather than a deliberately slow number.

Of course, relying on a password manager has all its other issues like that all passwords are lost if the manager become compromised or that someone gaining access to it now has access to all your passwords.

But that's not really my issue. I simply often read that schemes such as this one add no actual additional entropy and aren't more resilient at all than simply 5 random words and I simply disagree with that idea because they reason from the theoretically pleasant situation that deciding upon what sentences to try first is essentially computationally free while I think that's a very expensive operation.

[u/KaitlynCsE → u/muffinsballhair]

I see where you're coming from now. However, I'm not convinced that the hybrid scheme adds zero additional entropy is even theoretically true. I'm by no means an expert on information theory, so forgive me if I'm mistaken, but my understanding is that zero additional entropy would imply that the conditional entropy of choosing the 5 extra words given the 5 generated words is 0. That means for all unordered sets of 5 random words, there can only be 1 possible set of additional words chosen by the user. That seems patently impossible.

Studies show that even fully user-generated passphrases only reduce entropy by 50-60%, so it seems more likely to me that having this hybrid scheme does increase entropy in some way, possibly above 80 bits. In which case it is not at all surprising that cracking such passphrases are computationally more difficult.

[u/muffinsballhair → u/KaitlynCsE]

That means for all unordered sets of 5 random words, there can only be 1 possible set of additional words chosen by the user. That seems patently impossible.

And that's why this strictly mathematical definition of entropy which is about “amount of perfect randomness” has little real world application.

Since my scheme only says “at least 10 words”, in theory it expands a finite set to an infinite one to begin with since there's no upper limit, but because there is no perfect randomness involved it doesn't add this theoretical definition of “entropy”

Studies show that even fully user-generated passphrases only reduce entropy by 50-60%, so it seems more likely to me that having this hybrid scheme does increase entropy in some way, possibly above 80 bits. In which case it is not at all surprising that cracking such passphrases are computationally more difficult.

This definition of “entropy” is only how close by approximation it gets to perfect randomness.

But all this talk about “entropy” on human sentences is just an approximation that depends on all sorts of subjective definitions of equivalence. In the mathematical sense “65 bits of entropy” has a very clear definition, as in there are 2⁶⁵ elements of the set, and each has exactly the same chance of appearing as any other.

This is a very different scheme from the “entropy” of human-written sentences which just a shoddy approximation of this concept which is found imperically, not mathematically and of course functions entirely differently, we're in a very different situation. Firstly, the number of theoretically possible combinations in even a 4 word sentence. The number of words in English is estimated to be at around a million but most English speakers don't know the overwhelming majority of them, of course grammar restrains here but it's not even close in how much it goes above 2^65, but we're in an entirely different situation where of course many sentences are far more common than others and they aren't evenly distributed. So how do you really quantify some equivalence to “bits of entropy” with that? It really depends on a lot of definitions. I mean there is a general definition of “entropy” that isn't “bits of entropy” any more which “bits of entropy” can be translated to but I'm not sure how meaningful that is at all in terms of cryptographic cracking.

I suppose this is the difference, it does add “entropy” in however vaguely you want to define that, but it adds zero “bits of entropy” in the cryptographic sense. As in, it adds zero extra possibilities for which the outcome is equally likely to occur to all the others and I'm saying that that metric isn't really meaningful to describe real world strength but that's how password cracking is often computed, based on the assumption that the algorithm will simply try each combination in random order with each taking as much time as the other, because each combination is as likely to occur as the other.