Хеш-функции простыми словами
Когда вы скачиваете программу и сверяете контрольную сумму, входите по паролю, подписываете документ или добавляете блок в Bitcoin, работает хеш-функция. Она превращает любой объём данных в короткий отпечаток фиксированного размера — хеш, причём так, что этот процесс невозможно обратить или подделать. Идея проста, но требования к хорошей хеш-функции строги, и две из самых распространённых, MD5 и SHA-1, их не выдержали.
Отпечаток данных
Хеш-функция принимает входные данные любой длины и возвращает хеш фиксированной длины: 256 битов для SHA-256, записанных как 64 шестнадцатеричные цифры. Одни и те же данные всегда дают один и тот же хеш, поэтому хеш может представлять данные. Если у двух файлов одинаковый хеш SHA-256, можно быть уверенным, что они идентичны, а если хотя бы один бит скачанного файла повреждён, его хеш перестаёт совпадать с тем, который указал издатель. Поскольку возможных входов гораздо больше, чем хешей, каждому хешу должно соответствовать множество входов; хорошая хеш-функция просто делает невозможным найти хотя бы один из них.
Три обещания
Криптографическая хеш-функция даёт три обещания. Стойкость к нахождению прообраза: по данному хешу нельзя найти вход, который его даёт. Стойкость к нахождению второго прообраза: по данному входу нельзя найти другой вход с тем же хешем. Стойкость к коллизиям: нельзя найти никакие два входа с одинаковым хешем. Для идеальной хеш-функции с n битами лучшая атака — угадывание: около 2ⁿ попыток для прообраза и около 2ⁿᐟ² для коллизии. Хеш-функцию называют взломанной, когда кто-то находит способ, намного более быстрый.
Лавинный эффект
Измените один бит входа, и каждый бит хеша должен измениться с вероятностью одна вторая, независимо от остальных. Тогда небольшое изменение сообщения даёт хеш, который выглядит совершенно не связанным с прежним, и хеш ничего не выдаёт о том, какая часть входа изменилась. SHA-256 добивается этого, выполняя 64 раунда, которые циклически сдвигают, складывают и комбинируют восемь 32-битных слов его состояния, так что за несколько раундов каждый бит входа влияет на каждое слово. Простая сумма байтов, напротив, меняется ровно на столько, на сколько изменился вход, и потому выдаёт всё.
Как устроен SHA-256
Сначала SHA-256 дополняет сообщение: дописывает бит 1, нули и длину сообщения, пока общий размер не станет кратным 512 битам. Затем он обрабатывает сообщение блоками по 512 битов. Каждый блок растягивается до 64 слов, которые подмешиваются в состояние из восьми 32-битных слов; его начальные значения — фиксированные числа, взятые из квадратных корней первых восьми простых чисел. Состояние после последнего блока и есть хеш. Эту цепочечную схему, названную по именам её авторов (Ralph Merkle и Ivan Damgård), используют также MD5, SHA-1 и SHA-512; более новый SHA-3, стандартизированный в 2015 году, устроен иначе — по схеме, которая называется «губкой».
Атака «дней рождения»
В группе из 23 человек вероятность того, что у двоих совпадают дни рождения, чуть больше половины, хотя в году 365 дней, потому что важно число пар, а оно растёт как квадрат размера группы. Коллизии хеш-функции подчиняются тому же правилу. Среди 2ᵏ возможных хешей коллизию следует ожидать примерно после √(π/2 · 2ᵏ) случайных входов. Для 32 битов это около 82 000 входов — дело нескольких мгновений; для 128 битов это около 2⁶⁴, что под силу крупным вычислительным проектам. Поэтому 128 битов MD5 никогда не были щедрым запасом, и поэтому SHA-256 удваивает длину, чтобы обеспечить стойкость в 128 битов.
MD5 и SHA-1: взломаны
Ron Rivest разработал MD5 в 1991 году, а NSA — SHA-1, опубликованный в 1995 году. В 2004 году Xiaoyun Wang и её коллеги показали, как быстро создавать коллизии MD5, а в 2008 году исследователи использовали их, чтобы подделать сертификат, которому доверяли веб-браузеры. Шпионская программа Flame 2012 года использовала коллизию MD5, чтобы выдать себя за обновление Microsoft. SHA-1 пал в 2017 году, когда Google и CWI Amsterdam опубликовали два разных PDF-файла с одинаковым хешем SHA-1, потратив около 2⁶³ вычислений. Оба алгоритма по-прежнему годятся для обнаружения случайных ошибок, но не для того, что может стать целью атакующего.
Где используются хеши
Цифровая подпись подписывает хеш документа, а не сам документ. Git называет каждый файл и коммит по его хешу, а майнеры Bitcoin ищут заголовки блоков, двойной хеш SHA-256 которых начинается с длинной серии нулей. Сайты никогда не должны хранить пароли — только их хеши; но поскольку люди выбирают короткие пароли, такой хеш должен быть медленным и с солью, вычисляемым методами вроде bcrypt, scrypt или Argon2, чтобы угадывание стало дорогим. Контрольные суммы вроде CRC-32, которые используются в файлах ZIP, изображениях PNG и сетях Ethernet, тоже являются хешами, но созданы для борьбы с помехами, а не с атакующими.
Попробуйте сами
Откройте песочницу хеш-функций, чтобы хешировать собственный текст с помощью SHA-256, SHA-512, SHA-1, MD5, CRC-32 и игрушечной суммы байтов. Измените один символ и посчитайте изменившиеся биты, запустите тест лавинного эффекта на тысяче изменений одного бита, чтобы увидеть колоколообразную кривую вокруг половины хеша, и найдите настоящие коллизии по первым 8–32 битам хеша, чтобы увидеть атаку «дней рождения» в действии.
Часто задаваемые вопросы
Хеширование — это то же самое, что шифрование?
Нет. Шифрование задумано так, чтобы его мог обратить тот, у кого есть ключ; у хеширования нет ключа, и обратить его не может никто. Шифрование сохраняет сообщение в тайне, а хеш лишь даёт отпечаток, позволяющий проверить сообщение, которое у вас уже есть.
Сколько времени заняло бы нахождение коллизии SHA-256?
При атаке «дней рождения» — около 2¹²⁸ вычислений хеша, а это число из 39 цифр. Даже если бы все компьютеры на Земле не занимались ничем другим, это заняло бы неизмеримо больше времени, чем возраст Вселенной. Никакого короткого пути не известно.
Почему два хеша одного и того же текста никогда не различаются?
Хеш-функция детерминирована: в ней нет ни случайности, ни ключа, поэтому одни и те же байты всегда дают один и тот же хеш. А вот незаметные глазу различия, например пробел в конце, другой символ конца строки или другая форма Unicode для буквы с диакритикой, дают другой хеш.
Что такое соль?
Случайное значение, которое хранится рядом с хешем пароля и подмешивается в него. Тогда два пользователя с одинаковым паролем получают разные хеши, и атакующий не может использовать одну заранее вычисленную таблицу распространённых паролей для всех учётных записей.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Открыть песочницу хеш-функций