Около 2010 года сложное вредоносное ПО под названием Flame захватило механизм, который компания Microsoft использовала для распространения обновлений на миллионы компьютеров с Windows по всему миру. Это вредоносное ПО, как сообщалось, было разработано совместно США и Израилем, и оно распространило вредоносное обновление по всей зараженной сети, принадлежащей иранскому правительству.

Ключевым моментом атаки «столкновения» было использование уязвимости в функции хеширования MD5, которую Microsoft использовала для аутентификации цифровых сертификатов. Создав идеальную цифровую подпись на основе MD5, атакующие подделали сертификат, который аутентифицировал их вредоносный сервер обновлений. Если бы эта атака была использована более широко, она имела бы катастрофические последствия во всем мире.

Неприятно близко к зоне опасности

Это событие, которое стало известно в 2012 году, теперь служит предостерегающей историей для криптографических инженеров, которые размышляют о крахе двух важных криптографических алгоритмов, используемых повсюду. С 2004 года было известно, что MD5 уязвим для «столкновений», — фатальной ошибки, которая позволяет противникам генерировать два различных входных данных, производящих идентичные выходные данные.

В течение четырех лет две другие работы исследований еще больше продемонстрировали слабость MD5. Последняя использовала 200 игровых консолей Sony PlayStation, работающих в течение трех дней, чтобы сгенерировать поддельный сертификат TLS. Несмотря на то, что фатальная ошибка была хорошо известна, небольшая часть инфраструктуры Microsoft по-прежнему использовала эту функцию хеширования.

Решив не допустить повторения подобной ситуации, организации по всему миру внедряют новые алгоритмы для замены RSA и эллиптических кривых. Более трех десятилетий эти два алгоритма с открытым ключом были известны как уязвимые для алгоритма Шора, серии уравнений, которые позволяют квантовому компьютеру достаточной силы решать математические проблемы, лежащие в основе этих двух алгоритмов, за полиномиальное время, что является значительным ускорением по сравнению с экспоненциальным временем, необходимым классическим компьютерам.

Sometime around 2010, sophisticated malware known as Flame hijacked the mechanism that Microsoft used to distribute updates to millions of Windows computers around the world. The malware—reportedly jointly developed by the US and Israel—pushed a malicious update throughout an infected network belonging to the Iranian government.

The lynchpin of the “collision” attack was an exploit of MD5, a cryptographic hash function Microsoft was using to authenticate digital certificates. By minting a cryptographically perfect digital signature based on MD5, the attackers forged a certificate that authenticated their malicious update server. Had the attack been used more broadly, it would have had catastrophic consequences worldwide.

Getting uncomfortably close to the danger zone

The event, whichcame to lightin 2012, now serves as a cautionary tale for cryptography engineers as they contemplate the downfall of two crucial cryptography algorithms used everywhere. Since2004, MD5 has been known to be vulnerable to “collisions,” a fatal flaw that allows adversaries to generate two distinct inputs that produce identical outputs.

Within four years,twoother pieces ofresearchfurther demonstrated the weakness of MD5. The latter used 200 Sony Playstations running for three days to generate a rogue TLS certificate. Despite the fatal flaw being well known, a small part of Microsoft’s sprawling infrastructure still used the hash function.

Determined to keep a similar scenario from playing out again, organizations everywhere are rolling out new algorithms to replace RSA and elliptic curves. For more than three decades, the two public-key algorithms have been known to be vulnerable toShor’s algorithm, a series of equations that allow a quantum computer of sufficient strength to solve the mathematical problems underpinning these two algorithms in polynomial time, a dramatic speed-up from the exponential time required by classical computers.