id: Гость   вход   регистрация
текущее время 13:57 28/03/2024
Владелец: unknown редакция от 14/04/2010 17:18 (автор: unknown) Печать
Категории: криптография, хэширование, симметричное шифрование
https://www.pgpru.com/Новости/2010/АтакаРикошетомИРазличителиНаОсновеПодпространствДляАнализаХэш-функцииWhirlpool
создать
просмотр
редакции
ссылки

14.04 // Атака рикошетом и различители на основе подпространств для анализа хэш-функции Whirlpool


Mario Lamberger, Florian Mendel, Christian Rechberger, Vincent Rijmen, и Martin SchlЁffer опубликовали подробную работу по использованию ряда техник в криптоанализе хэш-функции Whirlpool. В настоящее время идёт конкурс NIST на хэш-функцию SHA-3, на который авторы Whirlpool даже не подавали заявку, так как эта функция не соответствует ряду формальных критериев конкурса. Чем же актуальна эта работа?


Во-первых, полученный результат интересен с точки зрения общих критериев проектирования хэш-функций и может дать стимул к новым работам. Во-вторых, авторы подтверждают полезность новых критериев стойкости хэш-функций, в том чиле специально рекомендованных NIST для конкурса SHA-3. В третьих, Whirlpool основана на байт-ориентированном шифре W, который является почти точной копией шифра AES-Rijndael, но с изменением размера блока до 512 бит. При этом авторы утверждают, что их работа показывает уязвимость в дизайне AES, так как на него распространяются аналогичные методы криптоанализа, что должно послужить в будущем более пристальному изучению структуры AES для создания новых блочных шифров (один из авторов этой работы — Vincent Rijmen является создателем AES). Наконец, функция Whirlpool успела получить некоторое распространение, как наиболее обоснованная альтернатива взломанным MD5 и SHA-1 и была единственной хэф-функцией, стандартизированной ISO/IEC с 2000 года, не опирающейся на дизайн MD4.


Криптографическая хэш-функция H отображает сообщение m, имеющее произвольную длину, в фиксированное по длине хэш-значение h. Избегая излишней формализации можно сказать, что криптографическая хэш-функция должна удовлетворять трём классическим требованиям стойкости: нахождению прообраза, нахождению второго прообраза и нахождению коллизий. Если длина хэш-значения на выходе функции равна N, то противник всегда сможет найти первый и второй прообразы методом перебора 2N различных сообщений, а нахождение коллизий потребует 2N/2 попыток за счёт парадокса дней рождения. Ранее считалось, что этих свойств достаточно для достижения идеальной стойкости.


Последующие исследования показали, что это не так. В ходе конкурса NIST на SHA-3 исследователи обратили внимание на (полу-)начальные коллизии, предколлизии и др. Любое проявление "поведения, отличного от ожидаемого для случайного оракула" стало рассматриваться как подозрительное, даже если уязвимость была показана в отношении функции сжатия, а не для полной хэш-функции.


Интересным результатом данной работы явилось успешное применение рикошет-атаки — разновидности дифференциального криптоанализа, значительным образом оптимизированного для взлома хэш-функций и в тоже время ставшего высокоуровневой моделью в их проектировании. Рикошет атака может быть использована для получения разного типа коллизий и в тоже время она особенно успешна против простых байт-ориентированных структур на основе AES.


Вторым важным результатом работы стало введение и определение проблемы подпространств, как естественного расширения и формализации требований в вопросах предколлизий. Наконец, в этой работе показан различитель для полной функции сжатия Whirlpool и таким образом продемонстрировано первое отличие этой функции от идеальной модели.


Рикошет атака была предложена Менделем и др. ранее для анализа хэш-функций, основанных на AES. Эта атака основана на дифференциальном криптоанализе. Дифференциальный криптоанализ — это один из основных инструментов в анализе симметричных криптопримитивов. Первоначально разработанный для DES, затем он был применён к блочным, потоковым шифрам, хэш-функциям. Дифференциальная атака использует предсказуемое прохождение разности между парой на входе криптопримитива к соответствующему выходу. То, что определяет различные паттерны входа, промежуточные значения и выход криптопримитива, называется характеристикой или иначе дифференциальным путём. Пара, которая соответствует характеристике называется правильной парой. Отношение количества всех правильных пар ко всем возможным входным парам, в некоторых случаях усреднённое по отношению ко всем ключам (если примитив управляется ключом), называется вероятностью пути.


Сокращённые дифференциалы были предложены Кнудсеном для анализа блочных шифров. Если в стандартной дифференциальной атаке необходимо знание полной разности между входом/выходом, то в случае сокращённых дифференциалов достаточно только частично определенной разности, например для каждого байта можно проверить только соответствует он заявленной разности или нет.


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


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


Таким образом, для нахождения (пред)коллизий используется трёхшаговый алгоритм:


  1. Нахождение высоковероятностного пути.
  2. Использование техники модификации сообщений для определения некоторых значимых битов.
  3. Нахождение оставшихся битов сообщения путём угадывания с последующей проверкой.

В атаке предколлизий используется две фазы, называемые фазой приближения и фазой отскока. В соответствии с этими фазами функция сжатия, внутренний блочный шифр или перестановка делятся на три части. Часть фазы приближения помещается в центральную часть шифра, а две части исходящий фазы — в начало шифра вслед за входящей фазой. Для исходящей фазы конструируются два высоковероятностных (сокращённых) дифференциальных пути и соединяются с входящей фазой.
Помещая наиболее ресурсоёмкую часть атаки в центр шифра и используя такого рода техники перегруппировок можно значительно сократить ресурсы на технику модификации сообщений. Эти методы уже использовались в криптоанализе MD5 и в атаках Вагнера по типу бумеранг и дифференциалов второго порядка.


Авторы улучшили эти техники для криптоанализа Whirlpool и ещё раз доказали слабость ключевой функции AES-подобных структур, которая упрощает перегруппировку.


Новые требования NIST требуют, чтобы любые подмножества фунции сохраняли свойства стойкости самой функции в пересчёте на мощность множества. Это имеет большой практический смысл, так как позволяет произвольным образом обрезать выход хэш-функции до нужного минимального значения. Но на практике некоторые программисты используют например для уменьшения величины выхода хэш-функции xor двух половин выхода, что является почти таким же простым и малозатратным как и отбрасывание лишней половины битов. (Прим. перев.: этот вопрос долгое время оставался без аргументированного ответа: что лучше — простое отбрасывание или xor? С другой стороны в случае идеальной стойкости самой хэш-функции оба варианта сокращения размера её выхода должны быть равностойкими).


В случае xor должно быть сложно подобрать пару сообщений m, m' такую, что H (m) xor H (m' ) = z, иначе говоря для любого типа линейного преобразования L должно быть сложно найти пару входов m,m' такую, что L(H (m) xor H (m' )) = 0. С одной стороны противник не должен выбирать L поскольку для любых m,m' можно тривиально найти L, удовлетворяющее последнему условию. С другой стороны, если мы требуем, чтобы противник мог найти подходящий m,m' для произвольно выбранного L или для большого подмножества, то интутивно может казаться, что противнику будет крайне сложно подобрать соответствующие этим случаям плохо спроектированные хэш-функции.


Авторам удалось предложить вариант формализации проблемы подпространств и проанализировать сложность проблемы подпространств. С подробными выкладками можно ознакомиться в работе.


Используя технику различителя на подпространствах, исследователи смогли не только построить различитель хэш-функции Whirlpool, но и найти различитель внутреннего шифра W в модели открытого ключа. Ранее такая работа была известна для AES, но теперь есть больше оснований говорить об собенностях криптоанализа всех AES-подобных структур. Также им удалось получить восьмираундовый различитель для W в модели известного ключа. В такой модели противнику известен ключ блочного шифра и он пытается доказать, что перестановка шифртекстов по отношению к открытым текстам не является идеально псевдослучайной (шифр не соотвествует идеальной модели PRP). Для всех 10 раундов была проведена аналогичная атака только с использованием подобранного ключа.


Источник: Cryptology ePrint Archive