4 ms·

1 and 2 are easy. Sort the words and use levenshtein distance to correct unrecognized words to the nearest valid word, prior to doing the password hashing. 3

1 and 2 are easy. Sort the words and use levenshtein distance to correct unrecognized words to the nearest valid word, prior to doing the password hashing. 3 is slightly more difficult; for 7-of-8 you'd have to store 9 hashes, one for the full list, and 8 more hashes resulting from removing one of the 8 words. What you gain in user friendliness costs you since you have to store several times the hashes, and you have to run multiple hash computations for each attempted login. It should be noted that 1 and 3 both reduce entropy significantly. A system that lets users omit one of the words in their passphrase will end up with users omitting one of the words all the time (why would you type more than you have to, particularly for passphrases of 20-40 characters?); the effective security of an 8 word passphrase with that system is worse than if it was a 7 word passphrase with no leeway for forgetting words. With a strict comparison but a passphrase of one less word, attacker then has to guess the right 7 words. By allowing a word to be forgotten, the attacker can guess any of 8 different 7-word passphrases and get in. Any system that reminds you of the full passphrase has to store the passphrase unhashed (or equivalent, like, with each sub-hash, storing a hint for the missing word), which is unacceptable.

Franciscouzo 12y ago
You could use Secret Sharing[1] for 3. [1] https://en.wikipedia.org/wiki/Secret_sharing https://en.wikipedia.org/wiki/Secret_sharing
jannic 12y ago
The system may only store a hash of the correct password, and then try to brute force it with the entered (slightly wrong) password as a starting point. This has several advantages: - Nearly as secure as only accepting the correct password (as an attacker could do the brute forcing as well, without help from the system) - Incentive for the user to remember and type the correct password, as logging in with an incorrect password takes longer - After successfully brute forcing the password, the system can remind the user of the correct one - without having to store it! Of course, this is not without disadvantages: - Much more load on the server, which probably can't be offloaded to the client without leaking the hash. (But perhaps it can, by offloading parts of the calculation to the client, and only doing the final comparison on the server.) - Depends on efficiently generating a list of likely passwords given an imperfect starting point - one needs to develop a model of likely user errors. Assuming 56 bit passwords, and 2^20 hashes per second, one could try all 4-bit-errors in 9s and all 5-bit-errors in 8min. But 'all possible n-bit errors' is not a realistic measure, as errors wouldn't be random. 56 bit would be about 10 random letters, and e.g. assuming that the only possible errors are omissions of letters, one could forget 3 letters and would still be able to login in about 1 minute. On the other hand, an attacker without any knowledge of the password would need ~2000 CPU years to brute force the password. (Of course the values should be tuned according to the intended security level.)
twotwotwo 12y ago
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
pflanze 12y ago
> Any system that reminds you of the full passphrase has to store the passphrase unhashed Store it encrypted (the same way you encrypt the payload; you can keep around a single copy of the encrypted full passphrase so you don't have to add it to any actual payload). Iff you have a match of one of the hashes, you can decrypt the full passphrase and hence show it.
colanderman 12y ago
> 3 is slightly more difficult; for 7-of-8 you'd have to store 9 hashes, one for the full list, and 8 more hashes resulting from removing one of the 8 words. What you gain in user friendliness costs you since you have to store several times the hashes, and you have to run multiple hash computations for each attempted login. Naw. Store one hash (of all 8 words, sorted), along with an (unencrypted) total function mapping words^7 → words, constructed in such a way as to maximize entropy. This can be implemented simply by storing an XOR of the (dense) index of all 8 words: XOR the 7 provided words together with the stored XOR to reveal the 8th, then hash all 8 to check the password. (Yes, storing the XOR of the word indices unencrypted reveals information – exactly one word's worth of information, which represents knowledge of the 8th word given knowledge of the other 7. i.e., this knowledge does not reduce the search space below that of 7 sorted words. Hence this same system can be used to remind the user of the full password given the partial password as well.)

Franciscouzo 12y ago

You could use Secret Sharing[1] for 3. [1] https://en.wikipedia.org/wiki/Secret_sharing https://en.wikipedia.org/wiki/Secret_sharing

jannic 12y ago

The system may only store a hash of the correct password, and then try to brute force it with the entered (slightly wrong) password as a starting point. This has several advantages: - Nearly as secure as only accepting the correct password (as an attacker could do the brute forcing as well, without help from the system) - Incentive for the user to remember and type the correct password, as logging in with an incorrect password takes longer - After successfully brute forcing the password, the system can remind the user of the correct one - without having to store it! Of course, this is not without disadvantages: - Much more load on the server, which probably can't be offloaded to the client without leaking the hash. (But perhaps it can, by offloading parts of the calculation to the client, and only doing the final comparison on the server.) - Depends on efficiently generating a list of likely passwords given an imperfect starting point - one needs to develop a model of likely user errors. Assuming 56 bit passwords, and 2^20 hashes per second, one could try all 4-bit-errors in 9s and all 5-bit-errors in 8min. But 'all possible n-bit errors' is not a realistic measure, as errors wouldn't be random. 56 bit would be about 10 random letters, and e.g. assuming that the only possible errors are omissions of letters, one could forget 3 letters and would still be able to login in about 1 minute. On the other hand, an attacker without any knowledge of the password would need ~2000 CPU years to brute force the password. (Of course the values should be tuned according to the intended security level.)

twotwotwo 12y ago

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

pflanze 12y ago

> Any system that reminds you of the full passphrase has to store the passphrase unhashed Store it encrypted (the same way you encrypt the payload; you can keep around a single copy of the encrypted full passphrase so you don't have to add it to any actual payload). Iff you have a match of one of the hashes, you can decrypt the full passphrase and hence show it.

colanderman 12y ago

> 3 is slightly more difficult; for 7-of-8 you'd have to store 9 hashes, one for the full list, and 8 more hashes resulting from removing one of the 8 words. What you gain in user friendliness costs you since you have to store several times the hashes, and you have to run multiple hash computations for each attempted login. Naw. Store one hash (of all 8 words, sorted), along with an (unencrypted) total function mapping words^7 → words, constructed in such a way as to maximize entropy. This can be implemented simply by storing an XOR of the (dense) index of all 8 words: XOR the 7 provided words together with the stored XOR to reveal the 8th, then hash all 8 to check the password. (Yes, storing the XOR of the word indices unencrypted reveals information – exactly one word's worth of information, which represents knowledge of the 8th word given knowledge of the other 7. i.e., this knowledge does not reduce the search space below that of 7 sorted words. Hence this same system can be used to remind the user of the full password given the partial password as well.)