Конференции ИВТ СО РАН

Тезисы докладов

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

Большинсво блоковых шифров являются итерационными, т.е. содержат много раундов (циклов) преобразований, обычно обрамленных некоторым прологом и эпилогом [1]. Каждый из этих этапов, в свою очередь, может быть поделен на некоторое число более простых шагов, выполняющих преобразования данных и шифрующих их с помощью некоторых подключей, полученных из основного ключа. Мы предлагаем атаку по выбранному тексту для шифра, который может быть представлен такой итерационной схемой с относительно небольшими подключами. Это возможно для таких современных шифров, как RC5, RC6, AES и др. Отметим, что в реализации атаки используются новые методы статистического тестирования, предложенные авторами в [2,3,4].

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

Одно из требований к блоковым шифрам состоит в том, что имея на входе последовательность различных блоков, шифр должен выдавать на выходе последовательность бит, которая выглядит случайной. Истинно случайная последовательность может быть определена как последовательность, порожденная бернуллиевским источником с равными вероятностями нулей и единиц. Мы будем неформально называть последовательности "более случайными" или "менее случайными" в зависимости от того, как сильно они отличаются от истинно случайных последовательностей. Один способ измерения случайности состоит в использовании некоторой статистики, вычисляемой на основе последовательности и имеющей такое свойство, что менее случайные последовательности имеют большее значение статистики (с учетом некоторой вероятности ошибки в суждении). Это может быть хорошо известная статистика x², подчиняющаяся распределению хи-квадрат.

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

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

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

Экспериментальное исследование предложенной атаки проводилось следующим образом. Во-первых, была проанализирована степень случайности зашифрованных последовательностей как функция числа шагов шифрования. Цель была найти максимальное количество шагов, на которых тесты могли отличить зашифрованную последовательность от истинно случайной. Во-вторых, было проверено предположение, на котором базируется атака, а именно, увеличивает ли случайность последовательности дешифрование с неверным подключом, точнее, различимы ли с помощью тестов последовательности полученные при дешифровании с верным и неверными ключами. В-третьих, на основе полученных результатов была реализована непосредственно атака на шифр. Эксперименты проводились на многопроцессорной системе, содержащей 10 1-ГГц процессоров Alpha с 1Г байт памяти в каждом.

Эксперименты подтвердили наши предположения о принципиальной возможности предлагаемой градиентной статистической атаки. В частности, шифр RC5, имеющий 8 раундов, может быть взломан при использовании 2³³ пар текст-шифротекст.

[1] Menzes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996.

[2] Ryabko B. Ya., Stognienko V. S., Shokin Yu. I. A new test for randomness and its application to some cryptographic problems // Journal of Statistical Planning and Inference. V. 123, N. 2. 2003. P. 365-376.

[3] B. Ya. Ryabko, V. A. Monarev. Using information theory approach to randomness testing. Journal of Statistical Planning and Inference, 2005 (accepted; available online 15 July 2004, see: Articles in Press).

[4] Ryabko B. Ya., Fionov A. N., Monarev V. A., Shokin Yu. I. Using information theory approach to randomness testing // 2nd Russian-German Advanced Research Workshop on Computational Science and High Performance Computing. -- Stuttgart, Germany, March 14 - 16, 2005. -- http://www.hlrs.de.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск