3 ms·

Yeah, I did some rough calcs (after my anti-procrastination timer expired and I couldn't waste more time here, haha). If you have ~1000 words, ~10 bits/word, se

Yeah, I did some rough calcs (after my anti-procrastination timer expired and I couldn't waste more time here, haha). If you have ~1000 words, ~10 bits/word, seven words is 70 bits, and you lose about 12 of those by allowing reordering, and obviously 10 if you let them flub a word (via a parity word or storing 8 hashes). Seven words could be 48 bits with both kinds of variation allowed, or 58 or 60 with only one kind allowed. It might also help users remember to give them limited choice of code (pick one of 4 or 8 codes, say), which could cost you up to 2-3 more bits (on the paranoid assumption that users will pick according to predictable patterns). How much entropy you target depends on the system. If it needs to work as a crypto key, then you really need entropy, and good luck to you. (Maybe you have folks remember a piece and write a piece down, and use an expensive key scheduley thing to stretch the concatenated result out.) If it's for a login system where you can rate-limit, then, hey, even 32 bits is a lot if the attacker has to wait one second between tries. Just realized, if you use a parity word to recover from the user flubbing one word in a login system, you don't need to store the cleartext in order to correct the word they missed--you just redo the parity calculation on the remaining words to recover it. Yay. Also, to recover after a parity error in a seven-word phrase, you have to check seven different potential passphrases (assume word 1 was erased, apply parity to recover it, check, repeat), so I guess it takes another three bits off your security on top of the 10 of losing a word. On users just omitting a word all the time if the system lets them, I think 1) you require them to enter the full number of words every time, 2) if you see an error recoverable using parity, first you tell them which word was wrong and ask them to re-enter it, 3) if they still can't get it, you tell them what the word was (shoulder-surfer issues obv) and they have to type it. Then you minimize how much you show, you (try to) keep the user from slowly forgetting the passphrase one word at a time, and you make sure that entering your whole passphrase is the fastest way to log in. Though it's nice what weird stuff you can do while keeping a hashed cred DB, if it were a login code (not crypto key) and there were big wins to other aspects of the system to keeping the clear version around (for example, it let you do some significantly better error-tolerance strategy), I'm not sure you have quite the same level of obligation around a random token that you give out specifically for your app as you do around a password the user entrusts you with that they also use elsewhere.

darkmighty 12y ago
One of the greatest problem with login systems currently is not the entropy but the min-entropy [1] of the passwords. This random keyword approach greatly reduces this main threat so I'd say It's an acceptable tradeoff to have entropy for your average user and have a reliable system as you suggested. I don't think your parity method works for error recovery (it would probably work if it were a lot more complicated). If you store words are 10-bit values, each bit is independent from the other. Let's assume if a user makes a mistake the mistaken word value is uncorrelated with the true one. Then parity will only allow error detection, and your method of assuming erasures will simply generate N different correct word hypotheses. Interestingly, if you don't need permutation reliability (I don't think you'd need it anyway, people create meaning associating the words in the given order), you could use an ECC to achieve M-out-of-N passphrase securely, allowing both erasure and error correction! For example, with 4096 words, you could do 6-out-of-8 words with two errors (or 5-out-of-8 with erasures) by splitting the words in 4 3-bit groups and using a GF(8) Reed-Solomon [2] error correction ([8,5,4] code). The resulting system would have 5*12 = 60 bits of min-entropy. There's plenty of room to present some 8 choices of combinations to users and let them pick one, leaving 57 bits. [1] http://en.wikipedia.org/wiki/R%C3%A9nyi_entropy#Min-entropy http://en.wikipedia.org/wiki/R%C3%A9nyi_entropy#Min-entropy [2] http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_corr...
- twotwotwo 12y ago
  Getting to this late, but if I hear you right, generating a set of hypotheses was exactly what I was trying for with the parity. If you see a, say, 6-word input where the parity doesn't work out, you "erase" each of the six words and replace it with the parity of the other words, and check if the result is the user's password. It'd mean the user(/attacker) could make you do a 6 hash checks each time they tried to log in, so it'd cost you ~13 bits of security not just 10. And, yes, min-entropy is a really helpful concept here. Captures well that nobody's password is a good crypto key, but at the same time it deals with the attacks trying the really common overused passwords on a lot of accounts. Very cool that you could tolerate 2 errs/3 erasures and still have 60 bits with ECC if you trade off ordering. ECC and coding theory is one of those areas where I wish I had slightly more CS education so I could do more than just gawk at its power.

darkmighty 12y ago

One of the greatest problem with login systems currently is not the entropy but the min-entropy [1] of the passwords. This random keyword approach greatly reduces this main threat so I'd say It's an acceptable tradeoff to have entropy for your average user and have a reliable system as you suggested. I don't think your parity method works for error recovery (it would probably work if it were a lot more complicated). If you store words are 10-bit values, each bit is independent from the other. Let's assume if a user makes a mistake the mistaken word value is uncorrelated with the true one. Then parity will only allow error detection, and your method of assuming erasures will simply generate N different correct word hypotheses. Interestingly, if you don't need permutation reliability (I don't think you'd need it anyway, people create meaning associating the words in the given order), you could use an ECC to achieve M-out-of-N passphrase securely, allowing both erasure and error correction! For example, with 4096 words, you could do 6-out-of-8 words with two errors (or 5-out-of-8 with erasures) by splitting the words in 4 3-bit groups and using a GF(8) Reed-Solomon [2] error correction ([8,5,4] code). The resulting system would have 5*12 = 60 bits of min-entropy. There's plenty of room to present some 8 choices of combinations to users and let them pick one, leaving 57 bits. [1] http://en.wikipedia.org/wiki/R%C3%A9nyi_entropy#Min-entropy http://en.wikipedia.org/wiki/R%C3%A9nyi_entropy#Min-entropy [2] http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_corr...

twotwotwo 12y ago
Getting to this late, but if I hear you right, generating a set of hypotheses was exactly what I was trying for with the parity. If you see a, say, 6-word input where the parity doesn't work out, you "erase" each of the six words and replace it with the parity of the other words, and check if the result is the user's password. It'd mean the user(/attacker) could make you do a 6 hash checks each time they tried to log in, so it'd cost you ~13 bits of security not just 10. And, yes, min-entropy is a really helpful concept here. Captures well that nobody's password is a good crypto key, but at the same time it deals with the attacks trying the really common overused passwords on a lot of accounts. Very cool that you could tolerate 2 errs/3 erasures and still have 60 bits with ECC if you trade off ordering. ECC and coding theory is one of those areas where I wish I had slightly more CS education so I could do more than just gawk at its power.