Researchers from the French National Institute for Research in Computer Science and Automation (INRIA) and Nanyang Technological University (Singapore) enhanced the SHA-1 algorithm, significantly simplifying the creation of two different documents with identical SHA-1 hashes. The essence of the method is to reduce the operation of a full collision search in SHA-1 to , where the collision occurs in the presence of specific prefixes, regardless of the other data in the set. In other words, one can compute 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 identical.
This type of attack still requires enormous computations, and prefix selection remains more complex than ordinary collision searches, but the practical effectiveness of the result is significantly higher. If previously the fastest method for finding collision prefixes in SHA-1 required about 277.1 operations, the new method reduces the number of computations to a range from 266.9 to 269.4. At this level of computation, the estimated cost of the attack is less than a hundred thousand dollars, which is quite affordable for intelligence agencies and large corporations. For comparison, finding a standard collision requires approximately 264.7 operations.
In Google's ability to generate different PDF files with the same SHA-1 hash is a trick that combines two documents into one file, switches the visible layer, and shifts the layer selection mark into the collision occurrence area. With similar resource expenditure (Google spent a year computing on a cluster of 110 GPUs to find the first SHA-1 collision), the new method allows for matching SHA-1 for two arbitrary sets of data. Practically, it enables the preparation of TLS certificates that reference different domains but have identical SHA-1 hashes. This capability allows a rogue certificate authority to create a certificate for a digital signature that can be used to authorize bogus certificates for arbitrary domains. This issue can also be exploited to compromise protocols that rely on the absence of collisions, such as TLS, SSH, and IPsec.
The proposed prefix search strategy for collisions involves breaking down calculations into two stages. The first stage entails searching for blocks that are on the verge of collision by embedding random chain variables into a predefined target set of differences. In the second stage, at the level of individual blocks, the obtained difference chains are matched with the state pairs that lead to collisions, using traditional collision search attack methods.
Although the theoretical possibility of an attack on SHA-1 was proven back in 2005, the first collision was practically in 2017, SHA-1 still remains in use and is covered by certain standards and technologies (TLS 1.2, Git, etc.). The main goal of this work was to provide yet another compelling argument for the immediate discontinuation of SHA-1, especially in certificates and digital signatures.
Additionally, it can be noted of the cryptanalysis of block ciphers , developed by the NSA and approved in 2018 as a standard .
Researchers managed to develop a method for recovering the private key based on two known pairs of plaintext and ciphertext. With limited computational resources, key recovery takes from several hours to several days. The theoretical success rate of the attack is estimated at 0.25, while the practical rate for the existing prototype is 0.025.
Source: opennet.ru
