Метод бумеранга

Метод бумеранга (boomerang attack) предложен в 1999 г. известнейшим криптоаналитиком – профессором университета Беркли (Калифорния, США) Дэвидом Вагнером (David Wagner). Данный метод, фактически, является усилением дифференциального криптоанализа (см. третью часть статьи) и состоит в использовании «квартета» (т.е. четырех вместо двух) открытых текстов и соответствующих им шифртекстов, связанных следующими соотношениями [16] (см. рис. 1):

Рис.1 Метод бумеранга.

 1.   Предположим, что алгоритм шифрования можно логически разделить на две примерно равные по трудоемкости части. Например, N-раундовый алгоритм с раундами схожей структуры делится на две части по N/2 раундов.

2.   Обозначим процедуру зашифрования первой части алгоритма как E₀(). Для формирования квартета выберем два открытых текста P и P’, разность которых составляет некую величину D. В результате обработки этих текстов функцией E₀() получаем разность D*, т.е. (считая, что разность определяется операцией XOR):

E₀(P) Å E₀(P’) = D*.

3.   Продолжим зашифрование текстов P и P’ путем применения к ним процедуры зашифрования второй части алгоритма, которую обозначим E₁(). В результате получим два шифртекста – C и C’:

C = E₁(E₀(P)),

C’ = E₁(E₀(P’)).

4.   В данном случае разность между C и C’ криптоаналитика не интересует, однако, данные шифртексты используются для получения двух других выбранных шифртекстов: D и D’, связанных с предыдущими определенной разностью Ñ:

C Å D = C’ Å D’ = Ñ.

5.   Затем формирование квартета продолжается в обратную сторону (от чего проистекает название метода): к D и D’ применяется функция «полу-расшифрования» E₁^-1(), в результате чего получается некая разность Ñ*:

E₁^-1(D) Å E₀(P) = E₁^-1(D’) Å E₀(P’) = Ñ*

(стоит отметить, что E₁^-1(C) = E₀(P)).

6.   «Окончательное» расшифрование шифртекстов D и D’ дает в результате два открытых текста, обозначаемых Q и Q’:

Q = E₀^-1(E₁^-1(D)),

Q’ = E₀^-1(E₁^-1(D’)).

При этом Вагнер в [16] доказывает, что разность между полученными таким образом открытыми текстами Q и Q’ полностью аналогична разности между исходными текстами P и P’, т.е.:

Q Å Q’ = D.

Описанные выше соотношения четырех открытых текстов и четырех шифртекстов позволяют атаковать некоторые из алгоритмов, стойких к «классическому» дифференциальному криптоанализу. В ряде случаев (см. [16]) метод бумеранга позволяет существенно сократить объем требуемых для атаки данных (по сравнению с дифференциальным криптоанализом). Кроме того, атака применима к алгоритмам с гетерогенной структурой раундов.

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

Метод бумеранга применим против достаточно большого количества известных алгоритмов шифрования, среди которых стоит отметить алгоритмы-участники конкурса AES (конкурс по выбору нового стандарта шифрования США – см., например, [19]) CAST-256 [1], MARS [7] и SERPENT [2]. Впрочем, два последних алгоритма вскрываются только в вариантах с уменьшенным числом раундов [9].

Сдвиговая атака

Сдвиговая атака (slide attack) предложена в 1999 г. Алексом Бирюковым (Alex Biryukov) из института Technion, Хайфа, Израиль и упоминавшимся выше Дэвидом Вагнером [6].

Уникальность атаки состоит в том, что ее успешность не зависит от количества раундов атакуемого алгоритма. Однако, с помощью сдвиговой атаки можно вскрыть только те алгоритмы, раунды которых являются идентичными. Предположим, есть некий многораундовый шифр, в каждом раунде которого выполняется функция F(x, k), где x – выходное значение предыдущего раунда (или открытый текст для первого раунда алгоритма), а k – ключ раунда; предположим также, что ключи всех раундов являются идентичными. В этом случае для атаки используется следующая пара открытых текстов:

1.      Некий случайно выбранный текст P.

2.      Второй текст – P’, представляющий собой результат однораундового преобразования текста P, т.е.:

P’ = F(P, k).

Ясно, что соответствующие таким открытым текстам шифртексты (обозначим их C и C’ для P и P’ соответственно) связаны между собой аналогичным соотношением (см. рис. 2):

С’ = F(С, k).

Рис. 2 Сдвиговая атака.

Как видно из рис. 2, открытые тексты и соответствующие им шифртексты «сдвинуты» относительно друг друга на 1 раунд атакуемого алгоритма, что и предопределило название атаки (которое, как сказано в [6], предложено Брюсом Шнайером, многократно упомянутым в предыдущих частях этой статьи).

Множество алгоритмов шифрования построено по тому принципу, что функция раунда является слабой (но легко реализуемой и нетребовательной к ресурсам), а криптостойкость алгоритма шифрования определяется ее многократным повторением. Поэтому, имея две пары текстов (P, P’ и C, C’), связанные между собой лишь одним раундом шифрования, криптоаналитик способен (с помощью различных методов, описанных в данной статье) получить значение ключа раунда k. В данном случае это можно считать полным раскрытием алгоритма (см. первую часть статьи).

Соответственно, основная проблема атакующего состоит в нахождении двух открытых текстов, P и P’, связанных приведенным выше соотношением (предположим, что у злоумышленника есть доступ к шифратору с искомым ключом; однако, невозможно «заставить» шифратор выполнить лишь 1 раунд шифрования). Авторы атаки предлагают осуществлять поиск нужной пары следующим образом:

1.        Зафиксировав некоторое значение P, выполнить полный перебор остальных открытых текстов до нахождения нужного значения P’. Согласно парадоксу дней рождения (birthday paradox, подробно описан, например, в [21]), требуемый текст P’ будет найден после перебора порядка 2^n/2 текстов, где n – размер шифруемого блока в битах.

2.        «Правильная» пара P и P’ может быть определена следующим образом:

·      для P и каждого текста – кандидата в P’ (обозначим такой как P*) – получаются соответствующие шифртексты – C и C*;

·      из соотношения P* = F(P, k₁) определяется некое значение ключа раунда k₁; соответственно, из соотношения C* = F(C, k₂) определяется некое значение k₂;

·      совпадение k₁ и k₂ означает, что требуемое значение P’ = P* найдено, а k₁ = k₂ и есть искомое значение ключа раунда k.

Еще раз стоит отметить, что количество раундов алгоритма в данном случае никак не влияет на успешность его вскрытия.

С помощью данной атаки был полностью раскрыт алгоритм шифрования TREYFER, предложенный в 1997 г. для применения в смарт-картах и других устройствах с ограниченными ресурсами. Данный алгоритм имеет 32 раунда шифрования и 64-битный размер блока; в каждом раунде абсолютно идентично используется 64-битный ключ шифрования. Для атаки на TREYFER требуется около 2³² известных открытых текстов и 2⁴⁴ тестовых операций шифрования [6]. Кроме того, сдвиговая атака была применена к модифицированным вариантам известных алгоритмов DES (вариант 2K-DES) и Blowfish [6]; однако, атака нераспространима на их полноценные версии.

Несколько позже (в 2000 г.) вышла еще одна работа Бирюкова и Вагнера [5], в которой сдвиговая атака была усилена и распространена на алгоритмы, в которых функции раундов не совсем идентичны, но обладают существенным сходством. Усиленная атака была использована для взлома нескольких вариантов алгоритма DES, а также 20-раундового модифицированного отечественного стандарта шифрования ГОСТ 28147-89 [17].

Метод интерполяции

Метод интерполяции (interpolation attack) предложен в 1997 г. двумя датскими криптологами: Томасом Якобсеном (Thomas Jakobsen) и Ларсом Кнудсеном (Lars Knudsen) – и описан в их работе [8].

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

Авторы атаки доказали, что если число (ненулевых) коэффициентов полинома (обозначим его n) не превышает 2^m, где m – размер блока шифруемых данных в битах, то возможна атака на данный алгоритм шифрования, которая находит алгоритм, эквивалентный расшифрованию (или зашифрованию) данных искомым секретным ключом. Для такой атаки требуется выполнение n тестовых операций шифрования при наличии n известных открытых текстов.

В [8] Кнудсен и Якобсен показали, как с помощью метода интерполяции вскрыть алгоритмы KN [12] и PURE (данный алгоритм, однако, изобретен ими же для пояснения на нем данного метода), а также модифицированного варианта алгоритма SHARK (SHARK подробно описан, например, в [20]).

Невозможные дифференциалы

В 1998 г. изобретателями дифференциального криптоанализа Эли Бихамом (Eli Biham) и Эди Шамиром (Adi Shamir) совместно с упоминавшимся выше Алексом Бирюковым были опубликованы две работы ([3] и [4]), в которых был предложен принципиально новый вариант дифференциального криптоанализа, использующий невозможные дифференциалы (impossible differentials).

Если сравнивать невозможные дифференциалы с классическим дифференциальным криптоанализом (см. третью часть статьи), то видно, что использование невозможных дифференциалов представляет собой дифференциальный криптоанализ «от противного»: данный метод использует дифференциалы с нулевой вероятностью. Процесс вскрытия алгоритма с помощью невозможных дифференциалов можно кратко описать так:

1.   Выбирается нужное количество пар открытых текстов с требуемой разностью; получаются соответствующие им шифртексты.

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

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

Дифференциалы с нулевой вероятностью могут быть заменены дифференциалами с минимальной вероятностью – действия криптоаналитика при этом аналогичны описанным выше [15].

Невозможные дифференциалы могут быть применены для вскрытия усеченных (по количеству раундов) версий таких известных алгоритмов шифрования, как IDEA (подробное описание на русском языке есть в [18]), Khufu и Khafre [11], Skipjack [13], MISTY и KASUMI [10, 14].

Заключение

Это далеко не все из применяемых сейчас криптоаналитических методов. Однако, автор надеется, что дал представление об основных атаках на алгоритмы блочного симметричного шифрования. Два класса атак (из тех, которые не были рассмотрены в этой статье): атаки на связанных ключах и атаки по побочным каналам – будут рассмотрены в отдельных статьях, которые планируются к выходу на www.cio-world.ru в ближайшее время.

1.        Adams C., Gilchrist J. RFC 2612: The CAST-256 Encryption Algorithm. // Entrust Technologies, June 1999 – http://www.ietf.org.

2.        Anderson R., Biham E., Knudsen L. Serpent: A Proposal for the Advanced Encryption Standard. // http://csrc.nist.gov.

3.        Biham E., Biryukov A., Shamir A. Cryptanalysis of Skipjack Reduced to 31 Round using Impossible Differentials. // http://www.cs.technion.ac.il – 1998.

4.        Biham E., Biryukov A., Shamir A. Miss in the Middle Attacks on IDEA, Khufu and Khafre. // http://www.wizdom.weizmann.ac.il.

5.        Biryukov A., Wagner D. Advanced Slide Attacks. // http://citeseer.ist.psu.edu.

6.        Biryukov A., Wagner D. Slide Attacks. // http://citeseer.ist.psu.edu.

7.        Burwick C., Coppersmith D., D’Avignon E., Gennaro R., Halevi S., Jutla C., Matyas S.M.Jr., O’Connor L., Peyravian M., Safford D., Zunic N. MARS – a candidate cipher for AES. // http://www.research.ibm.com – IBM Corporation – Revised, September, 22 1999.

8.        Jakobsen T., Knudsen L.R. The Interpolation Attack on Block Ciphers. // http://citeseer.ist.psu.edu – 1997.

9.        Kelsey J., Kohno T., Schneier B. Amplified Boomerang Attack Against Reduced-Round MARS and Serpent. // http://citeseer.ist.psu.edu.

10.    Kuhn U. Cryptanalysis of Reduced-Round MISTY. // http://citeseer.ist.psu.edu – Dresdner Bank AG, Frankfurt, Germany.

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

12.    Nyberg K., Knudsen L.R. Provable Security Against a Differential Attack. // http://citeseer.ifi.unizh.ch.

13.    Skipjack and KEA algorithm specifications // http://csrc.nist.gov – Version 2.0 – 29 May 1998.

14.    Specification of the 3GPP Confidentiality and Integrity Algorithms. Document 2: KASUMI Specification. // http://portal.etsi.org - Version: 1.0 – 23^rd December 1999.

15.    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.

16.    Wagner D. The boomerang attack. // http://www.cs.berkeley.edu – U.C. Berkeley.

17.    ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. – М.: Госстандарт СССР, 1989.

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

19.    Панасенко С. Алгоритмы шифрования – финалисты конкурса AES. // http://www.ixbt.com – 24.08.2006.

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

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

Об авторе:

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

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

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

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

http://www.panasenko.ru

<<Страница 1