Need a time consuming symmetric encryption

Question

I have a database with millions of entries, each entry encrypted with a (different) password. Normally, only one entry is needed at a time. If somebody steals the database, I want to make it hard for them to get the data, even if they know the passwords, by making it very time consuming to extract all the information. Such as: If decrypting of one entry takes 10 seconds, decrypting of 50 million records takes years.

What approach would you suggest?

Answer 1

You can basically choose decryption time by jacking up the key length - have a look at http://www.javamex.com/tutorials/cryptography/rsa_key_length.shtml.

The only thing is though that encrypting with the longer key also takes significant time (though, exponentially less than decryption); so you're probably going to hit an upper bound where you're not willing to spend a month encrypting millions of rows.

Symmetric encryption tends to be fast, much faster than asymmetric, and tends toward algorithms where decryption and encryption times are very similar (since you're basically doing the exact same math backward). In a case where you can choose and you want slow, go with something like RSA.

Answer 2

You say that each row is encrypted with a different password, and you want to make it slow for an attacker to perform a blanket decryption of the entire table even if they know all of the passwords.

Since encryption happens with keys, not passwords, there's another piece you haven't mentioned: The means by which passwords become keys. If you're worried about passwords (not keys) being stolen, this is a fine place to manufacture your slowness. If you define the key as 4096 re-hashings of the password, it will be 18 years of Moore's Law before that process is as fast as a single hashing today. If 18 years isn't long enough (it's not!) then keep doubling.

Iterative hashing has its pitfalls however. The chance of collisions is increased, unless you mix some salt with each iteration. See: Strength of multiple hash iterations?

I also wonder if you're not being myopic in tackling this particular problem. "Passwords" (as typically defined) do not contain enough entropy to produce cryptographic key material in the first place. You need a "passphrase" instead, or you're losing the game.