7 ms·

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 wou

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?

jchw 7y ago
Blake3 is not for use in a password hashing algorithm; those have different goals. Check out Argon2 or bcrypt for that.
- diego_moita 7y ago
  Ok, thank you. I understand that it is for implementing things like dictionaries/hash tables.
  - lucb1e 7y ago
    Or integrity checking for non-authenticated encryption modes (wouldn't want file encryption or https to be slow).
  - nneonneo 7y ago
    No, Blake3 is a cryptographic hash algorithm, not for dictionaries or hash tables. It is intended for cryptographic signatures, file/data integrity, message authentication codes, etc. 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!
    - yarg 7y ago
      In any situation where a hashcode is cacheable (which seems to me to cover all situations where a hashcode even makes sense) a cryptographic hash function might not be such a bad idea (especially if you're IO bound in any way). 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.
      - yarg 7y ago
        Actually, a counter-point: there might be situations where you want an anti-cryptographic hash function - where similar inputs produce generally similar hashes. It could have some application as a preprocessing step in clustering (if it could be done efficiently).
        earenndil 7y ago
        Easy: for n-byte output, separate input into n equally-sized chunks (pad with zeroes if not enough). For each chunk, XOR all the bytes together.
        nneonneo 7y ago
        Those are called fuzzy or locality-sensitive hashes; they’re used a lot in image processing for similarity testing, for example. I don’t consider them to be in the same category as normal hashes, though, because fuzzy hashes have vastly different properties.
        dgacmu 7y ago
        The term for this is locality sensitive hashing, and it's very useful in some contexts.
      - nneonneo 7y ago
        Cryptographic hash functions can be orders of magnitude slower than functions tuned for hashtables and dictionaries. If you’re using them as hash table indexes, then you have to take the big cryptographically secure number and mod it by a small bucket count - and then you’re going to have collisions. If you don’t salt, then an attacker is going to predict the bucket indexes no matter how strong your hash function is, and since you can’t have that many buckets, they can just brute force to find collisions. 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.
codetrotter 7y ago
Blake3 is explicitly not a password hashing algorithm. For that use Bcrypt or Scrypt or Argon2. The authors of Blake3 point this out in the README of Blake3.
jayflux 7y ago
For general purpose algorithms yes. Blake3 is not a password hashing algorithm it’s a general purpose one, used for checksums or verifying 2 files are the same etc. For password hashing you’re correct they should be slow, bcrypt for example.
- ilvez 7y ago
  > 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 :)
  - thephyber 7y ago
    Guarantee, I agree. 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)
  - TheDong 7y ago
    You're being pointlessly pedantic. 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".
chefkoch 7y ago
I guess Most would use rainbow tables so it wouldn't matter.
geofft 7y ago
You can always make a fast hashing algorithm into a slow-enough password hashing algorithm by repeating it multiple times (as with PBKDF2) or better yet using a construction that also uses a minimum amount of memory, not just computational time. For most cryptographic applications (signing data in transit, signing data at rest, computing things like Merkle trees for applications like git and dm-verity), you want a hash that is fast to compute. It's basically only password hashing and cryptocurrency mining that needs to be slow. BLAKE3's readme says: (https://github.com/BLAKE3-team/BLAKE3 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/argon2-specs.pdf https://github.com/P-H-C/phc-winner-argon2/blob/master/argon...) is based on BLAKE2b.
- deleted 7y ago
  [deleted]
mrb 7y ago
Faster is always a good thing for a hashing primitive. 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.
olliej 7y ago
Different hashing functions have different purposes. More specifically a hashing function used for authenticating data must be fast, so should never be used for password hashing. 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).
deleted 7y ago
[deleted]
amlozano 7y ago
We often use 'hash' as a sort-hand way of saying 'Key Derivation Function' when talking about secrets like passwords. https://en.wikipedia.org/wiki/Key_derivation_function https://en.wikipedia.org/wiki/Key_derivation_function 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.
- throwawaymath 7y ago
  Unfortunately, not all password hashing algorithms are key derivation functions. That's just a common design and closely related.
  - lucb1e 7y ago
    I've never really understood the difference between a KDF, hashing function, password hashing function, though it's relevant to know when writing reports (I work for a security company). We recommend Argon2/scrypt/bcrypt for password storage of course, but we call them KDFs and I'm not sure if it's correct. From my understanding, a KDF can be fast, but a PBKDF must be slow. Could you elaborate or do you know a good resource (short of a whole book on low level crypto details)?
    - amlozano 7y ago
      When talking about passwords specifically in our reports (I work at a security company too), I tell our team to use the same language as NIST 800-63B, since its the best "standard" for passwords and authentication I can find. 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.
baby 7y ago
you are not supposed to use a hash to store a password (because hash functions are super fast), but a password hashing function instead like Argon2.
isopede 7y ago
Another way of making it "slower" is to require more memory to compute your algorithms. The idea being that lots of memory is expensive no matter how clever you are with the computation.

jchw 7y ago

Blake3 is not for use in a password hashing algorithm; those have different goals. Check out Argon2 or bcrypt for that.

diego_moita 7y ago
Ok, thank you. I understand that it is for implementing things like dictionaries/hash tables.
- lucb1e 7y ago
  Or integrity checking for non-authenticated encryption modes (wouldn't want file encryption or https to be slow).
- nneonneo 7y ago
  No, Blake3 is a cryptographic hash algorithm, not for dictionaries or hash tables. It is intended for cryptographic signatures, file/data integrity, message authentication codes, etc. 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!
  - yarg 7y ago
    In any situation where a hashcode is cacheable (which seems to me to cover all situations where a hashcode even makes sense) a cryptographic hash function might not be such a bad idea (especially if you're IO bound in any way). 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.
    - yarg 7y ago
      Actually, a counter-point: there might be situations where you want an anti-cryptographic hash function - where similar inputs produce generally similar hashes. It could have some application as a preprocessing step in clustering (if it could be done efficiently).
      - earenndil 7y ago
        Easy: for n-byte output, separate input into n equally-sized chunks (pad with zeroes if not enough). For each chunk, XOR all the bytes together.
      - nneonneo 7y ago
        Those are called fuzzy or locality-sensitive hashes; they’re used a lot in image processing for similarity testing, for example. I don’t consider them to be in the same category as normal hashes, though, because fuzzy hashes have vastly different properties.
      - dgacmu 7y ago
        The term for this is locality sensitive hashing, and it's very useful in some contexts.
    - nneonneo 7y ago
      Cryptographic hash functions can be orders of magnitude slower than functions tuned for hashtables and dictionaries. If you’re using them as hash table indexes, then you have to take the big cryptographically secure number and mod it by a small bucket count - and then you’re going to have collisions. If you don’t salt, then an attacker is going to predict the bucket indexes no matter how strong your hash function is, and since you can’t have that many buckets, they can just brute force to find collisions. 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.

codetrotter 7y ago

Blake3 is explicitly not a password hashing algorithm. For that use Bcrypt or Scrypt or Argon2. The authors of Blake3 point this out in the README of Blake3.

jayflux 7y ago

For general purpose algorithms yes. Blake3 is not a password hashing algorithm it’s a general purpose one, used for checksums or verifying 2 files are the same etc. For password hashing you’re correct they should be slow, bcrypt for example.

ilvez 7y ago
> 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 :)
- thephyber 7y ago
  Guarantee, I agree. 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)
- TheDong 7y ago
  You're being pointlessly pedantic. 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".

chefkoch 7y ago

I guess Most would use rainbow tables so it wouldn't matter.

geofft 7y ago

You can always make a fast hashing algorithm into a slow-enough password hashing algorithm by repeating it multiple times (as with PBKDF2) or better yet using a construction that also uses a minimum amount of memory, not just computational time. For most cryptographic applications (signing data in transit, signing data at rest, computing things like Merkle trees for applications like git and dm-verity), you want a hash that is fast to compute. It's basically only password hashing and cryptocurrency mining that needs to be slow. BLAKE3's readme says: (https://github.com/BLAKE3-team/BLAKE3 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/argon2-specs.pdf https://github.com/P-H-C/phc-winner-argon2/blob/master/argon...) is based on BLAKE2b.

deleted 7y ago
[deleted]

mrb 7y ago

Faster is always a good thing for a hashing primitive. 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.

olliej 7y ago

Different hashing functions have different purposes. More specifically a hashing function used for authenticating data must be fast, so should never be used for password hashing. 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).

deleted 7y ago

[deleted]

amlozano 7y ago

We often use 'hash' as a sort-hand way of saying 'Key Derivation Function' when talking about secrets like passwords. https://en.wikipedia.org/wiki/Key_derivation_function https://en.wikipedia.org/wiki/Key_derivation_function 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.

throwawaymath 7y ago
Unfortunately, not all password hashing algorithms are key derivation functions. That's just a common design and closely related.
- lucb1e 7y ago
  I've never really understood the difference between a KDF, hashing function, password hashing function, though it's relevant to know when writing reports (I work for a security company). We recommend Argon2/scrypt/bcrypt for password storage of course, but we call them KDFs and I'm not sure if it's correct. From my understanding, a KDF can be fast, but a PBKDF must be slow. Could you elaborate or do you know a good resource (short of a whole book on low level crypto details)?
  - amlozano 7y ago
    When talking about passwords specifically in our reports (I work at a security company too), I tell our team to use the same language as NIST 800-63B, since its the best "standard" for passwords and authentication I can find. 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.

baby 7y ago

you are not supposed to use a hash to store a password (because hash functions are super fast), but a password hashing function instead like Argon2.

isopede 7y ago

Another way of making it "slower" is to require more memory to compute your algorithms. The idea being that lots of memory is expensive no matter how clever you are with the computation.