Инструменты разработчика · SHA хеш-калькулятор
Эффект лавины: почему один измененный символ перезаписывает хеш SHA
· Как это работает
ша-256 криптография безопасность проверка
Измените одну букву, и примерно половина выходных бит изменится. В этом посте объясняется свойство лавины, почему оно важно для обнаружения взлома и как раунды SHA-2 достигают этого.
Ожидание небольшого изменения хеша — интуиция большинства людей и почему дизайн намеренно ее нарушает
Большинство людей ожидают, что одинаковые входные данные приведут к аналогичным результатам. Измените один символ в файле, и дайджест должен немного измениться. Вместо этого криптографические хэши предназначены для обратного: изменение одного бита во входных данных должно непредсказуемо перевернуть примерно половину выходных битов. Это свойство называется лавинным эффектом, и оно является преднамеренным. Конструкция служит определенной цели: обнаружению несанкционированного доступа.
Эффект лавины — вот почему «почти совпадение» не является концепцией в мире хеширования. Хэш точно совпадает или нет. Не существует понятия «достаточно близко». Это свойство делает хеширование полезным для проверки целостности и адресации контента, а также делает слабые алгоритмы хеширования непригодными для использования в целях безопасности.
Лавина означает широкое распространение продукции; в этой статье не делается никаких необоснованных утверждений о точной вероятности
Формально лавинный эффект означает, что для двух входных данных, которые отличаются на один бит, выходные дайджесты должны отличаться примерно на 50% своих битов. Для SHA-256 (256 bits выхода) изменение одного входного бита должно примерно перевернуть 128 выходных битов. Эффект неточный; это статистическое свойство. Но это сильная сторона: на практике каждый бит входных данных тщательно смешивается с каждым битом выходных данных.
Почему примерно половина? Потому что по-настоящему случайный результат будет отличаться от другого случайного результата в среднем ровно половиной своих битов (согласно принципу группировки и базовой статистике). Хорошая хэш-функция аппроксимирует случайность; он выдает результаты, которые не имеют видимой закономерности. В среднем половина битов переворачивается и является признаком случайности. Если хэш перевернул только 10% битов, злоумышленник сможет найти шаблоны и использовать их.
Зачем это нужно обнаружению несанкционированного доступа — небольшие изменения в документе не должны давать почти идентичный хэш, который можно было бы принять при беглом взгляде.
Обнаружение несанкционированного доступа основано на лавинном механизме. Если вы загрузите файл и вычислите его SHA-256, ожидаемый дайджест будет ba7816... (в качестве примера). Злоумышленник модифицирует файл, изменяя один байт. Новый дайджест меняется с ba7816... на что-то вроде 3d4e92... (совершенно другое). Когда вы сверяете файл с ожидаемым дайджестом, несоответствие становится немедленным и полным. Здесь нет места неправильному толкованию: файл был подделан.
Без лавины злоумышленник мог бы изменить байт, и дайджест мог бы сместиться лишь незначительно, до ba7817... (отличается одна шестнадцатеричная цифра). Случайное сравнение может не заметить разницу. Злоумышленник может даже искать входные данные, которые создают дайджест, начинающийся с ba78, утверждая, что файл является подлинным. Avalanche делает это непомерно дорогим: чтобы найти хотя бы два входа, где дайджесты начинаются с одних и тех же четырех шестнадцатеричных цифр, требуется больше работы, чем позволяет конструкция.
Как распространяются изменения в раундах — вращения, сложения и нелинейные функции, несущие влияние одного бита на все состояние
Раунды в SHA-256 (и раунды в SHA-512) предназначены для распространения изменений. В каждом раунде данные смешиваются с использованием нелинейных функций (выбор, большинство) и вращений. Однобитовое изменение входных данных попадает в расписание сообщений и распространяется по циклам. Вращения сдвигают позиции битов. Нелинейные функции скрывают влияние бита: изменение бита управления в операции выбора может перевернуть любой из выходных битов, в зависимости от выбираемых данных.
Начальные хеш-константы, константы расписания сообщений, объемы ротации и количество раундов были выбраны так, чтобы максимизировать лавинный эффект. Эти цифры не произвольны; они взяты из спецификации SHA-2 и прошли тщательный криптоанализ. Любое изменение констант или количества раундов приведет к использованию другого алгоритма (вероятно, более слабого).
Рабочий пример — хеширование двух входных данных, которые отличаются на один символ, и побитовое сравнение дайджестов.
Тестировать лавину несложно. Хэшируйте входные данные abc и запишите дайджест. Затем введите хэш abc и пробел или замените один символ другим: abd. Сравните шестнадцатеричные результаты. Для SHA-256 примерно половина шестнадцатеричных цифр 64 будет отличаться. Посчитайте их. Тестовый вектор из поста ToolAcre: abc создает ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad. Пустая строка создает e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855. Эти дайджесты не имеют общих шестнадцатеричных цифр.
Попробуйте это на калькуляторе ToolAcre с любым вводом. Перефразируйте предложение. Затем измените одну букву и еще раз хэш. Посчитайте разные шестнадцатеричные цифры. Вы обнаружите, что примерно половина (в большинстве случаев 32 из 64) различаются. Это лавинный эффект в действии. Это свойство конструкции алгоритма, а не совпадение.
Avalanche не обеспечивает поиск сходства и сам по себе не дает количественной оценки сопротивления коллизиям.
Avalanche не осуществляет поиск по сходству или приблизительное сопоставление. Если у вас есть дайджест ba7816... и вы хотите найти похожий дайджест, у вас нет ярлыка. Вы должны угадать или перебрать входные данные-кандидаты, хешировать каждый из них и проверить точное совпадение. Лавинный эффект приводит к тому, что каждое предположение с одинаковой вероятностью приведет к одинаковому или совершенно другому результату. Некоторые алгоритмы хеширования (называемые хешированием с учетом местоположения) предназначены для сохранения сходства; они полезны для обнаружения почти дубликатов и кластеризации, но не являются криптографическими хэшами.
Avalanche также не защищает от целенаправленного поиска столкновений. Криптоаналитик по-прежнему может искать два разных входа, которые дают один и тот же дайджест, но пространство поиска огромно. Решительный поиск столкновений отличается от визуальной диффузии. В этой статье не приводятся цифры, связанные с днем рождения, или график аппаратного обеспечения, поскольку здесь они не получены. Граница, которую можно защитить, заключается в том, что лавина сама по себе не доказывает и не дает количественной оценки сопротивления столкновению.
Вывод: никаких промахов — попробуйте односимвольный эксперимент в хеш-калькуляторе ToolAcre SHA и посмотрите, как изменится весь дайджест.
Хэш-калькулятор ToolAcre SHA запускает алгоритмы SHA через реализацию Web Crypto в браузере. Вы можете использовать его для проверки лавины самостоятельно. Каждый бит точности алгоритма учитывается на выходе, а реализация Web Crypto проверяется и поддерживается поставщиком браузера. Вы видите настоящий алгоритм, работающий на реальных входных данных. Противоречивое свойство, заключающееся в том, что одно изменение символа перезаписывает весь дайджест, не является недостатком; это функция, благодаря которой хеширование работает.
Когда вы используете хэш для проверки целостности, вы полагаетесь на лавину. Когда вы используете его для адресации контента (например, дайджесты образов контейнеров), вы зависите от свойства, заключающегося в том, что небольшие изменения создают совершенно разные дайджесты. Когда вы используете его в цифровой подписи (где подпись вычисляется по хешу сообщения), лавинный эффект гарантирует, что подделка сообщения приведет к заметным изменениям. Свойство является основой безопасности на основе хеша.