В криптографии линейный криптоанализ — это общая форма криптоанализа, основанная на нахождении аффинных приближений к действию шифра . Атаки были разработаны для блочных и потоковых шифров . Линейный криптоанализ — одна из двух наиболее широко используемых атак на блочные шифры; другой — дифференциальный криптоанализ .
Открытие приписывается Мицуру Мацуи , который первым применил эту технику к шифру FEAL (Мацуи и Ямагиши, 1992). [1] Впоследствии Мацуи опубликовал атаку на стандарт шифрования данных (DES), что в конечном итоге привело к первому экспериментальному криптоанализу шифра, о котором сообщалось в открытом сообществе (Мацуи, 1993; 1994). [2] [3] Атака на DES в целом непрактична, поскольку требует 2 47 известных открытых текстов . [3]
Были предложены различные усовершенствования атаки, в том числе использование нескольких линейных приближений или включение нелинейных выражений, что приводит к обобщенному криптоанализу с разделением . От новых конструкций шифров обычно ожидаются доказательства защиты от линейного криптоанализа.
Линейный криптоанализ состоит из двух частей. Первый заключается в построении линейных уравнений, связывающих открытый текст, зашифрованный текст и ключевые биты, имеющие высокую степень смещения; то есть, чьи вероятности хранения (в пространстве всех возможных значений их переменных) как можно ближе к 0 или 1. Второй заключается в использовании этих линейных уравнений в сочетании с известными парами открытого текста-зашифрованного текста для получения ключевых битов.
Для целей линейного криптоанализа линейное уравнение выражает равенство двух выражений, состоящих из двоичных переменных, объединенных с операцией исключающее ИЛИ (XOR). Например, следующее уравнение гипотетического шифра устанавливает сумму XOR первого и третьего битов открытого текста (как в блоке блочного шифра), а первый бит зашифрованного текста равен второму биту ключа:
В идеальном шифре любое линейное уравнение, связывающее открытый текст, зашифрованный текст и ключевые биты, будет выполняться с вероятностью 1/2. Поскольку уравнения, рассматриваемые в линейном криптоанализе, различаются по вероятности, их правильнее называть линейными приближениями .
Процедура построения приближений различна для каждого шифра. В самом базовом типе блочного шифра, сети подстановки-перестановки , анализ сосредоточен в первую очередь на S-блоках , единственной нелинейной части шифра (т. е. операция S-блока не может быть закодирована в линейном уравнении). Для достаточно маленьких S-блоков можно перебрать все возможные линейные уравнения, связывающие входные и выходные биты S-блока, вычислить их смещения и выбрать лучшие. Затем линейные аппроксимации для S-блоков необходимо объединить с другими действиями шифра, такими как перестановка и смешивание ключей, чтобы получить линейные аппроксимации для всего шифра. Лемма о накоплении — полезный инструмент на этом этапе комбинирования. Существуют также методы итеративного улучшения линейных аппроксимаций (Мацуи, 1994).
Получив линейную аппроксимацию вида:
затем мы можем применить простой алгоритм (алгоритм Мацуи 2), используя известные пары открытый текст-зашифрованный текст, чтобы угадать значения ключевых битов, участвующих в аппроксимации.
Для каждого набора значений ключевых битов в правой части (называемого частичным ключом ) подсчитайте, сколько раз аппроксимация справедлива для всех известных пар открытый текст-зашифрованный текст; назовите этот счетчик T. Частичный ключ, T которого имеет наибольшее абсолютное отличие от половины количества пар открытый текст-зашифрованный текст, обозначается как наиболее вероятный набор значений для этих ключевых битов. Это связано с тем, что предполагается, что правильный частичный ключ приведет к тому, что аппроксимация будет выполняться с большим смещением. Здесь важна величина систематической ошибки, в отличие от величины самой вероятности.
Эту процедуру можно повторить с другими линейными аппроксимациями, получая предположения о значениях ключевых битов, пока количество неизвестных ключевых битов не станет достаточно низким, чтобы их можно было атаковать методом грубой силы .
