05 декабря 2012
Обзор атак на алгоритм хэширования MD5: поиск коллизий
Часть 2
После описанной в первой части статьи работы [1] долгое время не появлялось каких-либо новых результатов в поиске коллизий для алгоритма MD5 – до 2004 г., когда была опубликована упомянутая ранее работа Ксиаоюн Ванг и ее коллег [2]. В данной работе не были описаны детали атаки на алгоритм MD5, однако, ее авторы привели два примера коллизий для двухблочных сообщений (в которых разность первых блоков двух сообщений вносит незначительное различие в состояние алгоритма, которое впоследствии аннулируется при обработке незначительно различающихся вторых блоков; схема двухблочной коллизии приведена на рис. 1) с использованием стандартного вектора инициализации алгоритма MD5 – т. е., в отличие от предыдущих результатов, это были коллизии для алгоритма MD5 целиком, без каких-либо модификаций. Мало того, в работе [2] утверждалось, что для поиска коллизий достаточно всего около часа работы мощного компьютера. Детали атаки на MD5 опубликованы не были, но приведенных примеров коллизий было достаточно для доказательства существования математических методов поиска коллизий для MD5. Как было сказано, например, в [3], анонсирование на конференции «CRYPTO 2004» найденных Ванг коллизий для MD5 привело аудиторию в «сильное волнение» (great excitement); выступление на конференции китайских специалистов было встречено овацией присутствующих [4].
Рис. 1 Схема двухблочной коллизии
В ответ на найденные коллизии компания RSA выпустила бюллетень [4], в котором в очередной раз отметила, что найденные коллизии вряд ли возможно использовать на практике (результаты практического использования коллизий рассмотрим в одной из последующих статей), но, тем не менее, компания по-прежнему рекомендует отказаться от использования MD5 в пользу более стойких алгоритмов, из которых наилучшим выбором считает стандарт хэширования SHA2 [5].
Работа [3], представленная в том же году тремя криптологами из Австралии, содержит подробный анализ структуры алгоритма MD5 с точки зрения применения дифференциального криптоанализа. Как отметили авторы данной работы, она написана «по следам» работы [2] и не содержит каких-либо новых атак на MD5, а лишь «описывает мысли авторов относительно представленных Ванг коллизий». Авторам [3] также не удалось реконструировать неопубликованные детали приведшей к коллизии атаки на MD5. Тем не менее, во многих последующих криптоаналитических исследованиях алгоритма MD5 (например, [6]) использовалась работа [3], благодаря масштабности и подробности выполненного в ней анализа.
В том же 2004 г. были опубликованы первые работы, представляющие атаки на различные применения алгоритма MD5, использующие факт возможности быстрого поиска коллизий для данного алгоритма. Атакам на приложения, использующие MD5, будет посвящена одна из следующих статей цикла.
В начале 2005 г. Властимил Клима (Vlastimil Klima) предложил альтернативный метод поиска коллизий, опубликовав в работе [6] примеры коллизий, как для стандартного вектора инициализации алгоритма MD5, так и для его произвольного значения (что справедливо и для предыдущего метода). Детали атаки в работе [6] также не были опубликованы, но, по примерным оценкам Климы, его метод поиска коллизий работал в 3-6 раз быстрее, чем неопубликованный метод китайских криптоаналитиков.
Несколько позже вышла работа [7], в которой Ксиаоюн Ванг и Хонгбо Ю (Hongbo Yu) описали детали атаки по поиску коллизий для MD5. Китайские специалисты использовали комбинированный криптоанализ – с разностью, определяемой операцией XOR, и с разностью, определяемой операцией вычитания по модулю 232. Как было сказано в [7], «комбинация этих двух видов разности дает нам больше информации, чем каждый из них по отдельности». Пример данных видов разности для двух 32-битных значений X и Y, подтверждающий их различную взаимодополняющую информативность, приведен на рис. 2.
Рис. 2 Пример применения двух видов разности
Работа [7] получила широкую известность еще и благодаря тому, что в ней предложена технология модификации сообщений, примененная для увеличения вероятности нахождения коллизии (и активно используемая криптоаналитиками впоследствии при анализе многих других алгоритмов хэширования). Последовательность действий для нахождения коллизии согласно [7] такова:
Этап 1. Поиск первой пары блоков (M0 и M0’ – см. рис. 1) в цикле до нахождения требуемой near-коллизии (см. ниже) по результатам обработкиM0 и M0’:
- Случайный выбор значения M0.
- Применение к M0 технологии модификации сообщений.
- Вычисление M0’ =M0 + ΔM0; оптимальное значение разности ΔM0 получено с помощью дифференциального криптоанализа:
ΔM0 = (0, 0, 0, 0, 231, 0, 0, 0, 0, 0, 0, 215, 0, 0, 231, 0),
где каждое число в скобках означает разность, определяемую операцией вычитания по модулю 232, между значениями 32-битных фрагментов блоков данных M0’ и M0 (см. описание алгоритма в [8]).
- Полученные значения M0 и M0’ дают требуемую near-коллизию с вероятностью 2-37. Для проверки соответствия необходимо применить к M0 и M0’ функцию сжатия алгоритма MD5 и убедиться в том, что найдена требуемая пара блоков, либо в том, что пара не дает требуемый результат. В последнем случае следует вернуться к шагу 1 для выбора нового значения M0.
Этап 2. Аналогичный поиск второй пары блоков (M1 и M1’) в цикле до получения коллизии:
- Случайный выбор значения M1.
- Применение к M1 технологии модификации сообщений.
- Вычисление M1’ =M1 + ΔM1:
ΔM1 = (0, 0, 0, 0, 231, 0, 0, 0, 0, 0, 0, -215, 0, 0, 231, 0).
- Полученные значения M1 и M1’ дают коллизию (с учетом near-коллизии в результате обработки первых блоков) с вероятностью 2-30. Аналогично первому этапу, для проверки применяется функция сжатия и выполняется возврат к шагу 1, если коллизия не получена.
Требуемые значения разности переменных состояния после обработки первой пары сообщений также определены с помощью дифференциального криптоанализа и приведены в таблице:
Переменная состояния X |
Разность X’ - X mod 232 |
A |
231 |
B |
231 + 225 |
C |
231 + 225 |
D |
231 + 225 |
Результирующая трудоемкость атаки на MD5 составляет около 239 операций хэширования для поиска первой пары блоков и около 232 операций для поиска второй пары.
Продолжение следует
Литература
- Dobbertin H. The Status of MD5 After a Recent Attack. // http://ftp.rsasecurity.com – German Information Security Agency – Bonn, Germany (опубликовано в RSA Laboratories’ CryptoBytes – 1996 – volume 2, number 2, pp. 1-6).
- Wang X., Feng D., Lai X., Yu H. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. // http://eprint.iacr.org – Revised on August 17, 2004.
- Hawkes P., Paddon M., Rose G. G. Musings on the Wang et al. MD5 Collision. // http://eprint.iacr.org – Qualcomm Australia, Gladesville, Australia.
- Randall J., Szydlo M. Collisions for SHA0, MD5, HAVAL, MD4, and RIPEMD, but SHA1 Still Secure. // http://www.rsa.com – RSA Laboratories – August 31, 2004.
- FIPS PUB 180-2. Secure Hash Standard. // http://csrc.nist.gov – National Institute of Standards and Technology – 2002 August 1.
- Klima V. Finding MD5 Collisions – a Toy For a Notebook. // http://eprint.iacr.org – March 5, 2005.
- Wang X., Yu H. How to Break MD5 and Other Hash Functions. // http://citeseerx.ist.psu.edu – Shandong University, Jinan, China.
- Панасенко С. Алгоритм хэширования MD5. // Sec.ru. – http://daily.sec.ru/publication.cfm?pid=35484 – 13.08.2012 г.
