id: Гость   вход   регистрация
текущее время 04:45 18/11/2019
Владелец: SATtva (создано 14/09/2006 22:50), редакция от 07/09/2006 21:54 (автор: SATtva) Печать
Категории: криптография, софт, pgp, алгоритмы, хэширование, сайт проекта, статьи
создать
просмотр
редакции
ссылки

Хэш-функции

MD5


Это пятый алгоритм из серии алгоритмов Рона Райвеста Message Digest. MD5 построен вокруг функции сжатия, принимающей ввод определенной фиксированной длины и возвращающей вывод меньшей фиксированной длины. Другими членами семейства Message Digest являются MD2 (адаптированный для работы на 8-битовых процессорах) и MD4 (алгоритм, созданный на краю безопасности. MD5 только чуть медленнее, но значительно надежней. MD4 взломан). MD5 определен в RFC 1321 [17]. Он производит 128-битовый хэш.


Чтобы схэшировать определенный ввод, он дополняется нулями, чтобы сделать его на 64 бита короче кратного 512 битам. Затем показатель длины ввода добавляется к строке ввода в виде 64-битового числа. Четыре 32-битовых переменных A, B, C и D инициализируются специальными закрепленными в стандарте числами, после чего каждый 512-битовый блок ввода вместе с текущими значениями A, B, C и D поступает на вход функции сжатия, а ее выход – 128-битовый блок – вновь делится на четыре 32-битовых числа, которые прибавляются, соотствественно, к A, B, C и D. Если обработаны все блоки ввода, A, B, C и D образуют выход алгоритма – хэш.


В параграфе о длинах ключей разъяснялось, почему для хэш-функции недостаточно 128 бит, чтобы потивостоять описанной ниже атаке на основе парадокса дней рождений. Для MD5 дело обстоит еще хуже: криптоаналитики произвели особые атаки, демонстрирующие недостатки в функции сжатия этого алгоритма.


Райвест намеревался создать для MD5 коллизионно-устойчивую функцию сжатия, но потерпел неудачу. Гансу Доббертину удалось получить коллизию в функции сжатия (см. [5] ), что заняло 10 часов вычислений на одном компьютере Pentium 90. Коллизия в функции сжатия – это комбинация таких (ABCD,x,y), что
сжатие(ABCD,x) = сжатие(ABCD,y)
(3.7)

Это не коллизия в MD5, как таковом, поскольку здесь отсутствует префикс документа, который бы привел ABCD к заданному значению. Таким образом, для PGP подобная коллизия не представляет непосредственной угрозы.


Краткий доклад, где была представлена эта коллизия, не содержал информации о том, каким образом она была получена. Полагаю, это было грамотное применение каких-то специфических для MD5 методик. Тем не менее, мне бы хотелось отметить, что найти коллизию в функции сжатия предсказуемо проще, чем найти ее в полном алгоритме хэширования.


Если вам нужно найти один документ с определенным хэшем, вероятность такого события составляет 2–128, поскольку вам доступен выбор лишь одной переменной – документа. В среднем, это потребует 2127 вычислений.


Если же вы ищите два документа x и y, производящих определенный хэш, то у вас есть две переменные (x и y), и, даже просто начав проверять хэш-значения произвольных документов, вы найдете такую пару всего за 264 шагов, поскольку теперь во всем 128-битовом пространстве поиска мы имеем две случайно размещенные точки. Такая операция намного быстрее.


Чтобы найти коллизию в функции сжатия, мы располагаем тремя переменными: x, y и значением ABCD. Если, и это важное "если", вам известен какой-то способ применить дополнительную свободу от обладания ABCD, вам, по-видимому, потребуется лишь 2128/3 = 243 вычислений. Если процессор Pentium может производить миллион сжатий в секунду, то за 10 часов можно выполнить 238 вычислений. Две эти цифры отличаются в 32 раза.


Приведенные рассуждения весьма гипотетичны и не дают вам подсказки, как производить поиск. Я только хотел обратить внимание на то, что нахождение коллизии подобной той, которую обнаружил Доббертин, ни для кого не является сюрпризом. Учитывая скорости современных компьютеров, 128-битовые свертки просто слишком малы. Сейчас использование MD5 является нерекомендуемым, а его наличие становится слабым местом PGP. Хотя практически алгоритм еще не взломали, в скором будущем этого можно ожидать. 1

SHA


Secure Hash Algorithm был разработан NIST и АНБ. Как и у MD5, его дизайн основан на MD4. SHA производит 160-битовую свертку. Алгоритм применяется в составе стандарта DSS, а его спецификации закреплены в Стандарте безопасного алгоритма хэширования, FIPS PUB 180 [16].


Повсеместно используемый вариант SHA называется SHA-1. SHA-1 – это модифицированная версия оригинального SHA, где было изменено несколько деталей, вероятно, с целью его усиления против определенных атак. PGP также использует эту обновленную версию – SHA-1.

RIPEMD-160


Эта 160-битовая хэш-функция, созданная Гансом Доббертином, Антуном Боссельерсом и Бартом Пренилом, предполагалась в качестве замены для 128-битового алгоритма хэширования RIPEMD. RIPE – это аббревиатура для европейского проекта RACE Integrity Primitives Evaluation (Оценка стойкости примитивов RACE), проходившего в 1988-1992 годах. RIPEMD-160 был опубликован в [4].

Безопасность

Атака на основе парадокса дней рождений

Лучшая атака, которая действует против каждой хэш-функции, называется атакой на основе парадокса дней рождений. Она основана на занимательном факте, что, в среднем, достаточно лишь группы из 23 человек, чтобы найти пару людей с общим днем рождения. В сценарии этой атаки Ева хочет получить подпись Боба под документом, который бы он ни за что не подписал. Чтобы добиться этого, она дает Бобу заверить хэш-значение невинного документа. Затем она распространяет его электронную подпись вместе с поддельным документом, и если он имеет тот же хэш, что и подписанный оригинал, это убеждает других людей, что Боб действительно заверил зловредный документ.


Ева создает целую уйму практически одинаковых невинных документов и сохраняет их хэши. Документы различаются в самых незначительных деталях: лишних пробелах, небольших изменениях слов, орфографических ошибках и т.д. Также она создает подобное множество зловредных документов и проверяет, чей хэш совпадет с одним из сохраненных хэш-значений невинных документов. Для каждого из этих множеств она сохраняет L = 2Sreal(H)/2 хэшей. Теперь черед за эффектом дней рождений. Вероятность того, что конкретное зловредное сообщение не коллизирует с любым невинным составляет (L2-L) / L2 = (L-1) / L. Довольно много. Однако, зловредные сообщения генерировались независимо друг от друга, так что вероятность, что ни одно зловредное сообщение не коллизирует с нормальным составляет (L-1)L / L ≈ 0.36. 2 Таким образом, весьма вероятно, что Ева получит коллизию. Если нет, она может попытаться еще. Эта атака демонстрирует, что Seff(H) ≤ Sreal(H)/2.


Исходя из определения о 80 битах достаточной безопасности, а также из атаки на основе парадокса дней рождений, длина свертки должна быть минимум 160 бит. И RIPEMD-160, и SHA-1 удовлетворяют этому требованию. На сегодня неизвестно особых снижающих их стойкость атак, поэтому обе хэш-функции считаются безопасными. В действительности, они обе довольно похожи, так что я не могу сказать, которая из них лучше.


Назад | Дальше



1 Алгоритм MD5 был взломан в августе 2004 года и более не применяется в OpenPGP для практических целей. См. сноску к параграфу "Длина ключа", – прим. пер.


2 Чтобы убедиться в этом, проверьте несколько значений, например, L = 100, 200, ...


 
Комментариев нет [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3