Hacker News Reader

Comment by amluto | Hacker News Reader

> SHA-1 is still perfectly fine for some applications like detecting duplicate files on a storage medium

If by “perfectly fine” you mean “subject to attacks that generate somewhat targeted collisions that are practical enough that people do them for amusement and excuses to write blog posts and cute Twitter threads”, then maybe I agree.

Snark aside, SHA-1 is not fine for deduplication in any context where an attacker could control any inputs. Do not use it for new designs. Try to get rid of it in old designs.

View on HN

By “perfectly fine” they mean detecting duplicate image or document files on your local storage, which it’s still perfectly fine for, and a frequent mode of usage for these types of tools.

Not every tool needs to be completely resilient to an entire Internets’ worth of attacks.

Why would you pick SHA1 which has significant attacks you need to consider as opposed to something like SHA2 that doesn't?

who is attacking you in this situation though? you're scanning the files on your local system and storing their hashes. you then look for duplicate hashes, and compare the files that created them. if the files are truly duplicates, you can now decide what to do about that. if they are not truly the same, then you claim to have found another case of collisions, write your blog post/twitthread and move on, but does that constitute being attacked?

sometimes, i really feel like people in crypto just can't detach themselves enough to see that just because they have a hammer, not everything in the world is a nail.

Why would you pick a function that is known to have issues when there are other functions that do the same thing but don't have known issues?

Your comparison is flawed. It's more like if you have a nail and next to it a workbench with two hammers - a good hammer and a not as good hammer. This isn't a hard choice. But for reasons that are unclear to me, people in this thread are insisting on picking the less good hammer and rationalizing why for this specific nail it isn't all that much worse. Just pick the better hammer!

thanks for the reply that did not answer the question asked.

Your question is irrelevant. If you don't care about security, SHA1 is a bad choice because there are faster hash functions out there. If you do care about security, SHA1 is a bad choice because it has known flaws and there exist other algorithms that don't. The only valid reason to use SHA1 is if there is a historical requirement to use it that you can't reasonably change.

Any analysis about how hard it is for an attacker to get a file on your local file system via a cloned got repo, cached file, email attachment, image download, shared drive, etc is just a distraction.

You would be right, except that there are no faster hash functions (on all modern Intel, AMD and ARM CPUs, which have hardware SHA-1).

BLAKE 3 is faster only in wall clock time, on an otherwise idle computer, because it fully uses all CPU cores, but it does not do less work.

BLAKE 3 is preferable only when the computer does nothing else but hashing.

Uh no.

On a modern intel CPU, one core of SHA1 does about 500MB/s worth of hashing. Blake3 on the same core is 1.5GB/s or faster.

On the ThinkPad I'm typing this on, the single-threaded BLAKE3 benchmarks hit 8.8 GB/s :)

Because people already have two decades of SHA-1 hashes in their database and a rewrite + rescan is completely pointless? Hell, I have such a system using md5. So you produced a hash collision, cool, now fool my follow-on byte-by-byte comparison.

Edit: Before anyone lecture me on SHA-1 being slow, yes, I use BLAKE2 for new projects.

because it's shorter, dealing with long hashes is annoying (I use md5, not sha1)

You could just discard half the sha256 hash. Using the first 16 bytes of sha256 is a lot more secure than using just md5, in which case you might as well just use crc32.

Its worship of the new. Nothing worth anything existed last week, so reimplementing an entire infrastructure is zero cost.

If you are going to follow up with a full comparison you can use something much cheaper then sha-1

I dont think this is what most people think of when they say deduplication. There are quite a few systems which will just scan for duplicates and then automatically delete one of the duplicates. In such a system sha1 would be inappropriate.

If you are just using sha1 as a heuristic you dont fully trust, i suppose sha1 is fine. It seems a bit of an odd choice though as something like MurmurHash would be much faster for such a use case.

SHA-1 cannot be trusted only when there is a possibility that both files whose hashes are compared have been created by an attacker.

While such a scenario may be plausible for a public file repository, so SHA-1 is a bad choice for a version control system like GIT, there are a lot of applications where this is impossible, so it is fine to use SHA-1.

I'm not sure what scenarios there are where you have a possibility of the attacker creating 1 file but not both. Especially because the attacker doesn't need to fully control both files but could control only a prefix of one of them and still do the attack.

I also think working out all the possibilities is really hard, and using sha256 is really easy.

Most people. I haven't been part of that group, for like, ever maybe?

If we're a group of devs with a not insignificant percentage of those devs being frontend/UI/UX types, then having the same image in multiple sizes, formats, etc is going to be pretty common. Looking for multiples of the exact file is only going to reduce so much. Knowing you have a library of images with a source and then all of the derivatives is going to get you a lot less files as long as you know you have the source, then running image based sameness is much more beneficial. Sure, this is niche territory, but yeah, and, so?

Maybe there's someone new(-ish) that hasn't really had to deal with cleaning up thousands of images to this extent. One would hope the same image in its various forms within a dev's env would be similarly named, but that's not guaranteed. If we could depend on filenames, we wouldn't need hashing, right?

In some cases deduplication happens at the file system layer transparently without you even realizing it. E.g. there are tools like https://github.com/lakshmipathi/dduper

I agree that image editing workflows are a different use case more suited to perceptual hashes than cryptographic hashes.

Because SHA1 is faster and that matters if you're hashing several TB of files?

But I don't know for sure that's the case.

First the preamble:

DO NOT USE SHA-1 UNLESS IT’S FOR COMPATIBILITY. NO EXCUSES.

With that out of the way: SHA-1 is not even particularly fast. BLAKE2-family functions are faster. Quite a few modern hash functions are also parallelizable, and SHA-1 is not. If for some reason you need something faster than a fast modern hash, there are non-cryptographic hashes and checksums that are extraordinarily fast.

If you have several TB of files, and for some reason you use SHA-1 to dedupe them, and you later forget you did that and download one of the many pairs of amusing SHA-1 collisions, you will lose data. Stop making excuses.

> there are non-cryptographic hashes and checksums that are extraordinarily fast.

Is it still true that CRC32 is only about twice as fast as SHA1?

Yeah I know the XX hashes are like 30 times faster than SHA1.

A lot depends on instruction set and processor choice.

Maybe another way to put it is I've always been impressed that on small systems SHA1 is enormously longer but only twice as slow as CRC32.

For a lot of interoperable-maxing non-security non-crypto tasks, CRC32 is not a bad choice, if its good enough for Ethernet, zmodem, and mpeg streams its good enough for my telemetry packets LOL. (IIRC iSCSI uses some variant different formulae)

CRC32 is fine for kilobyte-sized data packets.

For files, it is useless. Even if that was expected, I have computed CRC32 for all the files on an SSD. Of course, I have found thousands of collisions.

Birthday-style collisions don't matter for integrity checking.

32 bits is too small to do the entire job of duplicate detection, but if it's fast enough then you can add a more thorough second pass and still save time.

Deduplication is the kind of application where CRC is a decent approach and CRC has no resistance to attack whatsoever. SHA1 adds the advantage of lower natural collision probability while still being extremely fast. It's important to understand that not all applications of hashing are cryptographic or security applications, but that the high degree of optimization put into cryptographic algorithms often makes them a convenient choice in these situations.

These types of applications are usually using a cryptographic hash as one of a set of comparison functions that often start with file size as an optimization and might even include perceptual methods that are intentionally likely to produce collisions. Some will perform a byte-by-byte comparison as a final test, although just from a performance perspective this probably isn't worth the marginal improvement even for hash functions in which collisions are known to occur but vanishingly rare in organic data sets (this would include for example MD5 or even CRC at long bit lengths, but the lack of mixing in CRC makes organic collisions much more common with structured data).

SHA2 is significantly slower than SHA1 on many real platforms, so given that intentional collisions are not really part of the problem space few users would opt for the "upgrade" to SHA2. SHA1 itself isn't really a great choice because there are faster options with similar resistance to accidental collisions and worse resistance to intentional ones, but they're a lot less commonly known than the major cryptographic algorithms. Much of the literature on them is in the context of data structures and caching so the bit-lengths tend to be relatively small in that more collision-tolerant application and it's not always super clear how well they will perform at longer bit lengths (when capable).

Another way to consider this is from a threat modeling perspective: in a common file deduplication operation, when files come from non-trusted sources, someone might be able to exploit a second-preimage attack to generate a file that the deduplication tool will errantly consider a duplicate with another file, possibly resulting in one of the two being deleted if the tool takes automatic action. SHA1 actually remains highly resistant to preimage and second preimage attacks, so it's not likely that this is even feasible. SHA1 does have known collision attacks but these are unlikely to have any ramifications on a file deduplication system since both files would have to be generated by the adversary - that is, they can't modify the organic data set that they did not produce. I'm sure you could come up with an attack scenario that's feasible with SHA1 but I don't think it's one that would occur in reality. In any case, these types of tools are not generally being presented as resistant to malicious inputs.

If you're working in this problem space, a good thing to consider is hashing only subsets of the file contents, from multiple offsets to avoid collisions induced by structured parts of the format. This avoids the need to read in the entire file for the initial hash-matching heuristic. Some commercial tools initially perform comparisons on only the beginning of the file (e.g. first MB) but for some types of files this is going to be a lot more collision prone than if you incorporate samples from regular intervals, e.g. skipping over every so many storage blocks.

SHA-1 is implemented in hardware in all modern CPUs and it is much faster than any alternatives (not all libraries use the hardware instructions, so many popular programs compute SHA-1 much more slowly than possible; OpenSSL is among the few that use the hardware).

When hashing hundreds of GB or many TB of data, the hash speed is important.

When there are no active attackers and even against certain kinds of active attacks, SHA-1 remains secure.

For example, if hashes of the files from a file system are stored separately, in a secure place inaccessible for attackers (or in the case of a file transfer the hashes are transferred separately, through a secure channel), an attacker cannot make a file modification that would not be detected by recomputing the hashes.

Even if SHA-1 remains secure against preimage attacks, it should normally be used only when there are no attackers, e.g. for detecting hardware errors a.k.a. bit rotting, or for detecting duplicate data in storage that could not be accessed by an attacker.

While BLAKE 3 (not BLAKE 2) can be much faster than SHA-1, all the extra speed is obtained by consuming proportionally more CPU resources (extra threads and SIMD). When the hashing is done in background, there is no gain by using BLAKE 3 instead of SHA-1, because the foreground tasks will be delayed by the time gained for hashing.

Only when a computer does only hashing, BLAKE 3 is the best choice, because the hash will be computed in a minimal time, by fully using all the CPU cores.

> all the extra speed is obtained by consuming proportionally more CPU resources (extra threads and SIMD)

If you know you have other threads that need to do work, then yes, multithreading BLAKE3 would just pointlessly compete with those other threads. But I don't think the same is true of SIMD. If your process/thread isn't using vector registers, it's not like some other thread can borrow them. They just sit idle. So if you can make use of them to speed up your own process, there's very little downside. AVX-512 downclocking is the most notable exception, and you'd need to benchmark your application to see whether / how much that hurts you. But I think in most other cases, any power draw penalty you pay for using SIMD is swamped by the race-to-idle upside. (I don't have much experience measuring power, though, and I'd be happy to get corrected by someone who knows more.)

Ask the webkit source code repo how using sha-1 for that purpose went.

It depends what you are doing, but deduplication where a collision means you loose data, seems like an inapropriate place for sha-1.

Webkit incident: https://itwire.com/business-it-news/security/fallout-webkit-...

Why would someone be so idiotic as to not compare actual data before deleting probable extra copies?

> where an attacker could control any inputs

I believe the GP's point hinges on the word "attacker". If you aren't in a hostile space, like just your won file server and you are monitoring your own backups it's fine. I still use MD5s to version my own config files. For personal use in non-hostile environments these hashes are still perfectly fine.

Reply on news.ycombinator.com