What is the best algorithm for compressing a hash?

Question

What is the best way to transform a hash with a longer length into one with a smaller length, preventing as many collisions as possible? (Hashing the hash)

For example: Some versions of Git use SHA-1 for hashing commits. Of course, 15ce7ff90976b3e43738be403f5c985377646bb3 is rather large to display on a screen. Because of that, Github usually only shows the most significant 4 bytes (15ce7ff9) to refer to a specific commit.

But is this the best strategy or is there a better way? If SHA-256 was used instead of SHA-1, would the resulting "minified" hash be as secure and as colision-avoiding as possible within 4 bytes, regardless of the "minification" algorithm used?

Answer 1

What's better? Displaying more information than 4 bytes will be more secure mathematically speaking. However, it is unlikely that people will check all those bytes. Those bytes are more for identification than for authentication / security anyway. You could use a different alphabet than hexadecimals, say base 64, but I'd argue that that would be harder to remember, especially if more than 4 bytes are used.

For the 4 bytes it doesn't really matter. They only represent somewhat over 4 billion possibilities (using the short scale) and generating the same 4 bytes will be easy whatever hash function is used. The switch from SHA-1 to SHA-256 is about the full hash used internally.

---

The switch to SHA-2 is important in my opinion. Or it is at least important enough to make the switch. I haven't been swayed by Linus arguments yet, but that's mainly because I don't have a full overview of the vulnerabilities. However, I haven't seen a good argument why there wouldn't be an attack possible either. And the difference in speed really isn't worth to taking any risk.

---

A note about the wording: taking the first 4 bytes from a hash is not compression. Compression (as in the common meaning, such as the DEFLATE used by zip archives) is performed over all the bits, and tries to pertain some essential (or for lossless compression all of the) data. As explained in the comments below, compression of the output of a hash is an act of futility.

In cryptography compression has a different meaning. But the output must also depend on all the input bits.

Anyway, just removing the rightmost bytes from a hash is not the same thing.

Answer 2

What is the best way to transform a hash with a longer length into one with a smaller length, preventing as many collisions as possible?

TLDR: Decide if you want to resist preimage or collision; the later is hard and requires a better main hash than SHA-1. Re-hash the main hash with a purposely slow hash as used in passord-based hashes, and encode the outcome (truncated) using a binary-to-text conversion denser than hex.

---

One must be careful about the goal: is it to avoid collision (the word stated in the question), or to avoid preimage (as perhaps is thought)?

In preimage, adversaries try to come up with a message (or file content) having a certain hash (or compressed hash). They are initially given:

• in first preimage, the target hash.
• in second preimage, a message with that hash (and they must come up with a different message). That could be because they plan to change an existing message (that they did not had the freedom to define) into something else, without changing the hash.

In collision, adversaries try to make two messages having the same hash, but are not constrained about that value. That could be because they plan to submit one of the messages, and change it to the other at a later time.

To reach $b$-bit security (that is, $\mathcal O(2^b)$ work for an attack), we asymptotically need a $b$-bit hash to resist preimage, and a $2b$-bit hash to resist collision¹.

Thus the method of displaying the 8-character hex string coding the first 32 bits of the hash provides 32-bit resistance to preimage, which is mere minutes of computation, and only 16-bit resistance to collision, which is no resistance.

---

If the initial hash is SHA-1, there's limited hope with regards to collision, since it is known how to make SHA-1 collisions (trivially by reusing the prefix revealed by the shattered attack, or by repeating their attack). Sure, there are ways to detect messages crafted to allow shattered copycats, but I would not bet on their resistance to a clever variation.

With a better main hash such as SHA-256 or SHA-512, or if we only care about preventing preimage attacks, there are two ways to improve on this:

• Re-hash that main hash using a slow hash, then truncate the result. This is key stretching, as used in password hashing. Example slow hashes are Argon2 and Scrypt (modern and greatly improved replacements for the obsolete Bcrypt and PBKDF2). Use with some public salt (if possible message-dependent, e.g. a file name). There are parameters making it easy to control the CPU time and RAM per hash, e.g. $0.1$ second, 10MB RAM. With the same final truncation to 8 hex characters, an attack now requires $0.693\times2^{32}\times0.1$ CPU⋅seconds ($>9.6$ CPU⋅year) to be broken for preimage, or $\approx1.177\times2^{16}\times0.1$ CPU⋅seconds ($>2\text{h }08\text{'}$ on a single CPU) to be broken for collision, with 50% probability.
• Encode more bits per character in the compressed hash. Hex encodes 4 bits per character, base64 encodes 6, by pushing ASCII to its limits we can get to 6.55, using the resources of Unicode we could go to maybe 8 to 12 while keeping characters visually distinguishable (depending on culture of the audience).

These methods can be combined. With 8 characters restricted to 10 digits, 13 symbols ! # $ % & * + < > ? @ ^ _, and uppercase/lowercase letters less the 11 A E I O U a e i l o u (in order to avoid a large proportion of possibly embarrassing English words, and as an aside confusion with digits 0 1), we get to $10+13+2*26-11=64$ characters, thus 48 bits, thus >63,000 CPU.years to break preimage with 0.01s per re-hash and 50% probability of success.

Caution: unless there's a message-dependent salt (such as a file name, which complicates verification), adversaries need less work by a factor about $k$ in order to break preimage for one in $k$ rehashes. That's an issue if adversaries are happy to replace one message among $k$, even though they do not control which message will be replaced when they prepare the replacement.

The 0.01s per entropy-stretched re-hash would still be sizable work in a GIT context. At the very least, the server would have to maintain a cache of re-hashes in order to conserve CPU time/energy.

---

¹ See Birthday problem for cryptographic hashing, 101.

Answer 3

An important Information Theory tool to build a compression algorithm is AEP - Asymptotic Equipartition Property, which gives us the idea of typical sequences: roughly speaking, the most probable sequence $x_1,...,x_n$, with $X_1,...,X_n \sim p(x)$.

Compression considers the size of the set of typical sequences. The idea is to "concentrate the fire" coding the words in this set, and, therefore, reduce the size of bit representation of the original input: the smaller code words to represent the most frequent typical sequences. This is the general idea in ZIP, Lempel-Ziv algorithms.

The AEP tell us that the size of the typical set is $\sim 2^{nH(x)}$ (here $H(\cdot)$ is the Shannon Entropy). So, in the specific case of a "good" hash function, we don't know about $p(x_1,...,x_n)$ or about $p(x)$, and a good guess can be to consider $p(0)=p(1)=\frac{1}{2}$, and, therefore, work with $H(x) \sim 1$, maximum entropy to a binary source.

Considering a "good" hash function, the size of the set of typical sequences will be $\sim 2^n$, that is, almost the complete set of $n$-bit words. Therefore, there is no room for compression over a hash function output.

BTW, hash functions outputs are usually short. I'm not sure about the advantage of compressing, e.g., 256 bits, because we need metadata: to encode the typical sequences as a dictionary.