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

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

Объяснение

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

пример

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

Возможно, лучше всего объяснить корреляционные атаки на примере. Мы рассмотрим случай с генератором потока ключей Geffe. Генератор Geffe состоит из трех LFSR: LFSR-1, LFSR-2 и LFSR-3. Если мы обозначим выходы этих регистров как , и , соответственно, тогда логическая функция, которая объединяет три регистра для обеспечения выхода генератора, задается (т.е. ( И ), ИСКЛЮЧАЮЩЕЕ ИЛИ (НЕ И )). Существует 2 ³ = 8 возможных значений для выходов трех регистров, и значение этой функции комбинирования для каждого из них показано в таблице ниже: ${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {3}}$${\ Displaystyle F (x_ {1}, x_ {2}, x_ {3}) = (x_ {1} \ wedge x_ {2}) \ oplus (\ neg x_ {1} \ wedge x_ {3})}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {2}}$${\ displaystyle x_ {1}}$${\ displaystyle x_ {3}}$

Таблица вывода логической функции

${\ displaystyle x_ {1}}$	${\ displaystyle x_ {2}}$	${\ displaystyle x_ {3}}$	${\ Displaystyle 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

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

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

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

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

Уточнение статистической природы атаки

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

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

Определение

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

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

Усилие атаки генератора

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

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

Терминология

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

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

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

Последствия разработки шифров

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

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

Смотрите также

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

Ссылки

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

внешние ссылки

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