Researchers from the French State Institute for Research in Informatics and Automation (INRIA) and Nanyang Technological University (Singapore) improved to the SHA-1 algorithm, which greatly simplifies the creation of two different documents with the same SHA-1 hashes. The essence of the method is to reduce the operation of a full-fledged selection of a collision in SHA-1 to , in which a collision occurs when certain prefixes are present, regardless of the rest of the data in the set. In other words, you can calculate two predefined prefixes, and if one is attached to one document, and the other to the second, the resulting SHA-1 hashes for these files will be the same.
This type of attack still requires huge calculations and the selection of prefixes remains more difficult than the usual selection of collisions, but the practical effectiveness of the result is much higher. If so far the fastest method for finding collision prefixes in SHA-1 required 277.1 operations, then the new method reduces the number of calculations to a range from 266.9 to 269.4. With this level of computation, the estimated cost of an attack is less than a hundred thousand dollars, which is quite affordable for intelligence agencies and large corporations. For comparison, the search for a normal collision requires approximately 264.7 operations.
Π Google ability to generate different PDFs with the same SHA-1 hash trick with merging two documents into one file, switching the visible layer and shifting the layer selection mark to the collision area. At close resource costs (Google spent a year of computing on a cluster of 1 GPUs to find the first SHA-110 collision), the new method allows you to achieve a SHA-1 match for two arbitrary data sets. As a practical matter, you can prepare TLS certificates that mention different domains but match SHA-1 hashes. This feature allows a dishonest CA to create a digital signature certificate that can be used to authorize fictitious certificates to arbitrary domains. The problem can also be used to compromise protocols that rely on non-collision, such as TLS, SSH, and IPsec.
The proposed strategy for finding prefixes for collision involves splitting the calculations into two stages. The first step searches for blocks that are on the verge of a collision by embedding random chain variables into a predefined target difference set. At the second stage, at the level of individual blocks, the resulting chains of differences are compared with pairs of states leading to collisions using the methods of traditional collision brute force attacks.
Despite the fact that the theoretical possibility of an attack on SHA-1 was proven back in 2005, in practice the first collision was in 2017, SHA-1 is still in use and covered by some standards and technologies (TLS 1.2, Git, etc.). The main goal of the work done was to provide another strong argument for the immediate cessation of the use of SHA-1, especially in certificates and digital signatures.
Additionally, it can be noted cryptanalysis of block ciphers , developed by the US NSA and approved as a standard in 2018 .
The researchers managed to develop a method for recovering a private key based on two known pairs of plaintext and ciphertext. With limited computing resources, it takes from several hours to several days to select a key. The theoretical attack success rate is estimated at 0.25, and the practical one for the existing prototype is 0.025.
Source: opennet.ru