5 ms·

I am pretty suspicious of my meat-based random phrase generator. A lot of the analysis on the entropy of correcthorsebatterystaple type passwords assume the wor

by rawnlq 10y ago

I am pretty suspicious of my meat-based random phrase generator. A lot of the analysis on the entropy of correcthorsebatterystaple type passwords assume the words are uniformly drawn from a vocabulary of whatever thousands. But if you have a large enough dataset of passwords I bet you can find the true (non-uniform) distribution of words people actually draw from and the entropy will be a bit lower. And if you further restrict it to be almost grammatically correct phrases it will be further lower[1]. Am I just paranoid? [1] RNNs can learn the distribution of your grammar easily http://karpathy.github.io/2015/05/21/rnn-effectiveness/ http://karpathy.github.io/2015/05/21/rnn-effectiveness/. The worry is that human generators will condition their random words too much. e.g., "correct" ooohh brain just did a adjective let's throw it a noun next "horse".

Klathmon 10y ago
I'd love to see a study done on this. I have a feeling that a "phrase" password has significantly more entropy than a "character" password of double or even triple the length (comparing a word equal to a character length wise). Even taking into account that a real sentence would need to follow a lot of rules, there are still a LOT of adjectives , a LOT of nouns, etc... I'm sure your "meat based" generator is more open to targeted attacks if someone knows your interests or something, but I have a feeling that it's still such a large pool that it's safe. And if you start to include somewhat nonsensical phrases like "correct horse battery staple" that even opens things up more. Include other things like spacing, capitalization, misspellings, made up words, or even prepending or appending a "traditional" password gets you even more still.
- rawnlq 10y ago
  I don't know how to answer the other parts of your comment, but your "double or even triple length" estimate might be off: From https://en.wikipedia.org/wiki/Entropy_(information_theory) https://en.wikipedia.org/wiki/Entropy_(information_theory) > English text has between 0.6 and 1.3 bits of entropy for each character of message. For comparison if you used a random string of alphanumeric characters it will have lg(26 + 26 + 10) = 5.7 bits per character. So if your password is drawn from an english corpus, if the low end of the estimate is correct, it's only about as strong as a random password 9 times shorter (or 4 on the high end). But of course we don't want a grammatical english password. Question is how much entropy does our meat-based random generator actually lose due to language bias compared to random word selection from an english dictionary (which I don't disagree with the analysis of as long as it's machine generated).
  - adzm 10y ago
    Beyond grammar, the addition of intentional errors or symbols or Finnegans Wake can help increase the entropy drastically too.
  - camtarn 10y ago
    I wonder how much extra entropy you can add by introducing an extra language or two? For instance, having a password like 'unterwasserboot-sparkle-mocidade-yogurt'. It seems like multilingual folks would be at a distinct advantage here ... at least until you forget which of the words in your password was in which language, and you end up with 'submarine-faisca-jugend-yogurt' instead :)
- Dylan16807 10y ago
  If you pick completely random words from the dictionary, you get about 17 bits per word. That's worth between two and three random characters. If you take random words and arrange most of them into a sentence then you drop slightly but you're still okay. If you add any common words like "the" or "was", don't include them in your word count. While you could boost it with spacing, capitalization, misspellings, etc. you gain very few bits for each modification you have to remember. You're better off tossing a random character or two onto your phrase, or simply making it a word longer.
leshow 10y ago
BIP39 is a spec for generating secure mnemonics (passphrases) with 128-bit entropy. I've written a version in rust, have a look. github.com/leshow/rust_mnemonic BIP39 generates 12 word or 24 word mnemonics usually. This was just a small project I did, and hasn't been checked for correctness. However, it should give you an idea of how you can generate word sequences.
deleted 10y ago
[deleted]
nommm-nommm 10y ago
This is where diceware comes in. You are supposed to pick whatever word you roll on the first try, no exceptions, for this very reason. Rolling until you get a word you "like" reduces randomnesss significantly. They even say you should use only use real, meatspace dice to generate passwords to be truly random, not pseudorandom. http://world.std.com/~reinhold/dicewarefaq.html http://world.std.com/~reinhold/dicewarefaq.html >There are some obscure words in both lists. If you passphrase includes a word you don't know, look it up in a good dictionary. Learning the word's meaning will aid you memory and your vocabulary. Of course there's exceptions when you should start from scratch. http://world.std.com/~reinhold/diceware.html http://world.std.com/~reinhold/diceware.html >Because some words on the diceware list are two characters or less, you can get a very short passphrase. If your passphrase, including the spaces between the words, is less than 17 characters long, we recommend that you start over and create a new passphrase. You should also start over if your passphrase is a recognizable English sentence or phrase. (These situations are extremely rare.) (If it were me I'd just keep adding more and more words if my password was 17 chars or less)
- ams6110 10y ago
  When I use diceware I use random.org for the dice rolls. They claim true randomness generated from atmospheric noise.
  - leni536 10y ago
    Getting your entropy for crypto purposes from a 3rd party is not a great idea.
    - Fnoord 10y ago
      '3rd party' is rather vague in this context. At least to me it is. Perhaps its more clarifying to say the usage of any networking required is out of the question. E.g. you should be able to use a diceware application on a laptop which is completely off the grid.
  - DanBC 10y ago
    Is that because Random.org is really random, or because your threat model doesn't include state level actors taking over random.org?
deleted 10y ago
[deleted]

by rawnlq 10y ago

Klathmon 10y ago

I'd love to see a study done on this. I have a feeling that a "phrase" password has significantly more entropy than a "character" password of double or even triple the length (comparing a word equal to a character length wise). Even taking into account that a real sentence would need to follow a lot of rules, there are still a LOT of adjectives , a LOT of nouns, etc... I'm sure your "meat based" generator is more open to targeted attacks if someone knows your interests or something, but I have a feeling that it's still such a large pool that it's safe. And if you start to include somewhat nonsensical phrases like "correct horse battery staple" that even opens things up more. Include other things like spacing, capitalization, misspellings, made up words, or even prepending or appending a "traditional" password gets you even more still.

rawnlq 10y ago
I don't know how to answer the other parts of your comment, but your "double or even triple length" estimate might be off: From https://en.wikipedia.org/wiki/Entropy_(information_theory) https://en.wikipedia.org/wiki/Entropy_(information_theory) > English text has between 0.6 and 1.3 bits of entropy for each character of message. For comparison if you used a random string of alphanumeric characters it will have lg(26 + 26 + 10) = 5.7 bits per character. So if your password is drawn from an english corpus, if the low end of the estimate is correct, it's only about as strong as a random password 9 times shorter (or 4 on the high end). But of course we don't want a grammatical english password. Question is how much entropy does our meat-based random generator actually lose due to language bias compared to random word selection from an english dictionary (which I don't disagree with the analysis of as long as it's machine generated).
- adzm 10y ago
  Beyond grammar, the addition of intentional errors or symbols or Finnegans Wake can help increase the entropy drastically too.
- camtarn 10y ago
  I wonder how much extra entropy you can add by introducing an extra language or two? For instance, having a password like 'unterwasserboot-sparkle-mocidade-yogurt'. It seems like multilingual folks would be at a distinct advantage here ... at least until you forget which of the words in your password was in which language, and you end up with 'submarine-faisca-jugend-yogurt' instead :)
Dylan16807 10y ago
If you pick completely random words from the dictionary, you get about 17 bits per word. That's worth between two and three random characters. If you take random words and arrange most of them into a sentence then you drop slightly but you're still okay. If you add any common words like "the" or "was", don't include them in your word count. While you could boost it with spacing, capitalization, misspellings, etc. you gain very few bits for each modification you have to remember. You're better off tossing a random character or two onto your phrase, or simply making it a word longer.

leshow 10y ago

BIP39 is a spec for generating secure mnemonics (passphrases) with 128-bit entropy. I've written a version in rust, have a look. github.com/leshow/rust_mnemonic BIP39 generates 12 word or 24 word mnemonics usually. This was just a small project I did, and hasn't been checked for correctness. However, it should give you an idea of how you can generate word sequences.

deleted 10y ago

[deleted]

nommm-nommm 10y ago

This is where diceware comes in. You are supposed to pick whatever word you roll on the first try, no exceptions, for this very reason. Rolling until you get a word you "like" reduces randomnesss significantly. They even say you should use only use real, meatspace dice to generate passwords to be truly random, not pseudorandom. http://world.std.com/~reinhold/dicewarefaq.html http://world.std.com/~reinhold/dicewarefaq.html >There are some obscure words in both lists. If you passphrase includes a word you don't know, look it up in a good dictionary. Learning the word's meaning will aid you memory and your vocabulary. Of course there's exceptions when you should start from scratch. http://world.std.com/~reinhold/diceware.html http://world.std.com/~reinhold/diceware.html >Because some words on the diceware list are two characters or less, you can get a very short passphrase. If your passphrase, including the spaces between the words, is less than 17 characters long, we recommend that you start over and create a new passphrase. You should also start over if your passphrase is a recognizable English sentence or phrase. (These situations are extremely rare.) (If it were me I'd just keep adding more and more words if my password was 17 chars or less)

ams6110 10y ago
When I use diceware I use random.org for the dice rolls. They claim true randomness generated from atmospheric noise.
- leni536 10y ago
  Getting your entropy for crypto purposes from a 3rd party is not a great idea.
  - Fnoord 10y ago
    '3rd party' is rather vague in this context. At least to me it is. Perhaps its more clarifying to say the usage of any networking required is out of the question. E.g. you should be able to use a diceware application on a laptop which is completely off the grid.
- DanBC 10y ago
  Is that because Random.org is really random, or because your threat model doesn't include state level actors taking over random.org?

deleted 10y ago

[deleted]