Editing SHA-1 (section)

==== Birthday-Near-Collision Attack – first practical chosen-prefix attack ====
On 24 April 2019 a paper by Gaëtan Leurent and Thomas Peyrin presented at Eurocrypt 2019 described an enhancement to the previously best [[Collision attack#Chosen-prefix collision attack|chosen-prefix attack]] in [[Merkle–Damgård construction|Merkle–Damgård]]–like digest functions based on [[One-way compression function#Davies–Meyer|Davies–Meyer]] block ciphers. With these improvements, this method is capable of finding chosen-prefix collisions in approximately 2<sup>68</sup> SHA-1 evaluations. This is approximately 1 billion times faster (and now usable for many targeted attacks, thanks to the possibility of choosing a prefix, for example malicious code or faked identities in signed certificates) than the previous attack's 2<sup>77.1</sup> evaluations (but without chosen prefix, which was impractical for most targeted attacks because the found collisions were almost random)<ref name="stevens-attacks"/> and is fast enough to be practical for resourceful attackers, requiring approximately $100,000 of cloud processing. This method is also capable of finding chosen-prefix collisions in the [[MD5]] function, but at a complexity of 2<sup>46.3</sup> does not surpass the prior best available method at a theoretical level (2<sup>39</sup>), though potentially at a practical level (≤2<sup>49</sup>).<ref name="leurent-peyrin-sha1">{{cite conference |chapter-url=https://hal.inria.fr/hal-02424900/file/SHA1_EC19.pdf |last1=Leurent |first1=Gaëtan |last2=Peyrin |first2=Thomas |title=Advances in Cryptology – EUROCRYPT 2019 |chapter=From Collisions to Chosen-Prefix Collisions Application to Full SHA-1 | conference= 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019 |date=2019 |url=https://eprint.iacr.org/2019/459.pdf | publisher= Springer |series=Lecture Notes in Computer Science |volume=11478 |pages=527–555 |doi=10.1007/978-3-030-17659-4_18 |isbn=978-3-030-17658-7 |s2cid=153311244 | editor1= Yuval Ishai| editor2= Vincent Rijmen}}</ref> This attack has a memory requirement of 500+ GB.

On 5 January 2020 the authors published an improved attack called "shambles".<ref name="leurent-peyrin-sha1-shambles"/> In this paper they demonstrate a chosen-prefix collision attack with a complexity of 2<sup>63.4</sup>, that at the time of publication would cost US$45K per generated collision.