# In 2020, SHA-1 practically broken in chosen-prefix collision (CP-collision). Can double SHA-1 hashing prevent CP-collision?

In a recent study SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust by Gaëtan Leurent and Thomas Peyrin. 2020, they showed the first practical chosen-prefix collision attack that required two months of computations using 900 Nvidia GTX 1060 GPUs.

Chosen-prefix collision (CP- collision)1: two message prefixes $$P$$ and $$P'$$ are first given as challenge to the adversary, and his goal is to compute two messages $$M$$ and $$M'$$ such that $$H(P \mathbin\| M) = H(P' \mathbin\| M')$$ where $$\mathbin\|$$ denotes concatenation.

They worked for two kinds of attacks;

• 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 CP-collision from $$2^{67.1}$$ to $$2^{63.4}$$.

Actually, the CP-collision attack enables attackers to create some meaningful messages; however, classical collisions are not.

To demonstrate the attack they achieved a PGP/GnuPG impersonation (CVE-2019-14855).

### Questions:

• Can a double hashing $$h= \operatorname{SHA-1}(\operatorname{SHA-1}(m))$$ mitigate the CP-collision?* It seems so, since the meaningful part will not exist for attackers as longs as they are not able to break double $$\operatorname{SHA-1}$$. This seems not feasible, yet.
• An immediate follow-up question; if the answer is yes, should we design the new protocols based on double hashing?

*There can be many variants of double hashing.

• 1) This doesn't mitigate the collision. 2) Anything that can be changed from SHA-1(m) to SHA-1(SHA-1(m)) could be just as easily changed to SHA-3(m). – Paul Smith Jan 9 at 0:01

We might consider other constructions which may provide some strength e.g $$H(H(m) || m)$$ however:
• @kelalaka: A possible more useful double-hash might be $H(m) || H("hello world" || m))$ or something, or combine those two hashes somehow other than concat, maybe XOR. They can both be computed with only a single pass over the data so it's still usable as a stream hash where you only have access to the data once on the fly. (No extra memory bandwidth required either, and interleaving computation on 2 hashes in parallel is probably good for throughput.) But even if you need a short 160-bit hash, that might not be better than truncating a SHA-256 or SHA-512. – Peter Cordes Jan 8 at 3:34
• @PeterCordes Actually, NIST removed SHA-1 from the recommendation in 2011. The $2^{80}$ classical collision with 50% probability is not negligible, we should consider the lower probabilities, and there are already collective computing powers that can reach $\approx 2^{63}$ in a day, like Summit. Maybe the more interesting of this work is the use case. Truncating has one good side that prevents the extension attack that built-in SHA3. – kelalaka Jan 8 at 8:52