Дифференциальный криптоанализ на основе отказов устройства

В сентябре 1996 г. группа специалистов из компании Bellcore объявила о новом методе крип­тоанализа, позволяющем эффективно раскрывать секретный ключ, хранящийся в памяти портативного шифрующего/дешифрующего устройства, например Smart Card или PCMCIA. Сохранность ключа в подобных устройствах обеспечивается за счет уникальных характери­стик технологии TEMPEST. Впервые метод был успешно применен для раскрытия клю­ча криптосистемы RSA. Дальнейшие исследования нового метода, получившего название дифференциального криптоанализа на основе сбоев устройства (Differential Fault Analysis, DFA), продемонстрировали его эффективность при атаке на DES и другие блочные шиф­ры. Так, для раскрытия ключа DES понадобилось проанализировать двести шифротекстов. полученных в результате шифрования открытых текстов, хранящихся в памяти устройства. Показано, что применение тройного DES-шифрования не влияет на трудоемкость атаки.

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

Рассмотрим описанный метод на примере криптоанализа DES. Предположим, что имеет­ся два различных шифротекста, полученных при шифровании одного и того же открытого текста на фиксированном ключе. Известно, какой шифротекст получен в результате инвер­сии одиночного бита в процессе шифрования. Под инверсией подразумевается следующее: бит правой половины входного блока на одном из 16 циклов DES-преобразования меняет исходное значение 0 на значение 1, или наоборот. Причем позиция бита и номер цикла пре­образования выбираются случайно и имеют равномерное распределение.

На первом этапе атаки необходимо установить номер цикла преобразования, на котором произошла инверсия. Предположим, что инверсия произошла на последнем, шестнадцатом цикле DES-преобразования. Если инверсия произошла в правой половине блока (до заключи­тельной перестановки), то два шифротекста будут различаться в одном бите, локализован­ном в правой половине блока. Различие левых половин блоков шифротекста определяется выходами тех S-блоков (одного или двух), на входе которых появился инвертированный бит. Применение метода дифференциального криптоанализа позволяет раскрыть шесть бит клю­ча для каждого такого S-блока.

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

Для раскрытия подключа последнего цикла преобразования достаточно проанализиро­вать менее двухсот шифротекстов. Дальнейшее развитие атаки возможно в двух направле­ниях. Первый вариант - поиск секретного ключа путем исчерпывающей проверки 2⁸ = 256 кандидатов при заданном подключе (напомним, что разрядность подключа — 48 бит). Альтернативный вариант заключается в использовании знания о подключе, полученного на по­следнем цикле, для анализа предшествующих циклов. Последний вариант позволяет успешно атаковать DES в режиме EDE-шифрования на трех различных ключах.

Описанный метод работает и в тех случаях, когда инверсия возникает внутри F-функции или процедуры генерации подключей.

Метод дифференциального криптоанализа на основе отказов устройства можно приме­нять для атаки на такие блочные шифры, как IDEA, RC5 и Feal. Некоторые блочные шифры, например Khufu, Khafre и Blowfish, используют заданный секретный ключ для генерации S-блоков. В этом случае описанный метод позволяет раскрывать не только ключи, но и сами S-блоки.

Рассмотренный выше криптоаналитический метод позволяет эффективно раскрывать секретный ключ, хранящийся в памяти устройства, даже тогда, когда сам алгоритм крипто­графического преобразования неизвестен. Так, например, детали криптоалгоритма Skipjack составляют государственную тайну и засекречены Агентством национальной безопасности США. Однако аппаратная реализация криптоалгоритма в виде микросхемы Clipper входит в состав многих коммерческих устройств шифрования, например Fortezza PCMCIA.

Предполагается, что криптографические ключи хранятся в памяти с асимметричной ди­намикой сбоев. Это означает, например, что переход из состояния 1 в состояние 0 происходит с большей вероятностью, чем противоположное событие. Ячейки CMOS имеют симметричную динамику сбоев — все переходы равновероятны. Однако для некоторых видов энергонезави­симой памяти это не так. Например, при воздействии ультрафиолетового излучения ячейки EEPROM памяти принимают значение 0 с большей вероятностью, чем значение 1.

Предполагается также, что в криптографическое устройство можно вводить некоторый открытый текст m и в результате шифрования на ключе k, хранящемся в энергонезависимой памяти, получать на выходе шифротекст с. Поскольку память открыта на запись (но закры­та на чтение), в устройство можно ввести новый n-битный ключ k' вместо старого ключа k. Еще раз отметим, что основная задача криптоаналитика сводится не к дешифрованию некоторого шифротекста (сделать это очень просто, так как имеется доступ к соответству­ющему устройству), а к раскрытию секретного ключа, хранящегося в памяти устройства шифрования/дешифрования.

Криптоаналитическая атака включает два этапа:

1) на первом этапе неизвестный секретный ключ k, хранящийся в памяти устройства, ис­пользуется для серии шифрований фиксированного открытого текста m₀. После каждо­го шифрования устройство подвергается облучению. В результате последовательность шифротекстов на выходе устройства будет состоять из нескольких различных подпосле­довательностей c_o,c₁,c₂,...,c_f. Изменение шифротекста - переход от с_i к c_i+1 - обу­словлено направленной инверсией (из 1 в 0) некоторых бит ключа, иными словами - заменой ключа k_i на k_i+1, k_i ¹ k_i+1. Поскольку wt(k) @ n/2, можно предположить что f @ n/2 и шифротекст c_f представляет собой результат шифрования m₀ на нулевом ключе k_f. Отсутствие изменений в шифротексте после облучения — естественный
признак вырождения ключа до нулевого состояния;

2) на втором этапе выполняется восстановление исходного секретного ключа k₀ по нуле­вому ключу k_f. Пусть известен некоторый промежуточный ключ k_i+1, тогда, согласно модели сбоев, разумно предположить, что ключ k_f, отличается от k_i+1 в одной позиции, wt(k_i Å k_i+1) = 1. Тогда для раскрытия ключа k_i достаточно зашифровать m₀ на последовательности ключей k^‘_i+1, получаемых из k_i+1, последовательной заменой единиц на нули. Если результат шифрования равен с_i - ключ восстановлен.

Так как алгоритм шифрования неизвестен, то для проверки ключей придется воспользо­ваться устройством шифрования. Как было отмечено выше, устройство позволяет вводить различные ключи. Следовательно, для восстановления неизвестного ключа k₀ по известному k_f понадобится проверить О(n) ключей на каждом из О(n) шагов. Таким образом, трудоем­кость метода оценивается как О(n²) операций шифрования.

Помимо раскрытия секретного ключа, хранящегося в памяти устройства шифрования/де­шифрования, можно попытаться решить и более сложную задачу - идентифицировать неиз­вестный криптоалгоритм, включая определение функций цикла, 5-блоки и подключи.

Рассмотрим метод идентификации исходя из предположения, что реализованный в ус­тройстве криптоалгоритм соответствует конструкции Фейстеля.

Вначале необходимо установить, какие биты шифротекста получены в результате обра­ботки правого, а какие — левого подблока на последнем цикле криптографического преобра­зования. Для этого необходимо выполнить серию шифрований некоторого открытого текста В процессе шифрования устройство подвергают облучению, что приводит согласно описан­ной выше модели сбоев к инверсии некоторых битов. Анализ расстояния Хэмминга пары шифротекстов — искаженного и неискаженного — позволяет установить позиции бит, инвер­тированных на последнем или предпоследнем цикле преобразования. В качестве критерия для выбора шифротекстов используется некоторое пороговое значение, как правило, не пре­вышающее четверти размера блока. Таким образом, искаженные шифротексты, для которых расстояние Хэмминга пары не превышает заданного порогового значения, получены в резуль­тате сбоя на последнем или предпоследнем цикле преобразования. Сбой на последнем цикле приводит к изменению одного бита в правом и нескольких бит в левом подблоке. В 32-битном подблоке возможно не более 32 инверсий. Следовательно, для анализа понадобится не более 32 искаженных шифротекстов. Искаженные шифротексты, полученные в результате сбоя на последнем цикле, будут различаться в одном бите в правом подблоке и нескольких битах в левом подблоке.

После определения бит правого и левого подблоков можно установить их функциональ­ную зависимость. Предположим, что в криптоалгоритме применяется F-функция, состоящая из набора S-блоков. Некоторые биты правого подблока поступают на вход S-блока: выход­ное значение формирует биты левого подблока. Для определения входных и выходных бит, а также номера каждого S-блока достаточно выбрать все пары шифротекстов, различаю­щихся в одном бите в правом подблоке. Информации о различиях в левых подблоках для каждого номера позиции в правом подблоке достаточно для определения номеров S-блоков, их размеров, а также входных и выходных битов.

Содержимое S-блоков можно восстановить, построив таблицу Т(х) = S(x Å k) Å u, где k — подключ, а неизвестное значение u получено из правого подблока предыдущего цикла. Например, если в качестве неизвестного криптоалгоритма используется DES, можно восста­новить содержимое S-блоков, за исключением 6 + 4 = 10 из 64 х 4 = 256 неизвестных бит в каждом блоке. Для LOKI удается восстановить 2¹² х 8 - (12 + 8) = 32 748 неизвестных бит в каждом блоке. Недостающие биты могут быть восстановлены в результате обработки данных, полученных на последнем цикле преобразования. Описанный метод позволяет восстановить не сами S-блоки, а их сумму по модулю 2 (операция XOR) с подключами. Восстановле­ние S-блоков и подключей возможно путем анализа отличий результатов шифрования на нескольких ключах и данных из таблицы Т. Описанный метод был успешно применен для реконструкции S-блоков и алгоритма генерации подключей для DES и LOKI.

В некоторых блочных шифрах нелинейная функция F может быть реализована не в виде набора констант — S-блоков (как в DES и LOKI), а как последовательность различ­ных арифметических операций, сдвигов, логических операций И, ИЛИ, НЕ и т.д. Подобные функции также поддаются восстановлению. Можно восстановить F-функцию более общего вида с произвольно заданной операцией суммирования (XOR) правой половины бит подключа и некоторой функцией на выходе. В целях упрощения анализа можно интерпретировать такую F-функцию как один большой S-блок. Несмотря на высокую трудоемкость, задача восстановления такого S-блока практически реализуема — число входных и выходных бит S-блока не превышает половины размера блока шифротекста. Эффективность такого под­хода очевидна — другой метод идентификации блочного шифра на основе исчерпывающего перебора известных шифров и возможных ключей имеет практически неограниченную тру­доемкость. Описанная атака применялась для идентификации DES в качестве неизвестного блочного шифра. Для идентификации бит правой половины, а также входных и выходных бит и содержимого S-блоков потребовалось проанализировать около пятисот и пяти тысяч искаженных шифротекстов соответственно. Для восстановления входных значений S-блоков потребовалось проанализировать около десяти тысяч искаженных шифротекстов.

Отметим, что трудоемкость восстановления содержимого S-блоков существенно зависит от их размеров. Поскольку S-блок DES имеет 6-битный вход, то для его реконструкции до­статочно проанализировать не более 64 входных значений, полученных из искаженных бло­ков шифротекста. Трудоемкость аналогичной реконструкции для LOKI значительно выше — S -блоки имеют 12-битный вход (4096 различных значений).