Корреляционная иммунность¶

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

¶Определение и формализация

Пусть \( f: \{0,1\}^n \to \{0,1\} \) — булева функция от \( n \) переменных. Функция называется корреляционно-иммунной порядка \( m \) (где \( 0 \le m \le n \)), если для любого подмножества входных переменных размером не более \( m \) выход функции статистически независим от этих переменных. Иными словами, для любого набора из \( t \le m \) переменных \( x_{i_1}, \ldots, x_{i_t} \) и для любого фиксированного значения \( (a_1, \ldots, a_t) \in \{0,1\}^t \) вероятность того, что \( f(x_1, \ldots, x_n) = 1 \) при условии \( x_{i_1}=a_1, \ldots, x_{i_t}=a_t \), равна \( \frac{1}{2} \) (при условии равномерного распределения входных векторов).

Формально, корреляционная иммунность порядка \( m \) означает, что для любого ненулевого вектора \( \alpha \in \{0,1\}^n \) с весом Хэмминга \( w(\alpha) \le m \) коэффициент корреляции Уолша — Адамара \( \hat{f}(\alpha) = 0 \). Коэффициент \( \hat{f}(\alpha) \) определяется как:

\[ \hat{f}(\alpha) = \sum_{x \in \{0,1\}^n} f(x) (-1)^{\alpha \cdot x} \]

где \( \alpha \cdot x \) — скалярное произведение по модулю 2. Если \( \hat{f}(\alpha) = 0 \) для всех \( \alpha \) с весом \( w(\alpha) \le m \), то функция \( f \) является корреляционно-иммунной порядка \( m \).

¶История

Понятие корреляционной иммунности было введено в 1984 году криптографом Томасом Сигенталером в контексте анализа поточных шифров, использующих комбинирующие генераторы. Сигенталер показал, что если комбинирующая функция \( f \) не обладает корреляционной иммунностью, то между выходной последовательностью и последовательностями отдельных регистров сдвига существует статистическая зависимость. Это позволяет злоумышленнику, перехватившему достаточное количество битов шифротекста, восстанавливать начальные состояния регистров с меньшей вычислительной сложностью, чем полный перебор.

В 1985 году Уильям Миллер и Джон Мэсси предложили критерий, связывающий корреляционную иммунность с нелинейностью и другими свойствами булевых функций. Впоследствии теория была развита в работах Клода Шеннона, Ади Шамира и других, что привело к созданию методов синтеза функций с заданными криптографическими свойствами.

¶Свойства и ограничения

¶Компромисс с нелинейностью

Корреляционная иммунность находится в противоречии с другим важным криптографическим свойством — нелинейностью. Нелинейность булевой функции определяется как минимальное расстояние Хэмминга до множества всех аффинных функций. Чем выше порядок корреляционной иммунности, тем ниже может быть нелинейность. Это ограничение известно как теорема Сигенталера: для функции \( f \) от \( n \) переменных, обладающей корреляционной иммунностью порядка \( m \), её нелинейность \( N_f \) удовлетворяет неравенству:

\[ N_f \le 2^{n-1} - 2^{m} \]

Для достижения максимальной нелинейности (например, для бент-функций, у которых \( N_f = 2^{n-1} - 2^{n/2-1} \)) порядок корреляционной иммунности не может превышать \( n/2 - 1 \). Таким образом, при проектировании криптосистем приходится искать баланс между этими свойствами.

¶Взаимосвязь с алгебраической степенью

Алгебраическая степень функции (максимальная степень мономов в её представлении в виде полинома Жегалкина) также связана с корреляционной иммунностью. Функция, корреляционно-иммунная порядка \( m \), может иметь алгебраическую степень не выше \( n - m \). Это следует из того, что коэффициенты Уолша — Адамара для векторов малого веса равны нулю, что ограничивает структуру полинома.

¶Применение в криптографии

¶Поточные шифры

Корреляционная иммунность критически важна для комбинирующих генераторов — устройств, в которых выходная последовательность формируется как булева функция от нескольких линейных регистров сдвига (LFSR). Если комбинирующая функция не является корреляционно-иммунной, то злоумышленник может использовать корреляционные атаки, такие как атака Сигенталера, для восстановления начальных состояний регистров. Например, в шифре A5/1 (используемом в GSM) была обнаружена уязвимость, связанная с недостаточной корреляционной иммунностью.

¶Блочные шифры

В блочных шифрах корреляционная иммунность применяется при проектировании S-блоков (таблиц замен). S-блоки, обладающие высокой корреляционной иммунностью, затрудняют линейный криптоанализ, который опирается на статистические зависимости между входными и выходными битами. Например, в стандарте AES (Rijndael) S-блоки построены на основе обратной функции в поле Галуа, что обеспечивает высокую нелинейность и корреляционную иммунность.

¶Хэш-функции

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

¶Методы синтеза

¶Построение на основе кодов

Один из подходов к синтезу корреляционно-иммунных функций основан на теории кодирования. Функция \( f \) корреляционно-иммунна порядка \( m \) тогда и только тогда, когда её носитель (множество входов, на которых функция равна 1) образует код, исправляющий ошибки, с минимальным расстоянием не менее \( m+1 \). Для построения таких функций используются коды Рида — Маллера, коды БЧХ и другие.

¶Алгоритмы оптимизации

Для поиска функций с заданными параметрами (корреляционная иммунность, нелинейность, алгебраическая степень) применяются эвристические методы, такие как генетические алгоритмы, имитация отжига и методы случайного поиска. Например, в работе 2000-х годов были предложены алгоритмы, позволяющие находить функции от 10-12 переменных с корреляционной иммунностью порядка 4-5 и высокой нелинейностью.

¶Критика и ограничения

Хотя корреляционная иммунность является важным критерием, она не гарантирует полной безопасности. Известны атаки, которые обходят это свойство:

• Атаки на основе быстрого преобразования Уолша — Адамара (FFT-атаки) позволяют восстанавливать ключ даже при наличии корреляционной иммунности, если функция имеет низкую нелинейность.
• Алгебраические атаки используют представление функции в виде системы уравнений, что может быть эффективно даже при высокой корреляционной иммунности.
• Атаки по сторонним каналам (например, по времени выполнения или энергопотреблению) не зависят от статистических свойств функции.

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

¶Примеры

¶Пример 1: Функция от 3 переменных

Рассмотрим функцию \( f(x_1, x_2, x_3) = x_1 \oplus x_2 \oplus x_3 \) (сумма по модулю 2). Её таблица истинности: 0,1,1,0,1,0,0,1. Вычислим коэффициенты Уолша — Адамара для векторов веса 1: \( \hat{f}(1,0,0) = 0 \), \( \hat{f}(0,1,0) = 0 \), \( \hat{f}(0,0,1) = 0 \). Для вектора веса 2: \( \hat{f}(1,1,0) = 0 \), и т.д. Таким образом, функция является корреляционно-иммунной порядка 2 (максимально возможного для 3 переменных). Однако её нелинейность равна 0, так как она сама является аффинной.

¶Пример 2: Функция Майораны — МакФарланда

Функция \( f(x_1, \ldots, x_n) = \bigoplus_{i=1}^n x_i \cdot x_{i+1} \) (с циклическим переносом) обладает корреляционной иммунностью порядка 1 при \( n \ge 4 \). Её нелинейность растёт с увеличением \( n \), что делает её пригодной для использования в некоторых криптосистемах.

¶Источники

• Siegenthaler, T. (1984). "Correlation-immunity of nonlinear combining functions for cryptographic applications". IEEE Transactions on Information Theory, 30(5), 776–780.
• Canteaut, A., & Trabbia, M. (2000). "Improved fast correlation attacks using parity-check equations of weight 4 and 5". Advances in Cryptology — EUROCRYPT 2000.
• Carlet, C. (2010). "Boolean Functions for Cryptography and Error-Correcting Codes". In: Crama, Y., Hammer, P. (eds) Boolean Models and Methods in Mathematics, Computer Science, and Engineering.
• Menezes, A., van Oorschot, P., & Vanstone, S. (1996). "Handbook of Applied Cryptography". CRC Press.