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

Атака различением

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

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

Статистический анализ гаммы шифров

Статистические свойства

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

С. Голомб сформулировал три основных правила, которым должна удовлетворять последовательность, чтобы выглядеть случайной. Эти правила известны как постулаты Голомба. Пусть s – двоичная последовательность с периодом N. Двоичная последовательность s удовлетворяет постулатам Голомба, если:

1.Число “1” в каждом периоде должно отличаться от числа “0” не более чем на единицу.

2.В каждом периоде половина серий должна иметь длину один, одна четверть длину два, одна восьмая должна иметь длину три и т.д. (т.е. количество однобитовых серий равно половине периода, число двухбитовых серий – ¼ периода, число трехбитовых серий – 1/8 периода и т.д.) Кроме того, для каждой из этих длин должно быть одинаковое количество серий из “1” и “0”.

224

3. Функция автокорреляции для последовательности должна быть двузначной, т.е. принимать лишь два значения. Функция автокорреляции для последовательности s определяется как

C 1, ïðè 0 mod N .

Третье правило – это техническое выражение того, что Голомб описал как понятие независимых испытаний: знание некоторого предыдущего значения последовательности в принципе не помогает предположениям о текущем значении. Еще одна точка зрения на функцию автокорреляции состоит в том, что это некая мера способности, позволяющей различать последовательность и ее же копию, но начинающуюся в некоторой другой точке цикла.

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

Последовательность, удовлетворяющая постулатам Голомба часто именуется “pn- последовательностью”, где pn обозначает “pseudo-noise” (“псевдо-шумовая”).

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

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

Выделяют следующие тесты, предназначенные для оценки статистических свойств выходных последовательностей генераторов ключевого потока поточных шифров:

Качественный ГПСП, ориентированный на использование в системах поточного шифрования, должен быть криптографически стойким и обладать хорошими

225

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

Для анализа ГПСП используют множество различных тестов. Наиболее известными наборами статистических тестов являются: Diehard, Crypt-X , набор статистических тестов НИСТ (Национального Института Стандартов и Технологий, N),ключи).ВIST Statistical Test Suite) , а также наборы тестов, описанные. Поскольку существует очень много статистических тестов, то ни один из наборов нельзя считать полным.

Набор статистических тестов Diehard содержит следующие тесты: birthday spacings, overlapping permutation, binary rank test for 31x31 matrices, binary rank test for 32x32 matrices, binary rank test for 6x8 matrices, monkey, bitstream, count-the-1's test on a stream of bytes, count- the-1's test for specific bytes, parking lot test, minimum distance test, 3dspheres, sqeeze, overlapping sums, runs, craps.

Набор статистических тестов Crypt-X содержит следующие тесты: frequency, binary derivative, change point, runs, sequence complexity и linear complexity тесты.

Набор статистических тестов НИСТ включает в себя следующие статистические тесты: frequency (monobit), frequency test within a block, runs, test for the longest-run-of-ones in a block, binary matrix rank, discrete fourier transform (spectral), non-overlapping template matching, overlapping template matching, maurer's "universal statistical", lempel-ziv compression, linear complexity, serial, approximate entropy, cumulative sums (cusums), random excursions, random excursions variant.

Вописано 5 основных тестов: frequency (monobit), serial (two-bit), poker, runs, autocorrelation, а также универсальный тест Мауэра.

Вописано несколько эмпирических тестов: frequency, serial, gap, poker, coupon collector’s, permutation, run, maximum-of-t, collision, birthday spacings, serial correlation.

Для тестирования последовательностей, генерируемых различными шифрами, использовался набор статистических тестов НИСТ по ряду причин. Во-первых, набор статистических тестов НИСТ содержит самые строгие тесты, которые предназначены для тестирования генераторов, используемых для криптографических приложений. Во-вторых в рассмотрена проблема независимости используемых статистических тестов – степень

226

дублирования тестов между собой очень мала. В-третьих этот набор использовался для оценки AES кандидатов.

Тестирование

Основным принципом тестирования является проверка нулевой гипотезы H0: тестируемая последовательность случайна. Альтернативной гипотезой Ha является гипотеза о том, что последовательность неслучайна. По результатам каждого теста нулевая гипотеза либо принимается, либо отвергается.

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

Если предположение о случайности для тестируемых данных истинно, то в результате вычисленное тестовое значение статистики для этих данных будет иметь очень низкую вероятность (около 0,01%) превышения критического значения.

Возможно несколько исходов статистического тестирования. Безошибочным исходом является принятие решения о верности нулевой H0 или альтернативной Ha гипотезы при случайности или неслучайности тестируемых данных соответственно. А также возможны ошибки первого и второго рода. Ошибка 1-го рода возникает в том случае, если тестируемые данные являются случайными, но принимается решение об отклонении нулевой H0 гипотезы. Ошибка 2-го рода возникает в том случае, если тестируемые данные случайными не являются, но при этом принимается решение о принятии нулевой H0 гипотезы.

Ошибка 1-го рода часто называется уровнем значимости теста. Уровень значимости обозначается и может быть установлена до теста. Таким образом – это вероятность того, что тест покажет, что последовательность неслучайна, при том, что она в действительности случайна. Обычно принимают равным 0,01.

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

227