Some good points, but with an eye to the future I’m missing some discussion of the standardized prefix syntax to use in the stored hash.
For bcrypt, there’s the $2a$ (and $2x$ and $2y$ for obscure and annoying reasons) prefix which is recognised by most UNIX crypt() functions. Switching to a different algorithm means you would still have to support the old algorithm, so it’s quite important to have such a prefix to distinguish between old hashes and new ones. PHPass uses $P$ for its MD5-based scheme.
Settling on a standardized password hash means you get to use the same crypt() functions and can even access the db from non-PHP projects, which is always nice (although those are also not very likely to support $P$). Rolling your own somewhat non-standard usage of bcrypt by pre-hashing and base64 encoding means you’ll also have to come up with a unique prefix which then is most likely not widely supported by other libraries.
I agree with you. Think the point you raise are why I’m a little unconvinced by this passage:
This is “rolling our own crypto”.
Answer: No, it’s a well-understood pattern that’s been discussed in the PHP community for well over a decade.
It is a long discussed technique but it hasn’t gone through the type of precise specification and widespread implementation projects that I associate with trusted crypto code. Often the mistakes with crypto code isn’t the crypto code itself. It is the details in the more mudane bits around it.
Something I always found interesting is that both scrypt (Colin Percival, FreeBSD contributor) and bcrypt (Niels Provos, former OpenBSD contributor). They seem to be the most widely used algorithms for this problem space come from the BSD sphere.
The OG $1$ MD5-based crypt scheme (including the idea to make it future-proof by prefixing it with an algorithm identifier) was written up by Poul Henning-Kamp, when he was one of the main contributors to FreeBSD. See here for a bit of history.
However, another major crypt scheme that’s currently in use is by Ulrich Drepper of RedHat. He based it on SHA256/512 as an alternative to bcrypt, basically because blowfish was not a NIST-approved algorithm which made it unsuitable for some RedHat customers.
What’s wrong with picking Blake2 completely independently from your key round? I mean, why not some KDF and then Blake2? Why does input keying method being password suggest to you that you shouldn’t use it downstream?
(Not that I would reach for Blake2 as my default, but that would be for other reasons.)
What’s wrong with picking Blake2 completely independently from your key round?
What’s wrong with just choosing a random 256-bit key separate from anything?
The implied goal of a password KDF is to derive your key (or IKM if you’re using HKDF afterwards) from the password. And bcrypt simply isn’t built for that purpose.
I mean, why not some KDF and then Blake2?
The implied goal is to get your entropy from the password, and the password hashing algorithm in scope is bcrypt.
If you want a password KDF, scrypt and Argon2 are both password KDFs and password hashing functions. But bcrypt is only a password hashing function, not a password KDF.
The linked article covers this, somewhat redundantly.
Why does input keying method being password suggest to you that you shouldn’t use it downstream?
Let’s say you did some bcrypt + BLAKE2b dance, but don’t want one key, but rather, four keys. Or ten? (It doesn’t matter, really, how many you want. For our use case, it’s enough to be “more than one”.)
Do you run the Password-Based KDF multiple times (one for each key)?
No, because that would be stupid slow on your end (i.e., the defender), but the attackers can crack any of them to learn the password used for all the others. It’s the most wasteful way to solve this problem.
Solution: Only ever do the PBKDF once, and then use the output of that for a faster algorithm (such as HKDF) to split it into multiple derived keys.
Cache-hardness and memory-hardness are two criteria by which a password hashing algorithm may be judged. They are not modes of an individual algorithm.
I think they are analogous to the criterion I might call CPU-hardness. bcrypt was created to score well on the criterion of CPU-hardness in comparison to algorithms like SHA256. The algorithm purposely requires using a lot of CPU resources to get the result. Therefore, if an attacker tries to simultaneously brute-force many passwords by calculating bcrypt hashes of candidate passwords, the attacker will be limited by their CPU.
Thus, memory-hardness means requiring that whoever runs the algorithm dedicate lots of memory to that process, also with the goal of limiting the amount of simultaneous calculations that may be done.
I agree that the text quoted from the bscrypt README doesn’t clearly explain what cache-hardness is. But just by knowing what memory-hardness is, I can assume cache-hardness requires the attacker to use a large proportion of some cache (the quote implies that it’s GPU cache, but I don’t know if it also uses lots of memory cache or CPU cache).
In the years since the PHC concluded, the advances in password cracking techniques have not slowed down.
One of the PHC judges recently proposed a new algorithm called bscrypt which purports a property called “cache hard” rather than “memory hard”. The reasoning is that, for shorter run times, memory bandwidth and small CPU caches is a tighter bottleneck than overall memory requirements.
In fact, there’s an Argon2 variant (Argon2ds) which offers cache-hardness.
EDIT - odd, I meant to reply to GP rather than (current) parent post.
Rejecting would also have caused problems for Okta. And typical APIs for password hashing cannot return errors so they can’t reject long passwords.
The article says why not to reject:
The other thing to consider is that many people use passphrases, such as those generated from Diceware, which produce longer strings with less entropy per character.
When you develop a popular CMS, library, or framework, you cannot possibly know all the ways that your software will be used by others. It’s almost always better to be misuse-resistant.
Seems like a semantic disagreement right? In the Okta circumstance, Okta used username || password as a password itself if we view the input into bcrypt as definitionally a password.
While it’s simpler to limit at 72 chars in this case, Soatok suggests this because there’s a well documented case of what we might think of as a misuse of Bcrypt in the past.
This is a situation where the widespread use of dependent types would have come in handy. Let’s say that Okta was developing their software in a language with support for dependent types, and the bcrypt function accepted a byte array dependent on that integer 72. The developers would’ve had to prove that the input byte arrays they passed to the hash function were at most 72 characters in order for their code to compile at all, which would’ve made them acutely aware of the potential issue with concatenating a username and a potentially-lengthy password.
Some good points, but with an eye to the future I’m missing some discussion of the standardized prefix syntax to use in the stored hash.
For bcrypt, there’s the
$2a$(and$2x$and$2y$for obscure and annoying reasons) prefix which is recognised by most UNIXcrypt()functions. Switching to a different algorithm means you would still have to support the old algorithm, so it’s quite important to have such a prefix to distinguish between old hashes and new ones. PHPass uses$P$for its MD5-based scheme.Settling on a standardized password hash means you get to use the same
crypt()functions and can even access the db from non-PHP projects, which is always nice (although those are also not very likely to support$P$). Rolling your own somewhat non-standard usage of bcrypt by pre-hashing and base64 encoding means you’ll also have to come up with a unique prefix which then is most likely not widely supported by other libraries.I agree with you. Think the point you raise are why I’m a little unconvinced by this passage:
It is a long discussed technique but it hasn’t gone through the type of precise specification and widespread implementation projects that I associate with trusted crypto code. Often the mistakes with crypto code isn’t the crypto code itself. It is the details in the more mudane bits around it.
Something I always found interesting is that both scrypt (Colin Percival, FreeBSD contributor) and bcrypt (Niels Provos, former OpenBSD contributor). They seem to be the most widely used algorithms for this problem space come from the BSD sphere.
The OG
$1$MD5-based crypt scheme (including the idea to make it future-proof by prefixing it with an algorithm identifier) was written up by Poul Henning-Kamp, when he was one of the main contributors to FreeBSD. See here for a bit of history.However, another major crypt scheme that’s currently in use is by Ulrich Drepper of RedHat. He based it on SHA256/512 as an alternative to bcrypt, basically because blowfish was not a NIST-approved algorithm which made it unsuitable for some RedHat customers.
If you want a KDF and have BLAKE2, why would you use bcrypt?
Argon2 is the KDF based on blake2 fwiw, since the article discusses argon and bcrypt.
Because BLAKE2 isn’t a password KDF?
I wouldn’t use bcrypt if I wanted a KDF, but I also wouldn’t use BLAKE2 if I was working with passwords as my input keying material.
What’s wrong with picking Blake2 completely independently from your key round? I mean, why not some KDF and then Blake2? Why does input keying method being password suggest to you that you shouldn’t use it downstream?
(Not that I would reach for Blake2 as my default, but that would be for other reasons.)
What’s wrong with just choosing a random 256-bit key separate from anything?
The implied goal of a password KDF is to derive your key (or IKM if you’re using HKDF afterwards) from the password. And bcrypt simply isn’t built for that purpose.
The implied goal is to get your entropy from the password, and the password hashing algorithm in scope is bcrypt.
If you want a password KDF, scrypt and Argon2 are both password KDFs and password hashing functions. But bcrypt is only a password hashing function, not a password KDF.
The linked article covers this, somewhat redundantly.
Let’s say you did some bcrypt + BLAKE2b dance, but don’t want one key, but rather, four keys. Or ten? (It doesn’t matter, really, how many you want. For our use case, it’s enough to be “more than one”.)
Do you run the Password-Based KDF multiple times (one for each key)?
No, because that would be stupid slow on your end (i.e., the defender), but the attackers can crack any of them to learn the password used for all the others. It’s the most wasteful way to solve this problem.
Solution: Only ever do the PBKDF once, and then use the output of that for a faster algorithm (such as HKDF) to split it into multiple derived keys.
This does seem a bit Byzantine. What is the difference between The two modes cache hardened versus the other kind? I’m not quite sure what they mean.
Cache-hardness and memory-hardness are two criteria by which a password hashing algorithm may be judged. They are not modes of an individual algorithm.
I think they are analogous to the criterion I might call CPU-hardness. bcrypt was created to score well on the criterion of CPU-hardness in comparison to algorithms like SHA256. The algorithm purposely requires using a lot of CPU resources to get the result. Therefore, if an attacker tries to simultaneously brute-force many passwords by calculating bcrypt hashes of candidate passwords, the attacker will be limited by their CPU.
Thus, memory-hardness means requiring that whoever runs the algorithm dedicate lots of memory to that process, also with the goal of limiting the amount of simultaneous calculations that may be done.
I agree that the text quoted from the bscrypt README doesn’t clearly explain what cache-hardness is. But just by knowing what memory-hardness is, I can assume cache-hardness requires the attacker to use a large proportion of some cache (the quote implies that it’s GPU cache, but I don’t know if it also uses lots of memory cache or CPU cache).
The author links to a previous post, What We Do in the /etc/shadow – Cryptography with Passwords that explains that cache-hardness refers to CPU caches:
EDIT - odd, I meant to reply to GP rather than (current) parent post.
Sorry, I’m having difficulty parsing your question. What are you confused by exactly?
This is inaccurate. Okta fed the username and password to bcrypt. It wasn’t about long passwords.
I think rejecting passwords longer than 72 characters is a simpler option than doing some extra hashing on them, if you want to use bcrypt.
Rejecting would also have caused problems for Okta. And typical APIs for password hashing cannot return errors so they can’t reject long passwords.
The article says why not to reject:
Seems like a semantic disagreement right? In the Okta circumstance, Okta used username || password as a password itself if we view the input into bcrypt as definitionally a password.
While it’s simpler to limit at 72 chars in this case, Soatok suggests this because there’s a well documented case of what we might think of as a misuse of Bcrypt in the past.
This is a situation where the widespread use of dependent types would have come in handy. Let’s say that Okta was developing their software in a language with support for dependent types, and the
bcryptfunction accepted a byte array dependent on that integer 72. The developers would’ve had to prove that the input byte arrays they passed to the hash function were at most 72 characters in order for their code to compile at all, which would’ve made them acutely aware of the potential issue with concatenating a username and a potentially-lengthy password.