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

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

Хэш столкновения

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

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

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

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

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

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

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

Щедрость SHA1

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

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

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

В дополнение к Тодду, другие участники также внесли пожертвования в благотворительный фонд, собрав в общей сложности 2,5 биткойна.

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

Тодд сказал:

«Если бы это были сами авторы, мы бы ожидали, что награда будет востребована непосредственно перед опубликованием объявления. Как это случилось, это было не так.

Последствия для биткойнов

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

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

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

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

Как и SHA1, Тодд установил аналогичные преимущества в хеш-функциях RIPE MD160 и SHA256, которые необходимы для обеспечения целостности стандарта биткойнов, и поэтому могут нанести ущерб сети в случае компрометации.

Тодд пришел к выводу:

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