Здравствуйте, eao197, Вы писали:
.>>ту же подпись. И никакой софт не обнаружит подлог.
E>Сначала хорошо было бы иметь софт, который создаст этот второй документ с осмысленным содержимым и точно таким же хэшем. Если это вообще возможно.
Это очень даже возможно. Смотреть например практически-осуществимую атаку на X.509 сертификаты ([1], [2]). Есть варианты атак на изменение архивов (zip/gzip), которые снабжаются подписью с md5 (это самые первые варианты практических атак, использовали вообще 1 опубликованную коллизию MD5).
P.S. В первой ссылке кстати аннонсирована атака и на SHA-1.
Здравствуйте, Left2, Вы писали:
L>Я вот тоже на эту тему думал. Не знаю насчёт SHA-1, но как минимум MD5 — это алгоритм работы над потоком байт. То бишь, есть текущее(начальное) состояние и поток байт(с случае MD5 ЕМНИП это 64-разрядные слова), которые изменяют это состояниие. Так вот, если тебе нужно модифицировать документ — ты меняешь его состояние, а потом задача сводится к тому что нужно дописать какие-то данные дабы хеш остался тем же. Т.о., получается что мы решаем задачу No1 — поиск коллизии хеш-функции (правда, начальное состояние будет другим). Поправьте меня если не прав.
MD4/MD5/SHA-0/SHA-1/SHA-2 — это всё одно семейство и отличаются они только сжимающей функцией и начальными векторами.
Все эти алгоритмы предусматривают такой вариант, что если документы имеют разную длину, то их хэши наверняка будут разными — благодаря тому, что в конец сообщения перед хэшированием дописывается паддинг с длиной сообщения (называется трюк MD-усиление).
Само хэширование выполняется так: h = Hash(IV, Mi), Mi — блок сообщения, IV — это начальный вектор, который либо задаётся вначале, либо это значение хэширования предыдущего блока сообщения.
Теперь чтобы сделать два разных сообщения с одинаковым хэшем достаточно изменить только один блок сообщения, найти начальное значение вектора и найти к нему коллизию (скорее всего это будет какой-то мусорный блок).
То есть имеем два сообщения вида:
M = [M1, M2, M3] и M' = [M1, M2', M3] и такие что Hash(M) = Hash(M') — теперь осталось скрыть факт изменения и сделать сообщения осмысленными, для этого можно пользоваться всякими трюками современных редакторов аля Word — пусть сообщение — это некий договор, в котором нам требуется изменить некоторую цифру (напоминаю, что блок M3 может быть произвольным). Пишем некоторое выражение (аля "поле" в Word), которое вычисляется при открытии и базируется на содержании блока M2 или M2', например использует факт, что в блоке M2' имеется некий взведённый бит (0->1 от M2->M2'). И в зависимости от этого условия пишет в документ разные цифры: 100 рублей или 1000000 рублей.
Здравствуйте, eao197, Вы писали:
L>>Я вот тоже на эту тему думал. Не знаю насчёт SHA-1, но как минимум MD5 — это алгоритм работы над потоком байт. То бишь, есть текущее(начальное) состояние и поток байт(с случае MD5 ЕМНИП это 64-разрядные слова), которые изменяют это состояниие. Так вот, если тебе нужно модифицировать документ — ты меняешь его состояние, а потом задача сводится к тому что нужно дописать какие-то данные дабы хеш остался тем же. Т.о., получается что мы решаем задачу No1 — поиск коллизии хеш-функции (правда, начальное состояние будет другим). Поправьте меня если не прав.
E>Так вот этот хвостик может быть таковым, что в документ его запихнуть не представится никакой возможности, в противном случае сама структура документа (его формат) будет нарушен. Особенно, если этот документ будет не бинарный, в котром хрен знает что может быть, а текстовый (XML, LaTeX) в котором любой мусор будет выглядеть мусором.
Да, это тоже задача, но разрешимая. В xml всегда можно вставить пробелы, переводы строк, комментарий или processing-instruction, которые софтом обычно игнорируются. Конечно, если документы просматриваются человеком на наличие "неправильностей", то может и можно такое избежать, но много ли ты знаешь систем, где пользователи читают xml?
Короче говоря, никаких принципиальных препятствий нет. А хотелось бы, как, например, с возможностью факторизации чисел.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
A>Также в том году небезызвестный NIST провёл конкурс Hash WorkShop — предполагалось выработать новый вариант стандарта на хэш-функцию. Пока о результатах ничего не слышно.
А что амеры думают про алгоритмы на эллиптических функциях (таких как функция ГОСТ Р 34.11)?
И ещё интересно бы узнать насколько сейчас могут подделывать _одновременно_ MD5 и SHA1 (это чтобы OpenPGP стандарт "взломать").
Здравствуйте, netch80, Вы писали:
N>А что амеры думают про алгоритмы на эллиптических функциях (таких как функция ГОСТ Р 34.11)?
О функциях с ключами речь не идёт, они относительно неудобны и медленны.
N>И ещё интересно бы узнать насколько сейчас могут подделывать _одновременно_ MD5 и SHA1 (это чтобы OpenPGP стандарт "взломать").
SHA1 — ещё не найдено ни одной коллизии, вопрос взлома пока только теоретический. MD5 — последние результаты, нахождение произвольной коллизии = менее секунды.
Одновременный "взлом" двух хэш-функций зависит от того как именно они используются. А с алгоритмами OpenPGP я не знаком
Здравствуйте, Andir, Вы писали:
N>>А что амеры думают про алгоритмы на эллиптических функциях (таких как функция ГОСТ Р 34.11)? A>О функциях с ключами речь не идёт, они относительно неудобны и медленны.
Можно чуть подробнее?
N>>И ещё интересно бы узнать насколько сейчас могут подделывать _одновременно_ MD5 и SHA1 (это чтобы OpenPGP стандарт "взломать"). A>SHA1 — ещё не найдено ни одной коллизии, вопрос взлома пока только теоретический. MD5 — последние результаты, нахождение произвольной коллизии = менее секунды. A>Одновременный "взлом" двух хэш-функций зависит от того как именно они используются. А с алгоритмами OpenPGP я не знаком :-)
Там просто конкатенация значений двух контрольных сумм, далее шифруемая секретным ключом отправителя.
Здравствуйте, netch80, Вы писали:
N>Можно чуть подробнее?
Что именно? NIST рассматривает только однонаправленные функции без использования шифрования/ключевой информации, грубо говоря алгоритм должен использовать простые и лёгкие для анализа сжимающие функции. А ГОСТ, про который ты спросил — это хэширование с использованием шифрования из другого госта + генерирование ключей из самого сообщения.
A>>Одновременный "взлом" двух хэш-функций зависит от того как именно они используются. А с алгоритмами OpenPGP я не знаком N>Там просто конкатенация значений двух контрольных сумм, далее шифруемая секретным ключом отправителя.
То есть предполагается подобрать такую коллизию сообщения M: чтобы => MD5(M) + SHA-1(M) = MD5(M') + SHA-1(M'). О результатах в этом направлении мне ничего не известно, а теоретически взлом возможен за 2^80 коллизий SHA-1 .
Здравствуйте, Andir, Вы писали:
A>Здравствуйте, netch80, Вы писали:
N>>Можно чуть подробнее?
A>Что именно? NIST рассматривает только однонаправленные функции без использования шифрования/ключевой информации, грубо говоря алгоритм должен использовать простые и лёгкие для анализа сжимающие функции. А ГОСТ, про который ты спросил — это хэширование с использованием шифрования из другого госта + генерирование ключей из самого сообщения.
То есть функцию из ГОСТ Р 34.11 нельзя применить как хэш-функцию, не используя никаких дополнительных данных? Извини, не сталкивался с ней плотно, поэтому уточняю.
A>>>Одновременный "взлом" двух хэш-функций зависит от того как именно они используются. А с алгоритмами OpenPGP я не знаком N>>Там просто конкатенация значений двух контрольных сумм, далее шифруемая секретным ключом отправителя. A>То есть предполагается подобрать такую коллизию сообщения M: чтобы => MD5(M) + SHA-1(M) = MD5(M') + SHA-1(M'). О результатах в этом направлении мне ничего не известно, а теоретически взлом возможен за 2^80 коллизий SHA-1 .
То есть пока скорее всего неактуально. Это хорошо.
.