02 февраля 2007

С. Панасенко. Современные методы вскрытия алгоритмов шифрования.

С. Панасенко

CIO-World, ноябрь 2006

В первой части статьи были рассмотрены возможные атаки на алгоритмы симметричного шифрования.

Теперь опишем существующие криптоаналитические методы – от более простых к более сложным.

Метод грубой силы

Метод грубой силы (brute-force attack) предполагает перебор всех возможных вариантов ключа шифрования до нахождения искомого ключа.

Пусть размер ключа шифрования в битах равен b. Соответственно, существует 2^b вариантов ключа. Криптоаналитик должен методично перебрать все возможные ключи, т.е. (если рассматривать b-битную последовательность как число) применить в качестве ключа значение 0, затем 1, 2, 3 и т. д. до максимально возможного (2^b – 1). В результате ключ шифрования обязательно будет найден, причем в среднем такой поиск потребует 2^b/2, т.е. 2^b-1 тестовых операций шифрования.

Понятно, что необходим какой-либо критерий правильности найденного ключа. С атакой с известным открытым текстом все достаточно просто – при тестировании каждого ключа K_x шифртекст C расшифровывается (в результате получается некое значение M^’) и сравнивается с соответствующим ему открытым текстом M; совпадение M = M^’ говорит о том, что искомый ключ найден.

Несколько сложнее с атакой на основе шифртекста. В этом случае необходимо наличие какой-либо дополнительной информации об открытом тексте, например:

Если открытый текст является осмысленным текстом на каком-либо языке, перехваченный шифртекст должен иметь достаточный размер для однозначного расшифрования в осмысленный текст (минимально достаточный для этого размер называется точкой единственности). В основополагающей для современных симметричных криптосистем работе [15] размер единственности для английского языка теоретически определен как 27 букв. Если сообщение короче, то при переборе возможно появление нескольких различных осмысленных текстов, каждому из которых соответствует некий кандидат в искомые ключи. При невозможности перехвата дополнительных шифртекстов невозможно определить, какое из осмысленных сообщений является верным, если это не ясно из контекста.
Если открытый текст является бинарными данными, необходима какая-либо информация о том, что он из себя представляет. Если перехватывается архив, то при переборе ключей каждое значение M’ должно рассматриваться как возможный заголовок архива. При другом потенциальном M это может быть PE-заголовок исполняемого файла для Windows, заголовок графического файла и т. д.
Стоит отметить, что многие средства шифрования информации внедряют в формат зашифрованного объекта контрольную сумму открытого текста для проверки его целостности после расшифрования (см. подробное описание в [14]). Это может быть, например, имитоприставка, вычисленная согласно отечественному криптостандарту ГОСТ 28147-89 [13], или просто CRC32. Главное, что такая контрольная сумма может быть идеальным эталоном при криптоанализе, вполне подходящим для определения верного ключа.

Защита от атак методом грубой силы весьма проста – достаточно лишь увеличить размер ключа. Понятно, что увеличение размера ключа на 1 бит увеличит количество ключей (и среднее время атаки) в 2 раза.

Несмотря на простоту атаки методом грубой силы, существуют различные методы улучшения ее эффективности, например:

Атака методом грубой силы простейшим образом распараллеливается: при наличии, скажем, миллиона компьютеров, участвующих в атаке, ключевое множество делится на миллион равных фрагментов, которые распределяются между участниками атаки [3].
Скорость перебора ключей может быть во множество раз увеличена, если в переборе участвуют не компьютеры общего назначения, а специализированные устройства. В [3] приводится пример микросхемы ORCA компании AT&T (технология ПЛИС), которая способна перебрать до 30 миллионов ключей DES (стандарт симметричного шифрования США с 1977 по 1999 гг. [5]) в секунду. В той же работе [3] рассмотрено применение для перебора ключей специализированных микросхем, каждая из которых способна перебрать до 200 миллионов ключей DES в секунду. Следует учесть, что приведенные в [3] оценки даны на конец 1995 г. – сейчас перебор может осуществляться несравнимо быстрее.

Все эти методы были опробованы на стандарте шифрования США DES. Еще при его принятии в качестве стандарта у многих специалистов возникли обоснованные сомнения в достаточности размера его ключа (56 бит) [16]. Причем, с развитием компьютерной техники полный перебор ключа становился все более реальным. В 1993 году Майкл Винер (Michael Wiener) разработал принципы конструкции специализированного компьютера стоимостью порядка $1000000, способного перебрать ключи DES за 3,5 часа. Причем, данный компьютер имел возможность наращивания – при не фантастических для крупной организации или спецслужбы затратах порядка $10000000 полный перебор ключа DES должен был занять не более 21 минуты [11]. Ясно, что сейчас такой компьютер стоил бы в десятки раз дешевле [9].

Понятно, что с развитием вычислительной техники требования к размеру ключа шифрования постоянно возрастают. В той же работе [3] был рекомендован 90-битный размер ключа в качестве абсолютно безопасного (причем, с 20-летним запасом) на конец 1995 г. Сейчас подавляющее большинство алгоритмов шифрования используют ключи размером от 128-бит, что считается безопасным с примерно 80-летним запасом [4].

Современная вычислительная техника не позволяет «в лоб» атаковать 128-битный ключ полным перебором. Однако, атаки методом грубой силы часто используются в контексте других атак – например, с помощью дифференциального криптоанализа (данный метод будет описан в следующей части статьи) сужается область возможных ключей, после чего выполняется перебор оставшихся вариантов (один из вариантов подобной атаки описан в работе [2]).

Атаки класса «встреча посередине»

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

Любые методы, способные вскрыть алгоритм шифрования быстрее полного перебора ключей, эксплуатируют те или иные конструктивные недостатки алгоритма или его реализации. Начнем обзор таких методов с атак класса встреча посередине (meet-in-the-middle).

Простейший пример подобной атаки – вскрытие любого алгоритма шифрования, представляющего собой двойное шифрование данных с помощью какого-либо «одинарного» алгоритма. Рассмотрим алгоритм Double DES, представляющий собой двойное шифрование обычным DES’ом (см. рис. 1):

C = DES_k_2/2(DES_k_1/2 (M)),

где k_1/2 и k_2/2 – половины двойного ключа алгоритма Double DES, каждая из которых представляет собой обычный 56-битный ключ DES.

Рис.1. Алгоритм Double DES

Double DES решает основную проблему алгоритма DES (56-битный ключ шифрования слишком короток – как было показано выше) – 112-битный ключ Double DES невозможно вскрыть полным перебором. Однако, вскрытие Double DES легко выполняется атакой на основе известных открытых текстов. Предположим, у криптоаналитика есть открытый текст M1 и результат его зашифрования – С1. Он может выполнить следующую последовательность действий (см. рис. 2):

Выполняется зашифрование DES_kx(M1) на всем ключевом множестве (kx = 0…2⁵⁶-1) с записью результатов в некоторую таблицу.
Производится расшифрование DES^-1_ky (C1) также на всем ключевом множестве; результаты расшифрования сравниваются со всеми записями в таблице, сформированной на шаге 1.
Если какой-либо результат, полученный на шаге 2, совпал с одним из результатов шага 1, то можно предположить, что нужный ключ найден, т.е. соответствующие совпадающему результату kx = k_1/2, а ky = k_2/2.

Рис. 2. Пример атаки «встреча посередине»

Следует учесть, что таких совпадений может быть много – порядка 2⁴⁸ согласно [12]. Для «уточнения» правильного ключа из этих примерно 2⁴⁸ вариантов достаточно наличия еще одной пары текстов: M2 и C2. Криптоаналитик может использовать их абсолютно так же, как и первую пару (M1, C1), но перебор вариантов kx и ky осуществляется уже только по совпадениям первого перебора. В результате будет найден единственно верный ключ (вероятность повторного совпадения ничтожно мала – около 2^-16 [12]; в этом случае используется третья пара – M3 и C3 – при ее наличии).

В результате воздействия данной атаки сложность вычисления ключа Double DES всего в 2 раза выше, чем полный перебор ключей обычного DES, что несравнимо меньше 2¹¹² возможных вариантов «двойного» ключа. Алгоритм Double DES, собственно, и не используется, а упоминается лишь в подобных иллюстрациях к атаке «встреча посередине» (см., например, [12] или [14]).

Атака «встреча посередине» была изобретена в 1981 г. известными криптологами Ральфом Мерклем (Ralph C. Merkle) и Мартином Хеллманом (Martin E. Hellman) именно в применении к алгоритму Double DES [8]. Кроме того, эта атака (но в заметно более сложном исполнении) применима и к одному из вариантов «тройного» DES (Triple DES) [8].

Впоследствии атаки данного класса были неоднократно использованы для анализа различных алгоритмов шифрования; наиболее показательные примеры относятся к следующим алгоритмам шифрования:

Атака «встреча посередине» позволяет вычислить 192-битный ключ алгоритма DEAL (один из участников конкурса AES – см. [7]) выполнением порядка 2¹⁶⁶ тестовых операций шифрования; для вычисления 256-битного ключа необходимо порядка 2²²² операций [1]. И то, и другое не является практически осуществимым, но доказывает невысокий запас криптостойкости алгоритма DEAL.
Аналогично непрактичная атака возможна против еще одного участника конкурса AES – SAFER+ [10] – для его вскрытия необходимо 2²⁴⁰операций шифрования (при 256-битном ключе) [6].

Как видно, в отличие от Double DES, атака малоэффективна против более современных алгоритмов шифрования, что не удивительно. Однако, как и атака методом грубой силы, атака «встреча посередине» нередко применима в контексте других атак, а также для оценки запаса криптостойкости против модифицированных версий алгоритмов и алгоритмов с усеченным числом раундов.

Продолжение следует...

Литература

Baudron O., Gilbert H., Granboulan L., Handschuh H., Joux A., Nguyen P., Noilhan F., Pointcheval D., Pornin T., Poupard G., Stern J., Vaudenay S. Report on the AES Candidates. // http://csrc.nist.gov
Biham E., Biryukov A. An Improvement of Davies’ Attack on DES. // http://citeseer.ist.psu.edu – Technion, Haifa, Israel – 1994.
Blaze M., Diffie W., Rivest R.L., Schneier B., Shimomura T., Thompson E., Wiener M. Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security. // http://www.schneier.com – January 1996.
Daemen J., Peeters M., Van Assche G., Rijmen V. Nessie Proposal: Noekeon. // http://www.cosic.esat.kuleuben.be – 2000.
FIPS 46-3. Data Encryption Standard (DES). // http://csrc.nist.gov – Reaffirmed 1999 October 25.
Kelsey J., Schneier B., Wagner D. Key Schedule Weaknesses in SAFER+. http://www.schneier.com.
Knudsen L.R. DEAL – A 128-bit Block Cipher. // http://www2.mat.dtu.dk - February 21, 1998 – Revised May 15, 1998.
Merkle R., Hellman M. On the Security of Multiple Encryption. // http://www.cs.biu.ac.il – July 1981.
Quisquater J.-J., Standaert F.-X. Exhaustive Key Search of the DES: Updates and Refinements. // http://cr.yp.to – Universite Catholique de Louvain, Belgium.
SAFER+. Cylink Corporation’s Submission for the Advanced Encryption Standard. // First Advanced Encryption Standard Candidate Conference, Ventura, CA, August 20-22, 1998. Cylink Corporation.
Wiener M. Efficient DES Key Search. // http://citeseer.ist.psu.edu – Bell-Northern Research, Ottawa, Canada – August 20, 1993.
Брассар Ж. Современная криптология. – Пер. с англ.: М.: Полимед, 1999 – 176 с.
ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. – М.: Госстандарт СССР, 1989.
Панасенко С.П., Батура В.П. Основы криптографии для экономистов: учебное пособие. Под ред. Л.Г. Гагариной. – М.: Финансы и статистика, 2005 – 176 с.
Шеннон К. Теория связи в секретных системах. // Пер. с англ. В.Ф. Писаренко – http://info.phys.msu.su – 1949.
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – Пер. с англ.: М.: Издательство ТРИУМФ, 2002 – 816 с.

Об авторе: С. Панасенко, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук. Тел. (495)532-1313, (495)531-0000, е-mail develop@ancud.ru, сайт www.panasenko.ru

Источник: CIO

Показать все статьи автора >>

Просмотров: 2194

02 февраля 2007

С. Панасенко. Современные методы вскрытия алгоритмов шифрования.

Ссылки по теме

Ваши комментарии:

Публикации организации

Все публикации организации

В этой же рубрике

Информация

Отраслевые СМИ