Кто взломал алгоритм SHA1 (и что это значит для Bitcoin)?

Мир криптографии был переполнен новостями о том, что исследователи из Google и CWI Amsterdam добились успеха всоздание «хэш-коллизии»для двух разных документов с использованием алгоритма шифрования SHA1, что делает алгоритм «взломанным» согласно криптографическим стандартам.

Но что это означает простым языком и каковы последствия для сети Bitcoin ?

Коллизии хэшей

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

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

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

Учитывая математические законы, управляющие хеш-функциями, для некоторых значений входных данных неизбежно возникновение коллизий хеш-функций (поскольку диапазон данных, которые можно поместить в хеш-функцию, потенциально бесконечен, но длина выходных данных фиксирована).

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

Значимость результатов команды Google/CWI заключается в том, что им удалось создать коллизию хешей, найдя гораздо более эффективный метод — фактически в 100 000 раз более эффективный — чем простое угадывание всех возможных значений данных.

Эффективность этого метода означает, что SHA1 теперь официально взломан. (Эти результаты более подробно описаны наSHAttered.io(с пояснением затронутых систем.)

Премия SHA1

23 февраля внимательный пользователь Reddit на странице /r/ Bitcoin опубликовал пост, в котором указал на то, что давняя награда за обнаружение именно такой коллизии SHA1 теперь заявлено.

Первоначально вознаграждение, направленное на обнаружение уязвимостей в алгоритме, было объявлено исследователем криптографии Питером Тоддом впост на Bitcoin Talkфоруме в сентябре 2013 года, но оставался невостребованным до этой недели.

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

Помимо Тодда, другие Авторы также внесли пожертвования в баунти-фонд, собрав в общей сложности 2,5 биткоина.

По словам исследователя, время подачи заявления (немного позже публикации атаки столкновений) позволяет предположить, что вознаграждение получило не кто-то из первоначальных исследователей, а третья сторона, прочитавшая исследование команды Google и использовавшая его результаты.

Тодд сказал:

«Если бы это были сами авторы, мы бы ожидали, что вознаграждение будет затребовано непосредственно перед публикацией объявления. Но на самом деле этого T произошло».

Последствия для Bitcoin

Важно подчеркнуть, что криптография, лежащая в основе сети Bitcoin и использующая более безопасный алгоритм SHA256, не затронута напрямую этим Истории.

Однако, помимо обогащения получателя таинственного вознаграждения, уязвимость коллизии SHA1 действительно вызывает беспокойство у сообщества разработчиков Bitcoin , поскольку его система контроля версий Git использует SHA1 для генерации хэш-дайджеста для коммитов.

«Последствия T в том, что нам придется немедленно прекратить использование Git», — сказал Тодд, — «но это повысит важность проверки работы других людей, поскольку третья сторона может попытаться внедрить вредоносный коммит».

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

Помимо SHA1, Тодд назначил похожие вознаграждения заЗРЕЛЫЙ MD160 и хэш-функции SHA256 — обе они необходимы для целостности стандарта Bitcoin , и поэтому их компрометация может иметь катастрофические последствия для сети.

Тодд подвел итог:

«Если вы претендуете на эту награду, вам лучше QUICK потратить свои биткоины».

Двоичный кодизображение через Shutterstock