6:30 p.m.
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