Дифференциальный анализ на основе сбоев

Основоположниками атак на основе ошибок являются три специалиста американской компании Bellcore: Дэн Боне (DanBoneh), Ричард ДеМилло (RichardDeMillo) и Ричард Липтон (RichardLipton). В своей работе [5], вышедшей в 1996 г., они предложили данный вид атак и описали некоторые из возможных атак на основе ошибок на ряд асимметричных криптосистем.

Предложенную в [5] идею существенно развили и распространили на алгоритмы симметричного шифрования известнейшие израильские криптоаналитики Эли Бихам (EliBiham) и Эди Шамир (AdiShamir), которые в своей работе [3] предложили дифференциальный криптоанализ на основе сбоев (differentialfaultanalysis, DFA).

Рис 2. Структура алгоритма DES.

Бихам и Шамир в качестве атакуемого алгоритма выбрали DES, однако впоследствии данная атака была распространена на другие алгоритмы шифрования (об этом – ниже). Суть атаки на DES методом дифференциального криптоанализа на основе сбоев состоит в следующем:

1. Предполагается, что в процессе шифрования возникает инверсия одного бита в правой части регистра, содержащего текущее значение шифруемого блока данных (т.е. в B_i – см. рис. 2; более подробное описание алгоритма DES см. в части 3 статьи «Современные методы вскрытия алгоритмов шифрования»). Точное расположение бита, в котором возникает сбой, а также номер раунда, в процессе которого бит инвертируется, атакующему не известны. Кроме того, авторы атаки не конкретизируют воздействие на шифратор, приводящее к данному сбою.

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

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

· если ошибка возникла в раунде 16, то в правой половине шифртекстов будет различаться только 1 бит (здесь и далее не принимается в расчет финальная перестановка), в левой же различаться будут биты, соответствующие выходным битам той таблицы замен, входное значение которой содержит ошибочный бит (таких таблиц может быть и две);

· ошибка в раунде 15 также достаточно легко определяется: в этом случае различия в правой половине шифртекстов (которые аналогичны различиям в их левой половине в случае, если ошибка возникла в раунде 16) состоят в битах, соответствующих выходным битам одной или двух таблиц замен; проанализировав различия в левой и правой частях шифртекстов, достаточно легко определить, действительно ли ошибка возникла в раунде 15;

· несколько сложнее, но возможно определить случай, когда ошибка возникает в раунде 14;

· в случае, если ошибка возникает в более ранних раундах, данная пара шифртекстов является непригодной для анализа и отбрасывается.

4. К полученным шифртекстам применяется технология дифференциального криптоанализа (см. [2] и часть 3 статьи «Современные методы вскрытия алгоритмов шифрования»). Наиболее простой вариант возникает в случае, если сбой возник в 16 раунде: дифференциальный криптоанализ позволяет легко вычислить значения 6 бит ключа последнего раунда, т.е. K₁₆.

5. Для нахождения значений остальных бит K₁₆ аналогичным образом «прогоняются» через шифратор и анализируются дополнительные тексты. Согласно [3], для полного вычисления ключа последнего раунда достаточно от 50 до 200 шифртекстов.

6. Согласно процедуре расширения ключа алгоритма DES [7], K₁₆ содержит 48 из 56 бит исходного ключа шифрования алгоритма DES. Остальные биты можно легко вычислить перебором возможных 256 вариантов или анализом отброшенных ранее шифртекстов с ошибками на более ранних раундах.

Как видно, для данной атаки требуется несравнимо меньше данных, чем для собственно дифференциального криптоанализа алгоритма DES и других алгоритмов (см. часть 4 статьи «Современные методы вскрытия алгоритмов шифрования»). Однако, модель атаки является достаточно строгой и сложно реализуемой на практике. Тем не менее, данный метод криптоанализа является весьма мощным по сравнению с многими из рассмотренных ранее. А в работе [3] Бихам и Шамир продемонстрировали, как дифференциальный криптоанализ на основе сбоев может быть распространен на другие модели атак.

Помимо DES, Бихам и Шамир перечислили в работе [3] несколько алгоритмов, подверженных дифференциальному криптоанализу на основе сбоев: IDEA (см. описание в [17]), RC5 [12], FEAL (см. описание в [16]), Khufu и Khafre [10], Blowfish [13], а также TripleDES и DES с независимыми подключами (см. описание в [15]). Несколько видов атак данным методом предложено, например, в [4], [6] и [9] против текущего стандарта шифрования США – алгоритма AES [8].