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).
The list of attacks on SHA-1
- 2005, collision with complexity $2^{69}$, Finding collisions in the full SHA-1, Wang et. al.
- 2013, chosen-prefix collision with complexity $2^{77.1}$, New collision attacks on SHA-1 based on optimal joint local-collision analysis, Stevens et. al.
- 2013, collision with complexity $2^{64.7}$, from the previous article.
- 2016, free-start collision with complexity $2^{57.5}$, Freestart collision for full SHA-1. Stevens et. al.
- 2017, collision with complexity $2^{63.1}$, The first collision for full SHA-1., Steven et. al.
- 2019, chosen-prefix collision with $2^{67.1}$ complexity, From collisions to chosen-prefix collisions, Leurent et.al. application to full SHA-1
- 2020, collision with $2^{61.2}$ complexity, SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust, Leurent et. al. (The new article)
- 2020, chosen-prefix collision with $2^{63.4}$ complexity, same paper above.
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.