Piling-up lemma

Piling-up lemma (также известный как лемма о накоплении, лемма Мацуи) — это фундаментальное утверждение в области линейного криптоанализа, используемое для оценки смещения (bias) линейного приближения для суммы (XOR) нескольких независимых случайных двоичных переменных. Лемма позволяет криптоаналитику, зная смещения для отдельных частей шифра (например, S-блоков), вычислить смещение для комбинации этих частей, что является ключевым шагом при построении линейных атак на блочные шифры.

История и происхождение

Лемма была впервые сформулирована и применена японским криптографом Мицуру Мацуи в 1993 году в его работе по линейному криптоанализу шифра FEAL. Мацуи использовал её для построения эффективных линейных аппроксимаций, которые позволили вскрыть FEAL-4, FEAL-6 и FEAL-8. В 1994 году он же применил лемму для атаки на шифр DES, что стало одной из первых практических демонстраций линейного криптоанализа. С тех пор лемма является стандартным инструментом в арсенале криптоаналитика.

Формулировка

Пусть \(X_1, X_2, \dots, X_n\) — независимые случайные двоичные переменные (принимающие значения 0 или 1). Для каждой переменной \(X_i\) определим смещение \(\epsilon_i\) как отклонение вероятности того, что \(X_i = 0\), от значения 0,5:

\[ \epsilon_i = P(X_i = 0) - \frac{1}{2} \]

Тогда лемма утверждает, что смещение \(\epsilon_{1,2,\dots,n}\) для суммы по модулю 2 (XOR) этих переменных \(X_1 \oplus X_2 \oplus \dots \oplus X_n\) вычисляется по формуле:

\[ \epsilon_{1,2,\dots,n} = 2^{n-1} \prod_{i=1}^{n} \epsilon_i \]

Или, что эквивалентно, вероятность того, что сумма равна 0, равна:

\[ P(X_1 \oplus X_2 \oplus \dots \oplus X_n = 0) = \frac{1}{2} + 2^{n-1} \prod_{i=1}^{n} \epsilon_i \]

Пример для двух переменных

Для двух независимых переменных \(X_1\) и \(X_2\) с смещениями \(\epsilon_1\) и \(\epsilon_2\):

\[ P(X_1 \oplus X_2 = 0) = \frac{1}{2} + 2 \epsilon_1 \epsilon_2 \]

Это следует из того, что \(P(X_1 \oplus X_2 = 0) = P(X_1 = X_2) = P(X_1=0)P(X_2=0) + P(X_1=1)P(X_2=1)\). Подставляя \(P(X_i=0) = 1/2 + \epsilon_i\) и \(P(X_i=1) = 1/2 - \epsilon_i\), получаем указанный результат.

Доказательство

Доказательство леммы проводится методом математической индукции по числу переменных \(n\).

База индукции (\(n=1\)): Формула тривиально верна, так как \(\epsilon_1 = 2^{1-1} \epsilon_1 = \epsilon_1\).

Индукционный переход: Предположим, что утверждение верно для \(n-1\) переменных. Рассмотрим сумму \(S = X_1 \oplus \dots \oplus X_{n-1}\) и переменную \(X_n\). По предположению, смещение \(S\) равно \(\epsilon_S = 2^{n-2} \prod_{i=1}^{n-1} \epsilon_i\). Тогда для суммы \(S \oplus X_n\) применяем формулу для двух переменных:

\[ \epsilon_{S \oplus X_n} = 2 \epsilon_S \epsilon_n = 2 \cdot \left(2^{n-2} \prod_{i=1}^{n-1} \epsilon_i\right) \cdot \epsilon_n = 2^{n-1} \prod_{i=1}^{n} \epsilon_i \]

Что и требовалось доказать.

Применение в линейном криптоанализе

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

1. Анализ S-блоков: Для каждого S-блока шифра вычисляются смещения для всех возможных линейных аппроксимаций (входных и выходных масок). Это даёт набор \(\epsilon_i\) для отдельных нелинейных преобразований.

1. Построение линейного пути: Криптоаналитик выбирает последовательность линейных аппроксимаций для нескольких раундов шифра так, чтобы они соединялись через промежуточные биты. Каждая аппроксимация даёт своё смещение.

1. Применение леммы: Если аппроксимации на разных раундах независимы (что является ключевым предположением), то общее смещение для всего пути вычисляется как произведение смещений отдельных аппроксимаций, умноженное на \(2^{n-1}\), где \(n\) — количество аппроксимаций.

1. Атака: Полученное смещение используется для различения правильного ключа от случайного. Обычно требуется около \(1/\epsilon^2\) пар открытый текст — шифротекст для успешной атаки.

Пример: атака на DES

В своей знаменитой атаке на DES Мацуи использовал 14-раундовую линейную аппроксимацию с смещением около \(1.22 \times 10^{-11}\). Для этого потребовалось около \(2^{43}\) пар открытый текст — шифротекст. Лемма позволила ему вычислить это смещение, комбинируя смещения от S-блоков DES, каждое из которых было порядка \(1/4\) или \(1/8\).

Ограничения и критика

Лемма основана на предположении о независимости переменных. В реальных шифрах это предположение часто нарушается, особенно при большом числе раундов. На практике криптоаналитики используют лемму как приближение, а затем проверяют результаты экспериментально. Кроме того:

• Корреляция между раундами: Если аппроксимации на разных раундах коррелированы, лемма даёт завышенную оценку смещения.
• Неравномерное распределение: В некоторых шифрах (например, с использованием арифметических операций вместо S-блоков) смещения могут быть непостоянными или трудно вычислимыми.
• Вычислительная сложность: Для шифров с большим числом раундов или сложной структурой число возможных путей растёт экспоненциально, что делает полный перебор непрактичным.

Модификации и обобщения

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

Значение для криптографии

Piling-up lemma является одним из краеугольных камней линейного криптоанализа — одного из двух основных методов атак на симметричные шифры (наряду с дифференциальным криптоанализом). Её открытие привело к пересмотру стандартов проектирования шифров: разработчики стали уделять больше внимания устойчивости к линейным атакам, что выразилось в появлении таких шифров, как AES (Rijndael), который был специально спроектирован так, чтобы минимизировать смещения в S-блоках. Лемма также используется в анализе хеш-функций и генераторов псевдослучайных чисел.

Источники

• Matsui, M. (1993). "Linear Cryptanalysis Method for DES Cipher". Advances in Cryptology — EUROCRYPT '93.
• Matsui, M. (1994). "The First Experimental Cryptanalysis of the Data Encryption Standard". Advances in Cryptology — CRYPTO '94.
• Heys, H. M. (2002). "A Tutorial on Linear and Differential Cryptanalysis". Cryptologia, 26(3), 189–221.
• Stinson, D. R. (2005). "Cryptography: Theory and Practice" (3rd ed.). Chapman & Hall/CRC.