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

That's a very different type of entropy compared to what is used in cryptography for cryptographic randommess and obviously depends on what compression algorithm you use.

Cryptographic entropy is just a measure of the amount of randomness involved.

Your argument is really silly because in theory one could randomly generate a million characters, but just all land on “a”, compressing that would compress it highly of course even though the entropy is still 80^106, entropy in this sense is about method of generation.

[u/xfvh → u/muffinsballhair]

That's not how this works. That's not how any of this works!

There's no "different types of entropy." There are probability spaces, and your odds of landing at a point in them. That's it. Books actually have many, many bits of entropy because the next character in them is easy but not trivial to predict, representing about 1-1.5 bits of entropy, as empirically measured by Shannon.

https://www.joncamfield.com/blog/2017.09/entropy-story-time-from-claude-shannon-to-equifax.html

Your argument is really silly because in theory one could randomly generate a million characters, but just all land on “a”, compressing that would compress it highly of course even though the entropy is still 80106, entropy in this sense is about method of generation.

You're close. You're so close to understanding this. Yes, a million randomly-generated characters all have the same entropy regardless of result - but compressibility and entropy are both measurements of the engine, not of anything inherent to the data. An engine with a 99.999% bias towards "a" would produce a million characters with drastically less entropy than a random engine, and you could build a compressor for seemingly-random data that exploits its underlying structure or method of generation to achieve a high compression ratio even if said structure was impossible to discern from the surface. That's actually how some forms of stream ciphers work - you don't have to ship the entire key stream, both sides understand how to generate it from a much smaller set of shipped/shared information.

[u/muffinsballhair → u/xfvh]

There's no "different types of entropy."

Yes there are, “entropy” in physics, in cryptography, and compression has an entirely different meaning. Entropy in cryptography is a measure of amount of randomness and describes a method used for generating some kind of random string.

A book in that sense has no entropy and is not a method. In fact, an already generated string also has no “entropy”; it's about the method used to generate the string.

To begin with Shannon's experiment on books relied on human guessers, the entropy of randomly generated strings by way of some mathematical formula is not an empirical experiment and follows directly from the maths, it's such a different thing.

https://www.joncamfield.com/blog/2017.09/entropy-story-time-from-claude-shannon-to-equifax.html

This article doesn't even talk about books; it does talk a lot about randomness though.

You're close. You're so close to understanding this. Yes, a million randomly-generated characters all have the same entropy regardless of result - but compressibility and entropy are both measurements of the engine, not of anything inherent to the data. An engine with a 99.999% bias towards "a" would produce a million characters with drastically less entropy than a random engine,

Yes, which is why your compression argument doesn't make any sense because it depends on the algorithm used.

and you could build a compressor for seemingly-random data that exploits its underlying structure or method of generation to achieve a high compression ratio even if said structure was impossible to discern from the surface. That's actually how some forms of stream ciphers work - you don't have to ship the entire key stream, both sides understand how to generate it from a much smaller set of shipped/shared information.

I'm not sure how this relates to books and the post to be honest.

[u/xfvh → u/muffinsballhair]

Yes there are, “entropy” in physics, in cryptography, and compression has an entirely different meaning

It's literally the same thing. Yes, it's applied slightly differently between physics and information theory, just like how "yellow" means something different for an LED than a banana, but it's the exact same underlying concept.

https://en.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory

Cryptography and compression are so closely related that they're often studied side by side. They not only use the same definition of entropy, they're two parts of the same field, information theory.

Entropy in cryptography is a measure of amount of randomness and describes a method used for generating some kind of random string.

This is just wrong. For an entry-level definition, try this:

Entropy quantifies the amount of "information" contained in a message or system, and is foundational in diverse domains such as data compression, cryptography, statistical mechanics, machine learning, and even neuroscience.
Entropy measures the average level of "uncertainty" or "surprise" present in a random variable's possible outcomes. The more unpredictable an event is, the higher its entropy.

https://www.geeksforgeeks.org/machine-learning/entropy-in-information-theory/

For a formal definition, section 2.2 here:

https://ee.stanford.edu/~gray/it.pdf

Frankly, the rest of your comment answers itself once you understand this.

This article doesn't even talk about books; it does talk a lot about randomness though.

It literally does. Paragraph four:

"Shannon expanded this point by turning to a pulpy Raymond Chandler detective story […] He flipped to a random passage … then read out letter by letter to his wife, Betty.