4 ms·

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
  > Correct Horse Battery Staple 4 lg(100000) = 33 I think you mean 66. More realistically, 52 for Diceware's 7776-word dictionaries, or 44 for XKCD's 2000 common words.
  - ravi-delia 4y ago
    Yep, I somehow internalized that there were 100,000 words (on reflection, I couldn't name a tenth of that in one sitting), but also halved the result, and the error canceled out a bit. Terrible.
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)

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
> Correct Horse Battery Staple 4 lg(100000) = 33 I think you mean 66. More realistically, 52 for Diceware's 7776-word dictionaries, or 44 for XKCD's 2000 common words.
- ravi-delia 4y ago
  Yep, I somehow internalized that there were 100,000 words (on reflection, I couldn't name a tenth of that in one sitting), but also halved the result, and the error canceled out a bit. Terrible.

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)