Алгоритмы, вскрываемые дифференциальным криптоанализом

Если дифференциальный криптоанализ и был известен еще в середине 1970-х гг. (см. предыдущую часть статьи), то явно не всем разработчикам алгоритмов шифрования – многие из более поздних алгоритмов подвержены данному методу их вскрытия. Рассмотрим наиболее показательные примеры:
1. Известный алгоритм RC2 [18] вскрывается дифференциальным криптоанализом при наличии 259 выбранных открытых текстов [10] (см. первую часть статьи).

 2.     Не менее известный и широко используемый алгоритм RC5 (а именно, его основной вариант – RC5-32/12/16) [19] еще менее стоек к дифференциальному криптоанализу – он вскрывается при наличии 2⁴⁴ выбранных открытых текстов [3]. Существуют и другие варианты алгоритма RC5, также подверженные дифференциальному криптоанализу – подробности см. в [24].

3.     «Ускоренный» вариант алгоритма ICE – Thin-ICE [12] – вскрывается с вероятностью 25% при наличии 2²³ выбранных открытых текстов; при увеличении числа текстов до 2²⁷ вероятность вскрытия алгоритма возрастает до 95% [21].

4.     Один из вариантов алгоритма DES – Generalized DES (GDES) [25] с 16 раундами и размером блока 256 бит – вскрывается при наличии всего 6 (!) выбранных открытых текстов [1]. Некоторые другие варианты алгоритма DES (DESX, DES с независимыми подключами, s²DES и др.) также подвержены дифференциальному криптоанализу – подробности см. в [23].

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

 Линейный криптоанализ

Линейный криптоанализ изобрел японский криптолог Мицуру Мацуи (Mitsuru Matsui). Предложенный им в 1993 г. метод изначально был направлен на вскрытие алгоритма DES [15], описанного в предыдущей части статьи. Впоследствии линейный криптоанализ был распространен и на другие алгоритмы [17][1].

Смысл линейного криптоанализа состоит в нахождении соотношений следующего вида [15, 25]:

P_i1 Å P_i2 Å … Å P_ia Å C_j1 Å C_j2 Å … Å C_jb = K_k1 Å K_k2 Å … Å K_kc,     (1)

где P_n, C_n и K_n – n-е биты открытого текста, шифртекста и ключа соответственно.

Для произвольно выбранных бит открытого текста, шифртекста и ключа вероятность P справедливости такого соотношения составляет около ½. В том случае, если криптоаналитику удается найти такие биты, при которых вероятность P заметно отличается от ½, данным соотношением можно воспользоваться для вскрытия алгоритма.

Так же, как и в дифференциальном криптоанализе, сначала криптоаналитик находит некое однораундовое соотношение, затем пытается распространить его на большее число раундов, в результате находит соотношение для полнораундового варианта анализируемого алгоритма. Стоит отметить, что, в отличие от дифференциального криптоанализа, существуют алгоритмы поиска полезных соотношений; два подобных алгоритма изначально были описаны Мицуру Мацуи в [15], другие появились позже (см., например, [6]).

Рис 1.        Наиболее эффективное однораундовое соотношение для алгоритма DES.

На рис. 1 представлено наиболее эффективное однораундовое соотношение для алгоритма DES [15, 25]. Данное соотношение использует то свойство таблицы S5, что второй входной бит таблицы равен результату применения операции XOR над всеми 4-мя выходными битами с вероятностью 3/16 (т.е. смещение в 5/16 относительно вероятности ½), т.е. (применяя нотацию, использованную в предыдущей части статьи):

(bk₅)₂ = (bs₅)₁ Å (bs₅)₂ Å (bs₅)₃ Å (bs₅)₄,

что эквивалентно

bk₂₆ = bs₁₇ Å bs₁₈ Å bs₁₉ Å bs₂₀.     (2)

Шнайер в [25] пишет, что данное свойство таблицы S5 заметил еще Эди Шамир в 1985 г., однако, именно Мацуи удалось его использовать для атаки на алгоритм. Дальнейшее расширение данного свойства таково:

1.     Как показано на рис. 1, соотношение (2) распространяется на целый раунд алгоритма; в результате чего (с учетом перестановок) получается следующее однораундовое соотношение:

b₁₇ Å bp₃ Å bp₈ Å bp₁₄ Å bp₂₅ = (K_i)₂₆,

где i – номер раунда.

Рис 2.        Пример трехраундового соотношения.

2.     Весьма похоже на дифференциальный криптоанализ соотношение распространяется на несколько раундов. Пример такого соотношения показан на рис. 2 (соотношение (1) справедливо для тех бит, номера которых указаны на рисунке); его вероятность смещена относительно ½ на 0,0061 [25]. А для полнораундового DES известно соотношение, выполняющееся с вероятностью ½ + 2^-24 [2].

3.     С использованием максимально эффективного соотношения выполняется анализ имеющихся пар «открытый текст – шифртекст» с целью найти наиболее вероятные значения определенных бит ключа шифрования.

Весьма часто линейный криптоанализ используется в совокупности с атакой методом «грубой силы» (см. часть 2 статьи) – определенные биты ключа находятся с помощью линейного криптоанализа, после чего выполняется исчерпывающий поиск по возможным значениям остальных бит. Подобным образом алгоритм DES вскрывается при наличии 2⁴³ известных открытых текстов, что существенно эффективнее дифференциального криптоанализа [16, 25].

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

Линейный криптоанализ имеет одно весьма полезнейшее свойство: при определенных обстоятельствах соотношение (1) может быть преобразовано к следующему:

C_j1 Å C_j2 Å … Å C_jb = K_k1 Å K_k2 Å … Å K_kc.

В данном соотношении полностью отсутствуют биты открытого текста, т.е. с помощью линейного криптоанализа можно построить атаку на основе только шифртекста (см. первую часть статьи), что еще больше расширяет область применения линейного криптоанализа, поскольку атака, требующая только перехваченный шифртекст, является наиболее практичной. В [15] Мацуи описывает такую атаку на полнораундовый DES, которая срабатывает при допущении, что соответствующий перехваченным шифртекстам открытый текст представляет собой английский текст в формате ASCII. Для этой атаки криптоаналитику потребуется порядка 2⁵⁴ шифртекстов.

Помимо DES и упомянутого выше алгоритма FEAL, известны и другие алгоритмы, подверженные линейному криптоанализу, например (отметим, что линейному криптоанализу подвержено существенно меньше из известных алгоритмов, чем дифференциальному):

1.     Линейный криптоанализ действует против алгоритма RC5 [19] в случае, если искомый ключ шифрования попадает в класс слабых ключей [5].

2.     Алгоритмы NUSH [13] и Noekeon [4], известные своим участием в конкурсе криптоалгоритмов Евросоюза NESSIE, также вскрываются методом линейного криптоанализа [9, 22].

3.     Некоторые варианты алгоритма DES (DESX, DES с независимыми подключами и Biham-DES) вскрываются линейным криптоанализом – подробности см. в [23].

 Усеченные дифференциалы

 Вернемся к дифференциальному криптоанализу. При его использовании в ряде случаев, когда невозможно построить характеристику с достаточно высокой вероятностью, бывает возможно найти такую характеристику, которая использует не целиком разность между двумя открытыми текстами или двумя субблоками (соответственно, D или D_b в предыдущей части статьи), а некие усеченные дифференциалы (truncated differentials) – разность между определенными битами обрабатываемых данных. При этом, вероятность таких характеристик может быть существенно выше, чем вероятность классических «полных» характеристик.

Усеченные дифференциалы могут быть полезны, прежде всего, при анализе таких алгоритмов, в которых все (или почти все) операции выполняются над выровненными фрагментами данных – например, над байтами или 16-битными словами. И наоборот, если алгоритм содержит в достаточном количестве какие-либо перемешивающие операции над отдельными битами данных, его можно априори считать стойким против усеченных дифференциалов [20].

Использование усеченных дифференциалов предложил известнейший датский криптолог Ларс Кнудсен (Lars Knudsen) в своей работе [7]. Им было доказано, что усеченные дифференциалы более эффективны для атаки на 6-раундовый DES, чем «классический» дифференциальный криптоанализ. Однако, Ларс Кнудсен не смог развить данную атаку на DES с большим числом раундов.

Впоследствии усеченные дифференциалы были использованы для атак на известные алгоритмы Skipjack [11] и SAFER [8]. Результаты аналогичны атакам на DES – усеченные дифференциалы оказались максимально эффективны при атаках на варианты алгоритмов с усеченным числом раундов, но их не удалось распространить на полнораундовые версии атакуемых алгоритмов.

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

2.          Biryukov A., de Canniere C. Linear Cryptanalysis. // http://homes.esat.kuleuven.be.

3.          Biryukov A., Kushilevitz E. Improved Cryptanalysis of RC5. // http://citeseer.ist.psu.edu – Technion – Israel Institute of Technology, Haifa, Israel.

4.          Daemen J., Peeters M., Van Assche G., Rijmen V. Nessie Proposal: Noekeon. // http://www.cosic.esat.kuleuben.be – 2000.

5.          Heys H.M. A Timing Attack on RC5. // http://citeseer.ist.psu.edu - Memorial University of Newfoundland, St. John’s, Newfoundland, Canada.

6.          Heys H.M. A Tutorial on Linear and Differential Cryptanalysis. // http://www.engr.mun.ca – Memorial University of Newfoundland, St. John’s, Canada.

7.          Knudsen L.R. Truncated and Higher Order Differentials. // http://citeseer.ist.psu.edu – Aarhus University, Denmark.

8.          Knudsen L.R., Berson T.A. Truncated Differentials of SAFER. // http://citeseer.ist.psu.edu.

9.          Knudsen L.R., Raddum H. On Noekeon. // http://www.cosic.esat.kuleuven.be – April 24, 2001.

10.       Knudsen L.R., Rijmen V., Rivest R.L. Robshaw M.J.B. On the Design and Security of RC2. // http://theory.lcs.mit.edu.

11.       Knudsen L.R., Robshaw M.J.B., Wagner D. Truncated Differentials and Skipjack. // http://www.cs.berkeley.edu.

12.       Kwan M. The Design of the ICE Encryption Algorithm. // http://www.darkside.com.au – 1997.

13.       Lebedev A.N., Volchkov A.A. NUSH. Cryptographic Algorithms Based upon the Block Cipher Called «NUSH». // http://www.cosic.esat.kuleuven.be. – LAN Crypto, Int., Moscow, Russia.

14.       Linear cryptanalysis – Wikipedia, the free encyclopedia. // http://en.wikipedia.org.

15.       Matsui M. Linear Cryptanalysis Method for DES Cipher. // http://homes.esat.kuleuven.be – Mitsubishi Electric Corporation, Japan.

16.       Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996. // http://www.cacr.math.uwaterloo.ca.

17.       Ritter T. Linear Cryptanalysis: A Literature Survey. // http://www.cyphersbyritter.com – 1997.

18.       Rivest R. RFC 2268: A Description of the RC2® Encryption Algorithm. // http://www.ietf.org. – MIT Laboratory for Computer Science and RSA Data Security, Inc. – March 1998.

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

20.       Standaert F.-X., Piret G., Quisquater J.-J. Cryptanalysis of Block Ciphers: A Survey. // http://citeseer.ist.psu.edu – Universite catolique de Louvain, Belgium – 2003.

21.       Van Rompay B., Knudsen L.R., Rijmen V. Differential cryptanalysis of the ICE encryption algorithm. // http://www.cosic.esat.kuleuven.ac.be – 1998.

22.       Wenling W., Dengguo F. Linear cryptanalysis of NUSH block cipher. // http://www.scichina.com – Chinese Academy of Sciences – 2002.

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

24.       Панасенко С. Интересные алгоритмы шифрования, часть 2. // BYTE/Россия. – 2006 - № 5 – с. 74-79.

25.       Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – Пер. с англ.: М.: Издательство ТРИУМФ, 2002 – 816 с.

 Об авторе:

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

С автором можно связаться:     

по телефонам (495)532-1313, (495)531-0000

или по E-mail develop@ancud.ru 

http://www.panasenko.ru

<<Страница 1