4 ms·

Excuse my lack of knowledge on the subject. I know MD5 has it cryptographic security issues [1] but I almost always assumed that the main reason it was a 'weak'

Excuse my lack of knowledge on the subject. I know MD5 has it cryptographic security issues [1] but I almost always assumed that the main reason it was a 'weak' hash was due to it's speed and how, consequently, rainbow tables we're readily available. If this premise is correct, wouldn't that inherently make Blake2 less strong/secure since its faster? [1] http://en.wikipedia.org/wiki/MD5#Security http://en.wikipedia.org/wiki/MD5#Security

ftwinnovations 13y ago
It sounds like you are referring to password hashing. Neither BLAKE nor MD5 should be used for password hashing. At the bottom of the article make sure to read his section "P.S. this isn't about hashing passwords"
- zooko 13y ago
  You win a prize for reading to the end before posting!
JoshTriplett 13y ago
> I know MD5 has it cryptographic security issues [1] but I almost always assumed that the main reason it was a 'weak' hash was due to it's speed No, for hashes, you definitely want speed; that's not the problem with MD5. For applications where speed is not appropriate, such as password hashing, you want an iterated hash of some kind. (Disclaimer: as with most crypto, you want one of the existing implementations, not something custom.) The cyptographic security issues with MD5 concern breaks to the hash algorithm that make it possible to find hash collisions more easily than the number of bits in the hash would imply. A 128-bit hash should require 2128 hashing operations to find a collision against an existing fixed value. (Finding two independently chosen values with the same hash is far easier, due to the birthday problem: https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem ) MD5 has algorithmic weaknesses that make it far easier to find collisions, to the point where a current system can find some types of collisions in seconds.
dredmorbius 13y ago
For MD5, a core problem is that the total number of computable hashes is small, meaning that 1) rainbow tables are possible because the entire hash space can be stored in memory on commodity hardware, and 2) specific collisions can be trivially engineered. This means that both data authenticated by MD5 hashes (say, software package signatures) and access mediated by hashes (say: passwords, if you're incredibly stupid), can be trivially hacked.
- p1mrx 13y ago
  > the entire hash space can be stored in memory on commodity hardware Where can I buy commodity hardware with 2^128 bytes of RAM?
  - deleted 13y ago
    [deleted]
  - dredmorbius 13y ago
    I think I may have overstated my case ;-) I've taken the opportunity to look up how rainbow tables are used, and in practice, what are constructed are rainbows of likely hits, as well as exploitation of crytographic weaknesses in the MD5 algorithm. So, no, it's not the total address space, but, say, for keywords in multiple languages or known revealed passwords (of which the most common give you tremendous amounts of access -- the top 10 and 100 passwords will access many systems, and lists of millions are now available, for which rainbow tables are easily constructed). And the collision problem also remains. As for assembling large amounts of storage: with distributed systems, whether on bare metal, cloud systems, or botnets, it's possible to aggregate terrebytes of memory (not merely on-disk storage) for quite modest budgets within reach of a company or moderate-high-net-worth evil genious, let alone a state actor. For commodity x86 servers, high-end memory now looks to be ~320 - 512 GB, though terrabyte range wouldn't surprise me (I think SGI are still pushing the envelope in this area in their Rackable incarnation).
    - mnordhoff 13y ago
      That's still a bit of a distance from 5000000000000000000000000000 TiB. (I'm counting 2^128 128-bit values, not just 2^128 bytes.)
sillysaurus3 13y ago
In order to understand what makes a hash function weak, let's look at what makes one strong. From http://en.wikipedia.org/wiki/Cryptographic_hash_function http://en.wikipedia.org/wiki/Cryptographic_hash_function : "The ideal cryptographic hash function has four main properties: (a) it is easy to compute the hash value for any given message (b) it is infeasible to generate a message that has a given hash (c) it is infeasible to modify a message without changing the hash (d) it is infeasible to find two different messages with the same hash." MD5 fails (b), (c), and (d). One additional problem is due to the length extension attack: http://en.wikipedia.org/wiki/Length_extension_attack http://en.wikipedia.org/wiki/Length_extension_attack For MD5 and SHA-1, given any hash, it's possible to reconstruct the internal state of the hash function. (They're named "hash function," but "hash state machine" is probably a better way to think about it.) For example, MD5("The quick brown fox jumps over the lazy dog").hexdigest() => 9e107d9d372bb6826bd81d3542a419d6 Given 9e107d9d372bb6826bd81d3542a419d6, you can reconstruct the internal state of MD5, allowing you to continue hashing data. For example, you could add " while the cow goes moo:" MD5("The quick brown fox jumps over the lazy dog while the cow goes moo").hexdigest() => ab7e4a96438e33094a7df3d41fa89c47 MD5_FromHash("9e107d9d372bb6826bd81d3542a419d6").append(" while the cow goes moo").hexdigest() => ab7e4a96438e33094a7df3d41fa89c47 Ideally, you'd like to be able to reveal the hash publicly without revealing any details about the internal state of the hash algorithm. (It's my understanding that SHA-3 accomplishes this goal automatically.) Another way to accomplish that goal is to use HMAC-MD5 or HMAC-SHA1. At that point you can prove that you hashed something by prepending a secret key to the data. For example, HMAC_MD5("My 256-bit random secret key", "My message to be hashed").hexdigest() This would yield a hash value that you can reveal publicly, and which no attacker can append any data to. For any given data D, you can verify that you generated the hash value by computing HMAC_MD5("My 256-bit random secret key", D).hexdigest() and comparing it to the other hexdigest. If they're equal, then either some attacker has stolen your private key or you generated the hash. But if you tried this with plain old MD5, then an attacker can easily append data and trick you into thinking you generated it. This is actually all the time I have right now, so someone else please feel free to step in and fill in missing details, such as how to find two different messages which hash to the same MD5 value.
- glurgh 13y ago

ftwinnovations 13y ago

It sounds like you are referring to password hashing. Neither BLAKE nor MD5 should be used for password hashing. At the bottom of the article make sure to read his section "P.S. this isn't about hashing passwords"

zooko 13y ago
You win a prize for reading to the end before posting!

JoshTriplett 13y ago

> I know MD5 has it cryptographic security issues [1] but I almost always assumed that the main reason it was a 'weak' hash was due to it's speed No, for hashes, you definitely want speed; that's not the problem with MD5. For applications where speed is not appropriate, such as password hashing, you want an iterated hash of some kind. (Disclaimer: as with most crypto, you want one of the existing implementations, not something custom.) The cyptographic security issues with MD5 concern breaks to the hash algorithm that make it possible to find hash collisions more easily than the number of bits in the hash would imply. A 128-bit hash should require 2128 hashing operations to find a collision against an existing fixed value. (Finding two independently chosen values with the same hash is far easier, due to the birthday problem: https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem ) MD5 has algorithmic weaknesses that make it far easier to find collisions, to the point where a current system can find some types of collisions in seconds.

dredmorbius 13y ago

For MD5, a core problem is that the total number of computable hashes is small, meaning that 1) rainbow tables are possible because the entire hash space can be stored in memory on commodity hardware, and 2) specific collisions can be trivially engineered. This means that both data authenticated by MD5 hashes (say, software package signatures) and access mediated by hashes (say: passwords, if you're incredibly stupid), can be trivially hacked.

p1mrx 13y ago
> the entire hash space can be stored in memory on commodity hardware Where can I buy commodity hardware with 2^128 bytes of RAM?
- deleted 13y ago
  [deleted]
- dredmorbius 13y ago
  I think I may have overstated my case ;-) I've taken the opportunity to look up how rainbow tables are used, and in practice, what are constructed are rainbows of likely hits, as well as exploitation of crytographic weaknesses in the MD5 algorithm. So, no, it's not the total address space, but, say, for keywords in multiple languages or known revealed passwords (of which the most common give you tremendous amounts of access -- the top 10 and 100 passwords will access many systems, and lists of millions are now available, for which rainbow tables are easily constructed). And the collision problem also remains. As for assembling large amounts of storage: with distributed systems, whether on bare metal, cloud systems, or botnets, it's possible to aggregate terrebytes of memory (not merely on-disk storage) for quite modest budgets within reach of a company or moderate-high-net-worth evil genious, let alone a state actor. For commodity x86 servers, high-end memory now looks to be ~320 - 512 GB, though terrabyte range wouldn't surprise me (I think SGI are still pushing the envelope in this area in their Rackable incarnation).
  - mnordhoff 13y ago
    That's still a bit of a distance from 5000000000000000000000000000 TiB. (I'm counting 2^128 128-bit values, not just 2^128 bytes.)

sillysaurus3 13y ago

In order to understand what makes a hash function weak, let's look at what makes one strong. From http://en.wikipedia.org/wiki/Cryptographic_hash_function http://en.wikipedia.org/wiki/Cryptographic_hash_function : "The ideal cryptographic hash function has four main properties: (a) it is easy to compute the hash value for any given message (b) it is infeasible to generate a message that has a given hash (c) it is infeasible to modify a message without changing the hash (d) it is infeasible to find two different messages with the same hash." MD5 fails (b), (c), and (d). One additional problem is due to the length extension attack: http://en.wikipedia.org/wiki/Length_extension_attack http://en.wikipedia.org/wiki/Length_extension_attack For MD5 and SHA-1, given any hash, it's possible to reconstruct the internal state of the hash function. (They're named "hash function," but "hash state machine" is probably a better way to think about it.) For example, MD5("The quick brown fox jumps over the lazy dog").hexdigest() => 9e107d9d372bb6826bd81d3542a419d6 Given 9e107d9d372bb6826bd81d3542a419d6, you can reconstruct the internal state of MD5, allowing you to continue hashing data. For example, you could add " while the cow goes moo:" MD5("The quick brown fox jumps over the lazy dog while the cow goes moo").hexdigest() => ab7e4a96438e33094a7df3d41fa89c47 MD5_FromHash("9e107d9d372bb6826bd81d3542a419d6").append(" while the cow goes moo").hexdigest() => ab7e4a96438e33094a7df3d41fa89c47 Ideally, you'd like to be able to reveal the hash publicly without revealing any details about the internal state of the hash algorithm. (It's my understanding that SHA-3 accomplishes this goal automatically.) Another way to accomplish that goal is to use HMAC-MD5 or HMAC-SHA1. At that point you can prove that you hashed something by prepending a secret key to the data. For example, HMAC_MD5("My 256-bit random secret key", "My message to be hashed").hexdigest() This would yield a hash value that you can reveal publicly, and which no attacker can append any data to. For any given data D, you can verify that you generated the hash value by computing HMAC_MD5("My 256-bit random secret key", D).hexdigest() and comparing it to the other hexdigest. If they're equal, then either some attacker has stolen your private key or you generated the hash. But if you tried this with plain old MD5, then an attacker can easily append data and trick you into thinking you generated it. This is actually all the time I have right now, so someone else please feel free to step in and fill in missing details, such as how to find two different messages which hash to the same MD5 value.

glurgh 13y ago