5 ms·
Towards Reliable Storage of 56-bit Secrets in Human Memory [pdf]
- Scaevolus 12y agoMy attempt at reliable storage of large secrets: http://rmmh.github.io/abbrase/ http://rmmh.github.io/abbrase/ An example 60-bit secret: rolmangrionepolemp (mnemonic: "role man grinding one political employment"). A bit of a mouthful, but memorizable.
- case_sensitive 12y agocorrecthorsebatterystaple
- SAI_Peregrinus 12y ago"Clan accrue CIA marine slide + Matte Virgil auric libido booby" >128 bits of security (10 diceware words) not terribly difficult to memorize, easy to type. The + is just to make memorization easier, same with the capitalization. They can't hurt the entropy, and make it easier to remember. Pretty much all of my passwords that I can't store in a password safe (encrypted file) are of this sort. That's not a ton, but memorizing 5-10 10-word phrases is pretty easy. If you can memorize Jabberwocky, this sort of thing is easy.
- Scaevolus 12y agoThe uncorrelated nature of the words makes memorization harder. Using prefixes instead of precise words forgives minor memory slips and exchanging equivalent words. A good PBKDF (e.g. high difficulty scrypt) is good for stretching password security another 20-30 bits.
- sillysaurus3 12y agoWould you help me understand why this isn't closer to the security of a random 6 character password? It uses the first three letters from each word, and the first three letters of English words aren't random. I'm trying to read through the source code to understand it, but the Python version seems to be performing (slightly?) different steps than the JS version. Is the Python version an accurate description of your technique? At first glance, it seems like it could be a 60-bit secret, because a random 18 letter a-z password would be an 84-bit secret, so clearly you're taking the non-random nature into account somehow. But it's not clear to me exactly how it's 60-bit. The page you linked to does describe the high-level process, sort of, but it doesn't give an example, or explain "This is secure because..." so I figure I should ask you.
- colmmacc 12y ago> Would you help me understand why this isn't closer to the security of a random 6 character password? There are about 80 characters you can type, so a 6 character secret has 262,144,000,000 permutations (80^6) which is about 38 bits (2^38 is 274,877,906,944). 2^60 is much larger: 1,152,921,504,606,846,976 and its sixth root is 1024. So 1,024 memorable "characters" are needed. There are about 4000 unique word-based three letter prefixes: $ cut -c 1-3 /usr/share/dict/words | tr 'A-Z' 'a-z' | uniq | wc -l 4051 So 1,024 of those being associated with memorable words seems credible.
- Scaevolus 12y agoPrecisely. A sequence of prefixes is chosen, and then a mnemonic that fits the prefixes. Note that random 18-digit numbers have 59.8 bits of entropy.
- dTal 12y agoBear in mind "uniq" only removes adjacent duplicates. On my machine: $ cut -c 1-3 /usr/share/dict/words | tr 'A-Z' 'a-z' | uniq | wc -l 5089 $ cut -c 1-3 /usr/share/dict/words | tr 'A-Z' 'a-z' | sort | uniq | wc -l 3434 p.s. How do you do newlines on HN?
- Scaevolus 12y agoThe Javascript version is a relatively straight port from C, but uses the same algorithm as the Python. It picks a series of three-letter prefixes from a pool of 1024, then attempts to generate a mnemonic that fits it. I'll expand the explanation to give the security properties.
- jere 12y agoBesides length restrictions, why not just use the mnemonic as the password? It's no harder to memorize and, IMO, easier to type.
- Scaevolus 12y agoYou could, but I find entering long passwords annoying. I use a 9-letter (3 words, 30 bit) abbrase for my Android password, and find it's a tolerable balance between ease and security. There's no additional security in Abbrase-generated mnemonics.
- tunesmith 12y agoI wish I could use these kinds of passwords more often, but too many sites enforce the "must contain one number, one capital letter, and one punctuation symbol", oftentimes with a maximum password length.
- aftbit 12y agoAbsolutely insane. I'd like to see a browser plugin that will detect these sites and give you a form letter asking them to fix their security standards as well as the appropriate mailto link.
- avolcano 12y agoSomething like https://twofactorauth.org/ https://twofactorauth.org/ for password limitations would be great.
- case_sensitive 12y agoDon't want the passwords to be TOO strong, now do we? wink! wink! Also, it would be BETTER if people used two-factor authentication, maybe forcing the use of text messages to cell phones, so that they must use something they know and something they have. I wonder... if, maybe, we forced our users to select absurd, unnatural passwords they'll have no hope of remembering, and then maybe they'll have to call or text or e-mail for help almost every single time? wink! wink!
- jorgis 12y agoPractically every bank I do business with has these limitations. By contrast, my gmail password is 24 characters long, and contains capital and lowercase letters and punctuation. It makes me wonder what their back-end systems look like that they can't handle passwords longer than that.
- hyperbovine 12y agoOf course the human brain routinely stores memories which are vastly larger than 56 bits. The trick is in mapping those to passwords. For instance, if you went to grade school in the US I claim you can easily remember the following password: ipattfotusoaattrfwisonugiwlajfa. ("I pledge allegiance to the flag...") Song lyrics tend to work particularly well.
- WhitneyLand 12y agoThis is an insecure approach. Dictionary style attacks now can account for phrases from vast libraries of literature, pop culture, or anything else you're likely to remember.
- indubitably 12y agoBut the suggestion is to carry out a simple hash on the input phrase — one could use the second or third letter, for instance. (Or the first, second, third, first, second, third…) How could a dictionary-style attack predict all possible such arrangments?
- WhitneyLand 12y agoWhy not? The only limit on password cracking techniques is combinatorial complexity. This gives an overview: http://arstechnica.com/security/2013/10/how-the-bible-and-youtube-are-fueling-the-next-frontier-of-password-cracking/ http://arstechnica.com/security/2013/10/how-the-bible-and-yo...
- jorgis 12y agoBut do they take into account obscure maintenance manuals for foreign cars?
- mixedbit 12y agoA question is how much entropy a string like this has? Say you have 10 million English songs, if you always start a password with the first letter from a song, and choose the password to have between 20-30 letters, you only have about 26 bits of entropy in the password, which is trivial to brute force. You can increase the entropy by starting from a different word, or inserting random characters, but the entropy will never be close to the entropy of a random string of the same length.
- deepblueocean 12y agoVideo. Excellent presentation, for those who are interested: https://www.usenix.org/conference/usenixsecurity14/technical-sessions/presentation/bonneau https://www.usenix.org/conference/usenixsecurity14/technical...
- twotwotwo 12y agoHumans being the error-prone creatures we are, I wonder how it could work better to a longer word-based code, but allow for certain kinds of errors: for example, 1) word order doesn't matter, 2) it tries to correct a word not in the built-in word list to the "closest" word in it, 3) maybe you only need, say, seven of the eight words to be right to get in (then it might remind you of the real code). You can do a little calculation to see how many words you need to get to the desired number of bits then. Pretty different from passwords as we know them (#3 means you can't simply store a bcrypt/scrypt'd code--you could build something complicated tricks to square "allow one word wrong" with not storing plain PWs: each word is 10 bits and what you tell the user is really their secret code + a parity/ECC word, and correction happens before a convnetional password check--that rabbit hole goes deep, though.) But if all this gets average folks remembering more entropy than before, that makes it kind of interesting. On the study (which I admit just skimming), survey in 2010 suggested about half of Mechanical Turk users were located in the US (http://www.behind-the-enemy-lines.com/2010/03/new-demographics-of-mechanical-turk.html)--folks http://www.behind-the-enemy-lines.com/2010/03/new-demographi... who learned English at school would probably do better at memorizing a password in their native language. (I studied French many years in school, but I doubt I'd memorize a set of random French words as easily as English words.)
- harshreality 12y ago1 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.
- bayesianhorse 12y agoOr you could use the method of loci and learn a 10 character password in 5 minutes. I wrote a simple program which creates a random password and suggests keyword images...
- eksith 12y agoWould you be willing to share the program or source? That sounds like an interesting project.
- bayesianhorse 12y agoIt was rough kivy app, which I am not committed to publishing, currently. You can easily write your own, once you define a system for memorizing the characters. The idea is to use animal names for upper case characters, inanimate objects for lower case, and special mnemonics for other characters you want to use. A doormat for underscore, a bomb for exclamation mark etc. Then it's just a dictionary lookup. The tricky thing is to make the users understand how the method of loci works (Minecraft is a good medium for this), and that you need to repeat the password at least once per day until it is completely memorized.
- deegles 12y agoI wish there was a method to do PGP in human memory...
- rsync 12y agoI think it's much more interesting to explore hash algorithms optimized for memory. That is, md5 or sha256 checksum program that you could write from memory. That makes it possible to bootstrap a lot of use cases and OS loading and hardening scenarios - even disconnected from the network.
- minopret 12y agoFor sake of comparison and voice of experience, I actually do use fifty-six bit secrets for my various needs, as follows. The following secrets are at least fifty-six bits in size: * Nine "C isgraph" characters chosen uniformly at random. Those are lowercase, uppercase, digits, and 32 more typewriter symbols. This is the kind of password that I actually use for most systems where I frequently need to type the password myself. I am not making any claims about which kind of password everyone should use. * Ten alphanumeric characters chosen uniformly at random. Those are lowercase, uppercase, and digits. This is the kind of password that I use for systems where I may need to read someone the password over wired telephone service. That service has the advantage, as I understand, that eavesdropping on it is a Federal crime in the USA. * Five words chosen uniformly at random from the Diceware list of 7,776 words. This is the kind of password I use to lock each of my AES-encrypted master password files. In practice I have presumably degraded the security of my passwords despite my efforts. Here are two obvious ways to degrade the bit size of these secrets: * Failing to choose the elements in entirely unpredictable way. Rolling fair dice is OK. Using something built in a standard way for the purpose of generating passwords, such as KeePass, is OK. Mentally choosing combinations of characters is not OK, no matter how quirky you think your mind is. * Failing to keep every part of the secret completely concealed from everyone who does not own it. Letting people know that a password is a particular one of the above types is OK. Letting people see over your shoulder is not OK.