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.
best
is already make it unclear what you are asking. $\endgroup$ – kelalaka Apr 29 '20 at 20:32