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

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

История

Корреляционная атака впервые была описана в 1985 году Т. Зигенталером. Он описал атаку на генератор на основе комбинационной цепи, состоящий из n {displaystyle n} РСЛОС. Длины регистров рассматриваемого генератора равнялись L 1 , L 2 , … , L n {displaystyle L_{1},L_{2},ldots ,L_{n}} . Атака полного перебора на данную систему требует ∏ i = 1 n ( 2 L i − 1 ) {displaystyle extstyle prod _{i=1}^{n}displaystyle (2^{L_{i}}-1)} попыток, в то время как предложенная Зигенталером корреляционная атака всего ∑ i = 1 n ( 2 L i − 1 ) {displaystyle extstyle sum _{i=1}^{n}displaystyle (2^{L_{i}}-1)} . Данная атака так же может быть эффективна при взломе других генераторов на основе РСЛОС, например фильтрационных (filter generators)

Объяснение

Корреляционные атаки возможны, когда существует значительная зависимость между выходным значением отдельного РСЛОС в генераторе потока ключей и выходом логической функции, которая объединяет выходные значения всех РСЛОС. В сочетании со знанием части потока ключей, это позволяет злоумышленнику перебирать (brute-force) ключ для этого отдельного РСЛОС и остальной системы по отдельности. Например, для генератора потока ключей с четырьмя 8-разрядными РСЛОС объединенными логической функцией такой, что один из регистров скоррелирован с выводом логической функции, возможно сначала перебрать скоррелированный регистр, а затем оставшиеся три. В таком случае общее число вариантов для перебора составляет 28 + 224. В случае полного перебора системы число вариантов составило бы 232. Таким образом, данная атака позволила снизить сложность перебора, а следовательно и время затрачиваемое на него, почти в 256 раз. Если второй регистр также скоррелирован, можно повторить этот процесс и снизить сложность перебора до 28 + 28 + 216, что дает сокращение количества возможных вариантов почти в 65028 раз. В этом смысле корреляционные атаки можно считать алгоритмами типа «разделяй и властвуй».

Пример

Взлом генератора Geffe

Рассмотрим корреляционную атаку на примере генератора потока ключей Geffe. Генератор Geffe состоит из трех РСЛОС: РСЛОС-1, РСЛОС-2 и РСЛОС-3. Обозначим выходные значения этих регистров как x 1 {displaystyle x_{1}} , x 2 {displaystyle x_{2}} и x 3 {displaystyle x_{3}} соответственно. Пусть логическая функция, объединяющая три регистра для генерации ключа, определяется как F ( x 1 , x 2 , x 3 ) = ( x 1 ∧ x 2 ) ⊕ ( ¬ x 1 ∧ x 3 ) {displaystyle F(x_{1},x_{2},x_{3})=(x_{1}wedge x_{2})oplus ( eg x_{1}wedge x_{3})} (то есть ( x 1 {displaystyle x_{1}} AND x 2 {displaystyle x_{2}} ) XOR (NOT x 1 {displaystyle x_{1}} AND x 3 {displaystyle x_{3}} )). Существует 23 = 8 возможных наборов значений трех регистров. Значение функции F {displaystyle F} для каждого из них показано в таблице ниже:

Рассмотрим вывод третьего регистра, x 3 {displaystyle x_{3}} . Из приведенной выше таблицы видно, что 6 из 8 возможных значений x 3 {displaystyle x_{3}} равны соответствующему значению выхода генератора, F ( x 1 , x 2 , x 3 ) {displaystyle F(x_{1},x_{2},x_{3})} , то есть F ( x 1 , x 2 , x 3 ) = x 3 {displaystyle F(x_{1},x_{2},x_{3})=x_{3}} в 75% всех возможных случаев. Это означает, что РСЛОС-3 коррелирует с генератором. Это является уязвимостью, которую можно использовать следующим образом:

Предположим, перехватывается зашифрованный текст c 1 , c 2 , c 3 , … , c n {displaystyle c_{1},c_{2},c_{3},ldots ,c_{n}} соответствующий открытому тексту p 1 , p 2 , p 3 , … {displaystyle p_{1},p_{2},p_{3},ldots } , который был зашифрован с помощью потокового шифра с использованием генератора потока ключей Geffe, то есть c i = p i ⊕ F ( x 1 i , x 2 i , x 3 i ) {displaystyle c_{i}=p_{i}oplus F(x_{1i},x_{2i},x_{3i})} для i = 1 , 2 , 3 , … , n {displaystyle i=1,2,3,ldots ,n} , где x 1 i {displaystyle x_{1i}} - это выходное значение РСЛОС-1 в момент времени i {displaystyle i} и т. д. Предположим также, что известна некоторая часть открытого текста, например первые 32 бита, p 1 , p 2 , p 3 , … , p 32 {displaystyle p_{1},p_{2},p_{3},ldots ,p_{32}} . Это вполне вероятно: например, если известно, что открытый текст является корректным XML-файлом, тогда первые 4 символа ASCII должны быть «<XML», что соответствует 32 битам. Аналогичным образом, многие форматы файлов или сетевые протоколы имеют стандартные верхние или нижние колонтитулы, которые можно попробовать угадать. Данный тип атак, при котором известна часть текста, называется атаками на основе открытых текстов. Зная перехваченный шифротекст c 1 , c 2 , c 3 , … , c 32 {displaystyle c_{1},c_{2},c_{3},ldots ,c_{32}} и известные/угаданные символы исходного p 1 , p 2 , p 3 , … , p 32 {displaystyle p_{1},p_{2},p_{3},ldots ,p_{32}} , можно легко найти F ( x 1 i , x 2 i , x 3 i ) {displaystyle F(x_{1i},x_{2i},x_{3i})} для i = 1 , 2 , 3 , … , 32 {displaystyle i=1,2,3,ldots ,32} , вычисляя их по средствам исключающего или (XOR) от зашифрованного и открытого текстов. Таким образом, известно 32 последовательных бита выхода генератора.

Теперь можно начать перебор в пространстве возможных ключей для РСЛОС-3. Для любого данного ключа в пространстве ключей можно сгенерировать первые 32 бита выходных данных РСЛОС-3 и сравнить их с нашими восстановленными 32 битами всего выходного сигнала генератора. Поскольку ранее было установлено, что существует 75% корреляция между выходом РСЛОС-3 и генератором, известно, что, если правильно угадан ключ для РСЛОС-3, примерно 24 из первых 32 битов выхода РСЛОС-3 будут совпадать с соответствующими битами выхода генератора. Если догадка не верна, ожидается, что примерно половина или 16 из первых 32 битов этих двух последовательностей будут совпадать. Таким образом, можно восстановить ключ для РСЛОС-3 независимо от ключей РСЛОС-1 и РСЛОС-2. На этом этапе задача перебора системы из 3 РСЛОС была сведена к задаче перебора одного РСЛОС, а затем системы из 2 РСЛОС. Сокращение возможных вариантов для перебора зависит от длины РСЛОС. Для реальных значений это дает очень существенную экономию и может сделать атаки перебора практичными.

Однако, в данном примере задачу можно упростить еще раз. Из таблицы выше видно, что x 2 {displaystyle x_{2}} также совпадает с выходом генератора 6 раз из 8. Как и в случае с x 3 {displaystyle x_{3}} , корреляция составляет 75% между x 2 {displaystyle x_{2}} и выходом генератора. Можно решать задачу перебора РСЛОС-2 независимо от ключей РСЛОС-1 и РСЛОС-3. Таким образом, сложность взлома генератора Geffe равна сложности перебора трех независимых РСЛОС. Это означает, что генератор Geffe является слабым генератором.

Из таблицы так же видно, что x 1 {displaystyle x_{1}} согласуется с выходом генератора 4 раза из 8, корреляция составляет 50%. Соответственно, невозможно использовать перебор РСЛОС-1 независимо от других: правильный ключ даст выходной сигнал, который согласуется с выходным сигналом генератора в 50% случаев, однако неправильный ключ будет вести себя так же. В этом случае корреляционная атака на этот регистр невозможна при любом, сколь угодно большом объеме открытого текста. Таким образом, объединяющую функцию F ( x 1 , x 2 , x 3 ) {displaystyle F(x_{1},x_{2},x_{3})} следует выбирать так, чтобы корреляция между каждой переменной и выходом объединяющей функции была как можно ближе к 50%. На практике может быть трудно найти функцию, которая удовлетворяет этому условию, не жертвуя другими критериями.

В общем случае, если примитивные многочлены всех регистров генератора состоят всего из 3 слагаемых, а максимальная длина РСЛОС составляет n {displaystyle n} бит, то достаточно всего 37 n {displaystyle 37n} бит открытого текста для полного взлома генератора Geffe.

Статистический характер атаки

Хотя вышеприведенный пример хорошо иллюстрирует относительно простые концепции, лежащие в основе корреляционных атак, он, возможно, упрощает объяснение того, как именно происходит грубый перебор отдельных РСЛОС. Утверждается, что неправильно угаданные ключи будут генерировать вывод РСЛОС, который согласуется с выходом генератора примерно в 50% случаев, потому что для двух случайных битовых последовательностей заданной длины вероятность совпадения любого отдельного взятого бита последовательностей равна 0,5. Тем не менее, отдельные отдельные неверные ключи вполне могут генерировать выход РСЛОС, который согласуется с выходом генератора более или менее часто, чем в 50% случаев. Это особенно заметно в случае РСЛОС, чья корреляция с генератором не особенно сильна; для достаточно малых корреляций, не исключено, что неправильно угаданный ключ также приведет к выводу РСЛОС, который согласуется с желаемым числом битов на выходе генератора. Таким образом, не всегда возможно найти ключ для этого РСЛОС однозначно и с уверенностью. Вместо этого существует возможность найти несколько подходящих ключей, один из которых является верным, однако это все еще является серьезной уязвимостью в безопасности шифра. Более точно определить необходимое количество перехваченного открытого текста позволяют методы теории вероятности. Оно зависит от ошибок первого и второго рода P f {displaystyle P_{f}} и P n {displaystyle P_{n}} соответственно. Пусть p i {displaystyle p_{i}} - вероятность того, что F ( x 1 , … , x n ) = x i {displaystyle F(x_{1},ldots ,x_{n})=x_{i}} . Тогда можно показать, что например для P f = 1.3 ∗ 10 − 3 {displaystyle P_{f}=1.3*10^{-3}} и P n = 2 − L i {displaystyle P_{n}=2^{-L_{i}}} , где L i {displaystyle L_{i}} - длина соответствующего РСЛОС, необходимое количество бит N {displaystyle N} открытого текста составляет примерно:

N ∼ ( l n ( 2 L i − 1 ) + 3 2 p i ( 1 − p i ) 2 ( p i − 0.5 ) ) 2 {displaystyle Nsim left({{frac {{sqrt {ln(2^{L_{i}-1})}}+3{sqrt {2p_{i}(1-p_{i})}}}{{sqrt {2}}(p_{i}-0.5)}};} ight)^{2}}

Из формулы так же видно, что чем слабее корреляция между отдельным регистром и выходом генератора (то есть вероятность p i {displaystyle p_{i}} близка к 1/2), тем больше известного открытого текста требуется для того, чтобы найти ключ этого регистра с высокой степенью достоверности.