Противодействие активным атакам

 

К сожалению, какого-либо универсального «противоядия» против описанных здесь методов воздействия на шифратор не существует. Однако, существенно усложнить проведение атак на основе сбоев против аппаратного шифратора можно, в частности, следующими способами [1]:

 

1. Внедрение в шифратор детекторов различных воздействий (напр., детекторов изменения напряжения, частоты питания и/или синхронизации, освещенности и т.д.), которые, при обнаружении воздействия выполняли бы блокировку шифратора.

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

3. Различные виды дублирования вычислений со сравнением результатов.

 

Для программных шифраторов также предлагаются методы защиты [1]:

 

1. Использование контрольного суммирования фрагментов данных с периодической проверкой в процессе вычислений или различные контрольные вычисления.

2. Дублирование вычислений со сравнением результатов.

3. Внедрение в программу случайных избыточных вычислений.

 

Ясно, что подобные методы приводят к удорожанию шифратора и/или снижению его быстродействия, однако, видно, что цель в данном случае оправдывает средства.

 

 

1. Bar-El H., Choukri H., Naccache D., Tunstall M., Whelan C. The Sorcerer’s Apprentice Guide to Fault Attacks. // http://citeseer.ist.psu.edu.

2. Biham E., Shamir A. Differential Cryptanalysis of DES-like Cryptosystems. // http://citeseer.ist.psu.edu. – The Weizmann Institute of Science – July 19, 1990.

3. Biham E., Shamir A. Differential Fault Analysis of Secret Key Cryptosystems. // http://citeseer.ist.psu.edu. – Technion – Israel Institute of Technology, Haifa, Israel – 1997.

4. Blomer J., Seifert J.-P. Fault Based Cryptanalysis of the Advanced Encryption Standard (AES). // http://wwwcs.uni-paderborn.de. – 2003.

5. Boneh D., DeMillo R.A., Lipton R.J.On the Importance of Checking Cryptographic Protocols for Faults. // http://citeseer.ist.psu.edu. – Bellcore, Morristown, NJ.

6. Dusart P., Letourneux G., Vivolo O. Differential Fault Analysis on A.E.S. // http://citeseer.ist.psu.edu. – 01/10/2002.

7. FIPS 46-3. Data Encryption Standard (DES). // http://csrc.nist.gov. – Reaffirmed 1999 October 25.

8. FIPS Publication 197. Specification for the Advanced Encryption Standard. // http://csrc.nist.gov – November 26, 2001.

9. Giraud C. DFA on AES. // http://citeseer.ist.psu.edu. – Oberthur Card Systems, Puteaux, France.

10. Merkle R.C. Method and Apparatus for Data Encryption. // http://www.freepatentsonline.com. – United State Patent № 5003597 – Mar. 26, 1991.

11. Preneel B., Biryukov A., Oswald E., Van Rompay B., Granboulan L., Dottax E., Murphy S., Dent A., White J., Dichtl M., Pyka S., Schafheutle M., Serf P., Biham E., Barkan E., Dunkelman O., Quisquater J.-J., Ciet M., Sica F., Knudsen L., Parker M., Raddum H. Public Report D20: NESSIE security report. // http://www.cosic.esat.kuleuven.be. – February 19, 2003 – Version 2.0.

12. Rivest R.L. The RC5 Encryption Algorithm. // http://citeseer.ist.psu.edu. – MIT Laboratory for Computer Sciense, Cambridge – Revised March 20, 1997.

13. Schneier B. Description of a new variable-length key 64-bit block cipher (blowfish). // http://www.schneier.com.

14. Skorobogatov S.P., Anderson R.J. Optical Fault Induction Attacks. // http://www.cl.cam.ac.uk. – 2002 – University of Cambridge, United Kingdom.

15. Панасенко С. Алгоритм шифрования DES и его варианты. // Connect! Мир связи. – 2006 - №№ 3, 4, 5, 7.

16. Панасенко С. Алгоритм шифрования FEAL. // Мир ПК. – 2006 - № 5 – приложение на компакт-диске «Мир ПК – диск».

17. Панасенко С. Алгоритм шифрования IDEA. // BYTE/Россия. – 2005 - № 12 – с. 78-79.

 

 

Об авторе:

Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.

С автором можно связаться: по телефонам (495)532-1313, (495)531-0000

или по E-mail [email protected]

http://www.panasenko.ru

 

 

Криптоаналитические атаки на связанных ключах

Опубликовано 20 апреля 2007 года

Подводя итог цикла статей, посвященных обзору современных криптоаналитических методов, и отдельной публикации по этой теме в разделе "Тактика", рассмотрим семейство атак на алгоритмы шифрования, использующих связанные ключи (related-keys attacks).

Расширение ключа

Для начала стоит сказать о том, что весьма редко встречаются алгоритмы шифрования, которые используют ключ шифрования (или его фрагменты) в «чистом» виде (таким алгоритмом является, например, отечественный стандарт шифрования ГОСТ 28147-89 [10]). Подавляющее большинство алгоритмов шифрования выполняет существенную модификацию исходного ключа шифрования для его последующего использования в процессе преобразований. Такая модификация называется расширением ключа (keyextension, keyschedule); существуют примеры алгоритмов, в которых процедура расширения ключа является исключительно сложной по сравнению с собственно шифрованием, среди них стоит упомянуть алгоритмы HPC и FROG (см. описание в [12] и [11]). Название процедуры проистекает из того факта, что исходный ключ шифрования обычно имеет размер существенно меньший совокупности подключей, используемых в раундах алгоритма, т.е. расширенного ключа.

Получается, что алгоритм шифрования можно логически разделить на два субалгоритма: собственно шифрующие преобразования и процедура расширения ключа – см. рис. 1.

 

Рис. 1 Назначение процедуры расширения ключа.

 

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

· Весьма желательно, чтобы процедура расширения ключа могла вычислять ключи «на лету» (on-the-fly), т.е. параллельно с шифрующими преобразованиями: это позволит как распараллеливать вычисления в многопроцессорных системах, так и не тратить память для хранения всего расширенного ключа при шифровании в условиях ограниченных ресурсов.

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

· Степень подверженности алгоритма атакам на связанных ключах также весьма зависит от процедуры расширения ключа.

 

«Классическая» атака на связанных ключах

 

«Классическая» атака на связанных ключах, предложенная Эли Бихамом (EliBiham) в работе [1], во многом похожа на сдвиговую атаку, описанную в 5-й части статьи «Современные методы вскрытия алгоритмов шифрования». Основное различие состоит в том, что сдвиговая атака использует два открытых текста P и P’, связанных между собой следующим соотношением:

P’ = F(P, k₁),

где F() – функция раунда, а k₁ – подключ 1-го раунда, тогда как атака на связанных ключах использует весьма похожее соотношение между ключами.

Итак, предположим, что искомый ключ шифрования K в результате его обработки процедурой расширения ключа Ex(K) дает следующую последовательность подключей:

Ex(K) = {k₁, k₂, …, k_r-1, k_r},

где r – количество раундов алгоритма шифрования.

Предположим также, что есть некий ключ K’, расширение которого дает следующую последовательность:

Ex(K’) = {k₂, k₃, …, k_r, k₁},

т.е. последовательность подключей, формируемая на основе ключа K’, циклически сдвинута относительна последовательности искомого ключа K на 1 раунд (см. рис. 2).

 

 

 

Рис. 2 Подключи в «классической» атаке на связанных ключах

 

Суть атаки состоит в следующем [1, 4]:

1. Снова предположим, что криптоаналитику известно 2 ^{n /2} пар (P, C) открытых текстов и соответствующих им шифртекстов (зашифрованных на искомом ключе K), где n – размер блока шифруемых данных в битах.

2. Кроме того, криптоаналитику известно столько же (2 ^{n /2}) пар текстов (P’, C’), полученных уже с использованием ключа K’, связанного с K приведенным выше соотношением.

3. Для каждого соотношения текстов (P, C) и (P’, C’) криптоаналитик решает систему уравнений:

F(P, k*) = P’,

F(C, k*) = C’.

Криптоаналитик не может знать заранее, какой из 2 ^{n /2} текстов P’ соответствует конкретному тексту P. Однако, вероятность того, что два случайных текста будут соответствовать требуемому соотношению, равна 2^{- n}; соответственно, согласно парадоксу дней рождения (см. часть 5 статьи «Современные методы вскрытия алгоритмов шифрования»), требуемая пара (P, P’) должна быть найдена в среднем после анализа не более, чем 2 ^{n /2 + 1} текстов.

Весьма вероятно, что некий ключ k*, удовлетворяющий приведенным выше уравнениям, и есть искомый подключ k₁. В зависимости от процедуры расширения ключа знание k₁ может дать криптоаналитику достаточно много информации о искомом ключе K. Например, расширение ключа алгоритма LOKI89 [3] построено таким образом, что k₁ представляет собой просто левую 32-битную половину ключа K, т.е. после вычисления k₁ для нахождения K достаточно хотя бы перебора всего 2³² вариантов.

Необходимое условие для проведения данной атаки состоит в том, что функция раунда F() атакуемого алгоритма должна быть достаточно слабой для вычисления k*, что, однако, можно сказать применительно к большинству современных алгоритмов шифрования.

В зависимости от структуры самого алгоритма шифрования, трудоемкость атаки может быть существенно меньше описанного выше общего случая. В частности, для алгоритмов, основанных на сбалансированной сети Фейстеля (см., например, [14]), раунд алгоритма модифицирует данные, например, следующим образом:

{L_i+1, R_i+1} = {R_i, L_iÅF(R_i)},

где L и R – соответственно, левая и правая половины обрабатываемого блока данных, а i – номер раунда. Ясно, что в этом случае поиск требуемых пар (P, P’) существенно упрощается [4].

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

 

Атакуемые алгоритмы

 

Вернемся к алгоритму LOKI89. Схема процедуры расширения ключа данного алгоритма приведена на рис. 3 (ключ также используется для входного и выходного отбеливания – наложения ключа на шифруемые данные до и после остальных преобразований, что не показано на рисунке; знаком <<< на рис. 3 обозначен циклический сдвиг влево на указанное число бит). Как видно из рисунка, все подключи нечетных раундов наследуют одни и те же биты левой половины ключа K; аналогично им, правая половина ключа формирует все подключи четных раундов.

Рис. 3 Процедура расширения ключа алгоритма LOKI89.

 

Чрезмерная простота процедуры расширения ключа делает алгоритм подверженным описанной выше атаке на основе связанных ключей [1]:

· Для успешной атаки на основе выбранных открытых текстов (см. часть 1 статьи «Современные методы вскрытия алгоритмов шифрования») требуется всего 2¹⁷ тестовых операций шифрования.

· В случае использования известных открытых текстов сложность атаки возрастает до порядка 2³² операций.

В следующей версии алгоритма LOKI – LOKI91 [2] – процедура расширения ключа была несколько модифицирована, однако, алгоритм остался подверженным «классической» атаке на связанных ключах: для ее осуществления требуется 2³² (выбранные открытые тексты) или 2⁴⁸ (известные открытые тексты) операций [1]. Еще одна атака, использующая слабость процедуры расширения ключа алгоритма LOKI91, была предложена Ларсом Кнудсеном (LarsKnudsen) в работе [8]

Согласно [1], данной атакой вскрывается также один из вариантов алгоритма Lucifer (подробное описание всех вариантов алгоритма Lucifer можно найти в [13]); для его вскрытия на основе выбранных открытых текстов требуется около 2³² операций.

Другой вариант атаки на связанных ключах описан в [7]. Атака использует весьма интересную особенность алгоритма шифрования SAFERK-64 [9]: для почти каждого ключа K существует ключ K’ (отличающийся от K значением одного байта), такой, что для достаточно большого множества открытых текстов (до 2²⁸ из возможных 2⁶⁴) после 6 раундов шифрования (SAFERK-64 выполняет 6 раундов и финальное преобразование данных) результаты шифрования каждого из текстов на ключах K и K’ абсолютно эквивалентны. Финальное преобразование делает результаты шифрования различными, но только в одном байте шифртекста. Данная особенность позволяет вычислить 8 бит 64-битного ключа шифрования алгоритма SAFERK-64 на основе от 2⁴⁴ до 2⁴⁷ выбранных открытых текстов.