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

[Stian Thorgersen]

Ok, I figured that might have been what you where saying. That would
probably be a nice addition, but it would be fairly complex thing to add.
Say you have 10 million users in the db, starting a background task to
rehash all the credentials would make it churn away for days and grind all
other requests to a halt. So you'd need a background scheduling mechanism
that is capable of only scheduling when there is free resources. Then
there's also clustering to deal with.

On 20 March 2017 at 14:37, Thomas Darimont <thomas.darimont at googlemail.com>
wrote:

> Hello Stian,
>
> I know that Keycloak currently performs an ad-hoc migration of user
> credentials - but this requires user interaction.
> Users who don't login won't get their credentials updated.
>
> The idea described in the long post essentially boils down to the
> following:
>
> Migrate all existing user credentials incrementally, as a batch job in the
> background, while remembering the credential encoding algorithm previously
> used to be able to perform an ad-hoc credential validation and migration on
> the next user login.
>
> Validation via:
>   new_encoding(old_encoding(rawPassword)) == storedHash,
> if hashes matches:
>   update credential via new_encoding(rawPassword)
>
> With that in place one could comply with new credential encoding
> requirements for all users
> without requiring any user interaction while still being able to verify
> given credentials.
>
> Cheers,
> Thomas
>
> 2017-03-20 8:58 GMT+01:00 Stian Thorgersen <sthorger at redhat.com>:
>
>> We already do this to some degree. If the default hashing algorithm is
>> changed the users credentials are updated on the next login.
>>
>> Can you summarize your post please? I'm not sure what you are trying to
>> achieve beyond what we already do.
>>
>> On 19 March 2017 at 00:30, Thomas Darimont <thomas.darimont at googlemail.co
>> m> 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
>>
>>
>>
>