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

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

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

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

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

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


Рассмотрим современные криптоаналитические методы, для чего начнем с классификации атак на алгоритмы шифрования.

Атаки на алгоритмы шифрования

Осуществляя атаку, криптоаналитик может ставить целью решение следующих задач:

1. Получение открытого текста из зашифрованного.

2. Вычисление ключа шифрования.

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

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

Категория 1. Криптоаналитик имеет только возможность пассивного прослушивания некоего канала, по которому пересылаются зашифрованные данные (см. рис. 1). В результате у злоумышленника есть лишь набор шифртекстов, зашифрованных на определенном ключе. Такая атака называется атакой с известным шифртекстом. Она наиболее сложна, но данный вариант атаки наиболее распространен, поскольку он является самым "жизненным" - в подавляющем большинстве реальных случаев криптоаналитик не имеет возможности получить больше данных.

Рис. 1. Пассивный перехват зашифрованных данных.

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

Рис. 2. Активное воздействие на шифратор.

В зависимости от данных, которые криптоаналитик может "добыть" у шифратора, существуют следующие виды атак:

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

2. Атака с выбранным открытым текстом. У криптоаналитика есть возможность выбора открытых текстов для получения соответствующих им шифртекстов (как это может быть полезно криптоаналитику, будет рассмотрено ниже).

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

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

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

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

Количественная оценка криптостойкости алгоритмов шифрования

Криптостойкость является количественной характеристикой алгоритмов шифрования - для вскрытия конкретного алгоритма шифрования при определенных условиях (в том числе, определенным криптоаналитическим методом) требуется определенное число ресурсов. Ресурсами в данном случае являются следующие величины:

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

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

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

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

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

Криптоанализ модифицированных алгоритмов

Существует немало алгоритмов шифрования, которые являются криптографически стойкими. В известной работе понятие стойкого (strong) алгоритма определено так:

1. Алгоритм является криптографически стойким, если не существует каких-либо методов его вскрытия, кроме метода "грубой силы" (brute force), который будет рассмотрен в следующей части статьи.

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

Однако, например, бывает необходимо сравнить между собой два или более криптографически стойких алгоритма шифрования (как, например, на открытом конкурсе по выбору нового стандарта шифрования США AES). В этом случае используют другую характеристику (скорее качественную, чем количественную) - запас криптостойкости (security margin).

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

Другой вариант определения запаса криптостойкости - анализ модификаций исследуемого алгоритма с незначительными изменениями структуры раунда. Один из наиболее ярких примеров - вскрытие алгоритма Skipjack-3XOR при наличии всего 29 выбранных открытых текстов и соответствующих им шифртекстов выполнением всего около миллиона тестовых операций шифрования. По современным меркам, благодаря данной атаке Skipjack-3XOR можно считать весьма слабым алгоритмом, а ведь он отличается от известного и достаточно распространенного алгоритма шифрования Skipjack всего тем, что из структуры последнего удалены всего 3 конкретных операции XOR (побитовая логическая операция "исключающее или") из предусмотренных алгоритмом Skipjack 320 (!) подобных операций. Соответственно, были (однако, недоказанные) предположения о недостаточном запасе криптостойкости у алгоритма Skipjack. Впрочем, в случае анализа алгоритмов с подобными модификациями запас криптостойкости можно рассматривать только как качественную характеристику, имеющую достаточно косвенное отношение к исследуемому алгоритму шифрования.