Методы оценки качества алгоритмов поточного шифрования

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

1. Период

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

Наличие периода является статистическим “дефектом”, который позволяет отличить ПСП от истинно случайной. Если период ПСП, используемой в качестве ключевого потока, слишком маленький, то его относительно легко предсказать. Период ПСП должен быть достаточно болшим, чтобы никогда не повторится. Это обычно реализуется путем использования стандартного блока, который имеет доказуемо большой период, например, LFSR максимальной длины.

2. Криптоанализ шифров

Атаки на поточные шифры классифицируются в соответствии с [6]

информацией, которая доступна криптоаналитику;

целями атак;

способами реализации атаки.

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

Фундаментальное правило криптоанализа, впервые сформулированное голландцем А. Керкхоффом еще в XIX веке заключается в том, что стойкость шифра (криптосистемы) должна определяться только секретностью ключа. Иными словами, правило Керкхоффа состоит в том, что весь алгоритм шифрования, кроме значения секретного ключа, известен криптоаналитику противника. Это обусловлено тем, что криптосистема, реализующая семейство криптографических преобразований, обычно рассматривается как открытая система. Такой подход отражает очень важный принцип технологии защиты информации: защищенность системы не должна зависеть от секретности чего-либо такого, что

215

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

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

В зависимости от степени доступности информации криптоаналитику выделяют следующие типы атак:

1.Атака только при наличии шифртекста (ciphertext-only). Это наихудший случай для криптоаналитика. Криптоаналитик пытается по имеющемуся шифртексту восстановить исходный текст или ключ шифрования.

2.Атака при известном открытом тексте (known-plaintext). Криптоаналитик знает шифртекст и весь или часть открытого текста. Для аддитивного поточного шифра (гаммирования) это равносильно знанию всего или части ключевого потока. Целью криптоаналитика является определение ключа или остальной части открытого текста.

3.Атака при возможности выбора открытого текста (chosen-plaintext). Криптоаналитик имеет доступ к шифрующему устройству и может зашифровать любой открытый текст. Целью криптоаналитика является определение ключа шифрования.

4.Атака при возможности выбора шифртекста (chosenciphertext). Криптоаналитик имеет доступ к устройству расшифрования и может расшифровать любой шифртекст. Целью криптоаналитика является определение ключа шифрования.

На сколько реалистичны подобные атаки? Шифртекст легкодоступен, т.к. обычно передается по открытым, общедоступным каналам. Получить доступ к открытому тексту гораздо сложнее. Криптоаналитик может предположить наиболее вероятное содержание некоторых частей текста, например приветствие в заголовке письма. Если у криптоаналитика есть возможность уговорить или заставить кого-то зашифровать свои сообщения, то это получится случай атаки с выбранным открытым текстом. Атака с выбранным шифртектом является наименее реалистичной, но хороший шифр должен обеспечивать защиту и от такого типа атак.

216

Для синхронных поточных шифров 2, 3, 4 типы атак эквивалентны. Для самосинхронизирующихся же наиболее эффективной является 4 тип атаки.

Существует еще дополнительные виды атак – атака с возможностью выбора инициализирующего вектора (chosen-IV attack). В данном случае криптоаналитик может выбирать инициализирующий вектор (IV). И атака связанных ключей (related key attacks), где криптоаналитик может выбирать особую связь между ключами.

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

Взависимости от цели, преследуемой криптоаналитиком, выделяют следующие атаки:

1.Атака различением (distinguishing attack).

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

2.Предсказание (prediction).

Этот способ предназначен для предсказания выхода генератора ключевого потока более точно, чем предположение.

3.Восстановление ключа (key recovery).

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

последовательности ключевого потока более точными, чем предположение. Обычно выделяют следующие атаки на поточные шифры:

1. Исчерпывающий поиск ключа (атака грубой силой) (exhaustive key search).

217

2.Атака, основанная на согласовании памяти и времени (time-memory trade-off attack, TMTO).

3.Корреляционная атака.

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

4.Алгебраическая атака (algebraic attack).

Там, где корреляционная атака пробует найти линейную аппроксимацию выходной функции f, алгебраическая атака использует выражения более высокой степени. Первая алгебраическая атака называлась корреляционной атакой старшего порядка (high order correlation attack).

5.Атака “разделяй и властвуй”.

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

6.Атака смены ключа (rekeying attack).

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

7.Атака “предположи и определи” (guess-and-determine attack).

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

8.Атака по побочным признакам (side channel attack).

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

218