# What is the best algorithm for compressing a hash?

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?

• That may be enough for the git. This is completely opinion/requirement based. Git --fast version control – kelalaka Apr 29 '20 at 19:00
• I agree with @Kelalaka, for Git maybe is enough the firts 4 bytes. If you use SHA-256 the colision is minior compare with SHA-1, SHA256, is currently much more resistant to collision attacks as it is able to generate a longer hash which is harder to break. – AndresMontj Apr 29 '20 at 19:43
• 4-byte has $2^{16}$ colliision resistance. The Git is not using it really for Cryptographical usage, they use it for integrity checking and look up tables. – kelalaka Apr 29 '20 at 19:59
• I know, I know, git commit hashes are not a security feature. I just used Git as an example. – D. Pardal Apr 29 '20 at 20:26
• That is why this is not a really good question. And the best is already make it unclear what you are asking. – kelalaka Apr 29 '20 at 20:32

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.

• There is a practical and useful thing to do while keeping 8 hex characters: re-hash with entropy stretching. – fgrieu Apr 29 '20 at 20:23
• Interesting. But I guess you would not do that manually. Or is that actually performed in Git? – Maarten Bodewes Apr 29 '20 at 21:29
• I guess that would need to be performed by GIT when displaying, with a cache of SHA-256 to entropy-stretched rehash in order to avoid prohibitive CPU load. – fgrieu Apr 29 '20 at 21:42
• Sorry, @MaartenBodewes, but compression can be made over an adequate block size, which depends on the size of typical set (AEP - Asymptotic Equipartition Property.) We expect that a good hash function output doesn't "concentrate"... So it will be necessary a code of size $n$ to compress a $n$-bit hash "text": by AEP, the size of the typical set is $\sim 2^{nH(X)}$. As we dont know $H(X)$ from a $p(x_0,...,x_n)$ hash output, we must believe that $H(X) \sim 1$. So, there is no room to compression over a good hash function output. – McFly Apr 29 '20 at 23:41
• @McFly That's a perfect explanation, but I was talking about the wording in the question. I never said you can compress the output of a hash. I just explained what compression means in the generic sense (compared with taking just 4 bytes of anything). – Maarten Bodewes Apr 29 '20 at 23:45

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.

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.

• This interesting answer is taking "compressing" from the question's title in the sense that has in lossless data compression. In the question, "compression" is used for a summarization in less characters, aiming at keeping most of the initial intent of the thing. As explained in the questions first paragraph, here the intent is preventing collisions or preimages. And that can be done to a large degree. – fgrieu Apr 30 '20 at 13:21
• @fgrieu, I see. My concern was not only the "compressing" in the title, but also about the "(Hashing the hash)", but you're absolutely right: that is not the point. Anyway, I was also trying to give arguments to defend that 4 bytes don't give us a negligible probability of collision, but with a good hash function that can be useful for a visual versioning control. So, so I think that the Git strategy is interesting, so is the one in your answer! – McFly Apr 30 '20 at 15:40