Researchers from the French State Institute for Research in Informatics and Automation (INRIA) and the Nanyang Technological University (Singapore) presented an attack method (), which is touted as the first practical implementation of an attack on the SHA-1 algorithm that can be used to create bogus digital signatures for PGP and GnuPG. The researchers believe that now all practical attacks on MD5 can be applied to SHA-1, although they still require significant resources to implement.
The method is based on conducting , which allows for two arbitrary data sets to select additions, when attached, the result will be collision-causing sets, the application of the SHA-1 algorithm for which will lead to the formation of the same resulting hash. In other words, two complements can be calculated for two existing documents, and if one is appended to the first document and the other to the second, the resulting SHA-1 hashes for these files will be the same.
The new method differs from previously proposed similar techniques by improving the efficiency of collision detection and demonstrating a practical application for attacking PGP. In particular, the researchers were able to prepare two PGP public keys of different sizes (RSA-8192 and RSA-6144) with different user IDs and with certificates causing SHA-1 collision. included victim ID, and included the attacker's name and picture. At the same time, due to the selection of a collision, the certificate identifying the keys, including the attacker's key and image, had the same SHA-1 hash as the identification certificate, including the key and the name of the victim.
An attacker could request a digital signature for his key and an image from a third-party certification authority, and then transfer the digital signature for the victim's key. The digital signature remains valid due to the collision and verification of the attacker's key by the certification authority, which allows the attacker to gain control over the key with the name of the victim (since the SHA-1 hash for both keys is the same). As a result, the attacker can impersonate the victim and sign any document on her behalf.
The attack is still quite costly, but it is already quite affordable for the special services and large corporations. For simple collision detection using the cheaper NVIDIA GTX 970 GPU, the cost was $11, and for matching a collision with a given prefix - $45 (for comparison, in 2012, the cost of matching a collision in SHA-1 was estimated at $2 million, and in 2015 - 700 thousand). A practical attack on PGP took two months of computation using 900 NVIDIA GTX 1060 GPUs, which cost the researchers $75 to rent.
The method proposed by the researchers for detecting collisions is about 10 times more efficient than past achievements - the level of complexity of computing collisions was reduced to 261.2 operations, instead of 264.7, and collisions with a given prefix to 263.4 operations instead of 267.1. The researchers recommend switching from SHA-1 to using SHA-256 or SHA-3 as soon as possible, as they predict that the cost of conducting an attack will drop to $2025 in 10.
The GnuPG developers were notified of the issue on October 1 (CVE-2019-14855) and took action on November 25 with the release of GnuPG 2.2.18 to block the problematic certificates - all SHA-1 digital signatures created after January 19 of last year are now recognized as invalid. CAcert, one of the main CAs for PGP keys, plans to move to more secure hash functions for certifying keys. The OpenSSL developers, in response to information about a new attack method, decided to disable SHA-1 at the default first security level (SHA-1 will not be used for certificates and digital signatures during the connection negotiation process).
Source: opennet.ru