Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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?

share|improve this question
1  
Why do you impose this restriction? Keep passwords/keys secret, and hope for the best. Please remember that if the value of your database is high, the attacker will simply rent enough cloud capacity to crunch the numbers and get profit quickly. If the value of your database is not that large, then why spend your computing resources on slow encryption? –  Deer Hunter Feb 10 '13 at 7:12
1  
Martin, this is a bad idea. –  Lucas Kauffman Feb 10 '13 at 8:54
1  
@Bob because there is an inherent flaw, he assumes keys are compromised and thus wants an expensive algorithm. However considering constant evolution at which hardware gets faster, this solution would not be able to stand the challenge of time. I believe he should reconsider his scheme and find a way to ensure keys do not get compromised. –  Lucas Kauffman Feb 10 '13 at 9:32
1  
@LucasKauffman You can choose asymmetric algorithms likely to survive 20-30 years with the right keylengths. SHA-512 may last forever (schneier.com/crypto-gram-9902.html#snakeoil - read under Warning Sign #5). Assuming compromise of your datastore is a realistic scenario in a lot of cases, in pretty much any case where you're guarding something actually valuable. –  Bob Watson Feb 10 '13 at 9:48
1  
@Bob read the question again, he want a slow algorithm in the event his keys are compromised not only the data store. –  Lucas Kauffman Feb 10 '13 at 9:54

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.