Дифференциальный криптоанализ: методы и история развития

Введение

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

История

Открытие дифференциального криптоанализа обычно приписывается Эли Бихаму и Ади Шамиру в конце 1980-х годов, которые опубликовали ряд атак против различных блочных шифров и хеш-функций, включая теоретическую уязвимость стандарта шифрования данных (DES). Бихам и Шамир отметили, что DES оказался на удивление устойчив к дифференциальному криптоанализу, но незначительные изменения в алгоритме сделали бы его гораздо более восприимчивым. В 1994 году Дон Копперсмит, член первоначальной команды IBM DES, опубликовал статью, в которой утверждал, что дифференциальный криптоанализ был известен IBM уже в 1974 году, и защита от него была одной из целей проектирования. По словам автора Стивена Леви, IBM открыла дифференциальный криптоанализ самостоятельно, а АНБ, по всей видимости, хорошо знала об этой технике. IBM сохраняла некоторые секреты, как объясняет Копперсмит: "После обсуждений с АНБ было решено, что раскрытие деталей проектирования раскроет технику дифференциального криптоанализа – мощный метод, который можно было бы использовать против многих шифров. Это, в свою очередь, ослабило бы конкурентное преимущество, которым Соединенные Штаты обладали над другими странами в области криптографии". Хотя DES разрабатывался с учетом устойчивости к дифференциальному криптоанализу, другие современные шифры оказались уязвимыми. Блок-шифр FEAL стал одной из первых целей для этой атаки. Изначально предложенная версия с четырьмя раундами (FEAL-4) может быть взломана, используя всего восемь выбранных открытых текстов, и даже 31-раундовая версия FEAL подвержена атаке. В отличие от этого, для успешного криптоанализа DES с помощью этой схемы требуется примерно 2<sup>47</sup> выбранных открытых текстов.

Механизм атаки

Дифференциальный криптоанализ обычно представляет собой атаку с выбранным открытым текстом, то есть злоумышленник должен иметь возможность получить шифротексты для некоторого набора открытых текстов по своему выбору. Однако существуют расширения, позволяющие проводить атаки на основе известного открытого текста или даже только шифротекста. Основной метод использует пары открытых текстов, связанных постоянной разностью. Разность можно определить несколькими способами, но обычно используется операция исключающего ИЛИ (XOR). Затем злоумышленник вычисляет разности соответствующих шифротекстов, надеясь обнаружить статистические закономерности в их распределении. Полученная пара разностей называется дифференциалом. Их статистические свойства зависят от природы S-блоков, используемых для шифрования, поэтому злоумышленник анализирует дифференциалы, где (и ⊕ обозначает исключающее ИЛИ) для каждого такого S-блока S. В базовой атаке ожидается, что одна конкретная разность шифротекстов будет встречаться особенно часто. Таким образом, шифр можно отличить от случайного. Более сложные варианты позволяют восстановить ключ быстрее, чем полным перебором. В самой простой форме восстановления ключа с помощью дифференциального криптоанализа злоумышленник запрашивает шифротексты для большого количества пар открытых текстов, а затем предполагает, что дифференциал сохраняется как минимум на r − 1 раундах, где r — общее количество раундов. Затем злоумышленник определяет, какие ключи раундов (для последнего раунда) возможны, предполагая, что разность между блоками перед последним раундом фиксирована. Если ключи раундов короткие, этого можно достичь, просто расшифровывая пары шифротекстов по одному раунду с каждым возможным ключом раунда. Если один ключ раунда считается потенциальным ключом раунда значительно чаще, чем любой другой ключ, то предполагается, что это правильный ключ раунда. Для любого конкретного шифра входная разность должна быть тщательно выбрана для успешной атаки. Проводится анализ внутренней структуры алгоритма; стандартный метод заключается в отслеживании пути высоковероятных разностей через различные этапы шифрования, называемого дифференциальной характеристикой. С тех пор как дифференциальный криптоанализ стал общеизвестным, он стал основной проблемой для разработчиков шифров. Ожидается, что новые разработки будут сопровождаться доказательствами устойчивости алгоритма к этой атаке, и многие из них, включая Advanced Encryption Standard, были признаны безопасными против неё.

Differential cryptanalysis is usually a chosen plaintext attack, meaning that the attacker must be able to obtain ciphertexts for some set of plaintexts of their choosing. There are, however, extensions that would allow a known plaintext or even a ciphertext only attack. The basic method uses pairs of plaintexts related by a constant difference. Difference can be defined in several ways, but the eXclusive OR (XOR) operation is usual. The attacker then computes the differences of the corresponding ciphertexts, hoping to detect statistical patterns in their distribution. The resulting pair of differences is called a differential. Their statistical properties depend upon the nature of the S boxes used for encryption, so the attacker analyses differentials where

(and ⊕ denotes exclusive or) for each such S box S. In the basic attack, one particular ciphertext difference is expected to be especially frequent. In this way, the cipher can be distinguished from random. More sophisticated variations allow the key to be recovered faster than an exhaustive search. In the most basic form of key recovery through differential cryptanalysis, an attacker requests the ciphertexts for a large number of plaintext pairs, then assumes that the differential holds for at least r − 1 rounds, where r is the total number of rounds. The attacker then deduces which round keys (for the final round) are possible, assuming the difference between the blocks before the final round is fixed. When round keys are short, this can be achieved by simply exhaustively decrypting the ciphertext pairs one round with each possible round key. When one round key has been deemed a potential round key considerably more often than any other key, it is assumed to be the correct round key. For any particular cipher, the input difference must be carefully selected for the attack to be successful. An analysis of the algorithm's internals is undertaken; the standard method is to trace a path of highly probable differences through the various stages of encryption, termed a differential characteristic. Since differential cryptanalysis became public knowledge, it has become a basic concern of cipher designers. New designs are expected to be accompanied by evidence that the algorithm is resistant to this attack and many including the Advanced Encryption Standard, have been proven secure against the attack.

Атака в деталях

Атака основывается прежде всего на том факте, что определенный шаблон разницы вход/выход встречается только для определенных значений входов. Обычно атака по сути применяется к нелинейным компонентам, как если бы они были твердотельными (чаще всего это таблицы поиска или S-блоки). Наблюдение за желаемой разностью выходных данных (между двумя выбранными или известными входными данными) позволяет предположить возможные значения ключа. Например, если дифференциал 1 => 1 (то есть разница в младшем значащем бите (LSB) входа приводит к разнице в LSB выхода) возникает с вероятностью 4/256 (что возможно для нелинейной функции в шифре AES, например), то этот дифференциал возможен только для 4 значений (или 2 пар) входов. Предположим, у нас есть нелинейная функция, в которой ключ применяется операцией XOR перед вычислением, а значения, позволяющие получить дифференциал, равны {2, 3} и {4, 5}. Если злоумышленник отправляет значения {6, 7} и наблюдает правильную разность выходных данных, это означает, что ключ либо 6 ⊕ K = 2, либо 6 ⊕ K = 4, то есть ключ K равен либо 2, либо 4. По сути, для защиты шифра от атаки для n-битной нелинейной функции желательно стремиться к значению, максимально приближенному к 2−(n − 1), чтобы достичь дифференциальной однородности. В этом случае дифференциальная атака потребует столько же вычислительных ресурсов для определения ключа, сколько и простой перебор. Нелинейная функция AES имеет максимальную дифференциальную вероятность 4/256 (большинство записей, однако, равны либо 0, либо 2). Это означает, что теоретически ключ можно определить за половину времени, необходимого для перебора, однако высокая степень разветвления AES предотвращает существование высоковероятных путей на нескольких раундах. Фактически, шифр AES был бы столь же устойчив к дифференциальным и линейным атакам, даже если бы использовал гораздо более слабую нелинейную функцию. Невероятно высокая степень разветвления (количество активных S-блоков) – 25 на 4R – означает, что за 8 раундов ни одна атака не включает менее 50 нелинейных преобразований, а это значит, что вероятность успеха не превышает Pr[атака] ≤ Pr[лучшая атака на S-блок]50. Например, при текущем S-блоке AES не генерирует фиксированный дифференциал с вероятностью выше (4/256)50 или 2−300, что значительно ниже требуемого порога 2−128 для 128-битного блочного шифра. Это позволило бы использовать более эффективный S-блок, даже если бы он был 16-однородным, вероятность атаки все равно была бы 2−200. Биекций для входов/выходов одинакового размера с однородностью 2 не существует. Они существуют в нечетных полях (например, GF(27)) с использованием кубирования или инверсии (можно использовать и другие показатели). Например, S(x) = x3 в любом нечетном двоичном поле невосприимчив к дифференциальному и линейному криптоанализу. Именно поэтому в конструкциях MISTY используются 7- и 9-битные функции в 16-битной нелинейной функции. Эти функции выигрывают в устойчивости к дифференциальным и линейным атакам, но проигрывают в устойчивости к алгебраическим атакам, то есть их можно описать и решить с помощью SAT-решателя. Именно поэтому AES (например) имеет аффинное преобразование после инверсии.

The attack relies primarily on the fact that a given input/output difference pattern only occurs for certain values of inputs. Usually the attack is applied in essence to the non linear components as if they were a solid component (usually they are in fact look up tables or S boxes). Observing the desired output difference (between two chosen or known plaintext inputs) suggests possible key values. For example, if a differential of 1 => 1 (implying a difference in the least significant bit (LSB) of the input leads to an output difference in the LSB) occurs with probability of 4/256 (possible with the non linear function in the AES cipher for instance) then for only 4 values (or 2 pairs) of inputs is that differential possible. Suppose we have a non linear function where the key is XOR'ed before evaluation and the values that allow the differential are {2,3} and {4,5}. If the attacker sends in the values of {6, 7} and observes the correct output difference it means the key is either 6 ⊕ K = 2, or 6 ⊕ K = 4, meaning the key K is either 2 or 4. In essence, to protect a cipher from the attack, for an n bit non linear function one would ideally seek as close to 2−(n − 1) as possible to achieve differential uniformity. When this happens, the differential attack requires as much work to determine the key as simply brute forcing the key. The AES non linear function has a maximum differential probability of 4/256 (most entries however are either 0 or 2). Meaning that in theory one could determine the key with half as much work as brute force, however, the high branch of AES prevents any high probability trails from existing over multiple rounds. In fact, the AES cipher would be just as immune to differential and linear attacks with a much weaker non linear function. The incredibly high branch (active S box count) of 25 over 4R means that over 8 rounds, no attack involves fewer than 50 non linear transforms, meaning that the probability of success does not exceed Pr[attack] ≤ Pr[best attack on S box]50. For example, with the current S box AES emits no fixed differential with a probability higher than (4/256)50 or 2−300 which is far lower than the required threshold of 2−128 for a 128 bit block cipher. This would have allowed room for a more efficient S box, even if it is 16 uniform the probability of attack would have still been 2−200. There exist no bijections for even sized inputs/outputs with 2 uniformity. They exist in odd fields (such as GF(27)) using either cubing or inversion (there are other exponents that can be used as well). For instance, S(x) = x3 in any odd binary field is immune to differential and linear cryptanalysis. This is in part why the MISTY designs use 7 and 9 bit functions in the 16 bit non linear function. What these functions gain in immunity to differential and linear attacks, they lose to algebraic attacks. That is, they are possible to describe and solve via a SAT solver. This is in part why AES (for instance) has an affine mapping after the inversion.