CHOCOLAT: CHOsen-prefix COLlision ATtack
The Associate Team CHOCOLAT is a collaboration between Inria (France) and NTU (Singapore), started in 2017. The team is led by Gaëtan Leurent (Inria) and Thomas Peyrin (NTU).
The main focus of the team is on the cryptanalysis of hash function. The goal of this collaboration is to find new cryptanalysis techniques, and to implement the attacks in practice when possible.
Scientific Program
The hash function SHA-1 is one of the most widely used hash functions in the industry, but it has been shown to not be collision-resistant by a team of Chinese researchers led by Prof. Wang in 2005. However, it took several years to implement the attack, because the estimated complexity is around 2⁶³ SHA-1 computations (this represents about 70000 years of computation on a normal PC). The first public collision was only demonstrated in February 2017, when a team of researchers from Google and CWI published the first collision in the full SHA-1, which confirms the validity of the previous cryptanalysis results.
While this clearly demonstrate the weakness of the algorithm, a much more powerful attack would be to find a collision such that the prefix of the colliding messages is chosen by some challenger beforehand. In particular, this would allow creating a rogue Certificate Authority certificate that would be accepted by browsers. Such an attack has already been deployed for certificates using the MD5 hash function, but MD5 is much weaker than SHA-1 and it has already been removed from most security applications. SHA-1 is still widely used and performing such an attack for certificates using SHA-1 would have a very big impact.
The objective of the project was to design a chosen-prefix collision attack against the SHA-1 hash function, and to implement the attack in practice. We estimated originally that this would require 2⁷⁰ computations, and the goal of the project was to use an ASIC cluster to perform such a computation.
Scientific Achievements
After three years of research, we have found a new cryptanalysis strategy to generate chosen-prefix collisions, and we have computed the first concrete chosen-prefix collision against SHA-1. This attack is highly technical to implement and requires a huge amount of processing power, but we have demonstrated that it is practical with an academic budget (below 100k USD). Moreover, the chosen-prefix collision we have computed leads to forgery of PGP/GnuPG keys, proving the impact of this type of attack. This is a very strong result, showing that SHA-1 must be removed immediately from security products that still use it.
For more detail about our main result, please visit the dedicated website.
In parallel, we have studied hardware architectures to implement SHA-1 attacks and have designed an FPGA prototype of the attacking tool. However, this analysis indicates that a GPU implementation of the attack if generally more efficient.
