[keycloak-dev] How to migrate all credentials stored in Keycloak to a new encoding algorithm?

[Bill Burke]

100 users with recommended hashing iterations (20000) took 9 seconds on 
my laptop.  This is just raw encoding with no DB updates included.

https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html

  " 9,223,372,036,854,775,808 SHA1 computations" And, I think, but am 
not certain, this is for one SHA1 iteration.   Are people overreacting 
to this, specifically for password hash storage?


On 3/18/17 7:30 PM, Thomas Darimont wrote:
> Hello group,
>
>
> Sorry - for the long read but the following contains a proposal with a
>
> general solution for the problem.
>
>
> TLDR; section at the end.
>
>
> If you have been using Keycloak for a while, you probably have a number of
> users in the
>
> system, whose passwords are encoded by the default
> Pbkdf2PasswordHashProvider which
>
> currently uses the PBKDF2WithHmacSHA1 algorithm.
>
> To change the algorithm, one could implement a custom password encoding via
> Keycloak’s
>
> PasswordHashProvider SPI. That works for user credential updates or newly
> created users,
>
> but what about the potentially large number of credentials of already
> existing users
>
> who are not active at the moment?
>
>
> If you need to ensure that user credentials are encoded and stored with
>
> the new algorithm, then you have to migrate all user credentials to the new
> algorithm.
>
>
> Storing and verifying stored passwords usually involves a single step of
> hashing in each direction:
>
> once stored as a hash, each try to enter the password is verified using the
> same hash function and
>
> comparing the hashes. If you have a collection of stored password hashes
> and the hash function must
>
> be changed, the only possibility (apart from re-initializing all password
> hashes) is to apply the
>
> second hash function to the existing hashes and remember to hash the
> entered passwords twice, too.
>
> That’s why it is unavoidable to remember which hash function was used to
> create the first hash of
>
> each password. If this information can be reconstructed, the sequence of
> hash functions to apply to
>
> a clear text password to produce a comparable hash can be reapplied. If the
> hashes match, the given
>
> password can then be hashed with the new hash function and stored as the
> new hash value, effectively
>
> migrating the password to use the new hash function. That’s what I propose
> below.
>
>
> The following describes an incremental method for credential updates,
> verification and migration.
>
> * Incremental Credential Migration
>
>
> Imagine that you have two different credential encoding algorithms:
>
>    hash_old(input, ...) - The current encoding algorithm
>
>    hash_new(input, ...) - The new encoding algorithm
>
>
> We now want to update all stored credentials to use the hash_new encoding
> algorithm.
>
> In order to achieve this the following two steps need to be performed.
>
>
> 1. Incrementally encode existing credentials
>
> In this step the existing credentials are encoded with the new encoding
> algorithm hash_new
>
> and stored as the new credential value with additional metadata (old
> encoding, new encoding)
>
> annotated with a “migration_required” marker.
>
> This marker is later used to detect credentials which needs migration
> during credential validation.
>
> Note that since we encode the already encoded credential value we do not
> need to know the plain
>
> text of the credential to perform the encoding.
>
> The encoding all credentials will probably take some time and CPU
> resources, depending on the number of credentials and the used encoding
> function configuration.
>
> Therefore it makes sense to perform this step incrementally and in parallel
> to the credential validation described in Step 2. This is possible because
> the newly encoded credential values
>
> are annotated with a  “migration_required” marker and all other credentials
> will be handled by their associated encoding algorithm.
>
>
> Eventually all credentials will be encoded with the new encoding algorithm.
>
>
> Pseudo-Code: encode credentials with new encoding
>
>
> for (CredentialModel credential: passwordCredentials) {
>
>     // checks if given credential should be migrated, e.g. uses hash_old
>
>     if (isCredentialMigrationRequired(credential)) {
>
>       metadata = credential.getConfig();
>
>       // credential.value: the original password encoded with hash_old
>
>       newValue = hash_new(credential.value, credential.salt, …);
>
>       metadata = updateMetadata(metadata, “hash_new”, “migration_required”)
>
>       updateCredential (credential, newValue, metadata)
>
>     }
>
> }
>
>
> 2. Credential Validation and Migration
>
> In this step the provided password is verified by comparing the stored
> password hash against the
>
> hash computed from the sequential application of the hash functions
> hash_old and hash_new.
>
>
> 2.1 Credential Validation
>
> For credentials marked with “migration_required”, compare the stored
> credential hash value with the result of hash_new(hash_old(password,...
> ),...).
>
> For all other credentials the associated credential encoding algorithm is
> used.
>
>
> Note that credential validation for non-migrated credentials are more
> expensive due to the multiple
>
> hash functions being applied in sequence.
>
>
> If the hashes match, we know that the given password was valid and the
> actual credential migration can be performed.
>
>
> 2.2 Credential Migration
>
> After successful validation of a credential tagged with a
> “migration_required” marker, the given
>
> password is encoded with the new hash function via hash_new(password). The
> credential is now stored with the new hash value and updated metadata with
> the “migration_required” marker removed.
>
>
> This concludes the migration of the credential. After the migration the
> hash_new(...) function is
>
> sufficient to verify the credential.
>
>
> Pseudo-Code: validate and migrate credential
>
>
> boolean verify(String rawPassword, CredentialModel cred) {
>
>
>
>     if (isMarkedForMigration(cred)){
>
>       // Step 2.1 Validate credential by encoding the rawPassword
>
>       // with the hash_old and then hash_new algorithm.
>
>       if (hash_new(hash_old(rawPassword, cred), cred) == cred.value) {
>
>
>         // Step 2.2 Perform the credential migration
>
>         migrateCredential(cred, hash_new(rawPassword, cred));
>
>         return true;
>
>       }
>
>     } else {
>
>      // verify credential with hash_new(...) OR hash_old(...)
>
>     }
>
>     return false;
>
> }
>
>
> TLDR: Conclusion
>
>
> The proposed approach supports migration of credentials to a new encoding
> algorithm in a two step process.
>
> First the existing credential value, hashed with the old hash function, is
> hashed again with the new hash
>
> function. The resulting hash is then stored in the credential annotated
> with a migration marker.
>
>
> To verify a given password against the stored credential hash, the same
> sequence of hash functions is applied to the
>
> password and the resulting hash value is then compared against the stored
> hash.
>
> If the hash matches, the actual credential migration is performed by
> hashing the given password again but
>
> this time only with the new hash function.
>
> The resulting hash is then stored with the credential without the migration
> marker.
>
>
> The main benefit of this method is that one can migrate existing credential
> encoding mechanisms to new
>
> ones without having to keep old credentials hashed with potentially
> insecure algorithms around.
>
> The method can incrementally update the credentials by using markers on the
> stored credentials to
>
> steer credential validation.
>
> It comes with the cost of potentially more CPU intensive credential
> validation for non-migrated
>
> credentials that need to be verified and migrated.
>
>
> Given the continuous progression in the fields of security and cryptography
> it is only a matter of time
>
> that one needs to change a credential encoding mechanism in order to comply
> with the latest recommended
>
> security standards.
>
>
> Therefore I think this incremental credential migration would be a valuable
> feature to add to
>
> the Keycloak System.
>
>
> What do you guys think?
>
>
> Cheers,
>
> Thomas
> _______________________________________________
> keycloak-dev mailing list
> keycloak-dev at lists.jboss.org
> https://lists.jboss.org/mailman/listinfo/keycloak-dev