RFC 4270 Attacks on Cryptographic Hashes in Internet Protocols

Network Working Group                                         P. Hoffman
Request for Comments: 4270                                VPN Consortium
Category: Informational                                      B. Schneier
                                           Counterpane Internet Security
                                                           November 2005

Attacks on Cryptographic Hashes in Internet Protocols

Атаки на криптографический хэш в протоколах Internet

PDF

Статус документа

Документ является информационным, не содержит стандартов Internet и может распространяться без ограничений.

Авторские права

Copyright (C) The Internet Society (2005).

Аннотация

Недавние сообщения об атаках с использованием коллизий в популярных алгоритмах хэширования, которые оказались успешней, чем ожидалось, заставили некоторых задаться вопросом о необходимости изменения некоторых протоколов Internet и способах достижения этого. В этом документе приведена сводка применения хэширования в протоколах, рассмотрено влияние атак с коллизиями на протоколы и показано, как предотвратить известные атаки на цифровые сертификаты, а также рассмотрены перспективные направления для разработчиков протоколов.

1. Введение

Летом 2004 г. группа исследователей представила конкретные доказательства уязвимости алгоритма хэширования MD5 к атакам с коллизиями [MD5-attack]. В начале 2005 г. та же группа показала похожую атаку на вариант алгоритма хэширования SHA-1 [RFC3174] с предсказанием уязвимости обычно применяемого SHA-1 при большом объёме работы (но меньшем, чем следует требовать для нормальной работы SHA-1) [SHA-1-attack]. Также в начале 2005 г. исследователи продемонстрировали конкретную конструкцию сертификатов PKIX [RFC3280], использующих MD5 для подписи [PKIX-MD5-construction], а другой исследователь показал более быстрый метод поиска коллизий MD5 (8 часов на компьютере с тактовой частотой 1,6 ГГц) [MD5-faster]. В результате этого среди экспертов-криптографов, разработчиков протоколов и других заинтересованных людей, началось активное обсуждение — что делать и нужно ли что-то делать. К сожалению некоторые из дискуссий основывались на ошибочной интерпретации обеих новостей и способов применения алгоритмов хеширования в основных протоколах Internet.

Алгоритмы хэширования применяются криптографами в разных протоколах безопасности на всех уровнях стека протоколов Internet. Они нужны из-за двух свойств безопасности — необратимости и отсутствия коллизий (эти свойства подробнее рассмотрены в следующем разделе и объяснить их проще в терминах нарушения). Недавние атаки показали, что одно из упомянутых свойств безопасности присутствует не всегда. Хотя, безусловно, возможно и на первый взгляд даже вероятно, что нарушение свойства защиты не будет влиять на общую безопасность многих конкретных протоколов Internet, консервативный подход к обеспечению безопасности заключается в смене алгоритмов хэширования. Сообщество Internet должно планомерно перейти от SHA-1 и MD5 (особенно) к более безопасным алгоритмам хэширования.

В этом документе приведена сводка сведений об алгоритмах хэширования и использующих их протоколах Internet, а также даны рекомендации, как избежать известных проблем с MD5 и SHA-1 и что следует принимать во внимание, если предсказанные атаки станут реальностью.

Текущая ситуация в общих чертах описана ниже.

• Алгоритмы MD5 и SHA-1 подверглись новым атакам и атаки на MD5 гораздо серьёзней атак на SHA-1.

• Атаки на MD5 осуществимы на любом современном компьютере.

• Атаки на SHA-1 не осуществимы на сегодняшних компьютерах, но станут возможны при их усовершенствовании или продолжении удешевления расчётов по закону Мура.

• Многие протоколы Internet общего назначения используют хэширование, не подверженное влиянию этих атак.

• Большинство затрагиваемых протоколов связано с цифровыми подписями.

• Более совершенные алгоритмы хэширования снизят уязвимость к таким атакам до приемлемого для всех пользователей уровня.

2. Алгоритмы хэширования и атаки на них

«Идеальный» алгоритм хэширования имеет несколько базовых свойств. Он преобразует блок данных (chunk), обычно являющийся сообщением произвольного размера, в результат фиксированного размера. Размер результата называют длиной хэша (hash length) и часто обозначают буквой L. Результат применения алгоритма хэширования к конкретному блоку данных называют хэш-значением (hash value) для этих данных. Для двух разных сообщений любого размера алгоритму следует обеспечивать чрезвычайно малую вероятность совпадения хэш-значений независимо от степени схожести сообщений и их размеров.

Из этого описания следуют два математических вывода. Для поиска пары сообщений M1 и M2 с одинаковым хэш-значением потребуется 2^(L/2) попыток. При любой разумной длине хэша решить такую задачу невозможно (отсутствие коллизий). Чтобы найти для сообщения M1 другое сообщение M2 с таким же хэш-значением, потребуется 2^L попыток. Это ещё более сложная задача (необратимость функции). Отметим, что описание относится к идеальному алгоритму хэширования, а при неидеальном алгоритме злоумышленнику может потребоваться меньше усилий, чтобы найти два сообщения с одинаковым хэш-значением.

Существует две категории атак.

Атаки против свойства отсутствия коллизий:

• Атаки с коллизиями (collision attack) позволяют злоумышленнику найти два сообщения M1 и M2 с одним хэш-значением за меньше, чем 2^(L/2) попыток.

Атаки против свойства необратимости:

• Атака с поиском первого прообраза (first-preimage attack) позволяет злоумышленнику, знающему нужное хэш-значение, найти сообщение с таким же хешем меньше, чем за 2^L попыток.

• Атака с поиском второго прообраза (second-preimage attack) позволяет злоумышленнику, имеющему нужное сообщение M1, найти другое сообщение M2 с таким же хэш-значением меньше, чем за 2^L попыток.

Две атаки с поиском прообраза очень похожи. В атаке с первым прообразом известно хэш-значение, но неизвестно сообщение, по которому оно создано, и нужно найти какое-либо сообщение с таким же хэш-значением. В атаке со вторым прообразом известно сообщение, для которого нужно найти другое сообщение, имеющее такое же хэш-значение. Атаки, позволяющие найти один прообраз, зачастую способны найти и другой.

При анализе использования алгоритмов хэширования в протоколах нужно понимать, какое из двух свойств хэширования является важным, особенно сейчас, когда свойство отсутствия коллизий ослабевает для популярных алгоритмов хэширования. Безусловно, важно понять, какие стороны выбирают материал для хэширования. Кроме того, как показали некоторые ранние исследования, в частности, [PKIX-MD5-construction], важно понимать, какая из сторон может предсказать начало хэшируемого объекта.

2.1. Известные в настоящее время атаки

Все известные в настоящее время практичные или почти практичные атаки на MD5 и SHA-1 связаны с поиском коллизий. Это удача, поскольку атаки на алгоритмы хэширования с поиском первого или второго прообраза были бы гораздо опасней в реальном мире, чем атаки с поиском коллизий, рассматриваемые далее.

Важно отметить, что для современных атак с поиском коллизий нужна некая структура битов хотя бы в одном из двух сообщений. Это означает, что найти два сообщения с одинаковым хэш-значением, которые были бы полезны в реальной атаке, сложнее, чем просто найти два сообщения с одинаковым хэш-значением.

3. Использование алгоритмов хэширования в протоколах Internet

Алгоритмы хэширования применяются в Internet множеством способов. Большинство протоколов, применяющих хэширование, делают это с обеспечением стойкости к атакам с поиском коллизий. Это не случайно, и хорошие разработчики протоколов создают свои протоколы так, чтобы они могли противостоять как можно большему числу будущих изменений в базовой криптографии, включая атаки на сами криптографические алгоритмы. Применения алгоритмов хэширования описаны ниже.

• Безотзывные цифровые подписи сообщений. Безотзывность — это услуга, защищающая от ложных отказов фактов участия во взаимодействии. S/MIME и OpenPGP позволяют отправителям подписывать содержимое создаваемых сообщений и получатель может проверить подпись на предмет её связи с сообщением. От сообщения невозможно отказаться, если оно было подписано, и получатель сообщения может впоследствии использовать подпись для подтверждения создания сообщения подписавшей стороной.

• Цифровые подписи в сертификатах доверенной третьей стороны. Это похоже на цифровую подпись сообщения, но сертификаты применяются во многих протоколах для аутентификации и управления ключами.

• Протоколы запрос-отклик (challenge-response) объединяют большое открытое случайное число с неким значением для сокрытия того при передаче по каналам без шифрования.

• Аутентификация сообщений с общим секретом похожа на протоколы запрос-отклик, но вместо использования открытых значений сообщение перед хэшированием объединяется с общим секретом.

• Функции вывода ключей многократно применяют алгоритмы хэширования для преобразования данных в случайную строку, применяемую для создания одного или нескольких ключей, используемых криптографическими протоколами.

• Функции перемешивания многократно применяют алгоритмы хэширования для преобразования данных в случайные строки, служащие для целей, отличных от создания криптографических ключей.

• Для проверки надёжности и обнаружения ошибок¹ обычно сравнивается хэш-значение для файла, полученное по отдельному каналу (out-of-band), со значением, рассчитанным получателем файла после его передачи по незащищённому протоколу, такому как FTP.

Из перечисленных методов только первые два подвержены атакам на основе коллизий, да и то лишь в некоторых случаях. На данный момент считается что в общем случае протоколы запрос-отклик неуязвимы, поскольку отправитель проверяет подлинность секрета уже имеющегося у получателя. Считается, что проверка подлинности сообщений с общим секретом не подвержена каким-либо атакам. Все функции вывода ключей в протоколах IETF принимают на входе случайные значения от обеих сторон, поэтому у злоумышленника нет возможности структурировать хэшированное сообщение.

4. Атаки с коллизиями и безотзывность цифровых подписей

Основная идея атак с поиском коллизий на алгоритм хэширования, используемый протоколом цифровой подписи, заключается в том, что злоумышленник создаёт два сообщения с одинаковым хэш-значением, добивается подписания одного из них, а затем использует подпись для другого сообщения с той или иной злонамеренной целью. Специфика таких атак зависит от используемого протокола и действий жертвы после получения подписанного сообщения. В классическом примере создаются два сообщения, одно из которых говорит: «Я плачу 10 долларов за выполнение этой работы», а второе: «Я заплачу 10000 долларов за выполнение этой работы». Первое сообщение представляется жертве, которую нужно вынудить подписать его. После этого выполняется работа, сообщение подменяется вторым с предъявлением его вместе с подписью (она остаётся действительной) и можно требовать 10000 долларов в оплату за выполненную работу. Если жертва откажется платить, можно обратиться в суд и показать второе сообщение с подписью².

Большинство атак с неотказуемостью основано на оценке человеком достоверности якобы подписанного сообщения. В случае атаки с хэш-коллизией, подпись в таком сообщении является действительной, как и подпись исходного сообщения. Жертва может воспроизвести (создать) исходное сообщение, показать, что оно было подписано, а также указать, что хэш-значения двух сообщений совпадают. Вероятность случайного совпадения составляет 1/2^L, что бесконечно мало как для MD5, так и для SHA-1.

Иными словами, для расстройства атаки с коллизией хэш-значений в протоколе с безотзывностью, где подписанное сообщение используется как предоставление полномочий, подписавший должен сохранить копию исходного подписанного сообщения. Сообщения, у которых имеются «двойники» с таким же хэшем, должны быть созданы одним лицом и не могут появиться случайно ни при каких известных и вероятных обстоятельствах. Совпадение хэш-значений у двух сообщений должно вызвать достаточно сомнений у человека, оценивающего действительность подписи, чтобы привести к провалу юридической атаки (и, возможно, к предъявлению встречного иска по поводу мошенничества).

Расстройство атак с коллизией в автоматизированных протоколах с неотказуемостью потенциально сложнее, поскольку здесь может не оказаться людей, обративших достаточное внимание, чтобы можно было спорить о том, что должно было произойти. Например, в приложениях обмена электронной данными (electronic data interchange или EDI) после аутентификации подписанного сообщения действия обычно выполняются автоматически. Определение практических последствий коллизии хэш-значений требует детального анализа и оценки протокола.

5. Атаки с коллизиями и сертификаты доверенной стороны

Цифровой сертификат является частным случаем цифровой подписи. В общем случае здесь не возникает атак с безотзывностью на стороннее лицо из-за того, что сертификаты имеют определённый формат. Цифровые сертификаты часто применяются в протоколах Internet для управления ключами и проверки подлинности стороны, с которой происходит взаимодействие, возможно, до предоставления доступа к сетевым службам или проявления доверия к стороне с приватными данными, например, сведениями о кредитной карте. Поэтому важно, чтобы предоставляющая сторона могла верить, что сертификат корректно идентифицирует лицо или организацию, указанную в сертификате. Если атакующий может получить сертификаты для разных субъектов с использованием одного открытого ключа, жертву можно ввести в заблуждение, представившись другим лицом.

Атака с коллизией на сертификаты PKIX, описанная в начале 2005 г., основана на возможности злоумышленника создать два разных открытых ключа, которые привели бы одинаковым хэш-значениям тела сертификата. Чтобы такая атака сработала, злоумышленник должен предсказать содержимое и структуру сертификата до его выдачи, включая используемое в сертификате отождествление (identity), порядковый номер, а также даты начала и завершения срока действия сертификата. Фактическим результатом такой атаки стало бы то, что человек с неким отождествлением смог бы получить цифровой сертификат для некого открытого ключа, но при этом иметь возможность утверждать, что он получен для другого открытого ключа (с тем же отождествлением, действительным сроком действия и т. п.). Поскольку отождествление в двух сертификатах совпадает, в реальности, вероятно, не найти ситуаций, когда такие сертификаты были бы как-то полезны злоумышленнику. В крайнем случае кто-то мог бы заявить, что доверенная третья сторона допустила ошибку, выдав сертификат с одним отождествлением и порядковым номером для двух разных открытых ключей. В действительности это маловероятно.

Очень важно отметить, что атаки с коллизиями затрагивают лишь те части сертификатов, которые не содержат удобочитаемой информации, такие как открытые ключи. Атака, включающая получение сертификатов с одним понятным человеку отождествлением, который был бы полезен для второго понятного человеку отождествления потребует больше усилий, чем простая атака с коллизией.

5.1. Вероятность связанных с хэшированием атак на сертификаты PKIX

Если доверенная третья сторона, выдающая сертификаты PKIX, хочет избежать описанной выше атаки, она может сделать другие подписанные части сертификата достаточно случайными, чтобы нивелировать любые преимущества злоумышленника в результате такой атаки. Было предложено несколько идей:

• сделать часть серийного номера сертификата непредсказуемой для атакующего;

• добавить случайный компонент в отождествление (identity);

• сделать сроки действия непредсказуемыми для атакующего путём сдвига их вперёд или назад.

Любой из этих механизмов увеличит для злоумышленника объем работы, которую он должен выполнить, чтобы заставить эмитента выпустить уязвимый для атаки сертификат.

6. Будущие атаки и их влияние

В сообществе специалистов по безопасности нет единого мнения о дальнейших действиях и даже авторы этого документа разошлись в подходах.

Один из авторов (Bruce) полагает, что всем нужно начать переход на SHA-256 [SHA-256] уже сейчас из-за продемонстрированных слабостей MD5 и SHA-1. В АНБ (US National Security Agency или NSA) говорят: «Атаки всегда становятся лучше и никогда не становятся хуже.» Современные атаки с коллизиями против MD5 легко выполнить на одном компьютере, а атаки на SHA-1 сегодня уже близки к осуществимости и со временем будут только совершенствоваться. Переход на новый стандарт хэширования лучше выполнить до возникновения паники, нежели при её наличии. Так же, как все сменили SHA-0 на SHA-1 из-за какой-то неизвестной уязвимости, обнаруженной в недрах АНБ, необходимо перейти от SHA-1 к SHA-256 на основе недавних атак. В SHA-256 используется хэш размеров 256 битов. Это обеспечит гораздо больший запас безопасности при появлении новых атак. Между тем, продолжающиеся в криптографическом сообществе исследования в течение нескольких следующих лет должны показать дальнейшие усовершенствования алгоритмов хэширования и, возможно, предложить новый алгоритм безопасного хэширования.

Другой автор (Paul) считает, что это неразумно по двум причинам. Во-первых, атаки с коллизиями на современные протоколы не показали каких-либо значимых реальных последствий. Кроме того, пока неясно, какой из более строгих алгоритмов хэширования будет хорошим выбором на долгий срок. Переход на другой алгоритм ведёт к потере совместимости и путанице для обычных пользователей криптографии (конечно, при появлении практичных атак до достижения согласия в части свойств алгоритмов хэширования на основе шифров Пол согласится с переходом на SHA-256).

Оба автора согласны с тем, что следует проделать работу по обеспечению для всех протоколов Internet возможности использования алгоритмов хэширования с более длинными хэш-значениями. К счастью, большинство современных протоколов уже готовы к этому, а другие следует исправить в короткие сроки.

Авторы документа придерживаются схожих мнений по части разработки новых протоколов. Брюс считает, что нужно сразу использовать SHA-256, а Пол думает, что сначала можно применять SHA-1, пока новые протоколы не подвержены атакам с коллизиями. В любом новом протоколе должна быть возможность смены всех криптографических алгоритмов, а не только алгоритма хэширования.

7. Вопросы безопасности

Документ целиком посвящён безопасности Internet.

В документе предполагается, что единственными атаками на алгоритмы хэширования в протоколах Internet являются атаки с поиском коллизий. Были обнаружены некоторые значимые атаки с поиском прообраза [Preimaging-attack], но пока они не осуществимы на практике. Если будут найдены практичные атаки с поиском прообраза, это окажет очень существенное влияние на многие протоколы Internet. «Практичность» здесь понимается как возможность осуществления атаки злоумышленником за значимое время и значимые деньги. Атаки с поиском прообраза, требующие расходов в триллионы долларов и времени в десятки лет не считаются практичными. Практичной может считаться атака стоимостью в несколько тысяч долларов и занимающая несколько недель.

8. Литература

[MD5-attack] X. Wang, D. Feng, X. Lai, and H. Yu, «Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD», August 2004, <http://eprint.iacr.org/2004/199>.

[MD5-faster] Vlastimil Klima, «Finding MD5 Collisions — a Toy For a Notebook», March 2005, <http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf>.

[PKIX-MD5-construction] Arjen Lenstra and Benne de Weger, «On the possibility of constructing meaningful hash collisions for public keys», February 2005, <http://www.win.tue.nl/~bdeweger/CollidingCertificates/ddl-final.pdf>.

[Preimaging-attack] John Kelsey and Bruce Schneier, «Second Preimages on n-bit Hash Functions for Much Less than 2^n Work», November 2004, <http://eprint.iacr.org/2004/304>.

[RFC3174] Eastlake, D. and P. Jones, «US Secure Hash Algorithm 1 (SHA1)», RFC 3174, September 2001.

[RFC3280] Housley, R., Polk, W., Ford, W., and D. Solo, «Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile», RFC 3280, April 2002.

[SHA-1-attack] Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, «Collision Search Attacks on SHA1», February 2005, <http://theory.csail.mit.edu/~yiqun/shanote.pdf>.

[SHA-256] NIST, «Federal Information Processing Standards Publication (FIPS PUB) 180-2, Secure Hash Standard», August 2002.

Приложение A. Благодарности

Авторы благодарны сообществу IETF, особенно активным участникам почтовой конференции SAAG, за ценные замечания. Спасибо Eric Rescorla за материалы, послужившие основой первой версии, а также Arjen Lenstra и Benne de Weger за важные замечания к первой версии документа.

Адреса авторов

Paul Hoffman

VPN Consortium

EMail: paul.hoffman@vpnc.org

Bruce Schneier

Counterpane Internet Security

EMail: schneier@counterpane.com

---

Перевод на русский язык

Николай Малых

nmalykh@protokols.ru

---

Полное заявление авторских прав

Copyright (C) The IETF Trust (2005).

К этому документу применимы права, лицензии и ограничения, указанные в BCP 78, и, за исключением указанного там, авторы сохраняют свои права.

Этот документ и содержащаяся в нем информация представлены «как есть» и автор, организация, которую он/она представляет или которая выступает спонсором (если таковой имеется), Internet Society и IETF отказываются от каких-либо гарантий (явных или подразумеваемых), включая (но не ограничиваясь) любые гарантии того, что использование представленной здесь информации не будет нарушать чьих-либо прав, и любые предполагаемые гарантии коммерческого использования или применимости для тех или иных задач.

Интеллектуальная собственность

IETF не занимает какой-либо позиции в отношении действительности или объема каких-либо прав интеллектуальной собственности (Intellectual Property Rights или IPR) или иных прав, которые, как может быть заявлено, относятся к реализации или использованию описанной в этом документе технологии, или степени, в которой любая лицензия, по которой права могут или не могут быть доступны. Не заявляется также применение каких-либо усилий для определения таких прав. Сведения о процедурах IETF в отношении прав в документах RFC можно найти в BCP 78 и BCP 79.

Копии раскрытия IPR, предоставленные секретариату IETF, и любые гарантии доступности лицензий, а также результаты попыток получить общую лицензию или право на использование таких прав собственности разработчиками или пользователями этой спецификации, можно получить из сетевого репозитория IETF IPR по ссылке http://www.ietf.org/ipr.

IETF предлагает любой заинтересованной стороне обратить внимание на авторские права, патенты или использование патентов, а также иные права собственности, которые могут потребоваться для реализации этого стандарта. Информацию следует направлять в IETF по адресу ietf-ipr@ietf.org.

Подтверждение

Финансирование функций RFC Editor обеспечено Internet Society.

---