Can I replace SHA-1 with SHA-512/160 to address Shambles?

Question

The destination is software (within a remote trust boundary) that expects SHA-1 results. Would it be safer for the source (that's within my own trust boundary) to replace my SHA-1 computation at my source with a SHA-512/160 instead?

Answer 1

Generic collisions

The generic collision attack on SHA-512 trimmed to $n=160$-bit will require $2^{80}$ complexity by the birthday paradox with a 50% success probability. The generic attack doesn't require any knowledge about the internals of the target hash function. It is about collecting hash outputs and looking collision among them by building a table and hoping that you find a collision. The cost is $O(2^{n/2})$ time and $O(2^{n/2})$ space to store the table.

If you are using a variant of Pollard's $\rho$ you can achieve constant $O(1)$-space with $O(2^{n/2})$-time. The best known is the van Oorschot–Wiener Time-Momory Trade-off technique with cost $O(2^{n/2})$. This can be parallelized with a linear speedup. Use $O(2^{n/4})$ machine to parallelize and get an answer in $O(2^{n/4})$ time at the same cost of $O(2^{n/2})$.

If you consider the Quantum attacks on hash functions, you should use 384 or 512 output sizes due to Brassard et. al' work. That has $\mathcal{O}(\sqrt[3]{n})$ attack time for n-bit hash function (for 256-bit $\mathcal{O}(\sqrt[3]{2^{256}}) \approx \mathcal{O}(2^{85})$). See the timing table in this answer.

SHA-1 weakness and Shamble

The researches use weaknesses that lie in the internals of SHA-1 and The Shambles' researches reduced the collision to $2^{61.2}$, see the list of other work in here. The Shambles' team used 900 GPUs that cost around $75.000 with their new method and calculated the forgery at most in two months. This is why they called practical. Their new records;

• They reduced the use of neutral bits BCJ+05 and boomerangs JP07 from $2^{64.7}$ to $2^{61.2}$
• Also, they improved graph-based technique (LP19) to compute Chosen-Prefix Collision from $2^{67.1}$ to $2^{63.4}$.

The Machines

There are machines already exist way before the attack's 900 GPUs, like the Summit in Oak Ridge that can reach $2^{63}$ SHA-1 calculations in a day. As long as, one cannot find a weakness in SHA-512/160, it will have an 80-bit classical collision resistance.

80-bit is no longer secure

Today, 80-bit collision resistance for any hash function is not considered secure. The NIST removed SHA-1 signatures from the recommendation in 2011.

NIST formally deprecated use of SHA-1 in 2011 [NISTSP800-131A-R2] and disallowed its use for digital signatures at the end of 2013.

R2 in 2019 on page 18 NIST allows it for nonsignature, although by that time it's clearly a bad idea (Thanks to Dave).

Actually, one can consider that it is not the SHA-1 is removed, the 160-bit hash output is removed from the recommendation. The 160-bit was related to 80-bit security that was enough during the early 2000s. And, note that the 50% probability of the birthday attack is not negligible in the view of the attackers. One must consider the lower probabilities.

Recommendation

It is wiser to update the software to new recommendations like the SHA3 series with good hash sizes like 256, 384, or 512 if you are working with the US government. If not, you can also use other good hash functions like Blake2. If you consider Quantum attacks, you should bigger than 256.

You can use it if you are satisfied but not advised.

Migrating the software shouldn't be a big problem. It is strongly recommended.

Answer 2

It's certainly better to move to a modern hash function without significant known weaknesses than to stick with one that is known to be broken. Furthermore using a larger state for the hashing process helps mitigate certain attacks, even if your output size is limited.

In an ideal world you would make the system support longer hashes, but if the choice is SHA1 or SHA256-160 then you should certainly go for the latter.

Answer 3

By all accounts SHA-512/160 is more secure than SHA1. The only question is it secure enough? If you are only worried about preimage or second preimage resistance the answer is yes. 160 bits should be sufficient for the forseeable future even faced against powerfull adversaries.

If you need collision resistance the answer gets more complicated. There are no known collisions of SHA-512/160 or SHA256/160 and no attacks better than generic attacks. We do have highly efficient hardware for calculating these hashes. A nation state (or tech giant) adversary could create such a collision. What about a modest adversary? If we look at: https://www.asicminervalue.com/miners/bitmain/antminer-s9-se-16th to get order of magnitude(Yes I know it's not the same), the electricity costs for 2^80 hashes would be a few million dollars. Consider improvements in efficiency in coming years and the cost barrier becomes not so high. If your secrets aren't worth more than a few thousand dollars you can get away with a 160 bit hash. And this is assuming a collision not tailored to you is irrelevant. It is likely someone will publish such collision in the next few years.

If at all possible move to SHA3 and a larger hash.

Answer 4

It is as safe as SHA-1 was initially supposed to be. The same would be true of most other notable secure hash functions with digests truncated to 160 bits.

Crucially, though, the security of the resulting algorithm is always limited to 160-bit pre-image resistance and 80-bit collision resistance. It doesn't matter how much higher SHA-512 or another hash function's security levels are.

Pre-image resistance is limited to the smaller of 160-bit (the output length) security or the substitute hash function's pre-image resistance. Collision resistance is limited to 80 bits (half the output length) or to the substitute hash's collisions resistance. (Whichever is smaller.)

Continuing to use a 160-bit hash function may still be a problem. Though the collision attacks on SHA-1 took less than 2⁸⁰ work, the gap between the ideal collision resistance of SHA-1 and its actual collision rseistance isn't so large to leave cautious people at ease. It would merely be a million times more costly to find a collision for an ideal 160-bit hash with today's hardware.

---

Why would SHA-512/160 be safer than SHA-1? There are no full- or partial pre-image attacks on SHA-512 that would cost less than 2¹⁶⁰. SHA-512 is believed to have 512-bit (full) pre-image resistance. Similar reasoning applies to collision resistance.

Remember that I said "most other notable secure hash functions" would be okay. This is because most modern hash functions are designed to behave like a random oracle. That means you can't differentiate a hash function from a process that generates a random output every time it sees a new input, sampling from a uniform distribution of all possible bit strings of a given length.

In the random oracle model, all potential output strings are equally likely. That makes individual output bits statistically independent of one another. With that definition, you can prove that any random oracle has the maximum possible collision resistance and pre-image resistance. (Determined only by the length of the output.)

Since truncating a string of uniform, statistically independent bits just produces another, shorter string of uniform independent bits, one can intuit that truncating the output of a random oracle produces a hash function with the identical security properties compared to an ideal hash function of the same (truncated) output length.

---

Caveats:

1. A random oracle is a presumed model. It cannot be proven that any certain hash function can be modeled accurately as one. It can only be disproven by finding weaknesses in the algorithm.
2. The minimum requirements for a hash function differs depending on who you ask. It's also said that a hash function only needs collision resistance and be one-way. In that case truncating the digest output can't be assumed to be safe. (The SWIFFT algorithm is the only example that comes to mind. However you see something similar with MAC functions. Hash-based MACs have predictable security properties if truncated. Generic MACs may not.)
3. SHA-512 is vulnerable to length extension attacks, so it's not always safe to treat it as a random oracle. If you don't consider random oracle inputs to be public knowledge, then you may need to use HMAC, double-hash, or truncate the output to prevent people from being able to derive valid hashes without secret knowledge. Since you truncate by 352 bits, length extension attacks are not relevant. Newer algorithms, like Blake2, SHA-3, and Skein are intended to behave like a random oracle and are not vulnerable to length extension attacks.