2

If future proof encryption is - in theory - possible it will require long password.

What are some of the strategies for storing or remembering very long - in this case rarely used - password?

For instance at one point Wikileaks shared the raw encrypted diplomatic cables with the community to prevent shutdown the password later leaked out. If I am right the password was very long string of random characters. Isn't storing such password securely equally challenging as storing the secret?

How about using a long verse from a Bible, the declaration of independence or similar "static" text that will be around unchanged in 100 years? What do you think of such strategy?

Community
  • 1
daniel.sedlacek
  • 934
  • 1
  • 8
  • 15
  • What do you mean by storing? Memorization techniques? | Memorizing a gigabyte file is obviously much harder than memorizing a passphrase. So I don't get that point either. – CodesInChaos Feb 18 '13 at 13:25
  • Note that, in your example of using text from the Bible, you're going to have problems if you're not using the same translation/source document. – Clockwork-Muse Feb 20 '13 at 00:42

4 Answers4

3

The virtue of a password is to make it possible for humans to remember it. If you want to store the password, then you are not talking about remembering; at which point you may forget this "long passphrase" business, which becomes just a nuisance. Store a random key which needs not be that long (16 bytes will be plenty in practice, the ultra-paranoid will go to 32 bytes, aka 256 bits, which is provably total overkill).

Also, a long verse from the Bible is a very poor passphrase because there are about 31000 verses in the Bible, thus making 31000 possible passphrases -- less than 15 bits of entropy, which is pathetic. As usual, it is not length which matters, but randomness; not what the password is, but what it could have been.

Community
  • 1
Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • Your point with Bible makes no sense, the encrypted file won't be labeled "encrypted with verse from bible, guess which one" – daniel.sedlacek Feb 18 '13 at 12:52
  • 1
    @daniel.sedlacek If a passphrase is expected then any reasonably smart adversary will try phrases from common books. The Bible is pretty much the go-to source for stuff like that. – Polynomial Feb 18 '13 at 13:02
  • You already suggested the Bible verse. So it does make perfect sense. It shows that size matters not, it's entropy that matter. If you have an algorithm/method to set your password over true randomness, there is a possibility that someone figures it out (you even revealed it here, for what we know). Thus, you can't rely on the obscurity of your method. Making hypothesis on the knowledge of the attacker is a mistake. – M'vy Feb 18 '13 at 13:04
  • Any half-witted attacker will see a file encrypted by you, google up your name, find this very question on Security.SE where you suggest using a verse from the Bible, and try just that. Assumptions like "the attacker will never think of that" rarely work in practice, and even when they do, they cannot be quantified (you cannot measure "smartness" of the attacker, whereas you can measure CPU power). – Thomas Pornin Feb 18 '13 at 13:34
  • guys I have mentioned Bible as an example, there is myriads of "static" text resources that wont change over time that can be used. If a go for a bible verse all I have to remember is a verse number and let's say an offset +- one letter or word or sentence from previous/next verse. Saying that I don't plan to use verse from Bible and I am not asking about security of using phrase from bible. I'm asking for a general advice on how to store long password. – daniel.sedlacek Feb 18 '13 at 13:45
  • 2
    @daniel.sedlacek if I ever use a piece of text from a book or similar I always deliberately missple words, concatenatewords or leave out caracters. That avoids attacks that simply feed in the book phrase by phrase. But it is better to make up weird phrases yourself *and* apply these techniques. – Maarten Bodewes Feb 18 '13 at 23:29
3

You'd be surprised how much entropy a relatively short passphrase can have.

Let's assume, for a minute, that 128-bit symmetric encryption was sufficient for the time frame you're interested in. That's a pretty safe assumption; in order to have even a one-in-a-million chance to guess the correct key in 100 years (which is the time frame of your linked question) would require a computer system able to calculate roughly 1.079e23 (that's 108 hexillion) possible keys per second. Even given the exponential pace of technology, it's extremely unlikely that even governments would gain access to that kind of computing power in the next 100 years. So, a hash of that length should be considered adequate.

Now, understand that hashing doesn't increase entropy; if there are only 1 million possibilities for a password used to generate a key, then it doesn't matter if the resulting key length is 32 bits or 256; all an attacker has to do, knowing the million possibilities, is simply try each of those instead of brute-forcing the entire keyspace. Therefore, to ensure that the strength of the encryption can't be sidestepped by guessing a weak password, we should have a passphrase that provides at least 128 bits of entropy. Assuming an entropy calculation of approximately 1.5 bits per letter when using common English dictionary words, and an average of 6.5 letters per dictionary word (by enforcing a minimum word size of 4 letters) the resulting passphrase would only have to be about 13 words long.

That's if the words chosen were completely random, and therefore by knowing each previous word you would still have no clue what the next word would be. It would be difficult, but not impossible, to memorize 13 words and to pass that on to your descendants; you might form a poem out of the words with a system inherent in embedding the actual words of the passphrase with the filler. If your passphrase was itself a meaningful sentence, it would have to be longer because the number of words that would have meaning after any given combination would be reduced, thus reducing entropy of the phrase. You could probably get away with a paragraph of a literary work. The more obscure, the better; pretty much any work of Shakespeare is out, as are any holy texts like the Bible, Qu'ran, Mahabharata, etc. A completely original statement would be best. Either way, if you make the sentence meaningful you need more words; probably closer to 20 or 25 words, not counting words with three letters or less.

KeithS
  • 6,678
  • 1
  • 22
  • 38
  • Great answer; however its incompatible with your accepted answer to the referenced question -- use a one-time-pad. A one-time pad cannot be derived from a 128-bit entropy passphrase to encode anything longer than ~128-bits and still benefit from the unbreakable properties of being a OTP. In fact, using a one-time pad generated from a ~128 bit passphrase will more likely be easily breakable with standard cryptographic techniques. – dr jimbob Feb 18 '13 at 19:47
  • 1
    True, but a OTP is not a "password". This question asked for advice regarding passwords, so it's a different question that I answered differently; I made the (safe) assumption of using 128-bit symmetric encryption, which would be safe enough for 100 years assuming the cipher primitive used does not demonstrate a weakness in that time. – KeithS Feb 18 '13 at 20:29
2

Remembering a high-entropy randomly generated passphrase in your head is fairly easy (relevant xkcd, though I consider secure for offline encryption attacks 100+ bits of entropy).

Sharing among a few trusted individuals helps ensure redundancy so it is kept in case you are hit by a bus or develop amnesia. Granted, this expands the pool of people who can leak the password or be forced to leak it (relevant xkcd). If you have many such passwords, it makes sense to keep an encrypted list of these passwords (only decrypted locally on trusted machines). It makes sense to have many such passwords, as you never want to reuse passwords especially on multiple entities (relevant xkcd).

For long-term future-proof encryption, I again suggest remembering a passphrase among trusted individuals, documenting a key-derivation function and using a well-documented standard for encryption like AES256 that expected Moore's law type increases in computational power will do nothing to attack over the period of ~100 years.

Regardless, do not use a passphrase plus some sort of home-made key derivation function to generate a one-time-pad (like the accepted answer). The one-time-pad only has guaranteed secure only when the one-time use pad is truly random and the output of an home-made key derivation function is NOT random. When a one-time-pad possibly has identifiable patterns (e.g., generated from iteratively hashing a passphrase broken up in some pattern like this answer ), these patterns can be exploited and potentially quite easily. This is creating your own cipher and should not be done unless you are a crypto-expert have presented your scheme to many other crypto-experts and noone has made any headway on it. Its much better to use something like AES that has so far proven resilient to attacks, than to hastily make up your own cipher.

Community
  • 1
dr jimbob
  • 38,768
  • 8
  • 92
  • 161
1

One way is to construct the password from an easy phrase, and remember both the easy phrase and the password itself.

For example, take a short password string. Run SHA-256 on it to get a hash. Now, chop the hash into two halves, and hash each half. Put the two new hashes side by side. Chop this hash into four quarters, hash each one, string them together. Repeat a few more times (you have to remember how many times). Put all of the hashes side by side, and you have a very long, random-looking password. To generate it, one must know the starting seed, and the exact algorithm of generation. The seed can be made easy to remember, and so can the algorithm (the above one isn't too hard to remember)

Note that that's just an example, you need to make your own algorithm, and keep it in your head. Nobody can brute force your head1 (and thus it's impossible for them to figure out your hashing algorithm and they probably won't know that you are using one), so they'll just have to try and brute force your encrypted file directly. With a seemingly random and long password, that is hard.

1 Unless they try to get it via social engineering, which is indeed possible. Simplest thing to do: don't talk about the algorithm to anyone (or the seed string). Understand that you are the only one who needs to know either of these. Additionally, if you are using the password as a password to some site (as opposed to an encryption key for a file), then you should make sure you don't fall for phishing or a similar attack.

Manishearth
  • 8,237
  • 5
  • 34
  • 56
  • 1
    "Nobody can brute force your head" is a wrong assumption. There are methods to get pieces of information from people and that's called "Social Engineering". – M'vy Feb 18 '13 at 13:07
  • 1
    @M'vy: I assumed that it was a given in this context, especially since I mentioned "keep it in your head". I am well aware of social engineering :) – Manishearth Feb 18 '13 at 13:16
  • 1
    Or "Rubber Hose Cryptography". Getting the password from a human who knows it doesn't have to be done with mind games, and it doesn't have to be pleasant. – KeithS Feb 18 '13 at 16:29
  • 1
    @KeithS: Good 'ol $5 wrench? Yeah, but at that point there's nothing that can be done :s If you want to make something so that it can be retrieved at any time by you, you have to be wary of that possibility. I don't think there's any way around the $5 wrench attack, except maybe time-locking a part of the password. – Manishearth Feb 18 '13 at 16:33
  • this looks like creating your own [key-derivitation algorithm](http://en.wikipedia.org/wiki/Key_derivation_function) – ratchet freak Feb 18 '13 at 17:18
  • The main issue I have with this is that the repeated hashing doesn't add entropy, and it adds a relatively small proof of work. The resulting hash, however long and random-looking, will only be as complex, at its core, as the passphrase used to generate it. You're also advocating creating a homebrew KDF, which I simply can't condone. – KeithS Feb 18 '13 at 18:04
  • @KeithS: Yes. But since the KDF is in your head and nowhere else, it will be much harder to guess. I agree that homebrew hashes have issues. But this is only if you have a system that uses the hash with various inputs. In this case, the hash is in your head, and it's used for a single input -- I don't see how it can be guessed. The effective complexity is quite high -- nobody knows what your KDF is, they don't even know if you're using one. – Manishearth Feb 18 '13 at 18:33
  • Basically, the only issue I see with homebrew hashes is that someone can reverse engineer them. However, that can only work if they have access to a place where they can actually test inputs against the hashing function. Here, there is no such place. Besides, using a rather long (but easy to remember) salt _along with_ the homebrew KDF ought to solve the OPs problem -- store a very long password very securely. – Manishearth Feb 18 '13 at 18:36
  • *Someone* other than you has to know the KDF, unless you plan on living more than 100 years from now. First off, you don't actually need *that* long a key as long as each bit of the key has "full entropy" (it represents at least one bit of entropy of the input message). Given the 256 bits of a single SHA-256 hash, *provided* each bit has full entropy and there's no shortcut to guessing plaintexts vs keys, brute-forcing the key would require interstellar travel because we won't get enough energy from the Sun to power a thermally-perfect computer long enough to try all keys. – KeithS Feb 18 '13 at 18:53
  • @KeithS: Yeah, I was just extrapolating; showing how you can make an not-too-hard to remember long password. Regarding "someone other than you" -- well, if they have to know the kdf, they have to know the key as well (basically they have to know the entire password). What's wrong with that? If you want someone else to have access, you give them access, and make it clear that the algorithm should be locked up securely in their mind (or in a secure physical location). – Manishearth Feb 18 '13 at 18:56
  • Second, your repeated hashing doesn't add entropy, as I stated; however long the resulting key is, it's no more complex than the input. Repetitive hashing forms a proof of work; a process with no known shortcut which produces a result that's easy to check. They're designed to make computers work harder, not people. – KeithS Feb 18 '13 at 19:03
  • Lastly, homebrew is unnecessarily risky. PBKDF2-SHA256 is a publicly-known, well-documented algorithm. It's undergone significant scrutiny by people much, much more knowledgeable about math and cryptography than you or I. As a result, you have the extreme advantage in using it of simply being able to tell your descendants to use it; "Remember that nursery rhyme I taught you when you were little? Run it through the PBKDF2-SHA256 algorithm iterated one hundred million times, and it will produce a key that decrypts a special message that will tell you where Grandpa's gold is buried." – KeithS Feb 18 '13 at 19:09
  • A homebrew requires you to teach your children the complex nested hashing pattern on top of the nursery rhyme they should plug in. – KeithS Feb 18 '13 at 19:10
  • @KeithS: Nesting adds more entropy than just applying a hash n times, since the nesting algorithm can be more complex. Again, the point wasn't to increase entropy, the point was to generate a hard-to-guess but easy-to-remember long password. And, again, the OP doesn't mention anything about wanting to "pass it on". Besides, it's not totally homebrew--it's an undocumented combination of well documented hashes. – Manishearth Feb 18 '13 at 19:13
  • The context of the question was future-proof security, linking to a question asking specifically about encryption strong enough to withstand 100 years of trying. – KeithS Feb 18 '13 at 19:19
  • @KeithS: ah, I see. I'll fix this one tomorrow or something then :) – Manishearth Feb 18 '13 at 19:23