Hash collisions and exploitations – Instant MD5 collision
github.com
github.com
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.
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.
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.
https://link.springer.com/chapter/10.1007/978-3-642-01001-9_...
"Breaking a cipher simply means finding a weakness in the cipher that can be exploited with a complexity less than brute-force."
But please go on about how you know more than Schneier.
Schneier is illustrating the gap between the academic and practical meanings of "broken".
As Schneier writes as an introduction in the very paragraph you are trying to quote, "in academic cryptography, the rules are relaxed considerably." This is not a snub on academia; colloquial terms sometimes just mean something different than the academic definition.
This is not a mistake. Md5 is a nice compromise between being fast and having a low probability of having collisions while keeping the hashes nice and short. Simpler/faster hashing algorithms are available of course and they have even more potential for collisions and it's not an issue there either. But md5 is kind of easily accessible and there on most platforms. So, it's a good default to use if you need some kind of content hash.
I've never seen accidental collisions and intentionally trying to create collisions in a cache or a database id doesn't really serve any purpose to anyone. So yes, you could try to do that but why would you? The probability of unintentional collisions is low enough that it is not a concern. It's a complete non issue. You are never going to see one in your career.
Using it is not a security issue unless you use it for things that need to be secure in which case you should use something like sha3 or alternatives to that. But hash algorithms have applications beyond security sensitive ones. AWS using sha3 for s3 object content hashes would be overkill and a waste of CPU,
My Anti-virus kicked off after downloading this, identified as EICAR-AV-Test
From a bit of googling, it seems EICAR-AV-Test is a file to test antivirus
Note that your antivirus is also performing worse than even the average antivirus, which is already pretty bad. The EICAR test file is only meant to be detected if the file size is less than or equal to 128 bytes long.
I would not disagree that it makes the computer worse, there was a significant performance decrease when the latest version was installed earlier this year but this is off topic.
What I found interesting was that I didn't know about EICAR until today.
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.
There are non-compromised hashes, use that.
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.
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. :)
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"
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.
Not as a thought experiment. Thought experiments help you to grow.
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.
Of course in production, just use sha256, but there is nothing wrong with thinking about unorthodox solutions.
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 )
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.
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.
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.
Yes, I could construct this trivially, because MD5 is broken.
I get it that you're just hacking around, but reading what the olds said about MD5 is useful.
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.
I think all of the known MD5 collisions (and SHA-1 collisions even) are of inputs that are the same length.
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.
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.
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)
https://marc-stevens.nl/research/papers/C13-S.pdf
"Counter-cryptanalysis in principle enables the continued secure use of weak cryptographic primitives."
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.
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).
MD5 appears to be firmly in the "fun party trick" stage.
It seems we just weren't very good at designing hash functions in the 90s.
Well, great timing on that competition!
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.
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 applies. [2] https://www.win.tue.nl/hashclash/rogue-ca/
But I think what was meant by "publishing" was that the hashes would be available to parties who would be willing and able to preserve them indefinitely.
As a source of inspiration a good place to start might be B-LTA in the ETSI standards. I believe this takes into account the fact that the algorithm used for its creation might deprecated.
IIRC the way it works is (basically) that signatures are given a finite validity period and you undertake periodic re-signing. Therefore you build up a audit trail history of signatures with current algos as you go along.
WinRar 5 can do it, and I believe many backup software worth their salt can too.
You can send a message to someone else over an unreliable channel with a very good assurance that it hasn't been corrupted unintentionally, without needing a reliable channel.
You can send a message to yourself in the future over an untrusted channel with a very good assurance that it hasn't been tampered with without needing a trusted channel, because you trust yourself and can thus remember trustable information.
There's no way to send a message to someone else over an untrusted channel with a very good assurance that it hasn't been tampered with, without a trusted channel. You need some way to convey trustable information.
Not sure how to do that over 500 years though? Pass down the data as an heirloom, burry a SHA3 hash in a plaque below a building foundation, put a Blake3 hash on a granite tablet buried in the desert, write a SHA512 hash on the back of a Banksy painting. Put a BLAKE2b hash in your diary and get it accepted in a museum collection. The more you add, the more difficult it becomes for an attacker to find and alter all of them.
But really, you don't have to make those locations secret, you already get a lot of security by requiring an attacker to drive out into a desert to change that tablet, access a building foundation and tamper a Banksy painting. None of these are secure in the cryptographic sense, but even without secrecy that raises the bar for an attack substantially, and makes it more likely to be detected.
The hash could be revealed after the tampered message was found, and therefore after it would have been necessary. Imagine some critical decision was taken based on incorrect information, for example.
>you already get a lot of security by requiring an attacker to drive out into a desert to change that tablet
If you think remoteness is sufficient protection then there's no need for hashes or anything like that. Just do what 9gag did and etch your message onto stone and bury it wherever. They found the approximate location of that slab fairly quickly, but who's going to go digging in Spain just to smash a limestone slab with some memes on it? If someone is willing to do that once, doing it one or more times again is not a lot more effort.
At least one of them might be a Rosetta Stone for some future Society that way.
If someone cares and it matters to them, it is not infeasible.
If no one cares, then it may be feasible, but is pointless. No one would ever bother to check, even if said etched-in-glass checksum was still around and findable.
The Bible isn’t vastly different from it’s original writings - or one of the most printed works ever- due to time alone. it’s because each generation finds it’s own reason for propagating what they want (and not propagating what they don’t), and that’s a necessary property for it to exist in a way anyone cares about at all after this amount of time.
Otherwise it would just be (at best) some rotten parchment in a language no one can read, and of at most academic interest in some caves in the Middle East. If someone came up with a checksum on such rotten parchment, the only people who would care would be math nerds - assuming anyone ever found it.
This is kind of what real p2p, open, permissionless, decentralized blockchains are good for...
... Of course you can? If we're interacting via blockchain we both have mutually-known cryptographic public keys used to sign transactions. Assume without loss of generality they can't be used directly for public-key encryption (eg they're Lamport keys). I generate a McElice public encryption key and include it in a transaction signed with my signing key. You use that to encrypt your message and include the encrypted message in a transaction signed with your signing key. I decrypt the message; it's secret and tamper-proof.
If, as in londons_explore's comment, we're worried about any specific algorithm being broken, we can use a bunch of different signing keys, and a bunch of different encryption keys, such that a attack would have have to break all the signature algorithms or all the encryption algorithms to compromise the message.
So, no, a blockchain is not a trusted channel. For the purposes of communication, it offers no more security than the public Internet. It doesn't even guarantee delivery of messages.
(Disclaimer: Method not applicable to normal people.)
Broadcasting the hash would make sense if the message should stay secret for some time. Although 500 years is rather a long time for a zero-knowledge proof.
Hashing would be on top of it to ensure detection of tampering/errors. Using multiple hashes is also a good strategy.
MD5 is good enough if bit rot alone is the only thing you care about. It's still very hard to generate an MD5 collision with the same bit length, and doing so would generally require changing a VERY large number of bits to get a collision, which is not what happens with bit rot.
It might even be mathematically impossible to find two files that have the same MD5 hash and differ by less than a certain amount of bytes, though I don't know the proper way to formalize this.
(It's trivial to show for example that if you use any CRC as a hash, it is impossible to find a collision that differs by an edit distance of 1 and has the same length.)
> but also deliberate tampering.
You're never safe from this if you aren't the guardian of the official hash values. Someone could just change the file AND change the "official" hashes.
I think your best bet is just to publish it and also launch a copy into space with a 500 year orbit. If someone in the future tries to launch a similar data-comet with a shorter orbit, it will be visible in the trajectory. There's always the danger of them sending out a robotic space probe to mess with your data "in flight".
It's fully possible that your Uberhash function has some vulnerability that can be easily exploited regardless of the underlying security of the individual hash functions.
> Is the best available approach to hash the data with a bunch of hash algorithms and publish all the hashes?
This is much less secure than you think it is. See https://www.iacr.org/archive/crypto2004/31520306/multicollis...
If your signature scheme is broken over the years then that means that people can tamper with the files. So you can use different schemes just as with the hashes.
Who is going to be able to verify your identity after 500 years and/or have a verified copy of the hashes? Without the concept of identity, it's all just a bunch of bits.
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.
Why would you have colliding files? Perhaps because you're somebody working on hash collisions and have collected some examples.
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.
"""
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?
I've added some inverses of hash functions here: https://github.com/rurban/smhasher/tree/master/inverse
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.
[1] https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_co...
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.
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.
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.
- 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.
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?
I think I understand your meaning to be MD5 certainly still exhibits an avalanche effect; changing a single bit in the input changes about half the bits in the output. And if you trust the way you retrieve the hashed data and the hash (like it's on a local hard drive) then yes, it's certainly acceptable for that use. But collisions and second pre-image generation being faster than brute force are why people generally don't want to use it (MD5) when it's use spans trust domains.
My point is:
a. Don't use MD5 just because Bruce Schneier published a popular book that said it was okay RIGHT BEFORE all the research damning it came out. (Personally... I think Bruce should publish a third edition of this text expressly to remove the bit about MD5 being okay. I cannot tell you how many hours of billable time I've wasted explaining to software engineers that no... MD5 is not recommended for use even though at one time it was considered acceptable. And if you know not to use MD5, you're not the software engineer I'm talking about.)
b. You can use SHA256 and get avalanche, collision resistance AND second pre-image generation resistance. (Pretty sure you also get 1st pre-image generation resistance, but I haven't scanned the literature for that in a while.)
And while I'm thinking about it, let me add these points:
c. There are probably better hashing algorithms than MD5 for use with a hash map/table/tree.
d. If you're interested in how MD5 works, I recommend expanding the scope a bit and study Merkle-Damgård generally. Why MD5 has problems and other hash functions that make use of the Merkle-Damgård construction don't (or have different problems, or the same problems at different amounts of input) is pretty interesting.
And yes, if you happen to have a MD5 hardware accelerator or petabytes of data and MD5 hashes already, it's hard to change that overnight.
I'm not sure what you mean by this, but this:
>people generally don't want to use it (MD5) when it's use spans trust domains.
is exactly what I mean by "cryptography". I.e. guarding against intentional tampering. Are there a lot of people using it for this purpose? I don't remember seeing one.
>c. There are probably better hashing algorithms than MD5 for use with a hash map/table/tree.
For sure. Cryptographic functions (even obsolete ones) are almost always overkill and too slow for general data structures. Only use them if you can't find something more suitable for your data.
>And yes, if you happen to have a MD5 hardware accelerator or petabytes of data and MD5 hashes already, it's hard to change that overnight.
I was actually talking about SHA-256 acceleration, since I just saw like an hour ago that recent Intel CPUs have it. If your CPU has such instructions, by all means use it instead of software MD5, if all you need is data integrity.