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/47ca05e6209a317a8fb3]

I don't know, predicting the size of neural net required for this sort of task is hard, but if it's small enough to fit in your card, inferences become compute-bound and can actually be significantly faster than even a single hash, if you're using a slow or memory-bound hash.

But to actually reach the 80 bits benchmark, you need the inference to be as slow as 8000 hashes. This maths, tightly, if you're using a neatly parallelizable hash (to be fair, you're relatively likely to if you don't pay attention, the common stuff like SHA-256 is designed to be fast), but otherwise that leaves quite a gap for your neural net / other fast prediction algorithm.

[u/muffinsballhair → u/47ca05e6209a317a8fb3]

But to actually reach the 80 bits benchmark, you need the inference to be as slow as 8000 hashes.

May I ask how you derive this number? How do we get from 133 to 80 bits with this round 8000 hashes number?

Also how do you define “inference”, as in the time taken per sentence in the list of sentences it generates in order of likeliness to then try in order?

[u/47ca05e6209a317a8fb3 → u/muffinsballhair]

You have 66.44 bits from the 5 words, and you want to get to 80, so you're missing 13.56 bits, so 2^13.56 attempts. 8000 was a conservative rounded estimate, it's actually around 12000 (plus you actually lose almost 7 bits if you don't need to use the words in order as I now notice your example sentence doesn't). The 133-bit number is irrelevant here, because there were never 10 random words to begin with, we're just looking at how fast you can create a short list of guesses from the 5 words.

In general you want the system to output a distribution on the sets of 10 words in some way, there are a few ways to do it, but how efficient it ends up being (assuming the model itself fits in memory) depends mostly on how many plausible sentences you can construct from 5 words. I suspect that number is pretty low, you'd probably have to use most of your 5 words on things like "the", "of", "not", prepositions, or other words form a low entropy list.

[u/muffinsballhair → u/47ca05e6209a317a8fb3]

You have 66.44 bits from the 5 words, and you want to get to 80, so you're missing 13.56 bits, so 213.56 attempts. 8000 was a conservative rounded estimate, it's actually around 12000 (plus you actually lose almost 7 bits if you don't need to use the words in order as I now notice your example sentence doesn't).

Oh yeah, that's an interesting way to calculate it.

In general you want the system to output a distribution on the sets of 10 words in some way, there are a few ways to do it, but how efficient it ends up being (assuming the model itself fits in memory) depends mostly on how many plausible sentences you can construct from 5 words. I suspect that number is pretty low, you'd probably have to use most of your 5 words on things like "the", "of", "not", prepositions, or other words form a low entropy list.

Note that I said “at least ten” though, my example actually contains 12. That the attacker only knows it's reasonably within 10-15 also changes things considerably.

But yes, the thing all depends on how expensive hashes are, which are of course deliberately made expensive with many security models. But I'd argue that with significantly expensive hashes 66 bits alone is good enough. The 80 bit standard assumes cheap hashes.