Switching to new encryption method (without losing data?)

Question

Let's say you have a website that provides a service of some kind. Users can log in, they can store some kind of data, and there's various types of encryption in place to keep it all safe. Passwords are salted and hashed, user data is encrypted, the keys are kept securely, it's all good.

One day, the bad guys find a vulnerability in the encryption algorithm you're using. The details of what the vulnerability is or which algorithm it is etc. are irrelevant; the important part is that some or all of your data is no longer as safe as it was - it's now possible in real-life practice to get the user data back from the encrypted data you have stored.

How do you deal with this situation?

In the case of passwords, you could just invalidate everyone's passwords, issue reset notices, and hope that the email accounts you just sent those passwords to aren't similarly vulnerable... is this a good idea?

For the other data... Well, it's stored using reversible encryption, so I suppose you could run through decrypting it and re-encrypting it using the new non-broken method, but for that you need the keys, which will presumably (hopefully) be stored like passwords, using one-way enrcyption, so you're kind of stuck. Obviously your safest course of action is to scrub the data, but that seems rather drastic, and your users will likely be somewhat miffed at losing all of their data in the face of some hypothetical risk which may be very small and may never materialise.

One thought I did have was that you could take the encrypted data you have and encrypt it again with a different (non-broken algorithm), so that you know it can't be recovered using the new vulnerability, and then next time the user logs in, use the old method followed by the new method, and if it works, wipe the field and store a new version that just uses the new method. With salted hashes, you'd have to store the old and new salts as well, but that's no big deal. So, your table would need an extra column for a flag that lets you know whether or not that user has been migrated to the new system yet, and in the case of salted hashes, another column for the extra salt. Would this work, or is there a vulnerability in this that I haven't spotted? I'm aware that combining two cryptographic methods can sometimes produce a vulnerability that isn't present in either method when used alone, but if your current data is encrypted using a method that you now know to be insecure, my theory is that you might as well treat it as plaintext, at which point adding encryption can only make it safer.

Answer 1

The best way to do this is simply to migrate the crypto when a user logs in, or invalidate their password and data if this hasn't occurred after a few months.

So, for passwords, the user logs in, we know their plaintext password, so we just compute the new hash. Optionally force the user to pick a new password. For encrypted data, the user logs in, we know their password again, so we just re-encrypt.

The problem with re-encrypting is that you still need to know the password for the new cipher to use. It's also prone to situations where the underlying cipher is weak against timing or power analysis attacks.

The problem with re-hashing is that any collision vulnerabilities in the first hash scheme are perpetuated into the new scheme.

So for both, it's better to just wait for the user to log in and then migrate them over.

An alternative is to double-hash or double-encrypt as a temporary measure, then migrate on login. It's more development work, but works out a bit safer.