Is "faster" always a good thing in hashing algorithms?
Suppose a hashed password database falls into wrong hands. If they're hashed with a faster algorithm wouldn't it be easier to try a dictionary attack to discover the real passwords?
Suppose a hashed password database falls into wrong hands. If they're hashed with a faster algorithm wouldn't it be easier to try a dictionary attack to discover the real passwords?
BLAKE3's readme says: (https://github.com/BLAKE3-team/BLAKE3)
NOTE: BLAKE3 is not a password hashing algorithm, because it's designed to be fast, whereas password hashing should not be fast. If you hash passwords to store the hashes or if you derive keys from passwords, we recommend Argon2.
Argon2 (https://github.com/P-H-C/phc-winner-argon2/blob/master/argon...) is based on BLAKE2b.
For password hashing you’re correct they should be slow, bcrypt for example.
Slowness is not the quality of a hashing algorithm that guarantees anything :)
Resistance to quickly creating a rainbow table with significant coverage, however, is a reasonable property.
The mentioned bcrypt library allows you to “tighten the ratchet” over time as average computing power increases to make hashing a single password in 2010 take about the same amount of time on average modern computing hardware as in 2020 (assuming you correctly increase the number of iterations)
The commenter above obviously meant "slow to brute-force".
You're pedantically interpreting it to mean "slow for a given implementation, even if there are some scenarios under which it would be faster to brute force".
What the parent comment meant is clear enough I think, and it's accurate in that context. The whole point of modern hashing algorithms that require memory and have scaling difficulty factors is to make it slower for an attacker with certain kinds of resources to brute force it.
If you have a very slow hashing algorithm implementation of a fast hashing algorithm (say 'sleep 5, echo 1'), that's not slow by the parent's comment definition because it's not slow to brute force.
Similarly, if the hashing algorithm has predictable output that allows the attacker to derive information about the input, that obviously is also faster to brute-force.
That sort of pedantry is arguably somewhat useful if you also choose to provide a more precise definition or explanation. It's definitely not constructive if you just add a little smiley face and do it as an asinine "hah look at how smart I am".
No, that's simply not true, and that's what the person you replied to was trying to say. For a password hashing algorithm, you actively want it to be slow - to have a mathematically guaranteed minimum amount of time that each attempt takes, regardless of implementation. This is a security property of a password-hashing algorithm. It is a necessary attribute - you can't have a "good" password-hashing algorithm whose output can be computed arbitrarily quickly.
What you might be saying is that if an inefficient implementation is slow, we'd like to speed it up. Sure. The requirement of a good algorithm is that the most efficient implementation possible is slow.
For hashing passwords, you should not directly use a hashing primitive but instead stretch/iterate it through a higher-level algorithm, such as Argon2, that will (1) slow it down and (2) salt it.
Password hashing should always be performed using a hashing function designed specifically to prevent high speed execution - for that reason modern password hashing functions are both computationally slow (because of course), but also use large amounts of memory (to inhibit parallel execution).
I understand that it is for implementing things like dictionaries/hash tables.
For dictionaries/hash tables you'd typically use a very fast hash algorithm like xxHash, murmurHash, etc. Those are tuned for speed but can have collisions (typically they have very short outputs - 32 or 64 bits - so that they're easy to compare and compute with).
For cryptographic purposes (authenticity, integrity) you'd use a medium speed algorithm like SHA2/3, Blake2/3, etc. which are reasonably fast and essentially guarantee there won't be collisions (i.e. it's computationally hard to come up with collisions). These are meant to be computed quickly and potentially in parallel because you want to be able to verify data fast.
For password hashing you'd use a slow algorithm like bcrypt/scrypt or Argon2. These are designed specifically to be slow; some also use lots of memory specifically to slow down parallel attackers. You want password hashing to be relatively slow because you need to protect low-entropy data (a typical password only has a few dozen bits of security). By making the algorithm deliberately slow you would ensure that an attacker can't quickly guess the password, even if they have the hash.
These are the three major categories of hash; knowing which one to use in which application is pretty important. Don't mix them up!
With a bad hash function you can end up with a high level of bucket utilisation, significantly reducing the efficiency of the structure.
With user defined data there's even the possibility of maliciously crafted input attempting to force collisions as part of a DOS attack.
You can salt your input, and pretty much eliminate the issue - but as far as I can tell, you'll just end up rolling your own crypto.
It could have some application as a preprocessing step in clustering (if it could be done efficiently).
Salting is the way to deal with these issues, and for hash tables it works well even if your hash function isn’t cryptographically secure. Hence, for hash tables, salt+fast hash function should be sufficient.
These functions usually use hashes as a primitive, but there is more to them than that. Using a plain hash to store passwords is usually a red flag that the storage is insecure. I see it when doing source code audits: some legacy software using md5 without a salt.
To be precise I think security community should make an effort to separate the two terms more often. I've been trying to be more precise when writing and reviewing assessment reports.
The relevant bit here is this:
Verifiers SHALL store memorized secrets in a form that is resistant to offline attacks. Memorized secrets SHALL be salted and hashed using a suitable one-way key derivation function. Key derivation functions take a password, a salt, and a cost factor as inputs then generate a password hash.
They are specific about the type of KDF required: "one-way key derivation function".
The examples given later are PBKDF2 and Balloon.
It's essentially like rectangles versus squares. You can create a key derivation function out of anything which passes all the criteria of a password hashing function. But it won't be a particularly performant or useful key derivation function. Likewise you can create a password hashing algorithm out of a dedicated key derivation function, but that's insufficient on its own.
There's no need to get bogged down in the details, just continue recommending a reputable implementation of these algorithms. On the other hand, if you'd like to learn more out of intellectual curiosity, Boneh & Shoup's textbook is good (work in progress) [1]. Galbraith's textbook includes chapters which cover the topic to a depth that's beyond what you're looking for, but you'll learn whatever it is you want to know [2].
Finally, more accessible, informal answers that get the basic idea across are [3], [4].
2. https://www.math.auckland.ac.nz/~sgal018/crypto-book/main.pd...
3. https://security.stackexchange.com/questions/95410/what-is-t...
4. https://crypto.stackexchange.com/questions/70716/key-derivat...
A Key derivation function (KDF) is a basic and essential component of cryptographic systems: Its goal is to take a source of initial keying material, usually containing some good amount of randomness, but not distributed uniformly or for which an attacker has some partial knowledge, and derive from it one or more cryptographically strong secret keys.
Hash functions take arbitrary length input (well, up to some very large maximum size) and provide fixed-length output.
eXtensible Output Functions (XOFs)take arbitrary length input (up to some very large max) and provide arbitrary length output (up to some very large max).
Password Hashing Functions take (at least) three inputs: a unique salt, a secret password, and a tuning parameter (or set of parameters). They use the tuning parameter(s) to change the amount of work needed to compute their outputs. For any set of inputs they produce a deterministic output. The output may or may not be directly suitable for use as a cryptographic key, and may or may not be variable length.
Some password hashing functions are KDFs, taking effectively arbitrary input length and producing effectively arbitrary output length. PBKDF2 and Argon2 are KDFs.
Some password hashing functions are NOT KDFs, having limits on their input & output sizes. Bcrypt is not a KDF and not a hash function: it has a maximum 56-byte input (55 bytes if taking a null-terminated string, 72 bytes max in newer implementations) and a 60-byte output. It's suitable for logins where the password is hashed and compared to the stored hash, but not for directly deriving key material. And it's not necessarily suitable for non-ASCII passwords/passphrases, due to the short input.
> Bcrypt is not a KDF and not a hash function
This is true, but it's also a good example of what I was saying in my other comment. bcrypt is an example of a password hashing function which is not itself a KDF, but which can be used to construct a KDF.
All password hashing functions can be used to construct key derivation functions or simply are key derivation functions. But not all password hashing functions are key derivation functions. Whether or not it would be advisable to use a given password hashing function as a KDF depends, of course. In bcrypt's case you can construct a reasonable KDF. For example: https://github.com/pyca/bcrypt/blob/master/README.rst
Edit: NIST uses "one-way key derivation function" in their requirements, which I like, but that perhaps unfairly excludes other potential functions.