7 ms·

Disclaimer: This is a fun thought experiment. I'm not looking for actionable results, or advocating for relying on any of this comment for actual security. I'm

Disclaimer: This is a fun thought experiment. I'm not looking for actionable results, or advocating for relying on any of this comment for actual security. I'm clearly not a cryptographer; I just think it would be interesting to talk about here, and maybe more educated people could comment on how well these approaches might mitigate the exploits in the article. Play with me in this space. I'm curious if people have any interesting ideas on how to add some seasoning to MD5 to make it more secure. That is, simple, intuitive things you can do in combination with MD5 such that all the pieces in your scheme are still easily understood and don't amount to a new hash algorithm that can only be understood as a black box. Pretend MD5 is the only hash algorithm that has ever been found. Or that you're the Gilligan's Island Professor and MD5 hashes are your coconuts. What are the most potentially useful things you can build out of the most primitive, dumb components? For example: - Output the length of the input (or a hash of the length if you must have a constant-length output) - Hash the input forwards and backwards and produce two hashes. (Remembering that, though the output is 256 bits now, you still only have coconuts to work with.) - Include more complicated variations on the input in the hashes. e.g. start in the middle and oscillate forward and backward over the input, or move the second half of the input in front of the first before hashing, or use the input/hash of the input to seed a pseudorandom re-ordering of the input before hashing, etc. - Format-aware hashing - whatever program will interpret the content of the file can also produce a hash, or some [canonical] interpretation of the content that can be hashed. e.g., for an image format, we could ask the renderer how many iterations of some operation it had to perform to render the output, or in the worst case, hash the bitmap it produced.

masklinn 4y ago
... why are you trying to "season MD5 to make it more secure"? Calls to switch off of MD5 started in 1996, and MD5 has been considered broken for some 15 years. There are non-compromised hashes, use that.
- jrootabega 4y ago
  Because it's interesting to think about. It's hacking - doing something with technology that was not intended, and sometimes ill-advised, to see what kind of interesting results we can get.
  - masklinn 4y ago
    You're just throwing random shit at the wall, it's not hacking, it's just coldfusion.
    - deleted 4y ago
      [deleted]
  - groby_b 4y ago
    Then go hack. The point is, it's not an interesting hack for the vast majority of the audience. Because they've already seen this play out over and over and over. It's like sticking your hand in a grinder and yelling "for science". The result might be new for you, and it's hacking by your definition, but I'm fairly certain the rest of the audience is OK not investing time into the experiment.
    - jrootabega 4y ago
      I have no intention of sticking my metaphorical hand, or the hand of anyone, into a metaphorical grinder. But I will point out that it was someone who thought about, and experimented with, sticking fleshy pieces into power tools, that invented the SawStop. :)
- chrismarlow9 4y ago
  Speed and resource limitations. But overall I agree with you.
  - Retr0id 4y ago
    > BLAKE2b is faster than MD5, SHA-1, SHA-2, and SHA-3, on 64-bit x86-64 and ARM architectures. BLAKE2 provides better security than SHA-2 and similar to that of SHA-3 https://en.wikipedia.org/wiki/BLAKE_(hash_function)#BLAKE2 https://en.wikipedia.org/wiki/BLAKE_(hash_function)#BLAKE2
    - yencabulator 4y ago
      And BLAKE3 is a lot faster than that.
    - waynesonfire 4y ago
      so after reading your comment I was curious why SHA-3 won the NIST competition, https://csrc.nist.gov/csrc/media/projects/hash-functions/documents/sha-3_selection_announcement.pdf https://csrc.nist.gov/csrc/media/projects/hash-functions/doc... "NIST chose KECCAK over the four other excellent finalists for its elegant design, large security margin, good general performance, excellent efficiency in hardware implementations, and for its flexibility"
      - Retr0id 4y ago
        The real reason is that SHA-3 is more different to SHA-2 in terms of fundamental design. The SHA-3 contest was launched shortly after SHA-1 was broken, and was partly just a hedge against SHA-2 being broken too.
        xani_ 4y ago
        Or NSA decided to backdoor SHA3
    - chrismarlow9 4y ago
      Cool I was not aware of this. Sha2 is just my immediate go to and haven't re evaluated any other options in a long time.
adrian_b 4y ago
Nowadays it would be a complete waste of time to try to improve MD5, because there is no reason to use it for anything. Most modern CPUs from Intel, AMD or ARM implement in hardware at least SHA-1 and SHA-256, so these both are faster than MD5 implemented in software. If you only need 128 bits, you can truncate one of the longer hashes to 128 bits. SHA-1 is the fastest in the current CPUs, so even if it is also obsolete for applications where there is an adversary who attempts to find collisions, it remains a good choice for various non-cryptographic applications that need a long hash or random numbers. SHA-1 itself was an attempt to improve on MD5. Even if it was not entirely successful, it remains many orders of magnitude stronger than MD5. So if you want to know how MD5 can be improved, the best way is to compare the MD5 and the SHA-1 algorithms, and look at what was changed between them. Another improved MD5 is the RIPEMD-160 algorithm, so comparing RIPEMD-160 with MD5 is another source for seeing how MD5 can be improved, by different methods.
- TedDoesntTalk 4y ago
  > Nowadays it would be a complete waste of time to try to improve MD5 Not as a thought experiment. Thought experiments help you to grow.
  - adrian_b 4y ago
    I agree about the usefulness of thought experiments, but there are many other much more useful thought experiments, even in the domain of hashes. A large number of people have thought for several years about how to improve MD5, and the results were SHA-1 and RIPEMD-160. It is very instructive to study the evolution from MD4 to MD5 and to SHA-1 and RIPEMD-160, but it is very unlikely that attempting 30 years later to do something better than those, without completely changing a hash algorithm structure that is now well understood as being inappropriate, can teach you anything.
    - bombcar 4y ago
      The useful thought experiments are often to realize WHY the "trick to fix MD5" you came up with doesn't work.
Retr0id 4y ago
The simplest way to improve MD5 would be to add more rounds (but as others have mentioned, there are much better choices for any practical purpose) RE your last point, I'm not quite sure what attack you're defending against there, but most file formats do not have a well-defined "canonical interpretation", much less so one that is serializable into bytes. (If you think it sounds easy, you haven't thought about it hard enough :P )
- jrootabega 4y ago
  Well, for images I still think that there is such a thing, even if it's the least interesting example: the bitmap they ultimately render. (For formats that are allowed to produce different bitmaps, it gets more difficult and maybe impossible.) For the general case of any file format: I agree this approach is the least simple/dumb/trivial and might even violate the spirit of my original comment itself. But it's still interesting. By "[canonical] interpretation", I just meant some way to fingerprint the content while understanding the format. e.g., if it's a tarball, sum the total number of files and directories inside it. Concatenate all their names in a well-defined order and hash that. I know you can't prevent collisions entirely, but it may be relatively cheap to make it so that 2 files that are different (with respect to the file format) are likely to be represented differently.
  - Retr0id 4y ago
    If for a moment we assume that you can do it reliably (which I personally doubt, even for "simple" formats) - what's the point? Why not just hash the original file? What's the benefit here? For example, I could create two different PNGs that decode to the same bitmap. Or I could create one PNG that decodes to multiple different bitmaps, depending on which implementation decodes it (due to implementation bugs and/or under-defined areas of the specification). Or I could create a PNG that is also a valid ZIP archive.
    - jrootabega 4y ago
      There's no security benefit, and I would have a hard time coming up with a practicality benefit. It's mostly just interesting to think about, especially in response to the article. The article is demonstrating fast MD5 second preimage attacks for various file formats (EDIT: apparently not preimage attacks, just collision attacks), so in response to that I'm wondering how these MD5-specific attacks might be mitigated, for fun. Consider it alternate history fiction in which we never discovered anything better than MD5 :) In your examples, though, : > two different PNGs that decode to the same bitmap But would the the PNGs also have the same MD5 hash? > one PNG that decodes to multiple different bitmaps, depending on which implementation decodes it Yeah, that would be a challenge. Relying on implementation details, or results which are allowed to vary, wouldn't work. But since this is meant to supplement an existing MD5 hash, the idea is that the format consumer/interpreter would be in a good position to produce some format-aware fingerprint that is statistically likely enough to be different when the inputs are different.
dingosity 4y ago
Might be useful to look up the prior research. Search for Merkle-Damgard. And the IACR ePrint archive has quite a few interesting reads: https://eprint.iacr.org/ https://eprint.iacr.org/ I get it that you're just hacking around, but reading what the olds said about MD5 is useful.
- dingosity 4y ago
  Oh. Also. What you're doing here is "finding a second pre-image" which is slightly different from finding a collision. A second pre-image is where you already have a message and a hash and you want to find a second message that hashes to the same thing. Technically speaking, a collision is just finding two messages that hash to the same thing, but you don't necessarily get to pick what the two messages are. I mention it not to be an academic snob, but because when you read the literature, there are plenty of examples where you sort of have to know the two things are distinct, at least to the academics.
  - jrootabega 4y ago
    Thanks for pointing that out. It's definitely important to understand the difference, and not just academically. It helps us understand that the consequences of MD5 being broken have only been proven to work for collision attacks, and not preimage attacks. (But I still don't think using MD5 when you can use more secure alternatives is a good idea.)
AgentME 4y ago
>- Output the length of the input (or a hash of the length if you must have a constant-length output) I think all of the known MD5 collisions (and SHA-1 collisions even) are of inputs that are the same length.
- jrootabega 4y ago
  Interesting. I submitted by original comment with the misconception that it second preimage attacks against MD5 were feasible and were being used by the article. So I see how in the case where you want to defend against collisions (e.g. a malicious certificate signing request), length awareness might not help. I'm not sure if that would apply to a second preimage attack, though.
LawTalkingGuy 4y ago
There's a difference between bringing MD5 up to modern strength and simply blocking the attempts of attackers who've attained this MD5 forging kit. The later is an interesting though experiment. The point of a hash is to avoid feeding malicious data further into your pipeline so solutions that involve parsing the file and hashing its actual data-streams aren't a good idea. We'll focus on detecting the change before looking at the data. To make the attack harder, use file formats without expandable or optional sections. This attack works by parsing known file formats and making allowable changes. If you had encryption as one of your coconuts it would make this easier by making the whole file opaque, but the encryption could also be used to generate a hash-like construction so if you have good enough encryption you wouldn't be stuck with MD5 and there wouldn't be much thought experiment left... To stop this specific attack, assuming you had to use these formats, using MD5(file+reversed_file) or MD5(file)+MD5(reversed_file) or MD5('secret'+file) would work. This is massively beyond what a most people could make the tools do but it's probably not that much cryptographically harder. If your solution was a secret it would be pretty effective. The problem is that if you don't have encryption then they're watching you communicate. They can see the hash sum you tell the recipient to expect, and if this is the first time you've used this scheme, the steps to use to check it. But even if they don't observe this though, you're only using a small set of non-crypto operations and they can just try millions of combos (reverse the file, append a second copy, interleave bytes, etc.) and see if anything produces the same hash. Then they have discovered your algorithm and they can plan to modify their tools to perform the attack.
- jrootabega 4y ago
  Oh, I think secrecy would be against the spirit of the experiment. And yeah, I wonder what kind of mods they would need to make to their tools in response. If it takes 10 years to generate the collisions, then it seems like it might be a worthwhile approach (in the thought experiment universe only). But we should also recognize that the article demonstrates collision attacks, not preimage attacks, which would be the attack you want to worry about if you are using a trusted hash to verify a file you received over an untrusted channel.
bawolff 4y ago
For sha1, people made a system where you can detect the patterns that lead to a collision, and (for example) replace it with a different hash only for inputs that would be a problem. https://github.com/cr-marcstevens/sha1collisiondetection https://github.com/cr-marcstevens/sha1collisiondetection i think git does this to eek more life out of sha1. I imagine you could take a similar counter-cryptnalysis approach to md5. (I am out of my depth here, so there could be reasons this doesnt work for md5 im unaware of)
- jrootabega 4y ago
  Very cool! I searched for it here, and found some comments that imply it's possible to detect these attacks in MD5, but nothing too detailed. Much more advanced than I was thinking, but still hacky enough that it satisfies me!
  - versteegen 4y ago
    Yes, the paper linked elsewhere in this thread introduced counter-cryptanalysis, for both MD5 and SHA1: https://marc-stevens.nl/research/papers/C13-S.pdf https://marc-stevens.nl/research/papers/C13-S.pdf "Counter-cryptanalysis in principle enables the continued secure use of weak cryptographic primitives."
a1369209993 4y ago
The real "fuck you, cryptanalysts" option is two-pass hashing: H(m) = H0( H0(m) ~ m ) where H0 can be MD5 or any other normal hash and ~ is concatenation. This effectively adds a random salt to the hash, and even if a collision is found in the base hash, the salted version will 'start' (reach the start of the message) in a different state, so the collision blocks that carefully cancel out differences in the H0 state won't work on the salted state and vice versa. This doesn't eliminate the possibility of cryptanalysis in principle, but it does make it much, much harder.
twotwotwo 4y ago
One thing that, for me, sort of undermined the idea of adding strength "around" a weak hash was the multicollisions paper: https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf https://www.iacr.org/archive/crypto2004/31520306/multicollis... Intuitively you might think concatenating two hashes could make something way stronger than either, but the way these functions were constructed, that isn't necessarily true. It also shows a trick to efficiently make exponentially more collisions with linearly more work. It's not that those specific tricks work against every idea for fortification; the paper says it doesn't break some schemes you'd expect it to. But it does show that a weak Merkle-Damgård compression function has weird indirect effects, and that makes things built on one seem shakier. It can make some difference to try to build a system not to rely on collision resistance if possible, or not to give the attacker full control over the input to the hash. For example, CAs started putting a random serial number not predictable by the requestor into the generated cert, so the attacker couldn't predict all of the content being signed. They still moved off SHA-1, of course. There are lots of good things to say about newer functions. They do more work (more rounds, bigger state), may make better choices of where to spend their effort (newer functions seem to mix bits faster), and use today's CPU capabilities effectively (recent hashes support SIMD parallelism; SHA-512 uses your 64-bit ALU; SHA-256 even has x64 instructions).

masklinn 4y ago

... why are you trying to "season MD5 to make it more secure"? Calls to switch off of MD5 started in 1996, and MD5 has been considered broken for some 15 years. There are non-compromised hashes, use that.

jrootabega 4y ago
Because it's interesting to think about. It's hacking - doing something with technology that was not intended, and sometimes ill-advised, to see what kind of interesting results we can get.
- masklinn 4y ago
  You're just throwing random shit at the wall, it's not hacking, it's just coldfusion.
  - deleted 4y ago
    [deleted]
- groby_b 4y ago
  Then go hack. The point is, it's not an interesting hack for the vast majority of the audience. Because they've already seen this play out over and over and over. It's like sticking your hand in a grinder and yelling "for science". The result might be new for you, and it's hacking by your definition, but I'm fairly certain the rest of the audience is OK not investing time into the experiment.
  - jrootabega 4y ago
    I have no intention of sticking my metaphorical hand, or the hand of anyone, into a metaphorical grinder. But I will point out that it was someone who thought about, and experimented with, sticking fleshy pieces into power tools, that invented the SawStop. :)
chrismarlow9 4y ago
Speed and resource limitations. But overall I agree with you.
- Retr0id 4y ago
  > BLAKE2b is faster than MD5, SHA-1, SHA-2, and SHA-3, on 64-bit x86-64 and ARM architectures. BLAKE2 provides better security than SHA-2 and similar to that of SHA-3 https://en.wikipedia.org/wiki/BLAKE_(hash_function)#BLAKE2 https://en.wikipedia.org/wiki/BLAKE_(hash_function)#BLAKE2
  - yencabulator 4y ago
    And BLAKE3 is a lot faster than that.
  - waynesonfire 4y ago
    so after reading your comment I was curious why SHA-3 won the NIST competition, https://csrc.nist.gov/csrc/media/projects/hash-functions/documents/sha-3_selection_announcement.pdf https://csrc.nist.gov/csrc/media/projects/hash-functions/doc... "NIST chose KECCAK over the four other excellent finalists for its elegant design, large security margin, good general performance, excellent efficiency in hardware implementations, and for its flexibility"
    - Retr0id 4y ago
      The real reason is that SHA-3 is more different to SHA-2 in terms of fundamental design. The SHA-3 contest was launched shortly after SHA-1 was broken, and was partly just a hedge against SHA-2 being broken too.
      - xani_ 4y ago
        Or NSA decided to backdoor SHA3
  - chrismarlow9 4y ago
    Cool I was not aware of this. Sha2 is just my immediate go to and haven't re evaluated any other options in a long time.

adrian_b 4y ago

Nowadays it would be a complete waste of time to try to improve MD5, because there is no reason to use it for anything. Most modern CPUs from Intel, AMD or ARM implement in hardware at least SHA-1 and SHA-256, so these both are faster than MD5 implemented in software. If you only need 128 bits, you can truncate one of the longer hashes to 128 bits. SHA-1 is the fastest in the current CPUs, so even if it is also obsolete for applications where there is an adversary who attempts to find collisions, it remains a good choice for various non-cryptographic applications that need a long hash or random numbers. SHA-1 itself was an attempt to improve on MD5. Even if it was not entirely successful, it remains many orders of magnitude stronger than MD5. So if you want to know how MD5 can be improved, the best way is to compare the MD5 and the SHA-1 algorithms, and look at what was changed between them. Another improved MD5 is the RIPEMD-160 algorithm, so comparing RIPEMD-160 with MD5 is another source for seeing how MD5 can be improved, by different methods.

TedDoesntTalk 4y ago
> Nowadays it would be a complete waste of time to try to improve MD5 Not as a thought experiment. Thought experiments help you to grow.
- adrian_b 4y ago
  I agree about the usefulness of thought experiments, but there are many other much more useful thought experiments, even in the domain of hashes. A large number of people have thought for several years about how to improve MD5, and the results were SHA-1 and RIPEMD-160. It is very instructive to study the evolution from MD4 to MD5 and to SHA-1 and RIPEMD-160, but it is very unlikely that attempting 30 years later to do something better than those, without completely changing a hash algorithm structure that is now well understood as being inappropriate, can teach you anything.
  - bombcar 4y ago
    The useful thought experiments are often to realize WHY the "trick to fix MD5" you came up with doesn't work.

Retr0id 4y ago

The simplest way to improve MD5 would be to add more rounds (but as others have mentioned, there are much better choices for any practical purpose) RE your last point, I'm not quite sure what attack you're defending against there, but most file formats do not have a well-defined "canonical interpretation", much less so one that is serializable into bytes. (If you think it sounds easy, you haven't thought about it hard enough :P )

jrootabega 4y ago
Well, for images I still think that there is such a thing, even if it's the least interesting example: the bitmap they ultimately render. (For formats that are allowed to produce different bitmaps, it gets more difficult and maybe impossible.) For the general case of any file format: I agree this approach is the least simple/dumb/trivial and might even violate the spirit of my original comment itself. But it's still interesting. By "[canonical] interpretation", I just meant some way to fingerprint the content while understanding the format. e.g., if it's a tarball, sum the total number of files and directories inside it. Concatenate all their names in a well-defined order and hash that. I know you can't prevent collisions entirely, but it may be relatively cheap to make it so that 2 files that are different (with respect to the file format) are likely to be represented differently.
- Retr0id 4y ago
  If for a moment we assume that you can do it reliably (which I personally doubt, even for "simple" formats) - what's the point? Why not just hash the original file? What's the benefit here? For example, I could create two different PNGs that decode to the same bitmap. Or I could create one PNG that decodes to multiple different bitmaps, depending on which implementation decodes it (due to implementation bugs and/or under-defined areas of the specification). Or I could create a PNG that is also a valid ZIP archive.
  - jrootabega 4y ago
    There's no security benefit, and I would have a hard time coming up with a practicality benefit. It's mostly just interesting to think about, especially in response to the article. The article is demonstrating fast MD5 second preimage attacks for various file formats (EDIT: apparently not preimage attacks, just collision attacks), so in response to that I'm wondering how these MD5-specific attacks might be mitigated, for fun. Consider it alternate history fiction in which we never discovered anything better than MD5 :) In your examples, though, : > two different PNGs that decode to the same bitmap But would the the PNGs also have the same MD5 hash? > one PNG that decodes to multiple different bitmaps, depending on which implementation decodes it Yeah, that would be a challenge. Relying on implementation details, or results which are allowed to vary, wouldn't work. But since this is meant to supplement an existing MD5 hash, the idea is that the format consumer/interpreter would be in a good position to produce some format-aware fingerprint that is statistically likely enough to be different when the inputs are different.

dingosity 4y ago

Might be useful to look up the prior research. Search for Merkle-Damgard. And the IACR ePrint archive has quite a few interesting reads: https://eprint.iacr.org/ https://eprint.iacr.org/ I get it that you're just hacking around, but reading what the olds said about MD5 is useful.

dingosity 4y ago
Oh. Also. What you're doing here is "finding a second pre-image" which is slightly different from finding a collision. A second pre-image is where you already have a message and a hash and you want to find a second message that hashes to the same thing. Technically speaking, a collision is just finding two messages that hash to the same thing, but you don't necessarily get to pick what the two messages are. I mention it not to be an academic snob, but because when you read the literature, there are plenty of examples where you sort of have to know the two things are distinct, at least to the academics.
- jrootabega 4y ago
  Thanks for pointing that out. It's definitely important to understand the difference, and not just academically. It helps us understand that the consequences of MD5 being broken have only been proven to work for collision attacks, and not preimage attacks. (But I still don't think using MD5 when you can use more secure alternatives is a good idea.)

AgentME 4y ago

>- Output the length of the input (or a hash of the length if you must have a constant-length output) I think all of the known MD5 collisions (and SHA-1 collisions even) are of inputs that are the same length.

jrootabega 4y ago
Interesting. I submitted by original comment with the misconception that it second preimage attacks against MD5 were feasible and were being used by the article. So I see how in the case where you want to defend against collisions (e.g. a malicious certificate signing request), length awareness might not help. I'm not sure if that would apply to a second preimage attack, though.

LawTalkingGuy 4y ago

There's a difference between bringing MD5 up to modern strength and simply blocking the attempts of attackers who've attained this MD5 forging kit. The later is an interesting though experiment. The point of a hash is to avoid feeding malicious data further into your pipeline so solutions that involve parsing the file and hashing its actual data-streams aren't a good idea. We'll focus on detecting the change before looking at the data. To make the attack harder, use file formats without expandable or optional sections. This attack works by parsing known file formats and making allowable changes. If you had encryption as one of your coconuts it would make this easier by making the whole file opaque, but the encryption could also be used to generate a hash-like construction so if you have good enough encryption you wouldn't be stuck with MD5 and there wouldn't be much thought experiment left... To stop this specific attack, assuming you had to use these formats, using MD5(file+reversed_file) or MD5(file)+MD5(reversed_file) or MD5('secret'+file) would work. This is massively beyond what a most people could make the tools do but it's probably not that much cryptographically harder. If your solution was a secret it would be pretty effective. The problem is that if you don't have encryption then they're watching you communicate. They can see the hash sum you tell the recipient to expect, and if this is the first time you've used this scheme, the steps to use to check it. But even if they don't observe this though, you're only using a small set of non-crypto operations and they can just try millions of combos (reverse the file, append a second copy, interleave bytes, etc.) and see if anything produces the same hash. Then they have discovered your algorithm and they can plan to modify their tools to perform the attack.

jrootabega 4y ago
Oh, I think secrecy would be against the spirit of the experiment. And yeah, I wonder what kind of mods they would need to make to their tools in response. If it takes 10 years to generate the collisions, then it seems like it might be a worthwhile approach (in the thought experiment universe only). But we should also recognize that the article demonstrates collision attacks, not preimage attacks, which would be the attack you want to worry about if you are using a trusted hash to verify a file you received over an untrusted channel.

bawolff 4y ago

For sha1, people made a system where you can detect the patterns that lead to a collision, and (for example) replace it with a different hash only for inputs that would be a problem. https://github.com/cr-marcstevens/sha1collisiondetection https://github.com/cr-marcstevens/sha1collisiondetection i think git does this to eek more life out of sha1. I imagine you could take a similar counter-cryptnalysis approach to md5. (I am out of my depth here, so there could be reasons this doesnt work for md5 im unaware of)

jrootabega 4y ago
Very cool! I searched for it here, and found some comments that imply it's possible to detect these attacks in MD5, but nothing too detailed. Much more advanced than I was thinking, but still hacky enough that it satisfies me!
- versteegen 4y ago
  Yes, the paper linked elsewhere in this thread introduced counter-cryptanalysis, for both MD5 and SHA1: https://marc-stevens.nl/research/papers/C13-S.pdf https://marc-stevens.nl/research/papers/C13-S.pdf "Counter-cryptanalysis in principle enables the continued secure use of weak cryptographic primitives."

a1369209993 4y ago

The real "fuck you, cryptanalysts" option is two-pass hashing: H(m) = H0( H0(m) ~ m ) where H0 can be MD5 or any other normal hash and ~ is concatenation. This effectively adds a random salt to the hash, and even if a collision is found in the base hash, the salted version will 'start' (reach the start of the message) in a different state, so the collision blocks that carefully cancel out differences in the H0 state won't work on the salted state and vice versa. This doesn't eliminate the possibility of cryptanalysis in principle, but it does make it much, much harder.

twotwotwo 4y ago

One thing that, for me, sort of undermined the idea of adding strength "around" a weak hash was the multicollisions paper: https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf https://www.iacr.org/archive/crypto2004/31520306/multicollis... Intuitively you might think concatenating two hashes could make something way stronger than either, but the way these functions were constructed, that isn't necessarily true. It also shows a trick to efficiently make exponentially more collisions with linearly more work. It's not that those specific tricks work against every idea for fortification; the paper says it doesn't break some schemes you'd expect it to. But it does show that a weak Merkle-Damgård compression function has weird indirect effects, and that makes things built on one seem shakier. It can make some difference to try to build a system not to rely on collision resistance if possible, or not to give the attacker full control over the input to the hash. For example, CAs started putting a random serial number not predictable by the requestor into the generated cert, so the attacker couldn't predict all of the content being signed. They still moved off SHA-1, of course. There are lots of good things to say about newer functions. They do more work (more rounds, bigger state), may make better choices of where to spend their effort (newer functions seem to mix bits faster), and use today's CPU capabilities effectively (recent hashes support SIMD parallelism; SHA-512 uses your 64-bit ALU; SHA-256 even has x64 instructions).