That only works against basic bruteforce attacks, if you are using hybrid attacks those passwords become easier to crack.
What people don't realize that professionals who crack passwords for a living use quite sophisticated techniques using known information about the target, common masks, and patterns makes cracking specific passwords easier than just bruteforcing them.
If you use a 300K words dictionary and know or can assume that the paraphrase will be constructed out of 3-5 words the password entropy isn't as large as just thinking this is a single case or mixed case alpha with say 12-16 characters.
When dealing with generic password your basic unit is a character so a 16 char password is made out of 16 units each of those has a specific search space single case alpha it's 26, mixed alpha it's 52, single alpha numeric it's 36 and so on.
Here you have 3-4 units each has a fixed search space and that's the dictionary you use, the search space can be even more restricted if we can assume certain things about the algorithm that generated the passphrase.
If we take the poem example we can assume that words will not appear more than once in the passphrase and that they might need to rhyme this alone can reduce the password entropy considerably.
If we take other examples like story based passphrases e.g. "the quick brown fox jumps over the lazy dog" then we can base our assumptions based on what we know of the English language for example that words like "the" will appear at least once in such sentences as well as take some estimates about how many verbs, nouns, and pronouns will appear on average in each sentence based on their common distribution which allows you again to reduce the search space considerably.
Passphreases are still great when you need to ensure that your passwords won't be broken in bulk when a breach happens because unless your account is admin@ijustgothacked.com you most likely won't be a target and those types of datadumps are still usually broken through basic dictionary, masked and cheap bruteforce attacks.
If you might be targeted directly or phished than passphrases might not offer any sufficient level of protection and could actually be weaker than an annoying mixed-alpha-num-special password.
That of-course will change if everyone will start using passphrases if you expect that 50% of your hashed passwords dump is passphrases you will adapt your password cracking techniques accordingly.
You make some good points, but I'm not sure that non-repeating and rhyming actually need to affect entropy at all. If you randomly generate a sufficiently large number, then break it up into smaller pieces (as the article suggests), and then apply some mapping algorithm that goes from those pieces to a poem, as long as every possible number would generate a distinct poem, you haven't lost any of your randomness. More specifically, constraints like "must rhyme" don't have to lose randomness, they just have to have an algorithm that can map every possible number to a distinct rhyming phrase, which can easily be done by adding words to the poem (e.g. if you have 300k possible words, don't use an 18-bit number to generate each word, use a smaller bit size and map the number to a subset of the dictionary. Now you can control which subset each number maps to, and the only penalty is adding a word or two to the poem.
The only real constraint here is every single number must map to a viable poem, and every single poem that can be generated must represent one and only one number. This means the poem is truly just an encoding scheme for the number, and as long as the number is sufficiently large and randomly generated, the poem should be just as secure as the original number was.
They generate a random 60-bit number and map it to a poem, so it has exactly 60 bits of entropy. If you want to double it, memorize four lines instead of two.
Their passwords do have 60 bits of real entropy, but the estimates in the article aren't based on how long it would take to brute-force a 60-bit password - according to the paper, that would only take 11.3 years on a single (2011-era) GPU, rather less than the 5 million they told the Washington Post. At a guess, they're counting the entire 79-bit poem pool they're culling the actual valid passwords from, on the assumption an attacker will have to test all of them. (The algorithm maps those 60 bits onto one-million-poem wide slices of the pool, and returns only the one that looks most like valid English.)
You can also memorize a sentence or a paragraph from a book that you love and own (which also can be used if you ever forget, or need to share the password with anyone)).
If you've read the paper you'll see they have an optimization process that produces passphrases which are more easily memorized, this process allows you to build a specific dictionary, so you can build a hash table which will include all the hashes of all of the possible passwords that can be created by this method.
The password cracking numbers they reference in their paper refers to bruteforcing LM passwords using a GPU by randomly generating characters, using a rainbow table increases that number by several orders of magnitude, using masks and dictionary attacks also increases that number considerably.
Other assumptions like knowing the maximum password length supported by the authentication mechanism you are attacking can make this even more trivial to attack because while their average input is 52 or so chars per poem if you are attacking a system that does not allow more than 36 chars for example you pretty much limiting the password entropy to a few thousands of passwords in their case.
This was an interesting read but it lacks quite a bit of stuff to work in the real world, just like the fact that a 2048 bit RSA keys are in theory almost impossible to factor doesn't mean you can't do that if you can assume allot of things about the key, when you can employ work reducers you start shedding quite a bit of that on-paper entropy.
The optimization attempts to pick the most easily-memorized poem out of a million possible poems for each 60-bit number. It doesn't reduce the entropy below 60 bits, it starts at higher entropy and reduces it to 60.
Obviously if the authentication doesn't allow the password to be entered then the scheme won't work. That's true of any password scheme.
No. A passphrase constructed from 5 words /randomly selected/ from a 300k word dictionary has approximately 2.4 × 10²⁷ possibilities or 90 bits of security. Trying all combinations is effectively impossible. Even assuming you happen to know the exact dictionary that was used.
And, I would be shocked if the poem constraint takes off more than a few bits of freedom. (Only 1 in 128 words are compatible for your rhyming pair? That's 7 bits. Compensate for it in full by just adding one more word to the passphrase.)
But it's not random they specifically select sentences that form a poem that is valid in the English language and is easy to memorize.
If you apply other restrictions like knowing that the authentication mechanism only allows X number of characters and assuming that the user will attempt to come as close as possible to that max but cannot pass it obviously it allows you to reduce the amount of valid poems even further.
People who are good at password cracking and social engineering can often reduce the amount of possible passwords for a specific target to about 10,000 with quite high accuracy, this is less math and rocket science and more common sense and psychology in this case.
they specifically select sentences that form a poem that is valid in the English language
How many possible rhyming couplets are there? I'll give you a hint, it's a huge number.
and is easy to memorize.
They do this by choosing from a million candidates. That reduces the key space by log2(1000000) ~ 19.9 bits. Compensate in full by increasing the key size by two more words.
social engineering
Irrelevant. The passphrases are selected by computer.
Comments
That only works against basic bruteforce attacks, if you are using hybrid attacks those passwords become easier to crack.
What people don't realize that professionals who crack passwords for a living use quite sophisticated techniques using known information about the target, common masks, and patterns makes cracking specific passwords easier than just bruteforcing them.
If you use a 300K words dictionary and know or can assume that the paraphrase will be constructed out of 3-5 words the password entropy isn't as large as just thinking this is a single case or mixed case alpha with say 12-16 characters.
When dealing with generic password your basic unit is a character so a 16 char password is made out of 16 units each of those has a specific search space single case alpha it's 26, mixed alpha it's 52, single alpha numeric it's 36 and so on.
Here you have 3-4 units each has a fixed search space and that's the dictionary you use, the search space can be even more restricted if we can assume certain things about the algorithm that generated the passphrase.
If we take the poem example we can assume that words will not appear more than once in the passphrase and that they might need to rhyme this alone can reduce the password entropy considerably.
If we take other examples like story based passphrases e.g. "the quick brown fox jumps over the lazy dog" then we can base our assumptions based on what we know of the English language for example that words like "the" will appear at least once in such sentences as well as take some estimates about how many verbs, nouns, and pronouns will appear on average in each sentence based on their common distribution which allows you again to reduce the search space considerably.
Passphreases are still great when you need to ensure that your passwords won't be broken in bulk when a breach happens because unless your account is admin@ijustgothacked.com you most likely won't be a target and those types of datadumps are still usually broken through basic dictionary, masked and cheap bruteforce attacks.
If you might be targeted directly or phished than passphrases might not offer any sufficient level of protection and could actually be weaker than an annoying mixed-alpha-num-special password.
That of-course will change if everyone will start using passphrases if you expect that 50% of your hashed passwords dump is passphrases you will adapt your password cracking techniques accordingly.
You make some good points, but I'm not sure that non-repeating and rhyming actually need to affect entropy at all. If you randomly generate a sufficiently large number, then break it up into smaller pieces (as the article suggests), and then apply some mapping algorithm that goes from those pieces to a poem, as long as every possible number would generate a distinct poem, you haven't lost any of your randomness. More specifically, constraints like "must rhyme" don't have to lose randomness, they just have to have an algorithm that can map every possible number to a distinct rhyming phrase, which can easily be done by adding words to the poem (e.g. if you have 300k possible words, don't use an 18-bit number to generate each word, use a smaller bit size and map the number to a subset of the dictionary. Now you can control which subset each number maps to, and the only penalty is adding a word or two to the poem.
The only real constraint here is every single number must map to a viable poem, and every single poem that can be generated must represent one and only one number. This means the poem is truly just an encoding scheme for the number, and as long as the number is sufficiently large and randomly generated, the poem should be just as secure as the original number was.
They generate a random 60-bit number and map it to a poem, so it has exactly 60 bits of entropy. If you want to double it, memorize four lines instead of two.
Paper: http://www.isi.edu/natural-language/mt/memorize-random-60.pd...
Their passwords do have 60 bits of real entropy, but the estimates in the article aren't based on how long it would take to brute-force a 60-bit password - according to the paper, that would only take 11.3 years on a single (2011-era) GPU, rather less than the 5 million they told the Washington Post. At a guess, they're counting the entire 79-bit poem pool they're culling the actual valid passwords from, on the assumption an attacker will have to test all of them. (The algorithm maps those 60 bits onto one-million-poem wide slices of the pool, and returns only the one that looks most like valid English.)
Hence my suggestion to memorize two such passwords.
You can also memorize a sentence or a paragraph from a book that you love and own (which also can be used if you ever forget, or need to share the password with anyone)).
Better pick an obscure book, I've read about cracking programs with books in their dictionaries.
If you've read the paper you'll see they have an optimization process that produces passphrases which are more easily memorized, this process allows you to build a specific dictionary, so you can build a hash table which will include all the hashes of all of the possible passwords that can be created by this method.
The password cracking numbers they reference in their paper refers to bruteforcing LM passwords using a GPU by randomly generating characters, using a rainbow table increases that number by several orders of magnitude, using masks and dictionary attacks also increases that number considerably.
Other assumptions like knowing the maximum password length supported by the authentication mechanism you are attacking can make this even more trivial to attack because while their average input is 52 or so chars per poem if you are attacking a system that does not allow more than 36 chars for example you pretty much limiting the password entropy to a few thousands of passwords in their case.
This was an interesting read but it lacks quite a bit of stuff to work in the real world, just like the fact that a 2048 bit RSA keys are in theory almost impossible to factor doesn't mean you can't do that if you can assume allot of things about the key, when you can employ work reducers you start shedding quite a bit of that on-paper entropy.
The optimization attempts to pick the most easily-memorized poem out of a million possible poems for each 60-bit number. It doesn't reduce the entropy below 60 bits, it starts at higher entropy and reduces it to 60.
Obviously if the authentication doesn't allow the password to be entered then the scheme won't work. That's true of any password scheme.
No. A passphrase constructed from 5 words /randomly selected/ from a 300k word dictionary has approximately 2.4 × 10²⁷ possibilities or 90 bits of security. Trying all combinations is effectively impossible. Even assuming you happen to know the exact dictionary that was used.
And, I would be shocked if the poem constraint takes off more than a few bits of freedom. (Only 1 in 128 words are compatible for your rhyming pair? That's 7 bits. Compensate for it in full by just adding one more word to the passphrase.)
But it's not random they specifically select sentences that form a poem that is valid in the English language and is easy to memorize.
If you apply other restrictions like knowing that the authentication mechanism only allows X number of characters and assuming that the user will attempt to come as close as possible to that max but cannot pass it obviously it allows you to reduce the amount of valid poems even further.
People who are good at password cracking and social engineering can often reduce the amount of possible passwords for a specific target to about 10,000 with quite high accuracy, this is less math and rocket science and more common sense and psychology in this case.
How many possible rhyming couplets are there? I'll give you a hint, it's a huge number.
They do this by choosing from a million candidates. That reduces the key space by log2(1000000) ~ 19.9 bits. Compensate in full by increasing the key size by two more words.
Irrelevant. The passphrases are selected by computer.
Do the actual calculations.