Encryption at Rest Migrations

What should I do to move away from a weak encryption algorithms in my database or storage?

In order and without skipping or re-arranging steps:

  1. Add another field for the new version;
  2. Write to both fields;
  3. Optimistically read from the new field if populated and not the old field;
  4. Asynchronously re-encrypt everything;
  5. Read only from the new field;
  6. Remove the code that reads from the old field;
  7. Backup if deemed appropriate and drop the old field.