15

Quoting Wikipedia:

A password with, say, 42 bits of strength calculated in this way would be as strong as a string of 42 bits chosen randomly[.]

Assuming that interpretation is correct, combined with knowledge that cracking a random 256-bit number is infinitely expensive nay physically impossible, how can a passphrase with 256-bits of entropy practically be constructed & memorized?

Community
  • 1
  • 5
    By writing a poem and using it as a passphrase? – Philipp Jun 29 '14 at 18:27
  • @Philipp How long does it need to be, and can it be reliably memorized? –  Jun 29 '14 at 18:38
  • 1
    A common word has 11 bits of entropy, so you need 24 words. Whether or not you can reliably memorize a 24 word poem you wrote yourself depends on you. – Philipp Jun 29 '14 at 18:48
  • This question might relate to this: https://xkcd.com/936/ – BlueCacti Jun 29 '14 at 21:04
  • You don't provide any motivation for why we'd want a 256-bit passphrase. In almost any situation I can think of, there is likely no practical need or motivation for a passphrase with 256 bits of entropy. Once you get past 80-128 bits of entropy, brute force attacks are no longer a possibility, and larger keys are a basically a proxy for a certain kind of conservatism -- yet it's very hard to imagine a situation where the cost-benefit analysis of a 256-bit passphrase would make sense. – D.W. Jun 30 '14 at 04:05
  • possible duplicate of [An alternative to traditional passwords: is there some merit to this idea?](http://security.stackexchange.com/questions/15850/an-alternative-to-traditional-passwords-is-there-some-merit-to-this-idea) – D.W. Jun 30 '14 at 04:09
  • See also http://security.stackexchange.com/q/10294/971, http://security.stackexchange.com/q/15850/971, and lots of other materials on this site. In the future you might want to do a bit more searching and researching, and show us in the question what you've considered. – D.W. Jun 30 '14 at 04:10
  • @D.W. This question is far beyond the possible duplicate and has narrower scope. The second link does not address the practicality of a 256-bit passphrase which is an impractical 20 diceware words. Assuming that 5 bits per grammatical word is correct (per linked linguistics question) and that the average easy sentence length is 8 words, 256 bits can be achieved with 6.25 sentences, right at the magic memory point: 7. –  Jun 30 '14 at 04:30
  • @D.W. The last sentence is rude and presumptuous. I've been very diligent in trying to understand password strength and came here instead of crypto.se because I thought this would be the best place to find practical advice for implementing a theoretically unbreakable password. If it weren't for the great answer and some great comments, I'd regret that choice. –  Jun 30 '14 at 04:39
  • @D.W. Also, I'd just like to point out that I did not snub your first comment. Somehow, I managed to ask a few hot questions today and have been very busy. Also, the message box does not work 100%. I disagree that it becomes impractical to break > 128 bits. It may be cost prohibitive, but for someone who wants to protect a large amount of assets or something they consider priceless, it is very reasonable. –  Jun 30 '14 at 04:47
  • 1
    @Gracchus, it's not a question of belief. Try doing the arithmetic to see what it would cost to do exhaustive brute-force space against a128-bit key. I think you might be surprised. (The phrase "very reasonable" isn't one I would use.) Anyway, I'm sorry to hear you found my comment rude and presumptuous. That wasn't my intent, and I don't think it's rude to communicate expectations for questions on StackExchange sites. See, e.g., http://meta.stackoverflow.com/q/261592/781723. – D.W. Jun 30 '14 at 05:05
  • @D.W. Yes, I've very much looked into it to an obsessive degree lately, and my crash course on crypto.se should reflect that, so it's clear I've done my homework. My comments never mentioned belief; further, for hard data, I prefer the practical authority https://www.tarsnap.com/scrypt/scrypt.pdf Something below 256 bits is the theoretical limit, and I don't think it impractical at all for a user to desire that sort of protection if a password change is impossible due to uncertainty. I have to say, your laissez faire philosophy regarding entropy is alarming relative to your rep. –  Jun 30 '14 at 05:29
  • 2
    Also note that your passphrase will never be stronger than the lenght of the password hash. So if the site uses a 128 bit hash to store your password anything above that will not help in preventing brute force against your password. - If they can brute force 128 bits of entropy they will not find your passphrase, but they will find a password that the system will accept as your password. – Taemyr Jun 30 '14 at 07:40
  • Related: http://xkcd.com/936/ – PlasmaHH Jun 30 '14 at 11:19
  • 2
    Since you quoted an answer doing a thermodynamic analysis, knoweth: It is very unlikely that even a 128 bit key will be broken by brute force. Given an annual 10^20J available _worldwide_ from uranium, and a total reserve of 10^20J each in natural gas and petroleum, _using up all fossile fuel plus an entire year worth of uranium production_ on our planet would allow to do 10^42 elementary operations. Which equals counting to one 139 bit num, or 2048x to 128bits (decrypting 1 block is >1000 elem ops). Assuming there exist 3 keys more valuable than your key _in the world_, this isn't happening. – Damon Jun 30 '14 at 15:00

2 Answers2

16

A common word of the English language has approximately 11 bits of entropy. That means a 256bit passphrase (passtext?) would require 24 words.

How could one make up a text of that length which is still easy to memorize? You could write a poem. The art of writing poetry and memorizing poems is not hard to learn. It doesn't even has to rhyme. In fact, not rhyming makes it harder to crack. Have fun!

However, we assumed that all words are completely random. In natural language, some words are more likely to appear after others. Poetry also usually conforms to certain rules and structures which further reduces the entropy. This answer on linguistics.stackexchange.com comes to the conclusion that the entropy per word in a poem goes down to about 5 bits per word, so you would need to write and memorize a poem of at least 52 words to get over 256 bits of entropy.

Community
  • 1
Philipp
  • 49,017
  • 8
  • 127
  • 158
  • 1
    Thank you! Do you happen to know how much grammar reduces entropy? –  Jun 29 '14 at 19:10
  • @Gracchus That's more of a question for a linguist. I am not sure, so I made a (I think pessimistic) guess of 99% in the answer. – Philipp Jun 29 '14 at 19:12
  • Also, does it have to be a poem? In other words, does a poem have some special characteristic that contains more entropy than another set of text with an equal quantity of words? –  Jun 29 '14 at 21:00
  • You could make a long sentence, but a poem might be easier to remember – BlueCacti Jun 29 '14 at 21:01
  • 3
    @Gracchus: a poem (or any text that is easy to remember) contains *less* entropy than an equal number of words selected at random, and possibly less than prose although I wouldn't bet on it. Any internal structure or "rules" that make certain patterns more likely than others, is a reduction in entropy. This is more or less the same as the fact that a pronounceable series of letters has less entropy than a random sequence of any letters. However, 24 words is a very short poem, so you can compensate for quite a lot lower entropy if you just keep going. – Steve Jessop Jun 30 '14 at 00:52
  • @SteveJessop Indeed. I have asked a follow up question on linguistics.se to help narrow it down. http://linguistics.stackexchange.com/questions/8480/what-is-the-entropy-per-word-of-random-yet-grammatical-text –  Jun 30 '14 at 00:59
  • Now for the next question: how to type in a 37-word poem into a prompt discreetly and in a timely manner without typos in a variety of environments :-) – Thomas Jun 30 '14 at 01:03
  • "Write a poem" is pretty bad advice here. Assuming anything remotely resembling grammatical coherence, not to mention the kind of word-association that would lend itself to poetry and to memorization, the conditional probability distribution for the Nth word is going to be **highly** focused on a relatively small set of words, conditioned mainly by the position N-1, N-2, and perhaps N-3 words. – R.. GitHub STOP HELPING ICE Jun 30 '14 at 06:45
  • @Gracchus Incorporated the findings of that question on linguistics.stackexchange.com into mine. – Philipp Jun 30 '14 at 07:36
  • @Philipp Thank you so much Philipp! And thank you so very, very much for setting off the dominoes to create such a complete, canonical solution for an uncrackable pass! This is now the standard that I will use and recommend. Can't thank you enough! –  Jun 30 '14 at 07:41
  • @R.. "Write a poem" is exelent advice for creating a memorizable passphrase of 256 bits of entropy. It dilutes the entropy a lot, but enhances your capacity to remember by far more. Typing the passphrase is going to be annoying as hell though. – Taemyr Jun 30 '14 at 07:46
  • I wonder if certain hybrid approaches might not work better (although I'm not sure about the exact maths regarding how we'd calculate the entropy). E.g. I'm thinking along the lines of - picking one or more words from a 2nd / 3rd language (for the multi-linguals among us), throwing in one "uncommon" word, using an alphanumeric sub-password as one of the words, or using nonsensical words here and there. The question is whether these would win out (in terms of human memory) over longer, simpler passphrases. I'd love to see some actual numbers. – Daniel B Jun 30 '14 at 09:16
  • One thing to note is that you're going to encounter far more systems which won't accept your password. The average language has about 5-6 characters per word, so a 52 word poem would be 260-312 characters (more if you have some punctuation). I doubt there are many systems that support that long passwords for users. You also have to take into account that a 300 character password takes about 1 minute to enter, which you'll have to do without mistakes. You're better off making a 52 word poem with lots of punctuation and numbers, then take the first character of each word. – Nzall Jun 30 '14 at 09:38
  • @NateKerkhofs You probably don't want to be typing that master passphrase (it *is* your master passphrase, right? if you're remembering one poem per website you frequent, well, hats off) into a website anyway. If you're looking for that level of security a password manager is almost certainly in order (but still, a pain to type in either way). – Thomas Jun 30 '14 at 11:53
  • Even if you're using it as a master password for your password manager, you might run into the limits of that password manager as well. Unless Lastpass, Keepass, 1Password and all those other password managers allows a 300 character master password. not to mention that entering a 300 character password on a mobile device could get painful. – Nzall Jun 30 '14 at 12:24
5

Such a question would prove that the person asking it has become serious about the strength of their passwords, at which point you simply should start using a password manager. Seriously strong passwords, without memorizing a bunch of poems.

Andrew Hoffman
  • 1,997
  • 15
  • 17
  • Yes, I definitely use a password manager for low value passwords. This question is for maximum value passwords where the risk from a single point of failure, online storage, or even local storage is unacceptable. –  Jun 29 '14 at 20:12
  • @Gracchus then get really good at memorization. :P https://www.youtube.com/watch?v=oNrWgjh9tnU – Andrew Hoffman Jun 29 '14 at 20:42
  • 3
    I take it that one should use a strong password for one's password manager, so I don't think that the request to memorize "a passphrase" (that is, one) of this kind is dealt with by the password manager :-) – Steve Jessop Jun 30 '14 at 01:19
  • 1
    @SteveJessop But password managers are more likely to allow multi-factor authentication, which should be more secure than just a password, and more practical too if you're trying to create, memorise and type something like long. – Bob Jun 30 '14 at 06:18