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

[Thomas Darimont]

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