Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Топ:
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Интересное:
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2018-01-30 | 360 |
5.00
из
|
Заказать работу |
Вышедший в 1994 г. документ [12] содержал рекомендации разработчикам систем защиты в части генерации псевдослучайных чисел, для чего, среди прочих алгоритмов хэширования, рекомендовалось использовать алгоритм MD4 (хотя и с оговоркой, что он слабее остальных рекомендуемых алгоритмов). Удивительно, что в существенно более поздней редакции данного документа [13], вышедшей в 2005 г. (когда недостаточная криптостойкость MD4 уже была явной), из списка рекомендуемых алгоритмов исчез алгоритм MD2, но MD4 остался практически с той же оговоркой. При этом, в документе [13] в качестве обоснования потенциальной слабости MD4 были указаны атаки на два раунда данного алгоритма, но не были рассмотрены уже известные к тому времени атаки на полнораундовый MD4 (например, описанная в [14]).
Заключение
Практически во всех применениях алгоритма MD4 можно наблюдать один и тот же цикл с незначительными вариациями:
Алгоритм MD4 все еще достаточно широко используется, однако видно, что его жизненный цикл подошел к концу и алгоритм в ближайшем будущем будет представлять только исторический интерес. Статус «исторический» был присвоен алгоритму MD4 в 2011 г. [15]
Литература
Обзор результатов криптоанализа алгоритмов HMAC-MD4 и NMAC-MD4
Данная статья завершает исторический обзор, посвященный алгоритму хэширования MD4. Она описывает результаты криптоанализа алгоритмов аутентификации сообщений на основе MD4: HMAC-MD4 и NMAC-MD4. Конструкции HMAC и NMAC были подробно описаны в предыдущей статье.
Начало атакам на алгоритм HMAC-MD4 положила работа [1], авторы которой сделали вывод о том, что атаки на MD4 могут быть расширены на HMAC-MD4. Это справедливо и для HMAC-алгоритмов, основанных на других алгоритмах хэширования, вопреки существовавшему на тот момент (2006 г.) мнению, что HMAC-надстройка существенно меняет контекст атаки на нижележащий алгоритм хэширования, делая невозможным применение существующих атак на алгоритм к его HMAC-варианту.
Авторы работы [1] предложили альтернативное графическое представление алгоритма HMAC, которое (для одноблочного сообщения M) приведено на рис. 1.
Рис. 1 Графическое представление HMACдля одноблочного сообщения
Для атаки на HMAC используется дифференциальный криптоанализ, в котором применяются квартеты одноблочных сообщений Mi, Mi ’, Mj и Mj ’ с определенной разностью a:
Mi ⊕ Mi ’ = Mj ⊕ Mj ’ = a,
причем сообщения Mi и Mj выбираются случайным образом.
Каждая четверка сообщений проверяется на наличие коллизии, т. е. справедливо ли следующее равенство применительно к выходным значениям алгоритма HMAC Ci, Ci ’, Cj и Cj ’:
Ci ⊕ Cj = Ci ’ ⊕ Cj ’ = 0 или Ci ⊕ Cj ’ = Ci ’ ⊕ Cj = 0.
Схема такой коллизии приведена на рис. 2 (на рисунке не показаны ключевые элементы, разности показаны прерывистыми линиями).
Рис. 2 Коллизия для квартета одноблочных сообщений
В части криптоанализа алгоритмов HMAC-MD4 и NMAC-MD4 в работе [1] были достигнуты следующие результаты:
Анализ HMAC и NMAC был независимо выполнен в работе [2], вышедшей в том же 2006 г., в которой также было показано, что слабая функция хэширования может скомпрометировать HMAC и NMAC, построенные на ее основе, а также любые другие вышележащие конструкции при их недостаточной криптостойкости.
Авторы [2] использовали найденные ранее коллизии для алгоритма MD4 при построении коллизии для внутренней функции хэширования HMAC- или NMAC-MD4, т. е. для функции hash(k 1, m) при использовании NMAC. Схема такой внутренней коллизии двух многоблочных сообщений M 1 и M 2 для HMAC-варианта приведена на рис. 3. Как отмечено в [2], внешняя функция хэширования скрывает результат выполнения внутренней функции, но не может скрыть факт возникновения такой внутренней коллизии (поскольку в случае внутренней коллизии совпадут выходные значения HMAC или NMAC).
Рис. 3 Внутренняя коллизия алгоритма HMAC
Следующий шаг атаки – создание набора специально выбранных сообщений, внутренние коллизии на которых позволят полностью определить значение внутреннего секретного ключа (т. е. h(k ⊕ C 1) в HMAC или k 1 в NMAC). В результате авторы [2] предложили следующие атаки на HMAC-MD4 и NMAC-MD4:
Отметим, что относительно невысокая трудоемкость данных атак делает возможной их практическую реализацию. Поэтому (это указано и в [2]) алгоритмы HMAC-MD4 и NMAC-MD4 после публикации данных результатов следовало как можно быстрее перестать использовать.
Как и в работе [1], в [2] были предложены атаки на алгоритмы аутентификации сообщений на основе ряда других хэш-функций. Кроме того, авторы работы [2] предложили универсальную методику атак на HMAC и NMAC, а также возможные направления атак на нижележащие алгоритмы хэширования, позволяющие впоследствии атаковать надстройки над ними.
Еще одна универсальная методика атак на HMAC и NMAC была предложена в работе [3] (2007 г.). Суть методики в использовании коллизий алгоритма хэширования, лежащего в основе HMAC/NMAC, для нахождения вектора инициализации данного алгоритма. Поскольку в HMAC/NMAC в качестве вектора инициализации используется секретный ключ (в NMAC) либо результат его обработки функцией сжатия алгоритма хэширования (в HMAC), данная атака позволяет:
В частности, в [3] описана атака на алгоритмы HMAC-MD4 и NMAC-MD4, позволяющая вычислить описанные выше ключевые элементы данных алгоритмов. Для успешной реализации атаки необходимы значения HMAC/NMAC 288 выбранных сообщений; вычислительная трудоемкость атаки составляет 295 операций.
Результаты предыдущей работы были усилены авторами вышедшей в следующем году работы [4], в которой было предложено для вычисления ключа использовать не коллизии, а near-коллизии, которые существенно проще получить. В результате количество данных, необходимых для успешной атаки, было снижено с 288 до 272 сообщений и результатов их обработки алгоритмом HMAC/NMAC, а трудоемкость атаки была снижена с 295 до 277 операций.
Какие-либо последующие работы, посвященные анализу HMAC-MD4 и NMAC-MD4, не получили широкой известности. Последние достижения в криптоанализе данных алгоритмов показывают явную зависимость криптостойкости HMAC и NMAC от криптостойкости нижележащих алгоритмов хэширования. Поскольку активный криптоанализ HMAC и NMAC продолжается, в ближайшие годы возможно дальнейшее усиление результатов работы [4], которые пока находятся за гранью практической применимости.
Литература:
Алгоритм хэширования MD6: обзор криптоаналитических исследований
Сергей Панасенко,
зам. директора Фирмы «АНКАД»
по науке и системной интеграции,
кандидат технических наук
В отличие от широко распространенного алгоритма MD5, криптоанализу которого было посвящено множество работ, алгоритм MD6 распространения, практически, не получил, в результате чего он привлек несравнимо меньшее внимание криптоаналитиков. Широкую известность получило относительно немного работ по криптоанализу данного алгоритма.
Начало исследованиям алгоритма MD6 положила магистерская диссертация [1] одного из авторов алгоритма – Кристофера Кратчфилда (Christopher Crutchfield). Данная работа вышла еще до опубликования самого алгоритма – в июне 2008 г. Она была целиком посвящена обоснованию достаточной криптостойкости алгоритма MD6; основные положения данной работы вошли в опубликованную в октябре 2008 г. спецификацию алгоритма [2].
В начале 2009 г. вышли две работы Дмитрия Ховратовича (Dmitry Khovratovich) и его коллег из университета Люксембурга [3-5]. Авторы данных работ смогли представить внутреннее состояние функции сжатия алгоритма MD6 в виде системы линейных уравнений и применить впоследствии для ее решения метод Гаусса. В результате криптоанализа было доказано, что выполнением до 33 раундов внутреннего преобразования функции сжатия (напомним, что алгоритм MD6-160 выполняет 80 раундов – см. подробное описание MD6 в [6]) вырабатывается последовательность, не обладающая характеристиками псевдослучайной. Теоретически, данный метод можно использовать для последующего нахождения коллизий усеченной функции сжатия алгоритма.
В феврале 2009 г. вышла также работа [7], авторами которой были несколько криптологов из числа авторов алгоритма MD6. В данной работе они доказали, что полнораундовая функция сжатия алгоритма MD6, как и алгоритм целиком, вырабатывают последовательности, не отличимые от псевдослучайных. Авторы [7] сделали вывод об отсутствии в алгоритме MD6 структурных слабостей, из-за которых, в частности, были бы необходимы какие-либо ограничения на использование алгоритма.
Тогда же, в феврале 2009 г., Шахрам Хазей (Shahram Khazaei) и Уилли Мейер (Willi Meier) опубликовали коллизию функции сжатия алгоритма MD6, усеченной до 16 раундов, приводящую также к near-коллизии функции сжатия, усеченной до 19 раундов включительно. Трудоемкость вычисления коллизии составляла 230 операций при незначительных требованиях к памяти [5, 8] (детали атаки подробно описаны в [9] и [10]). В июле 2009 г. результаты Хазея и Мейера были усилены Томасом Ходанеком (Thomas Hodanek), который ускорил атаку на 16-раундовую функцию сжатия до 217 операций [11].
1 июля 2009 г. авторы алгоритма MD6 направили в NIST комментарий [12], содержащий список их собственных замечаний относительно алгоритма MD6 и конкурса SHA-3, в котором данный алгоритм участвовал. Несмотря на то, что в документе [12] (см. также [13]) было сказано, что «NIST вправе выбрать алгоритм MD6 в следующий раунд конкурса при желании», документ, фактически, представлял собой отзыв данного алгоритма с конкурса SHA-3, как минимум, по следующим причинам:
После этого не выглядит удивительным тот факт, что алгоритм MD6 не был выбран во второй раунд конкурса SHA-3 [14].
В том же 2009 вышла работа [15], в которой были предложены следующие атаки на усеченные версии алгоритма MD6:
Последней из получивших широкую известность работ, посвященных криптоанализу алгоритма MD6, была вышедшая в 2011 г. работа Этана Хейлмана (Ethan Heilman) [17]. Автор данной работы предложил новые доказательства достаточной криптостойкости алгоритма MD6 против дифференциального криптоанализа; доказанный запас криптостойкости алгоритма MD6 по сравнению с доказанным ранее авторами алгоритма был увеличен в два раза. Таким образом, выводы авторов алгоритма оего недостаточной криптостойкости, изложенные в [12], были опровергнуты. Тем не менее, вернуть алгоритм MD6 в список участников второго раунда конкурса SHA-3 было уже поздно: алгоритм MD6 выбыл из конкурса и, как одно из следствий, не получил широкого распространения.
Данная статья завершает серию публикаций, посвященных алгоритмам хэширования семейства MD. Автор выражает благодарность коллективу портала по безопасности Sec.ru за предоставленную возможность опубликования данной серии статей и активное в этом содействие, а также благодарность экспертам за время, потраченное на анализ статей цикла, и предоставленные экспертные оценки, отзывы и замечания.
Литература
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!