Криптоанализ поточных шифров, основанный на соотношении время/память/данные

Введем обозначения:

N – размер ключевого пространства (количество возможных ключей в блочном шифре или количество состояний генератора ПСП в поточном шифре);

P- время, необходимое для предварительной стадии криптоанализа;

M – объем памяти, необходимый для хранения данных, вычисляемых во время криптоанализа;

T-время, необходимое для основной стадии криптоанализа;

D – объем данных, полученных с помощью определенного ключа (для поточного шифра – объем доступной для анализа информации с выхода генератора ПСП).

В 1980 г. Хеллман предложил новый метод криптоанализа блочных шифров, основанный на соотношении

После этого Бэбидж и Голич установили, что соотношение TM = N можно применить к поточным шифрам, причем 1 < T<D. Затем А. Шамир и А. Бирюков предложили модификацию этого метода, при котором используется соотношение

причем

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

В случае блочных шифров размер N пространства поиска определяется как число возможных ключей. Предположим, что число возможных блоков открытого текста и шифротекста также составляет N и что объем данных с выхода шифра, доступных для анализа, составляет один блок, полученный из одного фиксированного блока открытого текста. Самая эффективная атака с применением соотношения время/память, с точки зрения Хеллмана, использует комбинацию параметров, которые удовлетворяют следующим соотношениям:

Оптимальный выбор T и M зависит от относительной стоимости вычислительных ресурсов (время вычисления, объем свободного пространства). Используя равенство T = M, Хеллман получил, что

Метод Хеллмана применим к любому блочному шифру, у которого отображение ключа на блок шифротекста (при фиксированном блоке открытого текста) ведет себя как произвольная функция / над пространством точек N. Если эта функция обратима, то соотношение принимает вид: TM = N, что сильно уменьшает сложность криптоанализа по сравнению с предыдущем случаем. Серьезным недостатком метода Хеллмана является то, что даже если криптоаналитик обладает большим числом D подобранных пар открытый текст/шифротекст, то совершенно неизвестно, как можно использовать эти данные для улучшения метода.

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

Простейшая атака на поточные шифры, использующая соотношение время/память, была независимо описана Бэбиджем и Голичем, после чего ее стали обозначать как BG-атаку. Она соотносит каждое из возможных состояний генератора со строкой (выходным блоком), содержащей первые ln N бит выходной последовательности генератора, считанные сразу после прохождения генератором этого состояния. Отображение у = f(x), где x – состояние, а у ~ выходной блок может рассматриваться как произвольная функция над пространством из N точек, причем эту функцию довольно-таки трудно инвертировать. Целью криптоаналитика является инвертирование ее над некой подстрокой выходной последовательности, для того чтобы восстановить внутреннее состояние генератора.

Во время подготовительной стадии атаки криптоаналитик выбирает M произвольных состояний xh вычисляет соответствующие им выходные блоки yt и сохраняет эти пары (Xi,yi) в специальной таблице по возрастанию yit Во время второй фазы атаки криптоаналитик получает

выходных бит и получает из них D возможных пересекающихся последовательностей бит

размером ln N. Затем производится поиск каждого значения yt в таблице, заполненной во время подготовительной стадии. Если по крайней мере одно значение yj будет найдено в таблице, то соответствующее значение Xj позволяет определить внутреннее состояние генератора. После того как криптоаналитику стало известно внутреннее состояние генератора в какой-то момент времени, он сможет продолжить тактировать генератор из этого состояния и восстановить оставшуюся часть открытого текста.

Следует отметить, что в принципе различные состояния генератора xi могут соответствовать одному и тому же выходному блоку yj и таким образом полученное состояние Xj может отличаться от реального. Однако такие ложные срабатывания увеличивают сложность атаки ненамного. Таким образом, соотношение можно привести к виду:

где P = M и атака занимает время T = D. Это представляет одну определенную точку на прямой TM = N. Игнорируя часть доступных выходных данных во время атаки, мы можем сокращать Гот D по направлению к 1 и таким образом свести соотношение к

где P = M для любых 1 < T<D.

Полученное выражение похоже на соотношение TM = N, которое использовал Хеллман, и превосходит его же соотношение TM2 = N2 (когда T = M, мы получаемвместо). Однако это формальное сравнение является обманчивым, так как эти атаки кардинально отличаются друг от друга: они применяются к различным типам криптоалгоритмов (блочные и поточные шифры), используют различные диапазоны параметров и требуют различного объема данных (около D бит и один блок).

Для того чтобы понять принципиальную разницу между атаками на блочные и поточные шифры, рассмотрим, как большое значение параметра D может ускорить время криптоанализа.

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

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

 

Источник: Acoсков А. В., Иванов М. A., Мирский А. A., Рузин А. В., Сланин А. В., Тютвин А. Н. Поточные шифры. – M.: КУДИЦ-ОБРАЗ, 2003. – 336 с.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100