Описание градиентной статистической атаки.

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

У целого класса современных блоковых шифров начальный секретный ключ K преобразуется в так называемые ключи раундов , которые используются последовательно для шифрования на разных этапах, называемых раундами. Для моей задачи на вход шифров подавались блоки , длина которых в двоичной записи равна длине блока данных шифра данных. Блоки подаются в последовательности , т.е. блоки следующего вида: 00…001, 00..0010, 000..0011,… (1). Одно из основных требований к современным блоковым шифрам состоит в том, что какая бы последовательность данных на входе не подавалась шифру, на выходе должна быть получена последовательность, мера случайности (или, сокращённо, «случайность») которой стремится к бесконечности или очень большая.

Если на вход шифра подавать данные вида (1), то вероятность обнаружить на выходе последовательность с отклонениями от «случайности» будет значительно выше. Мера случайности последовательности, полученной на выходе после i-го раунда в любом блоком шифре, возрастает с ростом числа раундов. В тоже время, во время дешифрования мера случайности последовательности убывает.

Кратко опишем схему градиентной атаки. Пусть есть какой-то i-ый раунд шифра: последовательность бит на входе операции дешифрования раунда i и эта же последовательность на выходе дешифратора раунда i: . Тогда схему дешифрования можно представить в виде: , где K_i – раундовый ключ. Дальше оцениваем меру случайности последовательности: При дешифровании с правильным ключом раунда она должна сильно уменьшиться, тогда как дешифрование с неправильным ключом аналогично шифрованию, т.е. оно наоборот увеличивает меру случайности последовательности. В итоге, если Г( ) < Г( ), то ключ раунда K_i подобран правильно, иначе – неправильно. Смысл атаки сводится к нахождению такого ключа K_i, который будет минимизировать Г( ). Теоретически для этого надо перебрать все вариантов, но исходя из того, что правильный ключ даёт существенно меньшую величину Г( ), можно подбирать ключи до нахождения этого «существенного минимума».

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

Таким образом, если существует статистический тест, который эффективно находит отклонения от случайности (Г < ) на (r-1) раунде, при r раундах шифрования в шифре, то ключ такого шифра можно найти существенно быстрее, чем методом прямого перебора секретного ключа К. Это основная идея «градиентной статистической атаки».