Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Curious Case of MD5

katelynsills.com

Post reply on HN
Print view View original

141–150 of 173 posts

Re: The Curious Case of MD5

#141

Post by masklinn »

ivanbakel wrote: post #138
masklinn wrote: post #120

Earlier quoted context omitted.

Ensuring every sequence is uniquely identified. Although they still want to avoid those, non-cryptographic hash functions often care a lot less about collision resistance, which is a problem when fingerprinting, which is the use case here. The alternative to a CHF in this case is not a non-cryptographic hash function, it's a dedicated fingerprinting scheme (like Rabin fingerprints). But a CHF is a perfectly good fing…

Those properties are not a direct result of a function being collision-resistant, which is a property that only makes sense in adversarial contexts. If nobody is trying to produce collisions, it doesn't matter if they're easy or hard to find. You might care that the output hashes are well-distributed for your closely-related input data, but as the comment you replied to above points out, there are non-cryptographic f…

> Those properties are not a direct result of a function being collision-resistant

It kind of is though.

> as the comment you replied to above points out, there are non-cryptographic functions with good avalanche properties which would satisfy that need without being collision-resistant.

No comment I replied to points anything near that. Your comment has basically no content, and the comment before that only asserts such existence without providing any guidance or evidence, linking to a page about the general concept of non-cryptographic hash function, which is utterly useless.

Not only that but avalanche properties do not matter at all for the use case: the hash is just a label for the sequence, it's fine if two similar sequences get similar hashes as long as those hashes are different. Some identifiers (like geninfo) are just centrally assigned integers.

Re: The Curious Case of MD5

#142

Post by Dwedit »

a1369209993 wrote: post #30
Dwedit wrote: post #29

Earlier quoted context omitted.

Don't be silly here, the MD5 is clearly in the plaintext here, and the NES ROM is only the first 40k of the file. It is not able to scan itself and print out a hash that way.

> the MD5 is clearly in the plaintext here Alright, I'll bite: at what byte offset in the binary file contents does a trivial encoding[0] of the MD5 hash occur? > the NES ROM is only the first 40k of the file. It is not able to scan itself and print out a hash that way. It is possible to encode the effects of multiple blocks of arbitrary[1] data on a hash function internal state (independently of what state you start…

I stand corrected here, ran it in a debugger, and the NES ROM appears to be doing significant computation between each HEX digit being displayed. Haven't actually read the trace log yet to confirm if it is performing MD5.

NES ROM still doesn't have any access to the rest of the file though.

Re: The Curious Case of MD5

#143

Post by adrian_b »

oconnor663 wrote: post #140
adrian_b wrote: post #83

Earlier quoted context omitted.

SHA-3 (also BLAKE2 or BLAKE3) is definitely more secure for very large documents than SHA-2. The security (i.e. the difficulty in finding collisions) decreases with the length of the document for SHA-2 and it stays constant for SHA-3. Nevertheless, it is unlikely that typical legal documents are big enough for this to matter, except when the hashes would be e.g. for entire seized HDDs or SSDs, so SHA-2 is an acceptab…

> The security (i.e. the difficulty in finding collisions) decreases with the length of the document for SHA-2 Could you spell this part out for me?

Twenty years ago this paper was considered surprising and, together with a handful of other attacks and with the concrete attacks against MD5 and SHA-1 succeeded by some Chinese researchers prompted the organization of the SHA-3 competition.

John Kelsey and Bruce Schneier: "Second Preimages on n-bit Hash Functions for Much Less than 2^n Work"

https://eprint.iacr.org/2004/304

The abstract at this link provides the essential results.

"We provide a second preimage attack on all n-bit iterated hash functions with Damgaard-Merkle strengthening and n-bit intermediate states, allowing a second preimage to be found for a 2^k-message-block message with about k * 2^(n/2+1) + 2^(n-k+1) work. Using SHA-1 as an example, our attack can find a second preimage for a 2^60 byte message in 2^106 work, rather than the previously expected 2^160 work."

Besides this result, there is also the previous result obtained by Joux for multi-collisions, which also become easier for longer input data (Antoine Joux: "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions").

Re: The Curious Case of MD5

#144

Post by callalex »

hollerith wrote: post #21
callalex wrote: post #20

This is the same legal system that still uses polygraphs as “lie defectors” and known-junk DNA matching tests as fact, so this isn’t exactly shocking.

What court has admitted polygraph test results into evidence? Surely, none in the US.

I suspect we have different definitions of “legal system” in mind. You are correct that such things cannot be admitted as evidence into a court case, but law enforcement agencies still use the machines and do their best to lie to unknowing victims that it will be admitted to court.

Re: The Curious Case of MD5

#145

Post by planede »

franga2000 wrote: post #113
planede wrote: post #112

Earlier quoted context omitted.

> the real document won't have hash colliding artifacts in it I don't think that hash colliding artifacts would necessarily be obvious. They could be in part of a file that ends up being ignored by parsers of the file format. Or it could be some low level noise in pixel values in scanned documents.

Both of those are things computer forensics experts are used to looking for and I'm certain even a beginner could find them.

Are court documents routinely analyzed by computer forensic experts, or only when there is suspicion of tampering?

Re: The Curious Case of MD5

#146

Post by ivanbakel »

masklinn wrote: post #141
ivanbakel wrote: post #138

Earlier quoted context omitted.

Those properties are not a direct result of a function being collision-resistant, which is a property that only makes sense in adversarial contexts. If nobody is trying to produce collisions, it doesn't matter if they're easy or hard to find. You might care that the output hashes are well-distributed for your closely-related input data, but as the comment you replied to above points out, there are non-cryptographic f…

> Those properties are not a direct result of a function being collision-resistant It kind of is though. > as the comment you replied to above points out, there are non-cryptographic functions with good avalanche properties which would satisfy that need without being collision-resistant. No comment I replied to points anything near that. Your comment has basically no content, and the comment before that only asserts…

It's true that being collision-resistant is a strong enough property to make collisions unlikely, but it doesn't hold that collision resistance is a requirement for such a hash function.

What is the relevance of collision resistance in this case? Why do you say it's a primary requirement of a hash function here? Why isn't uniformity with a large enough image space enough? Given that there is no adversary trying to produce collisions of generated identifiers, why does it matter that collisions are hard to deliberately create, rather than simply unlikely to occur?

Re: The Curious Case of MD5

#147

Post by Snow_Falls »

Pikamander2 wrote: post #109
laserbeam wrote: post #107

> MD5 should be considered broken and unsuitable for further use. Ya know... It's 2024 and Azure's blob storage ONLY supports MD5 for integrity checks when writing blobs. There are no other hash functions supported there. The default cloud storage solution implemented by one of the largest cloud providers out there ONLY uses MD5. I really want to use something else, but whenever I have to interact with them I must fa…

WordPress still uses MD5 for database passwords to this very day with no immediate plans to change it. That said, they apparently use eight passes of MD5 hashing along with salting, which they claim is a sufficiently secure combo. WordPress's core and default themes are known to be fairly secure, so I'd like to believe they know what they're talking about, but if nothing else it feels icky.

I'm confused, if they're going through the effort to make something known bad (MD5 secure, then why not just use something secure in the first place (e.g. SHA3)?

Re: The Curious Case of MD5

#148

Post by moyix »

gruez wrote: post #127
moyix wrote: post #59

Earlier quoted context omitted.

You can generate pairs of hashes for random inputs and check for collision without storing all of the outputs, no?

That requires way more hashes to be computed though.

I don't think that's correct? It's probabilistic, yes, but in expectation you would still need ~2^64 hashes to find a collision for a 128-bit hash (birthday paradox).

Re: The Curious Case of MD5

#149

Post by m3047 »

kmeisthax wrote: post #18

If you could just throw anyone who forged a digital signature in prison, you'd keep using MD5, too. The reason why people like us keep changing everything for security is specifically because we have no access to justice. Computer crimes are international and difficult to prosecute, so you might as well drop an algorithm like a hot potato if anyone - even just nation state actors - could break it. We build our rules…

Would have upvoted except for that last sentence. There is no such thing as a perfectly good airplane, at least as long as "perfect" means flawless rather than good enough. Granted, there is a whole dance for accepting the risk from known defects (that's the whole point).

Re: The Curious Case of MD5

#150

Post by ylk »

ylk wrote: post #91
8n4vidtmkvmk wrote: post #86

Earlier quoted context omitted.

Supposing I did want to use the file hash as a unique key and I really don't want to do a byte for byte comparison... And I care about speed but not so much about bad actors, what should I use?

Didn’t think about it much, but file size should be a good indicator if the hash isn’t horrible. md5 + file size comparison could work for your use-case.

One of the inputs for MD5 is the length of the message, so I'm at least wrong in the case of MD5. Don't know about the general case and although I'm interested in the answer I can't spend time on it right now. But if anyone has a pointer to a useful resource please reply.

In general, just use a good hash function.

Post reply on HN