4 ms·

English has ~1 bit of entropy per character. Replacing a character with a similar symbol adds ~1.5 bits to that character (there aren't leetspeak substitutions

English has ~1 bit of entropy per character. Replacing a character with a similar symbol adds ~1.5 bits to that character (there aren't leetspeak substitutions for every letter, so I am being a little generous). Random symbol insertions between words adds ~5 bits per ~5 characters (10 numbers, their shift-codes, and the punctuation, average word length is ~5). If every letter of the password is randomly leetspeak that yields 50 bits. If symbols are inserted between each word (average of ~4 in 20 characters) that yields 70 bits, which is barely greater than the 68 bits of entropy per second equivalent of 300M TH/s

nickelpro 4y ago
Please explain the math behind a 26 letter alphabet having 1 bit per character
- dangerlibrary 4y ago
  I was also skeptical of this claim. It seems to come from Schneier's "Applied Cryptography" and assumes you are using whole words in the password. https://en.wikipedia.org/wiki/Entropy_(information_theory)#cite_ref-Schneier,_B_page_234_6-0 https://en.wikipedia.org/wiki/Entropy_(information_theory)#c... > English text, treated as a string of characters, has fairly low entropy, i.e., is fairly predictable. We can be fairly certain that, for example, 'e' will be far more common than 'z', that the combination 'qu' will be much more common than any other combination with a 'q' in it, and that the combination 'th' will be more common than 'z', 'q', or 'qu'. After the first few letters one can often guess the rest of the word. English text has between 0.6 and 1.3 bits of entropy per character of the message.[6]: 234
- ravi-delia 4y ago
  Grammatical English is an extremely restricted subset of all strings of characters. You can actually see for yourself that it's in the ballpark of a bit by going to a book, covering up a line, reading the context, and trying to guess the next letter one at a time. I get it 3/4 times, and would probably be down to 1/2 if I had to do it the right way. Consider the difference in entropy between this totally randomly generated password, consisting of 4 words each from a pool of 100,000: Correct Horse Battery Staple 4lg(100000) = 33 And this one of the same length where each character was chosen from a bank of 68: VIW&jubiHZUgBrFA8PI9Vy1E(%G 28*lg(68) = 170
  - seanhunter 4y ago
    French dude gets in trouble with the law and has his encryption cracked. Hackernews goes into an extended (and extremely interesting) thread about the entropy content of grammatical English. Probably not that different in terms of entropy content per character, though. That being said I don't understand your calculation of 4lg(100000). That seems like it can't possibly be correct. For starters it is entirely independent of the entropy content of the words in the dictionary. I could have 100000 strong random passwords of 1000 characters each in my dictionary. Could you explain this a bit, please because there's obviously something I'm missing? Edit: Aah I think I get it - the assumption is both me and the attacker know the dictionary so the entropy content of the words doesn't matter, the only thing that matters is the joint probability distribution of the combinations I'm choosing. Is that correct?
    - ravi-delia 4y ago
      Oh yeah, my assumption is that it's 4 words chosen from a 100,000 word dictionary. I honestly have no idea if it's a reasonable estimate but it stuck in my head from XKCD's original correct-horse-battery-staple comic. Of course in real life an attacker won't know necessarily the distribution you've pulled your password from, but by using the exact distribution in your calculations you have an ironclad lower bound.
      - GoblinSlayer 4y ago
        Diceware uses 7776 word dictionary, xkcd uses a shorter dictionary.
        ravi-delia 4y ago
        My God, where on Earth did I get 100,000? I mean that's a lot of words, plausibly more than I will ever hear. And how did it just cancel out anyway so I got roughly the right entropy? This will frustrate me until I understand how I fucked it so totally
  - Freaky 4y ago
- deleted 4y ago
  [deleted]
- AlexCoventry 4y ago
  > As an example of a numerical value, GPT-2 achieves 1 bit per character (=token) on a Wikipedia data set https://towardsdatascience.com/perplexity-of-language-models-revisited-6b9b4cf46792 https://towardsdatascience.com/perplexity-of-language-models... (I have not checked this claim, it's just what I found from googling "best large-language model character-perplexity 2023".) A token in a LLM is generally more than one character, so I would guess that the entropy is a bit lower than that. Shannon estimated it at 0.6-1.3 bits/character in 1950 (https://mattmahoney.net/dc/entropy1.html https://mattmahoney.net/dc/entropy1.html)
dangerlibrary 4y ago
> English has ~1 bit of entropy per character. I think the discrepancy here is coming from the fact that you are assuming the password is using English words, where others are assuming completely randomly selected characters from the set /[a-zA-Z0-9]/, plus some special characters, which yields substantially more than 1 bit per character.
michaelmrose 4y ago
You are confusing the fact that you can store in some encodings one character per byte, 8 bits, with a bit of entropy.
- ravi-delia 4y ago
  Grammatical English has about a bit of entropy per character (Wikipedia has it between 0.6 and 1.3). Most passwords won't be fully grammatical, or even close, but it's a decent worst-case bound for passwords chosen by English speakers to be memorable. If you have a specific scheme it obviously goes out the window.
  - michaelmrose 4y ago
    with all the password leaks I wonder if you could determine the likely scheme used by a given user by the leaks associated with their email address.

nickelpro 4y ago

Please explain the math behind a 26 letter alphabet having 1 bit per character

dangerlibrary 4y ago
I was also skeptical of this claim. It seems to come from Schneier's "Applied Cryptography" and assumes you are using whole words in the password. https://en.wikipedia.org/wiki/Entropy_(information_theory)#cite_ref-Schneier,_B_page_234_6-0 https://en.wikipedia.org/wiki/Entropy_(information_theory)#c... > English text, treated as a string of characters, has fairly low entropy, i.e., is fairly predictable. We can be fairly certain that, for example, 'e' will be far more common than 'z', that the combination 'qu' will be much more common than any other combination with a 'q' in it, and that the combination 'th' will be more common than 'z', 'q', or 'qu'. After the first few letters one can often guess the rest of the word. English text has between 0.6 and 1.3 bits of entropy per character of the message.[6]: 234
ravi-delia 4y ago
Grammatical English is an extremely restricted subset of all strings of characters. You can actually see for yourself that it's in the ballpark of a bit by going to a book, covering up a line, reading the context, and trying to guess the next letter one at a time. I get it 3/4 times, and would probably be down to 1/2 if I had to do it the right way. Consider the difference in entropy between this totally randomly generated password, consisting of 4 words each from a pool of 100,000: Correct Horse Battery Staple 4lg(100000) = 33 And this one of the same length where each character was chosen from a bank of 68: VIW&jubiHZUgBrFA8PI9Vy1E(%G 28*lg(68) = 170
- seanhunter 4y ago
  French dude gets in trouble with the law and has his encryption cracked. Hackernews goes into an extended (and extremely interesting) thread about the entropy content of grammatical English. Probably not that different in terms of entropy content per character, though. That being said I don't understand your calculation of 4lg(100000). That seems like it can't possibly be correct. For starters it is entirely independent of the entropy content of the words in the dictionary. I could have 100000 strong random passwords of 1000 characters each in my dictionary. Could you explain this a bit, please because there's obviously something I'm missing? Edit: Aah I think I get it - the assumption is both me and the attacker know the dictionary so the entropy content of the words doesn't matter, the only thing that matters is the joint probability distribution of the combinations I'm choosing. Is that correct?
  - ravi-delia 4y ago
    Oh yeah, my assumption is that it's 4 words chosen from a 100,000 word dictionary. I honestly have no idea if it's a reasonable estimate but it stuck in my head from XKCD's original correct-horse-battery-staple comic. Of course in real life an attacker won't know necessarily the distribution you've pulled your password from, but by using the exact distribution in your calculations you have an ironclad lower bound.
    - GoblinSlayer 4y ago
      Diceware uses 7776 word dictionary, xkcd uses a shorter dictionary.
      - ravi-delia 4y ago
        My God, where on Earth did I get 100,000? I mean that's a lot of words, plausibly more than I will ever hear. And how did it just cancel out anyway so I got roughly the right entropy? This will frustrate me until I understand how I fucked it so totally
- Freaky 4y ago
deleted 4y ago
[deleted]
AlexCoventry 4y ago
> As an example of a numerical value, GPT-2 achieves 1 bit per character (=token) on a Wikipedia data set https://towardsdatascience.com/perplexity-of-language-models-revisited-6b9b4cf46792 https://towardsdatascience.com/perplexity-of-language-models... (I have not checked this claim, it's just what I found from googling "best large-language model character-perplexity 2023".) A token in a LLM is generally more than one character, so I would guess that the entropy is a bit lower than that. Shannon estimated it at 0.6-1.3 bits/character in 1950 (https://mattmahoney.net/dc/entropy1.html https://mattmahoney.net/dc/entropy1.html)

dangerlibrary 4y ago

> English has ~1 bit of entropy per character. I think the discrepancy here is coming from the fact that you are assuming the password is using English words, where others are assuming completely randomly selected characters from the set /[a-zA-Z0-9]/, plus some special characters, which yields substantially more than 1 bit per character.

michaelmrose 4y ago

You are confusing the fact that you can store in some encodings one character per byte, 8 bits, with a bit of entropy.

ravi-delia 4y ago
Grammatical English has about a bit of entropy per character (Wikipedia has it between 0.6 and 1.3). Most passwords won't be fully grammatical, or even close, but it's a decent worst-case bound for passwords chosen by English speakers to be memorable. If you have a specific scheme it obviously goes out the window.
- michaelmrose 4y ago
  with all the password leaks I wonder if you could determine the likely scheme used by a given user by the leaks associated with their email address.