Bueno, sugeriría BCrypt sobre PBKDF2.
Dicho esto, su solución debe ser doble.
-
Para asegurar el sistema inmediatamente, sí, su solución es buena. Trate el MD5 como la contraseña de entrada y tenga sal por usuario como usted sugiera.
-
Sugeriría migrar MD5 fuera de la imagen. (a menos que sea una aplicación estrictamente heredada)
La próxima vez que el usuario inicie sesión, su aplicación tendrá acceso a la contraseña no lavada y tendrá la capacidad de actualizar el hash con uno que omita el paso de MD5. Tendrá que tener algún indicador en la cuenta para saber si se ha completado.
También recomendaría Pepper en pendiente a la contraseña de entrada (o MD5) como una precaución de seguridad adicional.
BCrypt tiene una longitud máxima en contraseñas, por lo que es mejor colocar la contraseña de entrada combinada con Pepper en un hash SHA-256 primero. No estoy seguro si PBKDF2 tiene este límite. Eventualmente, algún día podrá usar un hash aún más reciente que tampoco tenga este límite.
Realmente, migrar fuera de MD5 probablemente no sea necesario, pero deshacerse de MD5 sería la solución ideal para la mejor resistencia a la colisión y parece un diseño más limpio.