- A
- Хеш
- B
- Хеш
| Хеш-функция | Биты | Хеш (A) | Статус |
|---|
Тест лавинного эффекта
Атака «дней рождения»
Песочница хеш-функций
Хеш-функция превращает любой текст, от одной буквы до целой книги, в короткий отпечаток фиксированного размера. Измените один символ, и хорошая хеш-функция выдаст совершенно другой отпечаток; при этом никто не может обратить её или найти два текста с одинаковым отпечатком. Введите два сообщения, отличающиеся одним символом, и сравните их хеши бит за битом, посмотрите на один и тот же текст в шести хеш-функциях — от SHA-256 до игрушечной контрольной суммы, измерьте лавинный эффект на тысяче изменений и сами найдите коллизию укороченного хеша. Введите сообщение A и выберите хеш-функцию. Сообщение B сначала совпадает с A, но с одним изменённым символом: сравните два хеша, каждый изменившийся бит отмечен на сетке. Нажмите «Изменить один символ», чтобы внести ещё одно небольшое изменение, или введите B сами. Таблица показывает A во всех хеш-функциях; нажмите на строку, чтобы выбрать функцию. Нажмите «Запустить тест», чтобы тысячу раз изменить один бит входа и увидеть, сколько битов хеша меняется, и «Найти коллизию», чтобы увидеть, как быстро у двух сообщений совпадут первые биты хешей.
Как это работает
- Введите сообщение A и выберите хеш-функцию. Сообщение B — это A с одним изменённым символом; их хеши показаны с отметкой каждой изменённой цифры и каждого изменившегося бита.
- Нажмите «Изменить один символ», чтобы внести ещё одно небольшое изменение, или отредактируйте B сами, и нажмите на строку таблицы, чтобы переключаться между SHA-256, SHA-512, SHA-1, MD5, CRC-32 и игрушечной суммой.
- Нажмите «Запустить тест», чтобы измерить лавинный эффект, и «Найти коллизию», чтобы увидеть атаку «дней рождения» на первые 8–32 бита хеша.
Какой должна быть хорошая хеш-функция
Криптографическая хеш-функция должна быстро вычисляться и каждый раз давать один и тот же хеш для одних и тех же данных. Кроме того, она должна быть односторонней: по хешу нельзя восстановить входные данные иначе, чем угадыванием. Она должна быть стойкой к коллизиям: никто не может найти два входа с одинаковым хешем. И она должна проявлять лавинный эффект: измените один бит входа, и каждый бит хеша изменится с вероятностью одна вторая, так что небольшое изменение даёт хеш, который выглядит никак не связанным с прежним. В SHA-256 замена последней буквы предложения обычно меняет около 128 из 256 битов.
Почему важен парадокс дней рождения
Если в комнате 23 человека, то скорее да, чем нет, у двоих из них совпадают дни рождения, хотя дней в году 365. Хеши ведут себя так же. При k битах существует 2ᵏ возможных значений, но у двух случайных сообщений хеш совпадёт уже примерно через √(2ᵏ) попыток — квадратный корень из этого числа. 32-битный хеш сдаётся примерно после 80 000 сообщений, здесь это доля секунды. Поэтому хешу нужно вдвое больше битов, чем уровень защиты, который он должен обеспечивать: SHA-256 даёт 128-битную защиту от коллизий, а MD5 со своими 128 битами и слабостями конструкции взломан.
Часто задаваемые вопросы
Почему один символ меняет весь хеш?
Потому что хеш-функция многократно перемешивает каждый бит входа с каждым битом выхода. SHA-256 выполняет над своим состоянием 64 раунда сдвигов, сложений и логических операций; через несколько раундов изменение одного бита входа распространяется на всё состояние. Результат выглядит случайным: в среднем меняется половина битов хеша, и какие именно — предсказать нельзя. В игрушечной сумме в приложении такого перемешивания нет, поэтому одна изменённая буква меняет в ней лишь один-два бита.
Можно ли обратить хеш?
Нет. Хеш имеет фиксированный размер, поэтому каждому хешу соответствует бесчисленное множество входов, а хорошая хеш-функция не даёт никаких подсказок, какой из них был использован. Единственный путь назад — угадывать входы и сравнивать хеши. Это работает для коротких или распространённых данных, поэтому пароли хранят с помощью медленной хеш-функции для паролей с солью, такой как bcrypt или Argon2, а не простого SHA-256.
Почему MD5 и SHA-1 называют взломанными?
Потому что исследователи нашли способы создавать коллизии — два разных входа с одинаковым хешем — гораздо быстрее, чем атакой «дней рождения». Для MD5 это показали в 2004 году, и сейчас это можно сделать за секунды на ноутбуке; для SHA-1 Google и CWI Amsterdam в 2017 году опубликовали два разных PDF-файла с одинаковым хешем. Ни один из этих алгоритмов больше не следует использовать для подписей и сертификатов. У SHA-256 и SHA-512 известных слабостей такого рода нет.
Чем контрольная сумма отличается от криптографического хеша?
Контрольная сумма, например CRC-32, создана для выявления случайных ошибок, таких как изменившийся бит в скачанном файле или на диске, и справляется с этим очень хорошо. Но её легко вычислить в обратную сторону, поэтому любой может изменить файл и подогнать его так, чтобы контрольная сумма осталась прежней. Криптографическая хеш-функция создана так, чтобы противостоять и намеренному атакующему.
Отправляется ли мой текст куда-нибудь?
Нет. Каждый хеш вычисляется в вашем браузере собственным кодом приложения, а ваши сообщения остаются в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор