25 ms·

Hash collisions and exploitations – Instant MD5 collision

167 points by losfair 4y ago

westurner 4y ago
MD5 > History, Security > Collision vulnerabilities: https://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities https://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities
retrocryptid 4y ago
And yet MD5 is still recommended in Applied Cryptography.
- traceroute66 4y ago
  > And yet MD5 is still recommended in Applied Cryptography. I'm guessing this is the usual HN dig at Schneier's book ? Fact is that Schneier was already warning against MD5 as far back as 1996. And if you look on more recent blog posts, he is not exactly silent on dissuading people against MD5. Fact is that like it or not, even today, MD5 still sees usage in the crypto landscape (see AWS S3 Content-MD5, for example). Therefore being able to understand how it works is still relevant, and in that respect Schneier's book is as good as any other.
  - stevewatson301 4y ago
    Further, SHA-256 operates on the same principle as well (repeated iterations of a one-way compression function, called a Merkle-Damgard iterative construction[1]). Learning how MD5 works is quite instructive in that regard. [1] https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_co...
  - dylan604 4y ago
    Like everything else in the world, knowing your audience, intended use, etc plays a key role. If you're protecting data against state actors, then yes, MD5 is not good enough. If you're just trying to decide if a transfer of a file went across a network without munging the data, then MD5 is good enough. If you're trying to post that file onto something that is publicly facing and want to provide the person downloading the file that it has not been modified, MD5 is probably not the best method.
    - dingosity 4y ago
      The point the OP made is it's easy to construct a second preimage with MD5. So if a bad guy, even a bad guy with meager resources, modifies the hash or the data in transit, you won't be able to identify the change the MITM made in either the data or the hash while it was transmitted. What you're probably thinking is a digital signature, which combines a hash and an asymmetric cipher (or a keyed hash if you keep that key secret.) But even then a bad actor can construct a second pre-image with MD5 which would cause the digital signature validate as authentic even though it's been changed. And an adversary with meager computational resources could perform this hack. This is the OP's point. You don't have to be a state actor to do this.
      - dylan604 4y ago
        Essentially, I was agreeing that MD5 is worthless for anything "secure" from 3rd party manipulation. However, it is fine for verification of non-adversarial purposes. It's much faster to run MD5 than SHA256 over a 60-120GB MOV file. Copying camera original footage from the card that is still warm from the camera and making copies to client deliverable storage before telling camera dept that it is okay to wipe the card and reuse is a thing I have done a lot. Speed is important. Security is not a concern at all. Copying a large MOV file from one storage pool to another, retrieving large media assets from tape archive, etc are also common situations where you just want to know that the copy is actually what you think it is from I/O errors during whatever transfer process. In these situations, I have zero concern that someone wearing a blackhat maliciously manipulated the data during the transfer.
        dingosity 4y ago
        The cost of the calculation of the hash is dwarfed by the cost of copying to/from an SD card (or even nvme devices.) If you hash the file as you transfer it, you'll not notice the difference between MD5 and SHA256.
  - retrocryptid 4y ago
    It's more of a dig on people who claim MD5 is okay because it's in Schneier's book. Not so much a dig on Schneier himself. And yes. I understand MD5 etag headers are common. I even understand that MD5 still passes the avalanche test -- Robshaw's observations on MD5 in 1996 are just as valid today. But according to Sasaki & Aoki, //both// collisions and second pre-image calculation are faster than brute force. Maybe MD5 //shouldn't// be used if all you need is avalanche. It turns out that SHA256 has both collision and second pre-image calculation resistance //as well as// avalanche effect. Maybe use that one instead.
    - fluoridation 4y ago
      I don't remember the last time I saw anyone use MD5 for cryptography. It's still used a lot for data integrity, because it still works perfectly well for that and it's faster than the SHA family (when there's no hardware implementation).
      - jabl 4y ago
        Based on a quick test here on a 417MB .tar.gz file I had lying around, best of 5 times for various coreutils (8.32) implementations: - md5sum: 0.570s - sha1sum: 0.667s - sha256sum: 1.662s - sha512sum: 1.011s - b2sum: 0.486s - cksum: 0.982s In conclusion: b2sum is both the fastest and AFAIU considered secure.
        retrocryptid 4y ago
        Moving from MD5 to SHA256 means we just about triple the amount of time it takes to generate a hash. But I suggest there are few applications where this speed improvement justifies the confusion I've seen in junior engineers who believe MD5 is okay because a. they use MD5SUM and b. Bruce Schneier said it was okay. Don't get me wrong. I trust that //YOU// will know not depend on a MD5 hash for anything where a bad guy can modify content over the wire. But... I'm going to go out on a limb and guess you're somewhat experienced. I worry about the kids who without the benefit of experience re-enact scenes from the cryptography edition of Lord of the Flies. But... if you know what you're doing... sure... use MD5... There's certainly no way your code will ever be used by a less experienced engineer, right?
omk 4y ago
Have always thought of creating email addresses with colliding MD5 hashes only to see how Gravatar's MD5 URL reacts to it.
londons_explore 4y ago
Question for people into cryptography + data archiving.... If I want to store data for 500 years, I want future people to be reasonably sure of the integrity of the data, both against 'bit rot', but also deliberate tampering. Is the best available approach to hash the data with a bunch of hash algorithms and publish all the hashes? Then if any hash algorithm remains unbroken, the integrity of my data is certainly still good. An attacker would have to do a simultaneous preimage attack for every hash algorithm I choose to break the scheme, which historically has never happened to my knowledge.
- egeozcan 4y ago
  Simultaneously finding collisions in multiple hash algorithms with 2 random inputs would be a hard task, and if one of those inputs is predetermined (your data), and the other needs to include a change that the attacker wants to see there? that really sounds impossible. But on the other hand, we are talking 500 years...
  - Perseids 4y ago
    The scenario is not finding collisions though. I assume londons_explore somehow finds a way to build a trusted relationship and channel with the future [1], say a piece of leather with the hashes burned into it that is ... stored publicly in Louvre with a ton of photo evidence spread all over the earth hence. As londons_explore is trusted, you only need Second Pre-image Resistance: Given a file (that was created outside of the attackers control) find a second file which has the same hash as the first file. Second pre-image attacks are super hard to accomplish. MD5 is still Second Preimage Resistant! Adding a second random input to the hash function, like you propose (that is to prime the internal state of the hash function with same random input, so when hashing of the usage data starts, the internal state of the hash function is unknown to the attacker) makes collision attacks much harder. In fact there is a term for that: target collision resistance. But second pre-image attacks, where the random input used for the hashing are known, don't get any harder. And if you don't transmit the random input over the secure channel as well, than second pre-image attacks get easier even (theoretically), as attackers have the possibility to manipulate the internal state outside of the usage data. Btw. reliance of target collision resistance, instead of collision resistance, is why Ed25519/Ed448 are much more resilient to problems with the hash function than ECDSA or any common RSA signature scheme. MD5 is still target collision resistant last time I checked. Remember the debacle of forged MD5 and later SHA1 certificates [2] ? Completely avoidable, if better signature schemes had been used. [1] Otherwise https://news.ycombinator.com/item?id=32912052 https://news.ycombinator.com/item?id=32912052 applies. [2] https://www.win.tue.nl/hashclash/rogue-ca/ https://www.win.tue.nl/hashclash/rogue-ca/
jrootabega 4y ago
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.
mikessoft_gmail 4y ago
abetusk 4y ago
From the README: """ Colliding any pair of files has been possible for many years, but it takes several hours each time, with no shortcut. This page provide tricks specific to file formats and precomputed collision prefixes to make collision instant. git clone. Run Script. Done. """ Could anyone weigh in on whether these ideas can be generalized to speed up MD5 collisions in general?
- Retr0id 4y ago
  What do you mean by this? You can't precompute all possible colliding blocks.
  - dingosity 4y ago
    They mean "compute the first pre-image."
1970-01-01 4y ago
The most interesting part was collision with certificates. Platinum ticket for malware.
EGreg 4y ago
I asked a while ago, whether it’s feasible to get another file to generate a given hash. The answer is no. Not even with MD5. Just be very sure that this is the guarantee you are looking for. Often, for Merkle Trees etc. that is EXACTLY what is needed. Can someone craft input files (eg images) to fool your system? Yes, but only at their own expense. Sometimes if you want the system to be resilient even in the fact of malicious inputs then yes, you should use SHA256 and higher.
- sacrosancty 4y ago
  They might not realize they're hurting themselves, which makes it a bug. Backblaze did this with one of these hash collisions. You could back up two different (colliding) files and when you tried to restore both, only two copies of the same file would be returned, the other one apparently lost forever. Why would you have colliding files? Perhaps because you're somebody working on hash collisions and have collected some examples.
omoikane 4y ago
See also: "Lifetimes of cryptographic hash functions" - https://valerieaurora.org/hash.html https://valerieaurora.org/hash.html MD5 appears to be firmly in the "fun party trick" stage.
- magila 4y ago
  That page hasn't aged all that well. The prediction that applications would need to switch to a new hash function "every few years" hasn't panned out. The feared improved attacks on SHA-2 have failed to materialize. Applications that chose SHA-2 20 years ago are still quite secure today. It seems we just weren't very good at designing hash functions in the 90s.
  - ComplexSystems 4y ago
    Good news for Bitcoin, as long as SHA-256 remains secure forever.
- waynesonfire 4y ago
  "In 2007, the NIST launched the SHA-3 competition" and the following year, 2008 SHA-2 is labeled "Minor weakness". Well, great timing on that competition!
Dwedit 4y ago
For anyone out there still using MD5 for any reason, check out this PDF file: https://www.alchemistowl.org/pocorgtfo/pocorgtfo14.pdf https://www.alchemistowl.org/pocorgtfo/pocorgtfo14.pdf (42MB). You can also rename it to a .NES file and run it in a NES emulator. It's a PDF File which is also a NES ROM that displays its own MD5 sum. The PDF also shows its own MD5 sum a few times. (The MD5 sum also happens to begin with 5EAF00D) When an arbitrary MD5 can be created that easily, it's useless for any cryptographic applications, or even any data integrity.
- pxx 4y ago
  MD5 may not be collision resistant, but the logic in your conclusion is completely wrong. There is no feasible pre-image attack on MD5. The MD5 generated _was not arbitrary_; they seem to have just brute-forced a few of the leading bytes and then did a Nostradamus attack. Again: finding something that hashes to an arbitrary MD5 sum is still not known to be feasible. This isn't a particularly good reason to use MD5, but this also means that MD5 is not broken in the way you think it is. When somebody finds something that hashes to all zeroes you can finally say that MD5 is completely broken. It is not known to be at that point yet.
  - TillE 4y ago
    Right. Nobody should use MD5 if at all possible, but it's important to understand how it is and isn't broken. Like, if I have the MD5 hash of a binary from a trusted source, I can basically rely on that, unless the attacker was involved in producing the trusted binary. In which case I'd usually have bigger concerns.
    - dingosity 4y ago
      No. MD5 is broken. You can find a pre-image faster than brute force. This is the definition of "broken" for a hash function. https://link.springer.com/chapter/10.1007/978-3-642-01001-9_8 https://link.springer.com/chapter/10.1007/978-3-642-01001-9_...
      - 4y ago
dekhn 4y ago
Side note: I recently saw an example code using tensorflow to determine the private key of some cryptosystem. I can't find it. It was literally operating on the bits of the key and somehow had a loss function. Any ideas?
- bawolff 4y ago
  I mean, if it worked it was probably for a really shitty cryptosystem, and hence less interesting.
a-dub 4y ago
in the era of high fidelity generative models, i suspect that the future of media formats will be security forward with built-in protections against length extension attacks. i'm having a hard time imagining any other future than one where people only trust signed media, and media is possibly even signed in hardware by actual physical sensors/compressors.
rurban 4y ago
Ad exploitations: I've added some inverses of hash functions here: https://github.com/rurban/smhasher/tree/master/inverse https://github.com/rurban/smhasher/tree/master/inverse
johnray7866 4y ago
[dead]

167 points by losfair 4y ago

MD5 > History, Security > Collision vulnerabilities: https://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities https://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities

retrocryptid 4y ago

And yet MD5 is still recommended in Applied Cryptography.

traceroute66 4y ago
> And yet MD5 is still recommended in Applied Cryptography. I'm guessing this is the usual HN dig at Schneier's book ? Fact is that Schneier was already warning against MD5 as far back as 1996. And if you look on more recent blog posts, he is not exactly silent on dissuading people against MD5. Fact is that like it or not, even today, MD5 still sees usage in the crypto landscape (see AWS S3 Content-MD5, for example). Therefore being able to understand how it works is still relevant, and in that respect Schneier's book is as good as any other.
- stevewatson301 4y ago
  Further, SHA-256 operates on the same principle as well (repeated iterations of a one-way compression function, called a Merkle-Damgard iterative construction[1]). Learning how MD5 works is quite instructive in that regard. [1] https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_co...
- dylan604 4y ago
  Like everything else in the world, knowing your audience, intended use, etc plays a key role. If you're protecting data against state actors, then yes, MD5 is not good enough. If you're just trying to decide if a transfer of a file went across a network without munging the data, then MD5 is good enough. If you're trying to post that file onto something that is publicly facing and want to provide the person downloading the file that it has not been modified, MD5 is probably not the best method.
  - dingosity 4y ago
    The point the OP made is it's easy to construct a second preimage with MD5. So if a bad guy, even a bad guy with meager resources, modifies the hash or the data in transit, you won't be able to identify the change the MITM made in either the data or the hash while it was transmitted. What you're probably thinking is a digital signature, which combines a hash and an asymmetric cipher (or a keyed hash if you keep that key secret.) But even then a bad actor can construct a second pre-image with MD5 which would cause the digital signature validate as authentic even though it's been changed. And an adversary with meager computational resources could perform this hack. This is the OP's point. You don't have to be a state actor to do this.
    - dylan604 4y ago
      Essentially, I was agreeing that MD5 is worthless for anything "secure" from 3rd party manipulation. However, it is fine for verification of non-adversarial purposes. It's much faster to run MD5 than SHA256 over a 60-120GB MOV file. Copying camera original footage from the card that is still warm from the camera and making copies to client deliverable storage before telling camera dept that it is okay to wipe the card and reuse is a thing I have done a lot. Speed is important. Security is not a concern at all. Copying a large MOV file from one storage pool to another, retrieving large media assets from tape archive, etc are also common situations where you just want to know that the copy is actually what you think it is from I/O errors during whatever transfer process. In these situations, I have zero concern that someone wearing a blackhat maliciously manipulated the data during the transfer.
      - dingosity 4y ago
        The cost of the calculation of the hash is dwarfed by the cost of copying to/from an SD card (or even nvme devices.) If you hash the file as you transfer it, you'll not notice the difference between MD5 and SHA256.
- retrocryptid 4y ago
  It's more of a dig on people who claim MD5 is okay because it's in Schneier's book. Not so much a dig on Schneier himself. And yes. I understand MD5 etag headers are common. I even understand that MD5 still passes the avalanche test -- Robshaw's observations on MD5 in 1996 are just as valid today. But according to Sasaki & Aoki, //both// collisions and second pre-image calculation are faster than brute force. Maybe MD5 //shouldn't// be used if all you need is avalanche. It turns out that SHA256 has both collision and second pre-image calculation resistance //as well as// avalanche effect. Maybe use that one instead.
  - fluoridation 4y ago
    I don't remember the last time I saw anyone use MD5 for cryptography. It's still used a lot for data integrity, because it still works perfectly well for that and it's faster than the SHA family (when there's no hardware implementation).
    - jabl 4y ago
      Based on a quick test here on a 417MB .tar.gz file I had lying around, best of 5 times for various coreutils (8.32) implementations: - md5sum: 0.570s - sha1sum: 0.667s - sha256sum: 1.662s - sha512sum: 1.011s - b2sum: 0.486s - cksum: 0.982s In conclusion: b2sum is both the fastest and AFAIU considered secure.
      - retrocryptid 4y ago
        Moving from MD5 to SHA256 means we just about triple the amount of time it takes to generate a hash. But I suggest there are few applications where this speed improvement justifies the confusion I've seen in junior engineers who believe MD5 is okay because a. they use MD5SUM and b. Bruce Schneier said it was okay. Don't get me wrong. I trust that //YOU// will know not depend on a MD5 hash for anything where a bad guy can modify content over the wire. But... I'm going to go out on a limb and guess you're somewhat experienced. I worry about the kids who without the benefit of experience re-enact scenes from the cryptography edition of Lord of the Flies. But... if you know what you're doing... sure... use MD5... There's certainly no way your code will ever be used by a less experienced engineer, right?

omk 4y ago

Have always thought of creating email addresses with colliding MD5 hashes only to see how Gravatar's MD5 URL reacts to it.

londons_explore 4y ago

Question for people into cryptography + data archiving.... If I want to store data for 500 years, I want future people to be reasonably sure of the integrity of the data, both against 'bit rot', but also deliberate tampering. Is the best available approach to hash the data with a bunch of hash algorithms and publish all the hashes? Then if any hash algorithm remains unbroken, the integrity of my data is certainly still good. An attacker would have to do a simultaneous preimage attack for every hash algorithm I choose to break the scheme, which historically has never happened to my knowledge.

egeozcan 4y ago
Simultaneously finding collisions in multiple hash algorithms with 2 random inputs would be a hard task, and if one of those inputs is predetermined (your data), and the other needs to include a change that the attacker wants to see there? that really sounds impossible. But on the other hand, we are talking 500 years...
- Perseids 4y ago
  The scenario is not finding collisions though. I assume londons_explore somehow finds a way to build a trusted relationship and channel with the future [1], say a piece of leather with the hashes burned into it that is ... stored publicly in Louvre with a ton of photo evidence spread all over the earth hence. As londons_explore is trusted, you only need Second Pre-image Resistance: Given a file (that was created outside of the attackers control) find a second file which has the same hash as the first file. Second pre-image attacks are super hard to accomplish. MD5 is still Second Preimage Resistant! Adding a second random input to the hash function, like you propose (that is to prime the internal state of the hash function with same random input, so when hashing of the usage data starts, the internal state of the hash function is unknown to the attacker) makes collision attacks much harder. In fact there is a term for that: target collision resistance. But second pre-image attacks, where the random input used for the hashing are known, don't get any harder. And if you don't transmit the random input over the secure channel as well, than second pre-image attacks get easier even (theoretically), as attackers have the possibility to manipulate the internal state outside of the usage data. Btw. reliance of target collision resistance, instead of collision resistance, is why Ed25519/Ed448 are much more resilient to problems with the hash function than ECDSA or any common RSA signature scheme. MD5 is still target collision resistant last time I checked. Remember the debacle of forged MD5 and later SHA1 certificates [2] ? Completely avoidable, if better signature schemes had been used. [1] Otherwise https://news.ycombinator.com/item?id=32912052 https://news.ycombinator.com/item?id=32912052 applies. [2] https://www.win.tue.nl/hashclash/rogue-ca/ https://www.win.tue.nl/hashclash/rogue-ca/

jrootabega 4y ago

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.

mikessoft_gmail 4y ago

abetusk 4y ago

From the README: """ Colliding any pair of files has been possible for many years, but it takes several hours each time, with no shortcut. This page provide tricks specific to file formats and precomputed collision prefixes to make collision instant. git clone. Run Script. Done. """ Could anyone weigh in on whether these ideas can be generalized to speed up MD5 collisions in general?

Retr0id 4y ago
What do you mean by this? You can't precompute all possible colliding blocks.
- dingosity 4y ago
  They mean "compute the first pre-image."

1970-01-01 4y ago

The most interesting part was collision with certificates. Platinum ticket for malware.

EGreg 4y ago

I asked a while ago, whether it’s feasible to get another file to generate a given hash. The answer is no. Not even with MD5. Just be very sure that this is the guarantee you are looking for. Often, for Merkle Trees etc. that is EXACTLY what is needed. Can someone craft input files (eg images) to fool your system? Yes, but only at their own expense. Sometimes if you want the system to be resilient even in the fact of malicious inputs then yes, you should use SHA256 and higher.

sacrosancty 4y ago
They might not realize they're hurting themselves, which makes it a bug. Backblaze did this with one of these hash collisions. You could back up two different (colliding) files and when you tried to restore both, only two copies of the same file would be returned, the other one apparently lost forever. Why would you have colliding files? Perhaps because you're somebody working on hash collisions and have collected some examples.

omoikane 4y ago

See also: "Lifetimes of cryptographic hash functions" - https://valerieaurora.org/hash.html https://valerieaurora.org/hash.html MD5 appears to be firmly in the "fun party trick" stage.

magila 4y ago
That page hasn't aged all that well. The prediction that applications would need to switch to a new hash function "every few years" hasn't panned out. The feared improved attacks on SHA-2 have failed to materialize. Applications that chose SHA-2 20 years ago are still quite secure today. It seems we just weren't very good at designing hash functions in the 90s.
- ComplexSystems 4y ago
  Good news for Bitcoin, as long as SHA-256 remains secure forever.
waynesonfire 4y ago
"In 2007, the NIST launched the SHA-3 competition" and the following year, 2008 SHA-2 is labeled "Minor weakness". Well, great timing on that competition!

Dwedit 4y ago

For anyone out there still using MD5 for any reason, check out this PDF file: https://www.alchemistowl.org/pocorgtfo/pocorgtfo14.pdf https://www.alchemistowl.org/pocorgtfo/pocorgtfo14.pdf (42MB). You can also rename it to a .NES file and run it in a NES emulator. It's a PDF File which is also a NES ROM that displays its own MD5 sum. The PDF also shows its own MD5 sum a few times. (The MD5 sum also happens to begin with 5EAF00D) When an arbitrary MD5 can be created that easily, it's useless for any cryptographic applications, or even any data integrity.

pxx 4y ago
MD5 may not be collision resistant, but the logic in your conclusion is completely wrong. There is no feasible pre-image attack on MD5. The MD5 generated _was not arbitrary_; they seem to have just brute-forced a few of the leading bytes and then did a Nostradamus attack. Again: finding something that hashes to an arbitrary MD5 sum is still not known to be feasible. This isn't a particularly good reason to use MD5, but this also means that MD5 is not broken in the way you think it is. When somebody finds something that hashes to all zeroes you can finally say that MD5 is completely broken. It is not known to be at that point yet.
- TillE 4y ago
  Right. Nobody should use MD5 if at all possible, but it's important to understand how it is and isn't broken. Like, if I have the MD5 hash of a binary from a trusted source, I can basically rely on that, unless the attacker was involved in producing the trusted binary. In which case I'd usually have bigger concerns.
  - dingosity 4y ago
    No. MD5 is broken. You can find a pre-image faster than brute force. This is the definition of "broken" for a hash function. https://link.springer.com/chapter/10.1007/978-3-642-01001-9_8 https://link.springer.com/chapter/10.1007/978-3-642-01001-9_...
    - 4y ago

dekhn 4y ago

Side note: I recently saw an example code using tensorflow to determine the private key of some cryptosystem. I can't find it. It was literally operating on the bits of the key and somehow had a loss function. Any ideas?

bawolff 4y ago
I mean, if it worked it was probably for a really shitty cryptosystem, and hence less interesting.

a-dub 4y ago

in the era of high fidelity generative models, i suspect that the future of media formats will be security forward with built-in protections against length extension attacks. i'm having a hard time imagining any other future than one where people only trust signed media, and media is possibly even signed in hardware by actual physical sensors/compressors.

rurban 4y ago

Ad exploitations: I've added some inverses of hash functions here: https://github.com/rurban/smhasher/tree/master/inverse https://github.com/rurban/smhasher/tree/master/inverse

johnray7866 4y ago

[dead]