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

[Thomas Darimont]

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.com
> > 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
>
>
>