Инструменты разработчика · SHA хеш-калькулятор
Объяснение Меркла-Дамгорда: конструкция SHA-1 и SHA-2
· Фон
ша-256 криптография API-интерфейс браузера
Функция сжатия фиксированного размера не может сама по себе хэшировать произвольные входные данные. Меркле-Дамгорд связывает его блок за блоком; В этом посте объясняется конструкция, ее идея доказательства и недостатки, которые она несет.
Произвольный ввод, фиксированный вывод — проблема, которую каждая хеш-функция должна решить в первую очередь
Хэш-функция должна сопоставлять произвольный ввод с фиксированным выводом. Сообщение размером три байта и сообщение размером три мегабайта должны оба выдать ровно 256 bits выходных данных для SHA-256. Хэш должен быть детерминированным, чтобы одни и те же входные данные всегда давали один и тот же результат. Выходные данные должны выглядеть случайными; изменение одного бита ввода должно изменить примерно половину выходных битов.
На первый взгляд это противоречивые требования, поскольку один быстрый алгоритм не может обрабатывать сообщения произвольной длины и выдавать однородный вывод фиксированной ширины. Конструкция Меркла-Дамгорда решает эту проблему, многократно используя функцию сжатия фиксированного размера, подавая выходные данные каждого приложения на вход следующего. Эта конструкция используется SHA-1 и всеми SHA-2 (SHA-256, SHA-384 и SHA-512).
Функция сжатия — микшер фиксированного размера, который принимает состояние и блок и возвращает новое состояние.
Функция сжатия — это основной криптографический примитив, лежащий в основе хеша Меркла-Дамгорда. Он принимает состояние фиксированного размера, обычно 256 bits для SHA-256 или 512 bits для SHA-512, и входной блок фиксированного размера, обычно 512 bits для SHA-256 или 1024 bits для SHA-512. Функция сжатия смешивает их вместе, используя побитовые операции, повороты и поиск по таблицам, создавая новое состояние того же размера. Эта функция должна быть устойчивой к коллизиям: найти две разные пары (состояние, блок), которые выдают одинаковый результат, должно быть сложно.
Сама функция сжатия не является полноценной хеш-функцией — она не обрабатывает произвольную длину входных данных и даже не обрабатывает первый входной сигнал, у которого нет предыдущего состояния. Напротив, это строительный блок, вокруг которого строится более крупная конструкция. Функция сжатия — единственная криптографическая операция, которая выполняется повторно; все остальное — это бухгалтерия, которая связывает эту функцию с полным хешем.
Цепочка и вектор инициализации — как блоки переходят друг в друга из фиксированного начального состояния.
Вектор инициализации — это фиксированное начальное состояние, выбранное тщательно, чтобы избежать симметрии или недостатков. Для SHA-256 IV представляет собой восемь 32-битных слов, полученных из дробных частей квадратных корней первых восьми простых чисел. Эти значения произвольны, но детерминированы, поэтому каждая реализация дает один и тот же результат. Первый блок сообщения смешивается с IV с помощью функции сжатия, создавая новое состояние. Второй блок сообщения смешивается с этим состоянием, создавая еще одно новое состояние, и так далее для каждого блока сообщения.
Эта цепочка является важной частью: выходные данные одного блока зависят от всех предыдущих блоков, поэтому изменение любого бита любого предыдущего блока приводит к изменению всех последующих блоков. К моменту обработки последнего блока состояние содержит информацию о каждом бите входных данных. Набивка — это трюк, благодаря которому эта конструкция звучит. Сообщение не всегда делится на блоки равномерно. В конструкции Меркла-Дамгорда используется усиление MD: к сообщению добавляется один бит, затем добавляются нули, пока не останется почти полный блок, затем добавляется исходная длина сообщения.
Дополнение длиной сообщения — почему усиление MD — это то, что делает конструкцию надежной
Аргумент безопасности Меркла-Дамгорда гласит, что если функция сжатия устойчива к коллизиям, то и весь хэш устойчив к коллизиям. Доказательством является сокращение: если бы вы могли найти коллизию в хэше, вы могли бы извлечь коллизию и в функции сжатия, что противоречит предположению, что с функцией сжатия трудно столкнуться. Интуитивно понятно, что любое столкновение в хэше должно в конечном итоге привести к столкновению в одном из вызовов функции сжатия, поскольку состояние полностью переносится вперед.
Слабые стороны в системе Меркле-Дамгорда были обнаружены со временем, хотя основная конструкция является надежной. Расширение длины является одним из них: злоумышленник, который видит дайджест сообщения, может расширить сообщение и вычислить действительный дайджест для более длинного сообщения, ничего не зная о входных данных. Атаки второго прообраза — это другое: для данного сообщения найти другое сообщение с тем же хешем проще, чем должно быть для некоторых типов сообщений. Эти недостатки послужили причиной разработки SHA-3, в котором используется другой подход, называемый губчатой конструкцией.
Заполнение кодировкой длины разделяет дополненные сообщения; полное доказательство безопасности находится за пределами хранилища
Функция сжатия для SHA-256 принимает 256-битное состояние (восемь 32-битных слов) и 512-битный блок. В операции используется 64 раундов, каждый из которых смешивает состояние с константой и словом из блока. При микшировании используются побитовые операции: XOR, AND, NOT. Он использует вращения и сдвиги, которые перемещают биты без изменения того, какие биты установлены. Он использует поиск по таблицам, который обеспечивает нелинейное смешивание, которого невозможно достичь в одиночку XOR.
SHA-512 использует ту же конструкцию, что и SHA-256, но с 64-битными операциями вместо 32-битных операций. Состояние — 512 bits (восемь 64-битных слов), а размер блока — 1024 bits. Функция сжатия имеет 80 раундов вместо 64, а константы и поиск в таблицах отличаются. Для SHA-384 состояние и функция сжатия такие же, как для SHA-512, но выводятся только первые 384 bits конечного состояния. Последние 128 bits отбрасываются. Именно из-за этого усечения SHA-384 устойчив к увеличению длины.
Расширение длины является выверенной границей строительства; утверждения о мультиколлизии и SHA-3 мотивации опущены
Безопасность хеша Меркла-Дамгорда зависит от наличия нескольких свойств. Функция сжатия должна быть устойчивой к коллизиям, поэтому атаковать ее напрямую невозможно. Схема заполнения должна гарантировать, что разные сообщения создают разные дополненные формы, поэтому каждое столкновение в хеше должно включать столкновение функции сжатия. Размер блока и размер состояния должны быть достаточно большими, чтобы грубая сила была невозможна. Более широкое состояние расширяет общее пространство поиска, но в этой статье не прилагается количество операций или дата осуществимости без встроенного вывода и проверенного источника.
Если злоумышленник обнаружит слабость в функции сжатия или если квантовые компьютеры станут практичными и смогут выполнять поиск в неструктурированном пространстве за время sqrt(2^n) вместо времени 2^n, тогда границы безопасности уменьшатся. Слабость, которая побудила SHA-3, заключалась не в поломке функции сжатия, а в проблеме с увеличением длины и других структурных уязвимостях. Конструкция губки позволяет избежать этого, никогда не публикуя свое полное внутреннее состояние.
Чего это не касается — конкретные функции SHA-256, описанные в отдельном посте.
То, как конструкция Меркла-Дамгорда обрабатывает каждый входной размер, является практическим следствием ее конструкции. Разделите сообщение на 512-битные блоки, дополните последний блок, последовательно обработайте каждый блок с помощью функции сжатия и выведите окончательное состояние. Для однобайтового ввода при заполнении создается 512-битный блок (один байт сообщения, один бит заполнения, 447 bits из нулей и 64 bits для длины). Количество сжатий — это количество 512-битных блоков, пропорциональное длине сообщения.
Каждый дайджест, который создает хэш-калькулятор ToolAcre SHA, основан на этой конструкции. 64-символьный дайджест SHA-256 представляет собой окончательное 256-битное состояние, напечатанное в шестнадцатеричном формате. 128-символьный дайджест SHA-512 представляет собой окончательное 512-битное состояние, напечатанное в шестнадцатеричном формате. Дайджест SHA-384 из символов 96 является первым 384 bits конечного 512-битного состояния. Заполнение за кулисами гарантирует, что каждое возможное сообщение создаст ровно нужное количество блоков и правильную ширину дайджеста. Это стандартная конструкция Меркла-Дамгорда, работающая в браузере.
Вывод: за четырьмя алгоритмами стоит один и тот же скелет — каждый дайджест, который производит ToolAcre SHA хеш-калькулятор, основан на этой конструкции.
Понимание конструкции полезно для понимания того, почему дайджесты всегда имеют одинаковую ширину и почему изменение одного бита входных данных меняет весь дайджест. Свойство цепочки означает, что каждый бит входных данных влияет на каждый бит выходных данных посредством серии операций микширования. Однобитовое изменение в начале сообщения будет распространяться на все последующие сжатия, поэтому окончательный дайджест будет совершенно другим. Это свойство называется лавинным эффектом и является признаком надежной хэш-функции.
Конструкция Меркла-Дамгорда используется уже несколько десятилетий и составляет основу наиболее широко используемых хэш-функций. SHA-1 и SHA-2 построены на этой конструкции, и многие развернутые системы полагаются на их выходные данные. Конструкция скорее устоявшаяся, чем экспериментальная, но эта история не делает любое использование безопасным; Расширение длины — это одна документированная граница. Понимание этой конструкции помогает разработчикам понять, почему сохраняются определенные свойства безопасности и почему существуют определенные векторы атак.