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

В сентябре 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 различных значений).

Дата добавления: 2014-01-05