Researchers from the French National Institute for Research in Computer Science and Automation (INRIA) and Nanyang Technological University (Singapore) have presented a method of attack (), which is touted as the first practical implementation of an attack on the SHA-1 algorithm that can be used to create fake digital signatures for PGP and GnuPG. The researchers believe that all practical attacks on MD5 can now also be applied to SHA-1, although they still require significant resources for execution.
The method is based on conducting , allowing for two arbitrary sets of data to be adjusted so that when these adjustments are attached, they will result in colliding sets, where applying the SHA-1 algorithm will produce the same resulting hash. In other words, for two existing documents, two adjustments can be calculated, and if one is attached to the first document and the other to the second, the resulting SHA-1 hashes for these files will be identical.
The new method differs from previously proposed similar techniques by improving the efficiency of collision searches and demonstrating practical applicability for attacks on PGP. In particular, the researchers managed to prepare two public PGP keys of different sizes (RSA-8192 and RSA-6144) with differing user identifiers and certificates that cause SHA-1 collisions. included the victim's identifier, while the contained the attacker's name and image. Thanks to the collision, the identifying certificate that included the key and the attacker's image had the same SHA-1 hash as the identification certificate that included the key and the victim's name.
The attacker could request a digital signature for their key and image from an external certification authority, then transfer the digital signature for the victim's key. The digital signature remains valid due to the collision and the certification of the attacker's key by the certification authority, allowing the attacker to take control of the key bearing the victim's name (since the SHA-1 hashes for both keys match). As a result, the attacker can impersonate the victim and sign any document on their behalf.
The attack remains quite costly, but is now affordable for intelligence agencies and large corporations. For a simple collision search using a cheaper NVIDIA GTX 970 GPU, the costs amounted to $11,000, while for a collision search with a specified prefix, it reached $45,000 (for comparison, in 2012, the estimated cost for a collision search in SHA-1 was $2 million, and in 2015 it was $700,000). Conducting a practical attack on PGP required two months of computations involving 900 NVIDIA GTX 1060 GPUs, with rental costs amounting to $75,000 for the researchers.
The method proposed by researchers for detecting collisions is approximately 10 times more effective than previous achievements — the complexity level of collision computations has been reduced to 261.2 operations, instead of 264.7, and collisions with a specified prefix to 263.4 operations instead of 267.1. Researchers recommend transitioning from SHA-1 to the use of SHA-256 or SHA-3 as soon as possible, as they predict that by 2025 the cost of conducting an attack will drop to $10,000.
The developers of GnuPG were notified about the issue on October 1 (CVE-2019-14855) and on November 25, with the release of GnuPG 2.2.18, they took measures to block problematic certificates — all digital signatures identifying SHA-1 created after January 19 of last year are now considered invalid. CAcert, one of the main certification authorities for PGP keys, plans to switch to using more secure hash functions for key certification. In response to the information about the new attack method, OpenSSL developers decided to disable SHA-1 at the proposed default first security level (SHA-1 cannot be used for certificates and digital signatures during the connection agreement).
Source: opennet.ru
