Is it safe to publish something encrypted with a password if you make it insanely difficult to crack?

Question

Let's say you have a very important private key that you don't want to lose. You think of posting it to http://pastebin.com/ but then relize that elimanates the point. So you think of encrypting with the help of password key derivation, but that normally isn't enough. You know this because similar algorithms are used to protect passwords on servers, and when those hashes get leaked, although the passwords are safe for a time, the server still tells everyone to change their password. This implies that it isn't safe for them to be public for long periods of time.

A server usually insists on password hashing to take only 1 second or something. Since this is a password for recovery, you don't care if it takes a while. You are fine if it takes a really long time, such as 24 hours, for example.

If you set your password key derivation to take a really long time, such as a day on a typical computer, is it safe to publish contents encrypted with that key publicly? Or will your still be vulnerable to brute force?

Answer 1

The reason for key strengthening is that passwords don't have as much entropy as is expected for the key. The time it takes to break a key is proportional to the number of possible keys. Strengthening algorithms used on passwords compensate for the poor entropy by increasing the proportionality constant. But the gap is so large that strengthening cannot compensate. A password with 64 bits of entropy is very hard to memorize — that's 10 random printable ASCII characters (if you start imposing memorable features, the entropy goes way down) or 14 random lowercase letters, but to reach 128 bits of “cracking difficulty”, which corresponds to the most common key size for symmetric encryption, you'd need a whooping 2^64 — about a century of CPU time.

In your scenario, a memorable password is the wrong method. It would be a password that you rarely use, yet needs to be very strong and thus hard to memorize.

Use a random key, instead of a password-derived key, and print it out. Store the printout in a secure place.

If the software you use requires a password, generate a random password with as much entropy as the key. 20 ASCII printable characters, or 28 random lowercase letters, or something equivalent, give you 128 bits of entropy. If technology progresses to the point that this is breakable, the key you're encrypting will probably not be secure anymore anyway. Since your password has enough entropy for a key, you don't need to strengthen it. Once again, print it out.

Once you go that route, you might as well print out the original key and forget about uploading it. But adding a level of indirection does have advantages. It means that an adversary needs to obtain both a copy of the encrypted key and a copy of the key encryption key. With this separation, if one of the parts is compromised, you may have time to act before the second one is also compromised. You can also store the key encryption key in several separate pieces. There are secret sharing algorithms that allow splitting a key in n pieces such that it can be recovered from any k pieces, but no fewer. If you want to keep things simple, you can generate multiple key encryption keys, upload the master key encrypted with each of these, and split the key encryption keys and dispatch the pieces so that it takes more than a single place to recover the whole thing.

Answer 2

For clarity to other readers, password-based key derivation is hashing, not encryption. It's designed to produce encryption keys from passwords, not encrypt passwords. You would hash the password with the function (which I will refer to as the PBKDF) and then encrypt the data with the resulting key.

A strong password hashed with a strong algorithm would take eons to break - if the people who designed the password storage system did a good job and the algorithms involved have no weaknesses, the would-be hash breaker would be dead millenia before the password was recovered. Responsible server operators ask people to change their passwords for defense in depth.

It would similarly take massive amounts of time to break good encryption. To brute-force AES-256, you would need to wait for the age of the universe many times over.

If you use a strong password and so many iterations of a PBKDF that it takes a full day to produce a key from a possible password, it could be easier for an attacker to brute-force the derived key rather than going through the process of guessing passwords and deriving the key from them.

Therefore, if you just use a password with at least as much entropy as the keys generated by the PBKDF, you could save yourself some time and just encrypt the data with the key from one iteration without compromising your security at all.