<< The Bcrypt algorithm was used to generate the cache key where we hash a combined string of userId + username + password. During specific conditions, this could allow users to authenticate by only providing the username with the stored cache key of a previous successful authentication. >>
So if the userid is 18 digits, the username is 52 characters, and the delimiters are 1 character each, then the total length of the non-secret prefix is 72, and bcrypt will drop the secret suffix.
You aren’t supposed to put more than the salt and the password into trad unix password hashes.
* They concatenated userId + username + password for a cache key
* Used BCrypt (which has a 72-byte limit)
* The concatenation could exceed 72 bytes, causing the password portion to be truncated
Why this is problematic:
* BCrypt is designed for password hashing, not cache key generation
* Mixing identifiers (userId, username) with secrets (password) in the same hash
* Truncation risk due to BCrypt's limits
Password storage should be separate from cache key generation. Use a random salt + appropriate hash function and for cache keys - use HMAC or KDF w/appropriate inputs
That should also mean that ca 50-52 character usernames are likely easily bruteforcable. Which makes the preconditions wider than those stated in the publication.
They’re saying that if a username is 50 characters, only 2 characters of the password are used to in the cache key. And a 2 character password is very bruteforceable.
Potentially ignorant question, why would they go for bcrypt over say HKDF[1], especially since they mix in public data like the username and potentially userid?
Can't believe the answers you're getting. The answer's a big fat NO. If you find yourself in that situation, there's something very incorrect with your design.
With no password in key: mildly cleaner to drop entries on password change, even if the cache didn't get the command to drop the key, the next login would override the old key's value anyhow, instead of potentially a key per password that was valid in the short period around a password change
Of course, if you have any validness of old sessions / passwords around a password change, you are doing something wrong.
My personal wondering is, considering KDF is meant to be expensive, why is IO more expensive to the point it needs a cache?
Because bcrypt is still viable. Its cost factor is easily scaled to commodity performance, keeping the attack cost high.
The main attack vector these days is GPU-based compute. There, SHA* algorithms are particularly weak because they can be so efficiently computed. Unlike SHA algorithms, bcrypt generates high memory contention, even on modern GPUs.
Add in the constraint of broad support, low "honest use" cost, and maturity (extensive hostile cryptanalysis), bcrypt stays as one of the better choices even 25 year later.
That said, bcrypt's main limitation is it has a low memory-size cost. There are some newer algorithms that improve on bcrypt by increasing the memory-size cost to more than is practical even for FPGA attacks.
More importantly, bcrypt didn't actually fail here. The vulnerability happened because okta didn't use it correctly. All crypto is insecure if you use it wrong enough.
after all of the headaches in the late 90s/early 2000s with truncating password hash functions, i'm just a little surprised that this sort of thing would still be an issue.
i understand performance concerns and design trade offs, but i would expect a secure hashing function in 2024 to do proper message scheduling and compression or return errors when truncations are happening.
i suppose 90s culture is hip again these days, so maybe this does make sense?
Bcrypt is still perfectly usable for its original purpose. They just picked/wrote a bad implementation that silently truncated inputs longer than the maximum input length. Would you also ask why they picked AES (a cipher from 1998) when the error was with the user (e.g. picking fixed/too short key)?
The goal of a salt is to prevent lookup attacks. Since the user id is unique to each user, it prevents the use of pre-computed lookup tables like a salt would.
The security of salting is twofold. Yes, it defeats the common rainbow table. But if the salt is known, a rainbow table for that salt can be computed. The security of salting depends on the salt being unknown.
If the salt is externally known, which the username and userID necessarily are, then the rainbow table for that account can be computed entirely offline, defeating the point of salting.
You're both right, but are coming at this from different directions. In the past a rainbow table was intended to reveal as many passwords on a system as possible once you got a copy of the passwords. If one of them happened to be a high-value account, great. But maybe access to an ordinary account is good enough for their (nefarious) purposes.
It's also possible to build a rainbow table when you already know an account is high-value and have the salt. You can't go download that rainbow table - you'll have to compute it yourself, so the cost to the attacker is higher. But if the account is valuable enough to justify targeting specifically, you'll do it.
The primary purpose of salting is to prevent precomputation being used to attack all users (e.g. rainbow tables). Even when specific salts are known they have already done this job.
Salts are not intended to be secrets.
If you want to treat a salt as if it was a private key, that would only provide additional protection for the very specific circumstance where the user hash is compromised, but the corresponding salt was not.
> then the rainbow table for that account can be computed entirely offline
So you basically bruteforce the password for a specific account before you get the actual hash but after you know the hashing scheme? I don’t see how this helps with any sort of attack though.
No, rainbow tables are hash-input specific. They're user-specific only if the salt is user-unique. Usernames aren't normally part of the hash input because they're assumed-public knowledge.
You can test this for yourself by creating a user account, then editing the master password database and manually changing the username without recalculating the password hash. The password will still work. If the username was part of the hash input, the password would fail.
You complained about them salting using the public username as salt. You asserted that this makes the rainbow table computable offline. I asserted that this didn't matter much for security since the table for H(username || secret) is username specific and not reusable for other usernames. Since precomputed rainbow tables consume quite a bit of space it is rather unlikely that anyone would have such a table stored for any random username.
Though you can salt a hash using a function that does not take a distinct salt input by just concatenating the salt with the value. This is a relatively common practice, but of course only works if there is no truncation of the salted input.
A delimiter fixes the problem if you're sure the delimiter character can never be inside the username and password. Better would be to prefix the length of each field. Better still would be separately hashing each field and concatenating the results.
Personally, I like a fixed uint8 or uint16 representing the length of each segment. Then, there are no forbidden characters or quoting required. Maybe I want to have \0 in my password.
You still need to make sure nulls can't show up, and you need to consider possible truncation scenarios caused by those nulls and make sure they won't cause silent failures at any point.
One pattern I bump up against from time to time is the delta between using a perfectly defensible technique for a given use-case (safe delimiters when constructing an input for a specific function) versus a desire to have each decision be driven by some universal law (e.g. "if you're streaming data between services, using null bytes as delimiters might not be safe if consuming services may truncate at null bytes, so NEVER use null bytes as delimiters because they can be unsafe")
It's not even a matter of one "side" being right or wrong. You can simultaneously be right that this is perfectly safe in this use-case, while someone else can be right to be concerned ("need to consider possible") because the code will forever be one refactor or copy/paste away from this concatenated string being re-used somewhere else.
Also, we're talking about user_id not user_email, so it should be the same length always. Well, unless you're silly and using databases sequence for IDs.
https://man.openbsd.org/crypt
<< The maximum password length is 72. >>
So if the userid is 18 digits, the username is 52 characters, and the delimiters are 1 character each, then the total length of the non-secret prefix is 72, and bcrypt will drop the secret suffix.
You aren’t supposed to put more than the salt and the password into trad unix password hashes.