страница 1
|
|||||||||||||||||||||||||||||||||||||||||||
Похожие работы
|
B. Соответственно, существует 2b - страница №1/1
Метод грубой силы Метод грубой силы (brute-force attack) предполагает перебор всех возможных вариантов ключа шифрования до нахождения искомого ключа. Пусть размер ключа шифрования в битах равен b. Соответственно, существует 2b вариантов ключа. Криптоаналитик должен методично перебрать все возможные ключи, т.е. (если рассматривать b-битную последовательность как число) применить в качестве ключа значение 0, затем 1, 2, 3 и т. д. до максимально возможного (2b – 1). В результате ключ шифрования обязательно будет найден, причем в среднем такой поиск потребует 2b/2, т.е. 2b-1 тестовых операций шифрования. Понятно, что необходим какой-либо критерий правильности найденного ключа. С атакой с известным открытым текстом все достаточно просто – при тестировании каждого ключа Kx шифртекст C расшифровывается (в результате получается некое значение M’) и сравнивается с соответствующим ему открытым текстом M; совпадение M = M’ говорит о том, что искомый ключ найден. Несколько сложнее с атакой на основе шифртекста. В этом случае необходимо наличие какой-либо дополнительной информации об открытом тексте, например:
Защита от атак методом грубой силы весьма проста – достаточно лишь увеличить размер ключа. Понятно, что увеличение размера ключа на 1 бит увеличит количество ключей (и среднее время атаки) в 2 раза. Несмотря на простоту атаки методом грубой силы, существуют различные методы улучшения ее эффективности, например:
Все эти методы были опробованы на стандарте шифрования США DES. Еще при его принятии в качестве стандарта у многих специалистов возникли обоснованные сомнения в достаточности размера его ключа (56 бит) [16]. Причем, с развитием компьютерной техники полный перебор ключа становился все более реальным. В 1993 году Майкл Винер (Michael Wiener) разработал принципы конструкции специализированного компьютера стоимостью порядка $1000000, способного перебрать ключи DES за 3,5 часа. Причем, данный компьютер имел возможность наращивания – при не фантастических для крупной организации или спецслужбы затратах порядка $10000000 полный перебор ключа DES должен был занять не более 21 минуты [11]. Ясно, что сейчас такой компьютер стоил бы в десятки раз дешевле [9]. Понятно, что с развитием вычислительной техники требования к размеру ключа шифрования постоянно возрастают. В той же работе [3] был рекомендован 90-битный размер ключа в качестве абсолютно безопасного (причем, с 20-летним запасом) на конец 1995 г. Сейчас подавляющее большинство алгоритмов шифрования используют ключи размером от 128-бит, что считается безопасным с примерно 80-летним запасом [4]. Современная вычислительная техника не позволяет «в лоб» атаковать 128-битный ключ полным перебором. Однако, атаки методом грубой силы часто используются в контексте других атак – например, с помощью дифференциального криптоанализа (данный метод будет описан в следующей части статьи) сужается область возможных ключей, после чего выполняется перебор оставшихся вариантов (один из вариантов подобной атаки описан в работе [2]). Любые методы, способные вскрыть алгоритм шифрования быстрее полного перебора ключей, эксплуатируют те или иные конструктивные недостатки алгоритма или его реализации. Начнем обзор таких методов с атак класса встреча посередине (meet-in-the-middle). Простейший пример подобной атаки – вскрытие любого алгоритма шифрования, представляющего собой двойное шифрование данных с помощью какого-либо «одинарного» алгоритма. Рассмотрим алгоритм Double DES, представляющий собой двойное шифрование обычным DES’ом (см. рис. 1): где k1/2 и k2/2 – половины двойного ключа алгоритма Double DES, каждая из которых представляет собой обычный 56-битный ключ DES. Рис.1 Алгоритм Double DES. Double DES решает основную проблему алгоритма DES (56-битный ключ шифрования слишком короток – как было показано выше) – 112-битный ключ Double DES невозможно вскрыть полным перебором. Однако, вскрытие Double DES легко выполняется атакой на основе известных открытых текстов. Предположим, у криптоаналитика есть открытый текст M1 и результат его зашифрования – С1. Он может выполнить следующую последовательность действий (см. рис. 2):
Рис.2 Пример атаки «встреча посередине». Следует учесть, что таких совпадений может быть много – порядка 248 согласно [12]. Для «уточнения» правильного ключа из этих примерно 248 вариантов достаточно наличия еще одной пары текстов: M2 и C2. Криптоаналитик может использовать их абсолютно так же, как и первую пару (M1, C1), но перебор вариантов kx и ky осуществляется уже только по совпадениям первого перебора. В результате будет найден единственно верный ключ (вероятность повторного совпадения ничтожно мала – около 2-16 [12]; в этом случае используется третья пара – M3 и C3 – при ее наличии). В результате воздействия данной атаки сложность вычисления ключа Double DES всего в 2 раза выше, чем полный перебор ключей обычного DES, что несравнимо меньше 2112 возможных вариантов «двойного» ключа. Алгоритм Double DES, собственно, и не используется, а упоминается лишь в подобных иллюстрациях к атаке «встреча посередине» (см., например, [12] или [14]). Атака «встреча посередине» была изобретена в 1981 г. известными криптологами Ральфом Мерклем (Ralph C. Merkle) и Мартином Хеллманом (Martin E. Hellman) именно в применении к алгоритму Double DES [8]. Кроме того, эта атака (но в заметно более сложном исполнении) применима и к одному из вариантов «тройного» DES (Triple DES) [8]. Впоследствии атаки данного класса были неоднократно использованы для анализа различных алгоритмов шифрования; наиболее показательные примеры относятся к следующим алгоритмам шифрования:
Как видно, в отличие от Double DES, атака малоэффективна против более современных алгоритмов шифрования, что не удивительно. Однако, как и атака методом грубой силы, атака «встреча посередине» нередко применима в контексте других атак, а также для оценки запаса криптостойкости против модифицированных версий алгоритмов и алгоритмов с усеченным числом раундов.
Об авторе: Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук. С автором можно связаться: по телефонам (495)532-1313, (495)531-0000 или по E-mail develop@ancud.ru http://www.panasenko.ru |
|