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

Основоположниками атак на основе сбоев являются три специалиста американской компании Bellcore: Дэн Боне (Dan Boneh), Ричард ДеМилло (Richard DeMillo) и Ричард Липтон (Richard Lipton). В своей работе, вышедшей в 1996 г., они предложили данный вид атак и описали некоторые из возможных атак на основе сбоев на ряд асимметричных криптосистем.

Предложенную в идею существенно развили и распространили на алгоритмы симметричного шифрования известнейшие израильские криптоаналитики Эли Бихам и Эди Шамир, которые в своей работе предложили дифференциальный криптоанализ на основе сбоев (differential fault analysis, DFA).

Бихам и Шамир в качестве атакуемого алгоритма выбрали DES, однако впоследствии данная атака была распространена на другие алгоритмы шифрования. Предполагается, что в процессе шифрования возникает инверсия одного бита в правой части регистра, содержащего текущее значение шифруемого блока данных. Точное расположение бита, в котором возникает сбой, а также номер раунда, в процессе которого бит инвертируется, атакующему не известны. Кроме того, авторы атаки не конкретизируют воздействие на шифратор, приводящее к подобному сбою.

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

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

К полученным шифртекстам применяется технология дифференциального криптоанализа. Наиболее простой вариант возникает в случае, если сбой возник в раунде 16: дифференциальный криптоанализ позволяет легко вычислить значения 6 битов ключа последнего раунда.

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

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

Как видно, для атаки на основе сбоев требуется несравнимо меньше данных, чем для собственно дифференциального криптоанализа алгоритма DES и других алгоритмов. Однако модель атаки является достаточно строгой и сложно реализуемой на практике. Тем не менее, этот метод криптоанализа является весьма мощным по сравнению со многими из рассмотренных ранее. А в работе Бихам и Шамир продемонстрировали, как дифференциальный криптоанализ на основе сбоев может быть распространен на другие модели атак.

Помимо DES, Бихам и Шамир перечислили в работе несколько алгоритмов, подверженных дифференциальному криптоанализу на основе сбоев: IDEA, RC5 FEAL, Khufu и Khafre, Blowfish, а также Triple DES и DES с независимыми подключами. Несколько видов атак данным методом предложено, против текущего стандарта шифрования США — алгоритма AES.

По материалам книги Сергея Панасенко «Алгоритмы шифрования»

Алгоритмы шифрования