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

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

Объяснение [ править ]

Корреляционные атаки становятся возможными, когда существует значительная корреляция между выходным состоянием отдельного LFSR в генераторе ключевого потока и выходными данными булевой функции, которая объединяет выходные состояния всех LFSR. Эти атаки используются в сочетании с частичным знанием ключевого потока, которое получается из частичного знания открытого текста. Затем эти два значения сравниваются с использованием XOR логического элемента . Эта уязвимость позволяет злоумышленнику подобрать ключ отдельно для отдельного LFSR и остальной части системы. Например, в генераторе потока ключей, где четыре 8-битных LFSR объединяются для создания потока ключей, и если один из регистров коррелирует с выходом логической функции, становится возможным сначала перебрать его, а затем оставшиеся три LFSR. В результате общая сложность атаки становится равной 2. ⁸ + 2 ²⁴.

По сравнению со стоимостью проведения грубой атаки на всю систему сложностью 2 ³², это представляет собой коэффициент экономии усилий атаки чуть менее 256. Если второй регистр коррелирует с функцией, процесс можно повторить и уменьшить сложность атаки до 2. ⁸ + 2 ⁸ + 2 ¹⁶ для коэффициента экономии усилий чуть менее 65028.

Пример [ править ]

Генератор Геффе [ править ]

Одним из примеров является генератор Geffe, который состоит из трех LFSR: LFSR-1, LFSR-2 и LFSR-3. Обозначим эти регистры как: $x_{1}$ , $x_{2}$ , и $x_{3}$ , соответственно. Тогда булева функция, объединяющая три регистра для обеспечения выходного сигнала генератора, имеет вид $F(x_{1},x_{2},x_{3})=(x_{1}\wedge x_{2})\oplus (\neg x_{1}\wedge x_{3})$ (то есть ( $x_{1}$ И $x_{2}$ ) XOR (НЕ $x_{1}$ И $x_{3}$ )). Есть 2 ³ = 8 возможных значений для выходов трех регистров, и значение этой объединяющей функции для каждого из них показано в таблице ниже:

Таблица вывода логической функции
$x_{1}$	$x_{2}$	$x_{3}$	$F(x_{1},x_{2},x_{3})$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Рассмотрим вывод третьего регистра: $x_{3}$ . В таблице выше показано, что из 8 возможных выходов $x_{3}$ , 6 равны соответствующему значению выхода генератора, $F(x_{1},x_{2},x_{3})$ . В 75% всех возможных случаев $x_{3}=F(x_{1},x_{2},x_{3})$ . Таким образом, LFSR-3 «коррелирует» с генератором. Это слабость, которую можно использовать следующим образом:

Перехват может быть произведен по зашифрованному тексту. $c_{1},c_{2},c_{3},\ldots ,c_{n}$ простого текста $p_{1},p_{2},p_{3},\ldots$ который был зашифрован с помощью потокового шифра с использованием генератора Geffe в качестве генератора потока ключей, т.е. $c_{i}=p_{i}\oplus F(x_{1i},x_{2i},x_{3i})$ для $i=1,2,3,\ldots ,n$ , где $x_{1i}$ это выход LFSR-1 в момент времени $i$ и т. д. Также возможно, что часть обычного текста, например $p_{1},p_{2},p_{3},\ldots ,p_{32}$ , первые 32 бита открытого текста (соответствуют 4 символам текста ASCII). Это вполне вероятно, учитывая, что простой текст является допустимым файлом XML, например, первые 4 символа ASCII должны быть «<xml». Точно так же многие форматы файлов или сетевые протоколы имеют очень стандартные верхние и нижние колонтитулы. С учетом перехваченного $c_{1},c_{2},c_{3},\ldots ,c_{32}$ и наши известные/предполагаемые $p_{1},p_{2},p_{3},\ldots ,p_{32}$ , мы можем легко найти $F(x_{1i},x_{2i},x_{3i})$ для $i=1,2,3,\ldots ,32$ путем XOR-объединения двух вместе. Это позволяет легко определить 32 последовательных бита выходного сигнала генератора.

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

Обратите внимание на таблицу выше, что $x_{2}$ также согласуется с выходом генератора 6 раз из 8, снова корреляция 75% между корреляцией $x_{2}$ и выход генератора. Мы можем начать атаку методом перебора на LFSR-2 независимо от ключей LFSR-1 и LFSR-3, оставив неповрежденным только LFSR-1. Таким образом, мы можем сломать генератор Geffe, приложив столько усилий, сколько требуется для перебора трёх полностью независимых LFSR. Это означает, что генератор Geffe является очень слабым генератором и никогда не должен использоваться для генерации потоков ключей потокового шифрования.

Обратите внимание на таблицу выше, что $x_{1}$ согласуется с выходом генератора в 4 случаях из 8 — корреляция 50%. Мы не можем использовать это для перебора LFSR-1 независимо от остальных: правильный ключ даст результат, который согласуется с выходом генератора в 50% случаев, но в среднем то же самое будет и с неправильным ключом. Это представляет собой идеальную ситуацию с точки зрения безопасности — функция объединения $F(x_{1},x_{2},x_{3})$ следует выбирать так, чтобы корреляция между каждой переменной и выходными данными объединяющей функции была как можно ближе к 50%. На практике может оказаться затруднительным найти функцию, которая достигает этого, не жертвуя при этом другими критериями проектирования, например длиной периода, поэтому может потребоваться компромисс.

Уточнение статистического характера атаки [ править ]

Хотя приведенный выше пример хорошо иллюстрирует относительно простые концепции корреляционных атак, он, возможно, упрощает объяснение того, как именно происходит перебор отдельных LFSR. Неправильно угаданные ключи будут генерировать выходные данные LFSR, которые согласуются с выходными данными генератора примерно в 50% случаев, поскольку для двух случайных битовых последовательностей заданной длины вероятность совпадения между последовательностями в любом конкретном бите равна 0,5. Однако отдельные неверные ключи вполне могут генерировать выходные данные LFSR, которые совпадают с выходными данными генератора более или менее часто, чем ровно в 50% случаев. Это особенно заметно в случае LFSR, корреляция которых с генератором не особенно сильна; для достаточно малых корреляций, конечно, не исключено, что неправильно угаданный ключ также приведет к выходному сигналу LFSR, который соответствует желаемому количеству бит выходного сигнала генератора. Таким образом, может оказаться невозможным идентифицировать уникальный ключ к этому LFSR. Однако возможно идентифицировать ряд потенциальных ключей, что по-прежнему является серьезным нарушением безопасности шифра. Более того, при наличии мегабайта известного открытого текста ситуация будет существенно иной. Неправильный ключ может генерировать выходные данные LFSR, которые согласуются с более чем 512 килобайтами выходных данных генератора, но вряд ли будут генерировать выходные данные, которые согласуются с целыми 768 килобайтами выходных данных генератора, как это сделал бы правильно угаданный ключ. Как правило, чем слабее корреляция между отдельным регистром и выходом генератора, тем более известный открытый текст требуется для нахождения ключа этого регистра с высокой степенью достоверности. Оценки длины известного открытого текста, необходимой для данной корреляции, можно рассчитать с помощью биномиальное распределение .

Корреляции порядка более высокого

Определение [ править ]

Корреляции, которые использовались в примере атаки на генератор Джеффа, являются примерами так называемых корреляций первого порядка : это корреляции между значением выходного сигнала генератора и отдельным LFSR. Помимо них можно определить корреляции более высокого порядка. Например, возможно, что, хотя данная булева функция не имеет сильной корреляции ни с одним из отдельных регистров, которые она объединяет, значительная корреляция может существовать между некоторой булевой функцией двух регистров, например, $x_{1}\oplus x_{2}$ . Это будет примером корреляции второго порядка. Таким образом можно определить корреляции третьего порядка и выше.

Корреляционные атаки более высокого порядка могут быть более мощными, чем корреляционные атаки одиночного порядка, однако на этот эффект распространяется «закон предельной отдачи». В таблице ниже показаны вычислительные затраты для различных атак на генератор потока ключей, состоящий из восьми 8-битных LFSR, объединенных одной логической функцией. Понять расчет стоимости относительно просто: самый левый член суммы представляет размер пространства ключей для коррелированных генераторов, а самый правый член представляет размер пространства ключей для остальных генераторов.

Усилие атаки генератора
Атака	Усилие (размер пространства ключей)
Грубая сила	$2^{8\times 8}=18446744073709551616$
Одиночная корреляционная атака 1-го порядка	$2^{8}+2^{7\times 8}=72057594037928192$
Одиночная корреляционная атака 2-го порядка	$2^{2\times 8}+2^{6\times 8}=281474976776192$
Одиночная корреляционная атака 3-го порядка	$2^{3\times 8}+2^{5\times 8}=1099528404992$
Одиночная корреляционная атака 4-го порядка	$2^{4\times 8}+2^{4\times 8}=8589934592$
Одиночная корреляционная атака 5-го порядка	$2^{5\times 8}+2^{3\times 8}=1099528404992$
Одиночная корреляционная атака 6-го порядка	$2^{6\times 8}+2^{2\times 8}=281474976776192$
Одиночная корреляционная атака 7-го порядка	$2^{7\times 8}+2^{8}=72057594037928192$

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

Терминология [ править ]

Булева функция $F(x_{1},\ldots ,x_{n})$ из $n$ переменных называется « $иммунитетом к корреляции m$ -го порядка» или обладает « $m$ -го порядка корреляционной устойчивостью » для некоторого целого числа $m$ , если между выходными данными функции и любой булевой функцией от $m$ ее входов не существует существенной корреляции. Например, булева функция, которая не имеет корреляций первого или второго порядка, но имеет корреляцию третьего порядка, демонстрирует корреляционную устойчивость 2-го порядка. Очевидно, что более высокая корреляционная устойчивость делает функцию более подходящей для использования в генераторе ключевого потока (хотя это не единственное, что необходимо учитывать).

Зигенталер показал, что корреляционная устойчивость $m$ булевой функции алгебраической степени $d$ от $n$ переменных удовлетворяет условию $m+d\leq n$ ; для данного набора входных переменных это означает, что высокая алгебраическая степень ограничит максимально возможную корреляционную устойчивость. Более того, если функция сбалансирована, то $m\leq n-1$ . ^[1]

Отсюда следует, что функция $n$ переменных не может быть невосприимчивой к $корреляциям n-$ го порядка. Это также следует из того факта, что любая такая функция может быть записана с использованием базиса Рида-Мюллера как комбинация операций XOR входных функций.

дизайна шифрования Последствия

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

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

См. также [ править ]

Темы криптографии

Ссылки [ править ]

Брюс Шнайер . Прикладная криптография : протоколы, алгоритмы и исходный код на языке C , второе издание. Джон Вили и сыновья, Inc., 1996. ISBN 0-471-12845-7 . Страница 382 раздела 16.4: Потоковые шифры с использованием LFSR.

^ Т. Зигенталер (сентябрь 1984 г.). «Корреляционная устойчивость нелинейных объединяющих функций для криптографических приложений». Транзакции IEEE по теории информации . 30 (5): 776–780. дои : 10.1109/TIT.1984.1056949 .
^ Чуан-Кун Ву и Эд Доусон, Построение корреляционных иммунных логических функций. Архивировано 7 сентября 2006 г. в Wayback Machine , ICICS97.

Внешние ссылки [ править ]

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

[Siegenthaler-1] Т. Зигенталер (сентябрь 1984 г.). «Корреляционная устойчивость нелинейных объединяющих функций для криптографических приложений». Транзакции IEEE по теории информации . 30 (5): 776–780. дои : 10.1109/TIT.1984.1056949 .

[2] Чуан-Кун Ву и Эд Доусон, Построение корреляционных иммунных логических функций. Архивировано 7 сентября 2006 г. в Wayback Machine , ICICS97.

[1]

[2]