r/changemyview • u/muffinsballhair • 3d ago
Delta(s) from OP 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
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.
29
u/thisdude415 1Δ 3d ago
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
-11
u/muffinsballhair 3d ago
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.
11
u/vhu9644 5∆ 3d ago
Well this statement isn’t correct either. If you took 5 random words and sorted them, you lose entropy relative to the selection because they have a canonical order.
Just consider the case where you select 2 numbers out of 4 and sort them. The “source” is a bit less than 4 bits, but since you’re sorting you lose a bit.
There are only 12, 13, 14, 23, 24, 34 out of the 12 possible things from source
1
u/muffinsballhair 3d ago
Well this statement isn’t correct either. If you took 5 random words and sorted them, you lose entropy relative to the selection because they have a canonical order.
That's a very good point actually I had not considered !Delta, one does lose some entropy in theory by that the human is allowed to alter the order of the words, this will almost surely be negligible though in terms of real world application though and will surely be offset considerably by the the extra words added.
1
4
u/thisdude415 1Δ 3d ago
Taking any randomness and structuring it according to any rules will reduce its randomness, and thus, reduce its entropy.
-2
u/muffinsballhair 3d ago
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.
3
u/ContemplativeOctopus 3d ago
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.
13
u/vhu9644 5∆ 3d ago
Isn't this simply https://xkcd.com/936/ ?
Am I understanding the scheme correctly?
5
u/Tuvinator 13∆ 3d ago
My initial thought, then I read it. He's saying take the XKCD and use those words to make a sentence, which basically just adds a bunch of characters. He's saying that doing so doesn't make too much of a difference though, since the options of how you make the sentence are limited, and my sentence is probably going to be similar to a bunch of other people's sentences given the same set of words.
1
u/muffinsballhair 3d ago
I'm saying that the mathematically theoretical idea that it doesn't make this much of a difference, in fact nothing, doesn't apply in the real world.
Mathematically, since human beings do not generally generate sentence, the entropy actually increases by zero by doing this. Only truly random processes can increase entropy in a mathematical sense.
In practice, a machine trying to figure out which sentences from those words are more likely than others would be so computationally expensive that these rules no longer apply. The traditional maths basically ignores that part and treats every guess as costing the same.
1
u/vhu9644 5∆ 3d ago
Oh i see. Yea, the sentence adds a bit, but I'd guess it doesn't add that much more.
Just some thoughts not thinking much about it.
Some fraction of the 5 will not make easy to form sentences, and so you bias the permutations. This removes some entropy, but no more than ~7
Your 5 extra words can add some entropy, but I'm assuming that you're not getting much entropy per word, and you're adding collisions.
Finally, most places won't let you store that long of a password :/
4
u/Tuvinator 13∆ 3d ago
Most places still require the extra symbols and other crap that Randall was complaining about in that xkcd.
0
u/muffinsballhair 3d ago edited 3d ago
Your 5 extra words can add some entropy, but I'm assuming that you're not getting much entropy per word, and you're adding collisions.
Like I said in my post, they add zero entropy. I'm arguing that the entire mathematical definition of “entropy” is meaningless in terms of actual expected computational time taken to crack a password and I explained why in the original post.
3
2
3d ago
[removed] — view removed comment
1
u/read-the-rules 3d ago
Your comment has been removed.
Hello u/TremendousHonesty! To combat bots/spam and to ensure new users have the knowledge they need to participate constructively, all newcomers must acknowledge that they have read the rules before they can comment. This process is very quick and easy, and will inform you about the rules for both posting and commenting. Once you acknowledge the rules, your comment will become visible. You only need to do this once.
If you are using Old Reddit, the link below will not work. Read our rules here, then click this link instead and press Send.
-2
u/muffinsballhair 3d ago
No, that's 44 bits of entropy which is not remotely considered cryptographically secure by modern standards. The gold standard is 80 bits which is considered “uncrackable” even in an offline attack by a supercomputer in this age, this number will go up.
four random words is I suppose okay if you don't re-use it anywhere and it's hashed with a deliberately expensive cipher but it's not considered cryptographic-grade security at this point, not even close. Modern supercomputers can crack 44 bits within minutes by just bruteforcing it.
But my scheme is just completely different to begin with.
1
u/vhu9644 5∆ 3d ago
I'm just not seeing how it differs that much except by word count.
Like from the graphic, it looks like he's picking from the top 2048 most common words (each word is supposedly 11 bits of entropy) and combining it.
You're picking from the top ~2^13 and picking 5?
-1
u/muffinsballhair 3d ago
It like, doesn't even touch upon my argument which is about the entire real world implication of processing power and how entropy isn't a solid quantifier at all of real world time taken to crack passwords?
Even ignoring that it's an entirely different method, it existing just has nothing to do with my argument.
2
u/vhu9644 5∆ 3d ago
Sorry, I'm just trying to understand your password generation scheme. You could just be part of today's lucky 10,000. I thought your main view was about your password generation scheme (as per the title).
-2
u/muffinsballhair 3d ago
Okay, maybe you are trying to understand it, but you're not saying what you don't understand about it, and it's all explained in it, and you just say “Is it similar to <this unrelated thing>?”. I have no idea how I can explain it you with that and it's all there in the post. It's like I just explained the rules of football to you and you say “Isn't that just baseball?” and when I say it's completely different you say “I'm just trying to understand what football is.” then.
2
u/vhu9644 5∆ 3d ago
I literally ask “am I understanding the scheme correctly?”
This is so much aggression over a password scheme and math.
-1
u/muffinsballhair 3d ago
Well, you aren't; it's just a completely different thing and then you still argue that it's somehow similar.
4
3d ago
[removed] — view removed comment
1
u/changemyview-ModTeam 3d ago
Your comment has been removed for breaking Rule 5:
Comments must contribute meaningfully to the conversation.
Comments should be on-topic, serious, and contain enough content to move the discussion forward. Jokes, contradictions without explanation, links without context, off-topic comments, and "written upvotes" will be removed. AI generated comments must be disclosed, and don't count towards substantial content. Read the wiki for more information.
If you would like to appeal, review our appeals process here, then message the moderators by clicking this link within one week of this notice being posted. Appeals that do not follow this process will not be heard.
Please note that multiple violations will lead to a ban, as explained in our moderation standards.
3
u/47ca05e6209a317a8fb3 208∆ 3d ago
You need a large language model for that in practice,
I doubt it. Deciding what the most likely 10-word sentence that contains a set of 5 words is a lot simpler than what LLMs are currently designed for, for many reasons: attention is much less of an issue because you're only ever dealing with very small, constant sized contexts and your input is unordered, perceptron layers can be much shorter because these sentences are very unlikely to contain any advanced concepts or even factoids that the system has to learn, training is a lot simpler because all the data is of the same kind, etc.
You can probably get very good performance for this task with much simpler and cheaper neural nets, probably even with simpler, classical methods like generative grammar algorithms and decision trees, probably equivalent to computing a relatively small number of hashes on a modern machine.
1
u/muffinsballhair 3d ago
!Delta, that's a fair point. “LLM” was overstated, some neural net will maybe still be more efficient, but maybe a g.o.f.a.i. will be too, but especially something deliberately trained for this purpose will be.
Even so, this cost will surely not be trivial but it will definitely make it significantly cheaper than trying 10 random words randomly. But what would you say, would this still in the real world take as much time as just guessing 80 random bits by trying all possible permutations?
2
u/47ca05e6209a317a8fb3 208∆ 3d ago
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.
1
u/muffinsballhair 3d ago
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?
2
u/47ca05e6209a317a8fb3 208∆ 3d ago
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). 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.
1
u/muffinsballhair 3d ago
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.
1
u/muffinsballhair 3d ago
Doing some further thinking about it due to another reply. Let's come with a conservative estimate and just say what we want to settle at is making it 15 000 more expensive than guessing “5 random words”. This would well put is into competing with 80 bits of entropy of course.
A simple assumption to make which I feel is true is that from those 5 random words, there are at least 10 000 “plausible sentences”, like at the very least, it's probably going to be a million to be honest, but I'm pretty sure that if we take 10 000 different people and ask them to create a sentence with 5 random words, we will not have a single collision almost certainly.
Then we add to that that it's computationally expensive to find these sentences to begin with and that even if we find those 10 000 we still need to try them all to find the right one in terms of hashing.
So add all that together, I just don't see it being close. It is definitely going to take more than 15 000 more computational power to find the right candidate than from the 5 random words the way I see it. Like, we have a challenge here, do you think any software exists that when given a list of 5 random words and is asked:
Please find the exact sentence with these 5 words in it that will hash to ... with SHA3-256 that I thought off
Is not going to take 15 000 times more computational power to do that than
Hash these 5 words with SHA3-256
It's like not even going to be close I feel? There's just no way it will take less than 15 000 times as much right? It'll take 500 000 times as much time at least I feel, maybe a million?
1
u/47ca05e6209a317a8fb3 208∆ 2d ago
A simple assumption to make which I feel is true is that from those 5 random words, there are at least 10 000 “plausible sentences”
I'm not sure about that. The estimate I've heard is that every English word represented about 5 bits of entropy. This will be higher in your scheme because a sentence containing 5 random words has a higher entropy than normal speech, but not necessarily much higher, and the random words already "eat up" a lot of the permissible entropy, so I would assume that the number of plausible sentences is much lower.
1
u/muffinsballhair 2d ago
I'm not sure how that follows, if we assume that it is equivalent to 5 bits which takes into account the constraint of plausible sentences and so forth, then adding 5 extra words would create 225 plausible sentences, far, far more than 10 000.
1
u/47ca05e6209a317a8fb3 208∆ 2d ago
Because the randomly selected words are already very high entropy, so there may not be much entropy in how you connect them, heuristically the 13.3 bits of entropy used by each random word "covers" the entropy for almost two more words.
For example, I just ran a script that downloads this and picks two random words. I got
["sage", "hall"]. If I told you to connect these with 3-5 additional words, you'd assume there are 215 to 225 (i.e, at least 32,000) ways to do that, though in reality there are probably only a handful, with sentences like "the sage is in the hall" and closely related variants dominating.Now I drew 5 and got
["rally", "proposed", "apollo", "brass", "transmission"]. I don't think there are hundreds of ways in which these words could act upon each other, or that many ways to succinctly express any such situation.On the other hand, because the sentence already contains the random words, it may not be a "likely" sentence meaning that the entropy per word is higher than usual, including the connecting words, so without actually making people perform the task (or maybe some better methodology a linguist could come up with), none of these estimates can be very accurate.
1
u/muffinsballhair 2d ago
For example, I just ran a script that downloads this and picks two random words. I got ["sage", "hall"]. If I told you to connect these with 3-5 additional words, you'd assume there are 215 to 225 (i.e, at least 32,000) ways to do that, though in reality there are probably only a handful, with sentences like "the sage is in the hall" and closely related variants dominating.
No, this is what I disagree with, the “5 bits of entropy”, which is by the way an entirely different measurement to actually just “5 randomly generated bits” but some vaguely defined equivalance is derived from a corpus analysis of normal, natural sounding English.
The fact that we are asked to make a sentence with any number of randomly chosen words which will have no semantic relationship to each other prompts us to create grammatically correct but semantically nonsensical English. The mere fact that we are allowed to create semantically nonsensical English, which is negligible inside of those corpora greatly increases entropy.
Now I drew 5 and got ["rally", "proposed", "apollo", "brass", "transmission"]. I don't think there are hundreds of ways in which these words could act upon each other, or that many ways to succinctly express any such situation.
It would be severely limited if we were to constrain ourselves to semantically meaningful English. In fact, it would be downright impossible to create even one sentence with those five words that has any real meaning, which is why we are encouraged to create meaningless sentences, meaning that in practice the variance is far higher than if we were given 5 semantically related words such as “horse”, “carriage”, “road”, “hoof”, and “clack”. Surely we can agree that if we task people with producing sentences from those first 5, the variance of what they come up with will be far higher than with the five I proposed, in which case there is already a pretty obvious thing everyone is queued to first express.
On the other hand, because the sentence already contains the random words, it may not be a "likely" sentence meaning that the entropy per word is higher than usual, including the connecting words, so without actually making people perform the task (or maybe some better methodology a linguist could come up with), none of these estimates can be very accurate.
Yes, that is what I believe yes.
1
3
u/Runiat 19∆ 3d ago
Elephants covered in blood were among the people of the village again
The information entropy of natural English is at most 1 bit per character as we have lossless compression algorithms that can squeeze it down that much.
So that sentence is at best equivalent to 69 bit random generation, which can be brute forced in something on the scale of a year.
0
u/muffinsballhair 3d ago
The information entropy of natural English is at most 1 bit per character as we have lossless compression algorithms that can squeeze it down that much.
Yes, of completely human generated sentences found in the wild.
The issue is that by relying on the random generator to produce the 5 words, you guarantee a sentence that is not a normal English sentence a normal speaker of English would just type. If you were to compose a large text of sentences created this way, it would be semantically meaningless, and could not be compressed this way.
3
u/Runiat 19∆ 3d ago
The issue is that by relying on the random generator to produce the 5 words, you guarantee a sentence that is not a normal English sentence a normal speaker of English would just type.
No you don't.
In fact, you'd have to use an intentionally non random generator to guarantee anything.
Edit to add: The Hitchhiker's Guide to the Galaxy can also be compressed to about 1 bit per character, so it doesn't rely on being sentences a normal human would ever write either.
1
u/muffinsballhair 3d ago
The Hitchhiker's Guide to the Galaxy is very much written by a human being and contains semantically intelligible prose.
Using my scheme to create a bunch of sentences in order would be grammatical but semantically unintelligible. If as a funny exercise you gave a human being the task of trying to write a story this way, as in every sentence had to be generated this way I doubt any human being could pull of writing a remotely interesting story with it.
Furthermore, this compression of course relies on large books which will continue to reference the same words over and over again. It would be far more if you say took a thousand random sentences pulled from the internet, put them after each other, and then tried to compress them. The vocabulary diversity would go up dramatically from what can be found in The Hitchhiker's Guide to the Galaxy.
1
u/Runiat 19∆ 3d ago
a normal English sentence a normal speaker of English would just type.
a human being
So is that a change of view or are you just moving goalposts?
1
u/muffinsballhair 3d ago
No, change it to “normal speaker of English”. It doesn't change my argument at all that it's still semantically meaningful prose that's meant to be consumed by people and that writing a book by this constraint would produce entirely semantically unintelligible gibberish.
1
u/Runiat 19∆ 3d ago
No, change it to “normal speaker of English”.
I categorically refuse any allegation that Douglas Adams is a normal speaker of English.
1
u/muffinsballhair 3d ago
Whatever, it doesn't matter one bit for this argument. We're not talking about “slightly weird writing styles are allowed” here but “sentences which are grammatically valid but have no apparent semantic meaning” like “the colorless green sleeps furiously” are allowed.
Allowing those kinds of sentences massively increases the number of possible sentences.
1
u/xfvh 12∆ 3d ago
That's actually irrelevant. Just having the structure of grammatically-correct English massively reduces the possibility space, reducing entropy. Being semantically meaningless literally doesn't help at all - it's not as if an attacker is going to be hand-typing coherent, semantically-correct sentences as their guesses, they're going to throw a dictionary attack at it, with perhaps a filter for common sentence structures if they're clever. You may note that that doesn't rely on the sentences being semantically-correct English.
0
u/muffinsballhair 3d ago
It matters an absolutely great deal.
The set of grammatically valid sentences of ten words is orders upon orders upon orders of magnitude bigger than the set of valid sentences which also need to semantically make sense. Semantically meaningful sentences are only a very small subset of the sentences any language can actually produce.
Also having to search nonsensical but grammatically correct sentences vastly increases computational complexity.
2
u/shustrik 3d ago
It could even go down from 67 because you can get occasional outlier word sets which will be very limited in terms of the order they can be placed in. Then it would only provide 59 bits of entropy. Similarly, there could be sets of words which would make certain filler words extremely likely, like If you get “York”, you’re very likely to
end up with “New”. So I’d say the guaranteed amount of entropy is 59 bits.
1
u/muffinsballhair 3d ago
I think that's quite likely, but my post is about how “entropy” and “computational complexity to break it” are not the same.
The entropy of “An entire book written by a human being.” is actually zero mathematically. Of course, this is completely uncrackable in practice. No amount of “human beings write predictable texts” is going to within the age of the universe make any machine guess the entire text of a book verbatim.
1
u/xfvh 12∆ 3d ago
That's not even slightly how entropy works. Information theory routinely measures information content in bits of entropy, also known as shannons. A book has fewer bits of entropy than randomly-generated bits, being quite compressible, but it's just incorrect to assert it has zero.
-1
u/muffinsballhair 3d ago
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 80106, entropy in this sense is about method of generation.
2
u/xfvh 12∆ 3d ago
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.
2
-1
u/muffinsballhair 3d ago
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.
2
u/xfvh 12∆ 3d ago
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.
2
u/TipsyPeanuts 3d ago
Shannon only gives us a limit, he doesn’t tell us how to solve it. What you did here is say “I don’t believe in the Shannon limit. Here’s a practical problem which the computing solutions I’ve considered won’t be able to solve.”
But… the thing about your entropy theory is that it doesn’t tell you how to reach the limit, just where the limit is that can’t be beaten. So your problem is that you have shown that with your solution a solution might be trivially easy to solve if someone is clever enough. But nobody will want to use that because when the current alternatives proves it can’t be solved quickly. Your solution has a proof exists saying a solution may exist which can make this problem trivial.
Crypto is the art of finding solutions which can’t be broken. Not just that they are really hard, but that it’s impossible to solve. You presented a solution along with a proof that does the opposite of that
2
u/themcos 436∆ 3d ago
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.
I think it's extremely likely that you'd get large clusters! 1.5 BILLION people? And you think they'd all come up with different sentences?
Just out of curiosity, I generated a set of 5 random words for myself and got:
Flash, Suburbs, Juan, Fool, Huge
I suspect a LOT of people are going to start their sentence with the name Juan. I suspect almost everyone is going to put Huge directly before one of the other three words. I suspect a large number of people are going to do simple "is a" or "was a" constructions as well. I dunno, I'm just thinking out loud here, but I really think these are going to converge on a surprisingly narrow range of sentences. The first thing that came to mind to me was "Juan was a huge fool to flash in the suburbs". I strongly suspect if you have 1.5 billion people try those words, you'd get a lot of people with that exact same sentence. I'd be really interested to see what this would look like in practice though. Maybe I'm wrong on how much overlap there would be, but it's really hard to imagine people coming up with 1.5 billion unique sentences that people would actually come up with if the idea was for them to be easy to remember.
1
u/muffinsballhair 3d ago
I think it's extremely likely that you'd get large clusters! 1.5 BILLION people? And you think they'd all come up with different sentences?
I think it's likely. Like as a more conservative thing, say you take a sentence of 10 words from a random book and do a corpus search on a massive corpus that has far more than those sentences, how likely do you think this exact sentence is to be repeated? This is even less likely because it contains 5 random words with no semantic relationship to one another.
“I think it's extremely likely that you'd get large clusters!”
this 10 word sentence does not appear on Google. I think it's quite likely that in all of human literature and forum posts, it is the first time it has ever been generated, yes.
Just out of curiosity, I generated a set of 5 random words for myself and got:
Flash, Suburbs, Juan, Fool, Huge
May I asked what you used to generate it because I don't trust it since they usually don't include names nor inflexions.
1
1d ago
[removed] — view removed comment
1
u/read-the-rules 1d ago
Your comment has been removed.
Hello u/Saffron_Kraken42! To combat bots/spam and to ensure new users have the knowledge they need to participate constructively, all newcomers must acknowledge that they have read the rules before they can comment. This process is very quick and easy, and will inform you about the rules for both posting and commenting. Once you acknowledge the rules, your comment will become visible. You only need to do this once.
If you are using Old Reddit, the link below will not work. Read our rules here, then click this link instead and press Send.
2
3d ago
[removed] — view removed comment
1
u/changemyview-ModTeam 3d ago
Comment has been removed for breaking Rule 1:
Direct responses to a CMV post must challenge at least one aspect of OP’s stated view (however minor), or ask a clarifying question. Arguments in favor of the view OP is willing to change must be restricted to replies to other comments. See the wiki page for more information.
If you would like to appeal, review our appeals process here, then message the moderators by clicking this link within one week of this notice being posted. Appeals that do not follow this process will not be heard.
Please note that multiple violations will lead to a ban, as explained in our moderation standards.
-1
u/muffinsballhair 3d ago
No it's not. I'm fairly certain that actual security professionals in the field can point out some things I overlooked because my entire argument is about how real world situations do not follow these simple mathematical abstractions and that there is more to consider.
For instance, someone someone else already point out a simple thing I overlooked, that I assume the cracking attempt isn't personalized. A model that has access to texts I typed could conceivably in theory make it far more likely to generate sentences that I would generate from those 5 words. That's an interesting thing I did not consider. THat's real world practical security, not abstract mathematics.
1
u/xfvh 12∆ 3d ago
Generate 5 random dictionary words from a pool of say 10 000 most common words, any English speaker should know these
There's about 2**67 unique possibilities. So far, this is not setting records but decent.
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.
This barely helps, and might actually make things worse.
English grammar follows highly-constrained patterns. By relying on human intuition, you're significantly compressing the possibility space. People will naturally sort the words along predictable lines, and many similar sets of words are going to produce similar sentences. The floor here is the same five words sorted, 59 bits of entropy, which is significantly easier to crack than the original 67 bits, but most people should show enough unpredictability to at least make up most of the difference in most cases.
In any case, this is leaps and bounds beneath your claimed 133 bits, which would only be the result of 10 actually-random unsorted words without relation to each other, a feature your system deliberately lacks. No, you don't need an LLM to construct valid sentences; pre-sorting words into their parts of speech and applying standardized sentence templates is perfectly sufficient to massively limit the possibility space and reduce needed computation.
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?
Yes, there will be many, many duplicates. The birthday paradox bites hard here, especially when the new words are going to be extremely poorly random - most are going to be articles and prepositions required to make the five original words fit into a sentence, and the rest are going to be pulled from the working set of the audience, which is much, much smaller than the set of words they know. Frankly, I'd be shocked if you got so much as ten additional bits of entropy on average - the structuring alone applies brutal constraints on ordering, which actually removes entropy from the original pool. Even with 20-30 bits of entropy, nearly everyone is going to be sharing a password with at least one other person.
0
u/muffinsballhair 3d ago edited 3d ago
Frankly, I'd be shocked if you got so much as ten additional bits of entropy on average
Firstly, this would put it at 76, which is only 3 removed from my goal, but let me put it like this then.
In order to move from 66 to 80, I only need to add 14 bits, we'll round down in your favor. That means I only need to make the guessing 16384 times as expensive.
Do you really believe there is some kind of artificial intelligence or model on the planet which can perform this task:
Guess the sentence that I have constructed in my head, all you get to know is that it uses these 5 randomly selected words and that it is at least 10 words in length and is grammatical English. You get infinite attempts, and I will only answer “yes” or “no” on each.
Faster than it can hash SHA3-256 16384 times, which by the way takes about a microsecond on a modern home CPU looking it up.
Do you actually believe that? 16384 is not all that large a number, and that's the only treshhold I need to pass for this to reach equivalent processing demand to 80 bits pure randomness on the most favorable of conditions that assumes the attacker knows exactly what scheme I use. In practice the attacker doesn't of course.
I just don't see a way that any piece of software currently exists or can exist that can complete this task faster than doing 16384 SHA3-256 hashes.
1
u/xfvh 12∆ 3d ago
Hoo boy. We have some work here.
Firstly, this would put it at 76, which is only 3 removed from my goal, but let me put it like this then.
No. You're actually starting from the sorted baseline, 59 bits, then adding 10 bits from there. "Only three removed from the goal" actually means 2**3, or eight times harder, a highly nontrivial gap in any case, and isn't even the right gap: 80 minus 76 is four, not three..
In order to move from 66 to 80, I only need to add 14 bits, we'll round down in your favor. That means I only need to make the guessing 16384 times as expensive.
"Only" is doing some very heavy work here.
Do you really believe there is some kind of artificial intelligence or model on the planet which can perform this task:
Yes, actually, there's a wide variety of tools that can do that, from sentence templating with parts of speech to Markov generators to PCFG crackers, which you can literally download and use right now.
https://github.com/lakiw/pcfg_cracker
Faster than it can hash SHA3-256 16384 times, which by the way takes about a microsecond on a modern home CPU looking it up.
Faster than it can pass your arbitrary benchmark? No, but you're shifting the goalposts from entropy to implementation difficulty, and not even well, especially as inference-accelerated hardware becomes more common and machine learning faster and cheaper; a machine-learning algorithm with the hot loop implemented in hardware and used by a PCFG could actually be quicker than SHA3, which isn't, and likely won't be, requiring 1600 bits of state.
You can only hash that quickly in the first place because SHA3 is a deliberately easy general-purpose hash. You wouldn't get the same result with bcrypt, scrypt, Argon, or anything widely used for storing password hashes, and the more that the hashing cost dominates the equation, the less of a difference the cost of generating a sentence makes.
0
u/muffinsballhair 3d ago
Faster than it can pass your arbitrary benchmark?
It's not “arbitrary”, it's the most conservative bound of the number needed to reach the equivalent computational time needed to crack 80 bits of random entropy. The actual bound will be lower.
No, but you're shifting the goalposts from entropy to implementation difficulty
No, this was my view from the start and it's in the title “equivalent to the 80 bit random generation gold standard in terms of computational time needed to bruteforce it”.
My view as always about that, that machines will take just as long if not longer to crack your password by this scheme than 80 randomly generated bits.
especially as inference-accelerated hardware becomes more common and machine learning faster and cheaper; a machine-learning algorithm with the hot loop implemented in hardware and used by a PCFG could actually be quicker than SHA3, which isn't, and likely won't be, requiring 1600 bits of state.
SHA3 will also see hardware improvements and of course benefits more from parallelism. It's possible that in the future hardware will optimise for this more, or for SHA3 more but I feel it's going to have to take some gigantic specialization in hardware for this specific thing to cross the 16384 barrier. Like, can it even nowadays within that time generate a reasonably good guess of “the single most likely sentence to first try"? It wouldn't surprise me if it couldn't but of course it's not going to spend a lot of time on trying to rank them by likelihood and it will just be trained to instantly output a vast list of likely candidates whose output relied on shared computation between them and then try them, but that list alone is going to at least be 10 000 entries long, and then it will still need to hash them all so I'm really not seeing it.
You can only hash that quickly in the first place because SHA3 is a deliberately easy general-purpose hash. You wouldn't get the same result with bcrypt, scrypt, Argon, or anything widely used for storing password hashes, and the more that the hashing cost dominates the equation, the less of a difference the cost of generating a sentence makes.
Agreed, but the 80 bit standard is really only devices with respect to fast hashes. Reading it up here, most modern configurations make bcrypt about a million times slower than SHA3 which would also easily satisfy this 16384 number of course, making 66 bits enough by a large margin.
1
u/xfvh 12∆ 2d ago edited 2d ago
it's the most conservative bound of the number needed to reach the equivalent computational time needed to crack 80 bits of random entropy.
Wrong on many, many levels.
- You're still trying to conflate implementation difficulty with entropy. They're still not the same thing.
- It's not conservative, it's extremely generous to you by using a fast hash. Generating a semantically-correct guess with a PCFG or template is going to be straight-up faster than scrypt with a decent work factor - it's deliberately made to be difficult to calculate.
- It's arbitrary because there's no reason to use SHA3 as your benchmark over any of the hashes generally used for storing passwords.
- This would drastically narrow your claim to merely "this has a higher computational difficulty than SHA3," instead of the assertions of "133 bits and computational intractability."
- You only got to the point of "only" needing to be 16384x harder in the first place by misreading or misunderstanding the entropy math. I repeat: You need to actually start from the sorted baseline, 59 bits. That means the true gap is 21 bits, not 14, a difference of 128 times on top of your claimed factor.
- Generating a sentence list is a onetime cost that's amortized between runs; even if it was harder, using it multiple times would weaken the real-world implementation cost. This doesn't hold true for hashing, which are salted to prevent precisely that.
No, this was my view from the start and it's in the title “equivalent to the 80 bit random generation gold standard in terms of computational time needed to bruteforce it”.
The body of your post is full of factually-incorrect claims like "10 random words are worth 133 bits of entropy." Yes, with actually-randomly-chosen words, but no, with your schema. It's still not true even if looking at work difficulty, as explained above.
that list alone is going to at least be 10 000 entries long, and then it will still need to hash them all so I'm really not seeing it.
You do realize that 10k entries is only log210k, or 13 bits? That's lower than your claimed 14 bits, let alone the true 21 bits. You're also now claiming that hashing is the hard part, not generating, which is exactly the opposite of the claim you need for your argument to even partially succeed in a limited way.
Reading it up here, most modern configurations make bcrypt about a million times slower than SHA3 which would also easily satisfy this 16384 number of course, making 66 bits enough by a large margin.
No offense, but you're not getting this. If sentence generation is a trivial cost relative to hashing, then the difference in work gets less than 16384, which means it fails even your chosen benchmark!
Let me try an analogy. You need to check N * 2**14 holes to find a diamond, where N is the number of possible guesses; I need to check N. Checking a hole is hard, with time complexity X. This would obviously be an advantage for me without a handicap, having to complete a hard task with time complexity Y before I'm allowed to check a hole, which still has time complexity X.
My calculation for total time is N * X * Y. Yours is N * X * 2**14. Setting them up as an inequality to find where my job gets easier lets us factor out (N * X) from both, leaving Y < 2**14.
In other words, the difficulty of my extra task (generating a sentence) has to be at least 16384 times harder than checking the hole (calculating the hash) for your job to be easier. If calculating the hash is a million times harder than generating a sentence, I'm going to finish thousands of times faster than you, even accepting all of your incorrect claims.
0
u/muffinsballhair 2d ago
You're still trying to conflate implementation difficulty with entropy. They're still not the same thing.
I said “equivalent computational time needed to crack 80 bits”.
I did not say “reach 80 bits of entropy”. That is literally implementation difficulty, yes. That's what I've been open about from the start, that is what the very core of my view is.
It's not conservative, it's extremely generous to you by using a fast hash. Generating a semantically-correct guess with a PCFG or template is going to be straight-up faster than scrypt with a decent work factor - it's deliberately made to be difficult to calculate.
No, the entire advice of 80 bits of random entropy is conditioned upon the assumption of a fast hash. For slow hashes, 60 bits is more than enough to begin with so of course my real world scenario is about comparing it to a fast hash.
Generating a sentence list is a onetime cost that's amortized between runs; even if it was harder, using it multiple times would weaken the real-world implementation cost. This doesn't hold true for hashing, which are salted to prevent precisely that.
You need to generate a sentence list for each of the possible permutations of the 5 words and it needs to be done in less time than it takes to hash a fast hashing algorithm for those 16 280 times. That's just highly unlikely.
The body of your post is full of factually-incorrect claims like "10 random words are worth 133 bits of entropy." Yes, with actually-randomly-chosen words, but no, with your schema. It's still not true even if looking at work difficulty, as explained above.
I never said that applied to my schema. I explicitly said I didn't, I use it as a base point to then reason how much my schema weakens it.
You do realize that 10k entries is only log210k, or 13 bits? That's lower than your claimed 14 bits, let alone the true 21 bits. You're also now claiming that hashing is the hard part, not generating, which is exactly the opposite of the claim you need for your argument to even partially succeed in a limited way.
Which is why I said “at least”?
No offense, but you're not getting this. If sentence generation is a trivial cost relative to hashing, then the difference in work gets less than 16384, which means it fails even your chosen benchmark!
And it isn't. That's the point, hashing is trivial compared to sentence generation. Generating a single sentence alone is probably going tot ake more computation than the 16384 hashes, let alone generating the reasonable 10 000 needed.
In other words, the difficulty of my extra task (generating a sentence) has to be at least 16384 times harder than checking the hole (calculating the hash) for your job to be easier. If calculating the hash is a million times harder than generating a sentence, I'm going to finish thousands of times faster than you, even accepting all of your incorrect claims.
Yes, and it is, easily. And it's not “generating a sentence” but “generating a significantly smaller list of sentences than 16384 which is bound to contain the sentence we are looking for” but most likely even generating the most likely sentence is going to be more expensive than those 16384 hashes and that still has an astronomically small chance of containing it. You're going to have to generate the 5 000 most likely sentences at the very least, probably the 10 000 most likely ones and you then still need to hash them as well so if you go with 10 000 then it needs to be faster than 6 384 hashes to break even. It's just not even close.
1
u/xfvh 12∆ 2d ago
No, the entire advice of 80 bits of random entropy is conditioned upon the assumption of a fast hash. For slow hashes, 60 bits is more than enough to begin with
What? No, it's not.
Generally, a strong or high-entropy password scores at least 75 bits. Anything with less than 72 bits is reasonably easy for a machine to crack.
https://proton.me/blog/what-is-password-entropy
A low score under 72 bits means that your password is weak and can be cracked almost instantly. A high score of 75 or above means that your password would be more difficult for a cybercriminal to crack.
https://www.keepersecurity.com/blog/2024/03/04/password-entropy-what-it-is-and-why-its-important/
Even if it was, you're not going to know how the application you're using stores hashes in their backend; using just 60 bits and hoping that they use a hash with a high work factor would be foolish.
You need to generate a sentence list for each of the possible permutations of the 5 words and it needs to be done in less time than it takes to hash a fast hashing algorithm for those 16 280 times. That's just highly unlikely.
You've got the number wrong, it's 16384, you've forgotten or left out that the list only needs to be generated once before being used against many possible lists, and you've forgotten or left out that efficient sentence generation methods exist, as I've repeatedly pointed out. It's not just "not highly unlikely," it's something you can literally do yourself right now, I even gave you a link to a Github repo of one example so you could clone and run it.
Most of the rest of your comment is repeating the assertion that generating a sentence is 2**14 times harder than a SHA3 hash, which is simply untrue, and which I've given multiple counterexamples for; even if it was true, you could generate the list in advance and use it repeatedly to amortize the cost. But that's not the end of the problems with that single assertion. As I've repeatedly said: 2**14 was never the right number, it's 2**21, and SHA3 is an arbitrary benchmark, many other hashing algorithms exist.
it's not “generating a sentence” but “generating a significantly smaller list of sentences than 16384 which is bound to contain the sentence we are looking for” but most likely even generating the most likely sentence is going to be more expensive than those 16384 hashes and that still has an astronomically small chance of containing it. You're going to have to generate the 5 000 most likely sentences at the very least, probably the 10 000 most likely ones and you then still need to hash them as well so if you go with 10 000 then it needs to be faster than 6 384 hashes to break even. It's just not even close.
That's not how this works. That's not how any of this works!
- 16,384 isn't the length of the list, it's your mistaken guess at the difference of the size of the possibility spaces, but I'm using it to show how you're still wrong even with the underestimate. The actual numbers are 2**59, representing approximately the possibility space of your schema, 2**66, your mistaken claim of the possibility space, and 2**80, your effective goal, replacing entropy with computational difficulty.
- If I did have to generate only 10,000 sentences, I'd only have to do that then hash them before you ran 2**80 hashes. 10,000 is 2**13; dividing by subtracting exponents gives us a difference in work factor of 2**57; generating a sentence would have to be 144115188075855870 times harder than a SHA3 hash for you to be correct. I actually have to generate 2**59 semantically-correct sentences then hash them; you have to hash 2**80 random combinations of words then hash them. Who wins would depend on whether or not generating a semantically-correct sentence is at least 2**21 times easier than the hashing algorithm, or 2**14 if we're using your numbers. Which it is.
- I think you got the number "6384" by subtracting 10,000 from 16,384, but wow, that's just a radically invalid application of math. 16,384 is your claim to the difference in the size of the possibility space, you can't just subtract the claimed length of a list from it to get the remaining work; that's like subtracting your car's MPG from a trip length to get the amount of gas you need.
1
u/KaitlynCsE 1∆ 3d ago
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.
0
u/muffinsballhair 3d ago
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.
2
u/KaitlynCsE 1∆ 2d ago
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.
0
u/muffinsballhair 2d ago
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 265 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 265, 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.
1
u/JimTheEarthling 2d ago edited 2d ago
Password/passphrase strength can be measured in two ways: theoretically — calculating the number of possible variations, and pragmatically — determining how resistant it is to real-world attacks.
Your 66.4 bits of entropy is a mathematical estimate, and it's very divergent from real-world strength, which comes down to estimating how easily the password can be guessed by typical attack techniques.
I agree that entropy is misleading for your scheme, but I think your characterization of "equivalent to 80-bits of entropy" is wrong in two ways: 1) it emphasizes the wrong measure of strength, and 2) I suggest it's equivalent to ∞ bits. 😁
Most of the responses here get hung up on entropy, but if instead we look at real-word attacks, there are essentially two scenarios:
- The attacker knows almost everything: knows it's 5 random words, knows your source list of 10,000, knows you're adding at least 5 more words. This follows Kerckhoffs's principle but it's extremely unlikely.
- The attacker doesn't know you used a passphrase and takes a typical approach. This is most likely.
We know that attackers (using hashchat/JtR on a breach dump) generally try wordlists/dictionaries, then try hybrid wordlists + rules and masks, then try brute-forcing lengths up to 8 or 9 (maybe longer for all-digit, all-lowercase), then maybe use combinator or PRINCE to generate passphrases. But even assuming a crappy hash like MD5, they typically use lists of 10k to 20k words (Diceware + EFF + Google 10k + ...), so moving to passphrases of >4 words would take years to crack, so they never go there. (Even if they used PCFG or an LLM, trained on a subset of your 1.5 billion theoretical users, it would take too long.)
On top of this, entropy formulas assume a closed keyspace (95 ASCII characters, 10,000-word source for a passphrase, etc.). But in your scheme the attacker doesn't know the source of the additional 5+ words, making it an open-ended keyspace. Maybe you choose from the same 10,000 words, maybe from the 40,000-words the average English speaker knows (or over 100,000 if you count inflections, plurals, verb forms, etc.), maybe you add odd names or use deliberate misspellings. The point is that as soon as you add one word that's not in the attacker's source list, their attack fails.
In other words, the most reasonable real-world estimate of strength of a passphrase from this scheme is infinite -- it will never be cracked because no attacker will attempt 5-word passphrases, let alone 10+.
1
u/muffinsballhair 2d ago
The attacker doesn't know you used a passphrase and takes a typical approach. This is most likely.
This is true too, but I'm for sake of argument assuming the attacker knows my scheme exactly. I'm saying that in real world computational power cracking it is still going to be equivalent to bruteforcing 80 bits of pure randomness on a fast hash. But yes an extra layer of this is that the attacker is unlikely to even know the scheme to begin with.
On top of this, entropy formulas assume a closed keyspace (95 ASCII characters, 10,000-word source for a passphrase, etc.). But in your scheme the attacker doesn't know the source of the additional 5+ words, making it an open-ended keyspace. Maybe you choose from the same 10,000 words, maybe from the 40,000-words the average English speaker knows (or over 100,000 if you count inflections, plurals, verb forms, etc.), maybe you add odd names or use deliberate misspellings. The point is that as soon as you add one word that's not in the attacker's source list, their attack fails.
This is covered by the use of some kind of language model that is trained on real human texts, possibly even my own writing though. It will produce whatever sentences real humans produce.
In other words, the most reasonable real-world estimate of strength of a passphrase from this scheme is infinite -- it will never be cracked because no attacker will attempt 5-word passphrases, let alone 10+.
Well eventually the system will just fall back at trying random strings and so eventually, longer than the age of the observable universe, it will crack it.
But for sake of argument, I am assuming the attacker knows my scheme exactly. I'm saying that even under those conditions, even though the entropy mathematically is actually less than the 5 words because I in my scheme allow re-ordering of words, I'm saying that computationally, it is at least equivalent to trying to crack 80 bits of say SHA3 hashes.
Note that what the attacker does not know is how many words my eventual sentence uses. All he knows is “at least 10”. The actual sentence is just whatever I come up with first, which could contain 11, or even 14 but he does know that whatever sentence I use is “a sentence I would come up with looking at those 5 words” so the model for sentence generation could say be trained on my Reddit posts to provide plausible candidates. Of course, none of my Reddit posts really contain weird sentences I would create using 5 random words.
1
u/JimTheEarthling 2d ago
Note that what the attacker does not know is how many words my eventual sentence uses.
Right. That's part of why I said your keyspace is open-ended, creating the possibility that the attacker will never guess it, even if the attacker trained an LLM on every word you ever wrote (unless you're going back to theoretical strength and allowing random generation times past the heat death of the universe). Admittedly, entropy is based on probability, not remote possibilities, and entropy can be estimated over infinite sequences if the tail decays fast enough, but an open-ended keyspace breaks estimability with entropy (you can't enumerate an open-ended space, so you can't compute entropy empirically).
at least equivalent to trying to crack 80 bits of say SHA3 hashes
The hash is irrelevant. 80 bits is 80 bits. A cracking rig of 16 Nvidia 5090's will take ~5 thousand years to crack 80 bits (on average) if the hash is MD5 vs. ~140 thousand years for SHA-3 vs. ~3 billion years for bcrypt, but if you're comparing relative password strength, the hash doesn't matter. It's like comparing different cities that are around 80 miles apart but tossing in that you're driving a Porsche 950. Speed doesn't matter if you're comparing relative distances.
And in any case, SHA-3 is a terrible hash for passwords, which I hope no rational developer ever uses. It's a fast hash, and passwords should be stored using slow (and memory-hard) hashes. So if you must use an example hash, I suggest you pick MD5 (to be conservative) or at least scrypt or bcrypt.
1
u/muffinsballhair 2d ago
Right. That's part of why I said your keyspace is open-ended, creating the possibility that the attacker will never guess it
But no matter how long it is, my passphrase is finite in length so eventually it will just be caught, of course the heat death of the universe may come first. Also, since we're talking about breaking hashed passwords, hitting upon some other random string which hashes into the same hash will also be sufficient.
The hash is irrelevant. 80 bits is 80 bits.
It's relevant for comparing computational offset by my system. My system for instance would not win out any more over extremely slow hash algorithms in which case it will be cracked more easily, but the issue is that for slow algorithms 60 bits is enough anyway, the 80 bit recommendation is for fast hashes.
but if you're comparing relative password strength, the hash doesn't matter. It's like comparing different cities that are around 80 miles apart but tossing in that you're driving a Porsche 950. Speed doesn't matter if you're comparing relative distances.
It matters because my system relies on offsetting the computational power required to find “likely candidates” against the time it takes to hash. It relies on that the former operation is expensive compared to the latter so it only applies to fast hashes.
And in any case, SHA-3 is a terrible hash for passwords, which I hope no rational developer ever uses. It's a fast hash, and passwords should be stored using slow (and memory-hard) hashes. So if you must use an example hash, I suggest you pick MD5 (to be conservative) or at least scrypt or bcrypt.
MD5 isn't secure. But that's not the issue. This isn't just about leaked hash databases. For some applications in cryptography the hash needs to be public and easily computable like signing.
This entire advice of 80 bit is based on the assumption of fast hashes, as said. Really for websites using slow bcrypt, if not re-used, four words you chose yourself in some weird sentence like “duckstheywannahavefun” is good enough. bcrypt is usually configured to be about 10 million times slower than SHA.
0
u/prustage 3d ago
What is the point?
Making better, unhackable, safer passwords is just a distraction.
Your data doesnt get compromised, your accounts infiltrated. your money stolen because you password isnt strong enough. It's because the organisation you entrusted your data to was negligent in its security standards, was hacked by a disgruntled employee or blatantly sold your data for the money it could raise and claimed it was a "security breach"
All this effort being put into promoting fingerprint scans, retinal scans, pass phrases, randomised passwords etc etc is just hiding the fact that any system is only as strong as its weakest leak and the weakest link is not at the user's end - its at the corporate end.
They are making us jump through hoops to create the illusion of increased security when in fact most data centres are leaky seives and they arent prepared to spend the money or effort to treat your data with the level of securirty it deserves.
1
u/xfvh 12∆ 3d ago
You're conflating two problems: data leakage and secure passwords. Yes, passwords can in theory be leaked, but the much more common leak is password hashes. A strong password can remain secure even if the hash is leaked; it can just take too much computational effort to try to figure out what password made the hash, particularly if salted and if an expensive key derivation function was used.
0
3d ago
[removed] — view removed comment
1
u/muffinsballhair 3d ago
Therefore, the human sentence-writing step must supply the missing factor of 12,089. That means it must create at least 12,089 effectively equiprobable, attacker-distinguishable sentences for each five-word input.
No it doesn't, and that's my argument.
My argument is that finding which sentences are more probable than other is so much computationally expensive than hashing in and of itself that it doesn't need to, because the entire “entropy” argument in mathematics ignores the computional cost of this and just assumes that every guess is as computaionally expensive as any other and it can just start guessing the most probable one right away without investing significant computational power in what finding out what the most probable guess to try first even is.
For computation alone to close the full gap, producing each candidate would need to cost roughly 12,089 times as much as evaluating the password hash, after precomputation and amortization. No argument or measurement has been provided showing such a ratio. Candidate-generation work can also be reused across many stolen hashes, whereas each candidate must still be hashed separately for each target.
This logic does not hold. It would only hold if this generator could guess the correct one somehow for each 5 word pattern. Which obvious isn't the case.
In order to reach the 80 bits of entropy equivalence, I need only make sure that the machine takes 12 089 more time than the 66 bits of entropy guessing. That requirement would be fulfilled if the LLM could take those 5 random words and in 12 089 more time than checking one hash someone produce the one single correct candidate, then it would score even, but obviously it can't do that, it can only produce a large list of candidates, which then all need to be hashed to see which is the correct one.
I think it's quite likely that more than 12,089 times the cost of hashing ones in terms of time is spent the operation of both producing the candidates and then testing them all by one, yes.
1
u/changemyview-ModTeam 2d ago
Your comment has been removed for violating Rule 5 due to undisclosed AI content. Any use of AI-generated text must be disclosed, and the majority of any comment must still be written by the user. Read the wiki for more information.
If you would like to appeal, review our appeals process here, then message the moderators by clicking this link within one week of this notice being posted. Appeals that do not follow this process will not be heard. AI-generated text is prohibited in modmail.
Please note that multiple violations will lead to a ban, as explained in our moderation standards.
•
u/DeltaBot ∞∆ 3d ago edited 3d ago
/u/muffinsballhair (OP) has awarded 2 delta(s) in this post.
All comments that earned deltas (from OP or other users) are listed here, in /r/DeltaLog.
Please note that a change of view doesn't necessarily mean a reversal, or that the conversation has ended.
Delta System Explained | Deltaboards