В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 6. Функции хэширования даже функции SHA еще не были проанализированы так, как нужно, но они по крайней мере были разработаны Управлением национальной безопасности (National Security Agency — NSA) и стандартизированы NIST 2 . Практически все современные функции хэширования (и все функции, ко- торые рассматриваются в этой главе) являются итеративными. Итеративные функции хэширования разбивают входное значение на последовательность блоков фиксированного размера m 1 , . . . , m k , используя некоторое правило дополнения для заполнения последнего блока. Затем блоки сообщения об- рабатываются по порядку с помощью функции сжатия h 0 и промежуточных состояний фиксированного размера. Этот процесс начинается с фиксирован- ного значения H 0 и определяется как H i = h 0 ( H i − 1 , m i ) . Последнее значение H k и будет результатом функции хэширования. Итеративный алгоритм хэширования имеет существенные практические преимущества. Во-первых, его намного легче определить и реализовать по сравнению с функциями, которые напрямую работают со значениями пере- менной длины. Во-вторых, итеративная структура позволяет начинать вы- числение хэш-кода сообщения, как только у нас появится хотя бы часть этого сообщения. Благодаря этому в приложениях, работающих с поточными дан- ными, хэшировать сообщение можно прямо “на лету”, не сохраняя данные в буфере. Как и при рассмотрении блочных шифров, не будем вдаваться в дета- ли работы функций хэширования. Разработчики криптографических систем смогут найти полные спецификации функций хэширования в указанной нами литературе или же в Internet. Для всех остальных полные спецификации — это ненужные подробности, которые лишь отвлекают читателя от основной идеи книги. 6.2.1 MD5 Разработанная Роном Райвестом (Ron Rivest) [81] 128-битовая функция хэширования MD5 является дальнейшим усовершенствованием функции MD4 [78] и обладает дополнительной стойкостью к атакам 3 . Согласно алгоритму MD5 исходное сообщение разбивается на блоки по 512 бит. Последний блок дополняется до нужной длины, после чего к нему дописывается длина исходного сообщения в битах. Функция MD5 использу- ет 128-битовое промежуточное состояние, которое разбивается на четыре 32- битовых слова. Функция сжатия h 0 состоит из четырех раундов, в каждом 2 Что бы вы ни думали об Управлении национальной безопасности, его наработки в об- ласти криптографии довольно неплохи. 3 Хотя функция хэширования MD4 очень быстрая, она довольно легко взламывается [24], поэтому не стоит ее использовать. 6.2. Современные функции хэширования 109 из которых выполняется перемешивание блока сообщения и промежуточного состояния. Перемешивание представляет собой комбинацию операции сложе- ния, операций XOR, AND, OR и операций циклического сдвига битов над 32- битовыми словами. (Более подробно это рассматривается в [81].) В каждом раунде целый блок сообщения перемешивается с промежуточным состояни- ем, поэтому каждое слово сообщения фактически используется четыре раза. После четырех раундов функции h 0 входное промежуточное состояние и ре- зультат складываются для получения выходного значения функции h 0 . Описанный алгоритм оперирования 32-битовыми словами весьма эффек- тивен в системах с 32-разрядной архитектурой. Данный подход был впервые применен в алгоритме MD4 и сейчас широко используется во многих крип- тографических функциях. В основе итеративного подхода к построению функций хэширования ле- жит следующая идея: если функция h 0 обладает сопротивляемостью колли- зиям, тогда функция хэширования h , построенная на основе h 0 , тоже будет обладать сопротивляемостью коллизиям. В конце концов, любая коллизия в h может произойти только при возникновении коллизии в h 0 . Недостатком алгоритма MD5 является то, что у его функции сжатия h 0 были выявлены коллизии [20]. На данный момент известных атак на саму функцию MD5 еще нет, однако наличие коллизий в функции сжатия делает использование MD5 потенциально небезопасным. Для большинства областей применения 128-битового размера хэш-кода MD5 явно недостаточно. Используя парадокс задачи о днях рождения, можно найти реальную коллизию для функции MD5 примерно за 2 64 оцениваний функции хэширования, что совершенно не подходит для современных систем. Поэтому мы не советуем использовать MD5. 6.2.2 SHA-1 Защищенный алгоритм хэширования (Secure Hash Algorithm — SHA) раз- работан Управлением национальной безопасности США (National Security Agency — NSA) и стандартизирован институтом NIST [70]. Первая версия этого алгоритма называлась просто SHA (теперь ее часто называют SHA-0) и имела весьма существенный недостаток. В NSA обнаружили этот недо- статок и разработали метод его исправления. Это было опубликовано NIST в качестве улучшенной версии алгоритма SHA под названием SHA-1. Тем не менее NIST не привел никаких сведений о найденном недостатке. Через три года Шабо (Chabaud) и Жу (Joux) опубликовали статью о слабом месте алго- ритма SHA-0 [16]. Эта ошибка была исправлена в алгоритме SHA-1, поэтому можно предположить, что речь идет именно о том загадочном недостатке, который был обнаружен NSA. |