И.Д. ГОРБЕНКО, д-р техн. наук, С.А. ГОЛОВАШИЧ, канд. техн. наук, А.Н. ЛЕПЕХА
Сегодня в области криптографических средств защиты информации происходит процесс обновления используемых алгоритмов криптозащиты: большинство наиболее распространённых алгоритмов уже морально устарели, в то время как новые алгоритмы требуют тща-тельного исследования и стандартизации…
УДК 681.3.06:519.248.681
СРАВНИТЕЛЬНЫЙ АНАЛИЗ БЛОЧНЫХ СИММЕТРИЧНЫХ ШИФРОВ, ПРЕДСТАВЛЕННЫХ В ПРОЕКТЕ NESSIE
Введение:
В 1998 в США был организован конкурс AES (Advanced Encryption Standard), направленный на выбор нового стандарта блочного симметричного шифрования (БСШ). В результате выполнения этого проекта в ка-честве нового стандарта был выбран алгоритм Rijndael (и на его основе принят стандарт США FIPS-197). В ноябре 2000 года прошел первый открытый семинар NESSIE (New European Schemes for Signatures, Integrity, and Encryption Новые европейские схемы для электронных подписей, обеспечения целостности информации и шифрования, ). Проект был начат под эгидой Европейской комиссии. Основными за-дачами проекта NESSIE является отбор лучших десяти криптографических примитивов. В этот набор входят алгоритмы блочного и поточного шифрования, генераторы случайных чи-сел, схемы быстрой аутентификации данных (MAC), хэш-функции и алгоритмы цифровой подписи. В качестве основных критериев отбора претендентов выбраны реальная безопас-ность, производительность, гибкость и требования рынка.
Проект NESSIE запланирован на три года и состоит из двух этапов. На перовой конфе-ренции в январе 2000 года на рассмотрение был вынесен список кандидатов для открытого обсуждения. В сентябре 2001 года завершилась первая фаза конкурса NESSIE и были объяв-лены первые результаты отбора. В течение второй фазы конкурса, которая завершится осе-нью 2002 года, планируется отобрать набор криптопримитивов для возможной стандартиза-ции некоторых из них в будущем.
Целью данной статьи является изложение и анализ промежуточных результатов проекта NESSIE относительно блочных симметричных криптоалгоритмов. Это позволит сформули-ровать требования, которые сегодня предъявляются к БСШ различного уровня стойкости, а также определить направления развития симметричных шифров.
Исследования, проводимые криптологами мира, позволят обнаружить слабые и сильные стороны различных блочных симметричных шифров.
1 Основные требования
В связи с прогрессом в усовершенствовании методов выполнения криптоаналитических атак к кандидатам были предъявлены повышенные требования [1]. Для БСШ рассматривает-ся три класса безопасности:
1. Высокий уровень безопасности длина блока lб=128 бит, длина ключа lк=256 бит.
2. Нормальный уровень безопасности длина блока lб=128 бит, длина ключа lк=128 бит.
3. Удовлетворительный уровень безопасности длина блока lб=64 бит, длина ключа lк=128 бит.
Криптоалгоритм должен строиться на основе использования криптографии симметрич-ных ключей. То есть ключи источника криптограмм и получателя должны или совпадать, или рассчитываться один из другого не выше чем с полиномиальной сложностью.
Каждый подаваемый на конкурс алгоритм должен содержать его описание, математиче-ское описание, таблицы, диаграммы и описание параметров (размер слова, размер ключа, требования к памяти, объем кода). Выбор используемых компонентов и параметров алго-ритма разработчики должны обосновать и предоставить в том же документе.
Участвующие в проекте алгоритмы должны допускать как программную, так и аппарат-ную реализацию. Для оценки сложности аппаратной реализации рекомендуется использо-вать в качестве показателя число логических элементов (вентилей); для программной реа-лизации тип процессора, тактовую частоту процессора и реализации на различных совре-менных языках программирования и т.п.
В данной статье представлены результаты, касающиеся криптографических алгоритмов высокого и нормального уровня стойкости. Некоторые сведения о первоначально допущен-ных алгоритмах 1-го класса стойкости приведены в табл. 1.
Скорость (сложность) криптоалгоритма рекомендуется оценивать в виде числа тактов работы процессора, необходимых для:
зашифрования одного блока данных;
расшифрования одного блока данных;
разворачивания ключа;
настройки алгоритма или его части (например, формирования таблиц).
Таблица 1
Наименование алгоритма Размер блока,бит Размер слова,бит Размер ключа,бит Размер подключа,бит Табл.подст./разм. табл. (бит х бит) Сдвиг/перестановка + умножение, бит XOR, ADD (бит) AND, OR, NOT (бит) Суммарная таблица подст. Размер кода прогр., кб
Anubis 128 8 128-320 128* (R-1) * 180+15* (R-12) 128 128 * 32
Camellia 128 8 128 1664 144(8×64) 130 2(128 бит)162(64 бит)8(32 бит) 144(64 бит)4(32 бит)4(32 бит) 144 8,2
Camellia 128 8 192-256 2176 192(8×64) 174 2(128 бит)216(64 бит)128(32 бит) 192(64 бит)6(32 бит)6(32 бит) 192 8,2
Grandcru 128 8 128 4224 50(5×8)672(8×8) 144(8 бит)160(8 бит) 1372(8 бит)32(8 бит) 144(8 бит) 722 16
Hierocrypt-3 128 8 128 1792 16(8×8)96(8×32)80(8×128) 144(32 бит) 120(32 бит)76(128 бит) 192(32бит) 182 15
Hierocrypt-3 128 8 192 2048 16(8×8)112(8×32)96(8×128) 168(32 бит) 140(32 бит)91(128 бит) 224(32бит) 224 15
Hierocrypt-3 128 8 256 2304 16(8×8)128(8×32)112(8×128 192(32бит) 160(32бит)106(128бит) 256(32бит) 256 15
Noekeon 128 32 128 2048 128 16(128бит),304(32бит) 32(32бит),32(32бит),32(32бит) 0 10,5
Продолжение таблицы 1
Nush128 128 32 128,192,256 4608 68(32бит) 212(32бит) 68(32бит) 0 15
Q 128 32 1280 128(8×8) 24 26(128бит),144(32бит) 56(32бит)16(32бит) 128 11,3
RC6 128 32 128 1408 40(32бит),80(32бит)+40(32бит) умножен. 40(32бит),84(32бит) 0 8
Safer++/128 128 8 128 1920 112(8×8) 15(64бит),456(8бит) 112 35
Safer++/256 128 8 256 2688 160(8×8) 21(64бит)648(8бит) 160 35
SC2000 (128) 128 32 128 1792 24(10×10)48(11×11) 48(32бит) 87(32бит),12(64бит),14(128бит) 145(32бит) 72 20
SC2000 (192, 256) 128 32 192-256 2048 28(10×10)56(11×11) 56(32бит) 98(32бит),14(64бит),16(128бит) 168(32бит) 84 20
Rijndael 128 8 128 1408 160(8×32) 30 11(128бит),120(32бит) 160
SHACAL-1 160 32 512 2560 224(32бит) 272(32бит),320(32бит) 180(32бит) 0 8
* 192+ 16*(R-12)
** 6144+512*(R-12)
2 Критерии и показатели оценки качества
В первой фазе конкурса NESSIE к алгоритмам при отборе предъявлялись следующие критерии:
1. Защищенность алгоритмов от криптоаналитических атак. При этом основными мето-дами криптоанализа являются: дифференциальный криптоанализ, расширения для диффе-ренциального криптоанализа, поиск наилучшей дифференциальной характеристики, линей-ный криптоанализ; интерполяционное вторжение; вторжение с частичным угадыванием ключа; вторжение с использованием связанного ключа; вторжение на основе обработки сбо-ев; поиск лазеек.
2. Особенности конструкции и открытость структуры. Представленные криптоалгорит-мы должны обладать понятной, легкоанализируемой структурой и основываться на надеж-ных математических и криптографических принципах.
3. Устойчивость при модификации. Все кандидаты проверяются на устойчивость к раз-личного рода модификациям: устойчивость к криптоаналитическим атакам при уменьшении числа циклов, сокращении компонентов используемых алгоритмом и т.п.
4. Статистическая безопасность криптографических алгоритмов.
5. Вычислительная сложность (скорость) зашифрования/расшифрования.
6. Сложность программной, аппаратной и программно-аппаратной реализации должна оцениваться объемом памяти как при программной, так и аппаратной реализации. В том числе, при программной количеством необходимой оперативной памяти, размером исход-ного кода, скоростью работы программы на различных платформах при реализации на из-вестных языках программирования. При аппаратной оценивается количеством вентилей и скоростью в Мб/с.
7. Универсальность криптоалгоритма:
возможность работы с различными длинами начальных ключей и информационных блоков;
безопасность реализации на различных платформах и приложениях.
возможность использования криптографического алгоритма в основных режимах работы БСШ.
3 Защищенность БСШ от криптоаналитических атак
Стойкость против криптоаналитических атак при оценке криптографического алгоритма является самой важной характеристикой. Сравнительный анализ криптоалгоритмов по этой характеристике является достаточно сложной проблемой. В настоящее время наибольшую угрозу для БСШ представляют аналитические атаки, постороенные на основе дифференци-ального и линейного криптоанализа. Криптоаналитические атаки, которые сегодня представ-ляют основную угрозу для БСШ, представлены во втором разделе данной статьи. Существу-ет несколько критериев оценки стойкости криптоалгоритма к указанным выше атакам. Пер-вым из них является критерий идеальной безопасности. В данном случае предполагается, что криптоаналитик располагает неограниченными ресурсами как по времени, так и по объ-ему памяти. Для того, чтобы криптоалгоритм удовлетворял данному критерию, необходимо, чтобы количество бит зашифрованных открытых текстов не превышало , где К количе-ство бит ключа, N количество бит блока. Однако на практике такой критерий не применим. Критерий доказуемой стойкости. На практике это означает, что криптоалгоритм может быть атакован при помощи решения какой-либо математической проблемы. Например, дискретно-го логарифма или факторизации. Такие модели чаще всего используются для оценки шиф-ров, использующих открытые ключи. Для блочных симметричных криптоалгоритмов наи-большую опасность представляют атаки, построенные на видоизменениях дифференциаль-ного и линейного криптоанализа. Как правило, оценивается сложность по временным затра-там, памяти и количестве необходимых данных. Алгоритмы, если для них не были обнару-жены криптоаналитические атаки, оцениваются по нижней границе вычислительных затрат, необходимых на реализацию той или иной атаки. Другая модель, используемая при оценке криптопримитивов, базируется на безопасном времени. Данная модель позволяет оценить стойкость криптоалгоритма на протяжении некоторого времени.
Основной моделью, которая использовалась в конкурсе NESSIE, была практическая мо-дель [2]. В ней оценивалось три параметра. Первый это время как количество тактов, не-обходимых для успешного криптоанализа. Второй это память как среднее число некото-рых данных, которые необходимо получить для работы криптоаналитического алгоритма. Третий это количество текстов, которые необходимо получить для успешной работы криптоаналитического алгоритма. Затраты на память считаются более дорогими, чем затраты на время. На практике при выборе криптоаналитического алгоритма жертвуют увеличением времени с уменьшением исходных данных. Атака считается успешной теоретически, если К бит ключа могут быть вычислены за время, меньшее времени прямого перебора ключа. Блочный симметричный криптоалгоритм можно считать безопасным, если не найдено атаки со сложностью время-данные, меньшей, чем 2К и 2N соответственно. Найти эффектив-ную атаку на новые криптоалгоритмы БСШ практически невозможно. Поэтому при сравне-нии БСШ реализуют атаки на криптопримитивы с уменьшенным количеством циклов или без криптографических преобразований.
В табл. 2 приведены результаты оценки атак на представленные в конкурсе NESSIE БСШ.
Таблица 2
Криптоалго-ритм Цик-лы Потенци-альнаяуязвимость Наилучшая атака
Циклы Техника Время Данные
Криптоалгоритмы прошедшие во второй тур
Camellia 18 x-1 S-box по-тенциально открыты для алгебраиче-ских атак. 566789911 Невыполнимые дифференциалыSquare (с FL блоками)Square (без FL блоков) Невыполнимые дифференциалы (без FL) Усеченные дифференциалы (без FL блоков) Square + ключ (с FL блоками) Дифференциальный криптоанализ (без FL блоков)Дифференциалы высокого поряд-ка (без FL блоков) 2112255,6220222552256 216211,72832602105221293
RC6 20 Малая по-граничная полоса стойкости, уязвим че-рез завися-щие от дан-ных сдвиги 1616814181517 Дифференциальный криптоана-лизЛинейный криптоанализЛинейный криптоанализМультилинейный криптоанализМультилинейный криптоанализ + 2-90 слабых ключей — аттака (статистическая) — для 2-80 слабых ключей 21862193 2190211927621202127
Rijndael 10 12 14 Маленькая граница безопасно-сти. Потен-циально от-крыт для ал-гебраиче-ских атак. Некоторые слабости в схеме раз-ворачивания ключей. 5677776777889 Невыполнимые дифференциалыSquareКоллизии (192, 256 бит ключ)Коллизии (128)Square (192 бит ключ)Square (256 бит ключ)SquareSquare (192 бит ключ)Square (256 бит ключ)SquareSquare (192 бит ключ)Square (256 бит ключ)Связанные ключи/ Square 256 связанных ключей (192 бит ключ) 2312722140212821762192244215521722120218822042224 229,523223223223223223223223221282119-21282119-2128277
Продолжение таблицы 2
Safer++ 8 Негомо-морфиче-ские линей-ные аппрок-симации. Мало бит и байт коли-чества вет-вей для рас-сеивания. 3,5 Линейный криптоанализ (сла-бые ключи) 2121
Криптоалгоритмы, не прошедшие во второй тур
Anubis 8 + N 56778 Невыполнимые дифференциа-лы Saturation (все ключи)Saturation (все ключи)Gilbert-Minier (ключ > 140) Saturation (ключ > 204) 2316х248212021402204 229,56х23221282322128
Hierocrypt-3 6-8 Схема раз-ворачивания ключей 2,533,5 ИнтегралИнтегралИнтеграл 21682402168 2136х23222х232
Noekeon 16 S-box со-держат идентичные функции.Много свя-занных ключей Дифференциальный/линейный криптоанализ
Nush128 Высоко-линейный отклонения Линейный криптоанализ 2К-1
Q 8 Высокие дифферен-циальный и линейные вероятности 8899 Дифференциальный Линейный (128 битный ключ)Линейный (192 бит ключ)Линейный (256 бит ключ) 2772962128 210521252125
SC2000 6,5-7,5 Высокие диф. веро-ятности 3,54,54,5 Дифференциальный криптоана-лизДифференциальный криптоана-лизДифференциальный криптоана-лиз
На алгоритм SAFER++ был осуществлен линейный криптоанализ [3]. Полученные ре-зультаты все еще не представляют угрозы для этого шифра (с любым блоком или ключом). Наилучшие результаты приведены в табл. 2. Атаки на 3-х и 4-х цикловый SAFER++ реально осуществимы для 26 212 групп слабых ключей 256 бит длиной.
На SC2000 были осуществлены три типа атак (таблица 2). Дифференциальный криптоа-нализ был осуществлен на 4,5 цикловый вариант SC2000 с 2110 парами откры-тый/шифрованный текст и было получено 32 бита ключа первого и последнего циклового ключа, оставшиеся 96 бит были определены полным перебором [4].
В документе к криптоалгоритму SHACAL были представлены результаты дифференци-ального и линейного криптоанализа. Были обнаружены криптоаналитические характеристи-ки на различном числе циклов. Для успешного осуществления атаки необходимо 2116 пар за-шифрованный/открытый текст, а для линейного криптоанализа это число колеблется около 280 [7].
Разработчики Hierocrypt первоначально представили успешную атаку на 2,5-цикловый вариант шифра, однако затем был найден улучшенный вариант этой атаки на 3,5 цикла с возможным расширением ее на большее число циклов [3].
При анализе Noekeon были обнаружены большие группы связанных ключей. Причем существование этих групп ключей одинаково для обеих схем распределения ключей. В ко-лонке вероятность указаны вероятности появления дифференциалов, в колонке ключи указано количество ключей, в которых существует данный дифференциал (для любого клю-ча).
Криптоалгоритм Q был успешно атакован при помощи дифференциального криптоана-лиза. Eli Biham с учениками нашел дополнительную дифференциальную характеристику [5] кроме описанных разработчиками. Был предложен улучшенный вариант атаки для данного алгоритма, сокращающий сложность криптоаналитической атаки на основе дифференциаль-ного криптоанализа. При этом сложность анализа уменьшается пропорционально количеству выбранных пар открытого и зашифрованного текста и наоборот.
Проведенные исследования криптоалгоритма Anubis показали, что его стойкость против известных криптоаналитических атак не превышает заявленных авторами. Однако исследо-вания также показали, что линейный криптоанализ дал эффективные результаты для алго-ритма с большим числом циклов, чем было заявлено авторами. Eli Biham в своих исследова-ниях [6] высказал свое мнение о необходимости изучения выявленных отклонений для рас-ширения данной атаки на большее число циклов.
Авторы Camellia представили 18-цикловый вариант алгоритма и утверждали, что даже 10 цикловый вариант безопасен. При исследованиях была обнаружена 3- и 7-цикловые ха-рактеристики с вероятностями 2-52 и 2-130 соответственно. Была атакована также 9-цикловая версия Camellia при помощи дифференциального криптоанализа. Линейный криптоанализ алгоритма не дал результатов [6].
RC6 успешно атакован при помощи дифференциального и линейного криптоанализа с уменьшенным числом циклов. Максимальная характеристика была обнаружена на 18-цикловом варианте алгоритма [7]. На данный момент RC6 является безопасным алгоритмом. Его безопасность основана на независимых циклических сдвигах.
4 Статистическая безопасность криптографических алгоритмов
Представленные на конкурс алгоритмы блочного шифрования были исследованы по критерию статистической безопасности. Это было сделано с целью выявления аномалий и зависимостей криптоалгоритмов, а также использования усовершенствованных атак. Для статистического исследования криптоалгоритмов использовался пакет NIST RIPE. Специ-ально для конкурса NESSIE этот пакет был расширен дополнительными тестами и инстру-ментами [8]. Для БСШ использовались наборы таких тестов, как корреляционный тест, тест линейной аппроксимации и тест корреляционного иммунитета (для S-box), а также тест ли-нейных факторов.
1. Корреляционный тест вычисляет матрицу зависимостей и матрицу расстояний для блочного симметричного шифра.Также определяется степень совершенства (dc), степень лавинообразного эффекта (da), строгий лавинный критерий (dsa). Эти параметры должны принимать при тестировании криптоалгоритма на полном количестве циклов значения: dc=1; da 1; dsa 1. При таких значениях алгоритм считается прошедшим данный тест:
, (1)
где: размерности матрицы зависимости ( х );
— элементы матрицы зависимости,
для =1,., ; .
(2)
где: для =1,., ; .
. (3)
Полнота проявляется в том случае, если каждый выходной бит зависит от каждого вход-ного. Лавинообразный эффект должен приводить к изменению в среднем половины выход-ных битов. Критерий распространения (строгий лавинный критерий) характеризует зависи-мость выходных значений от входных векторов с различным весом Хемминга.
2. Тесты линейной аппроксимации и корреляционного иммунитета основаны на быст-ром преобразовании Уолша. Эти тесты используются для тестирования S-блоков БСШ. Пусть имеется некоторая функция на , где . Функция имеет корреляцион-ный иммунитет порядка , если ее преобразование Уолша функции над опреде-ляется как принимающая действительные значения функция (4)
, (4)
где .
3. Тест линейных факторов определяет линейную характеристику (зависимость), кото-рая сохраняется между битами открытого текста, ключа и криптограммы.
Все криптоалгоритмы тестировались в режиме обратной связи по выходу. Для тестиро-вания использовался статистический пакет RIPE, который специально для конкурса NESSIE был видоизменен. Кроме того, криптоалгоритмы прошли тестирование в режиме счетчика.
Далее приводятся результаты тестирования для БСШ высокого уровня стойкости, кото-рые прошли первый отборочный тур. Это криптоалгоритмы SAFER++, Camellia, RC6, SHACAL и Rijndael.
При проведении первого этапа статистического исследования получены следующие ре-зультаты (табл. 3).
Таблица 3
Тип теста Camellia SAFER++ RC6 Rijndael SHACAL
Корреляционный:кол.вх.векторовкол.бит кот.измен dc da dsa 100063,9952671,0000000,9992390,992012 100064,0030161,00000000,9992500,992005 100064,006081,0000000,9992690,991951 100063,9945711,0000000,9992460,991925 100063,9931611,0000000,9993210,991965
Результаты анализа для всех алгоритмов показали, что отклонений от случайной после-довательности не наблюдается.
Тест на поиск линейных комбинаций (тест линейных факторов) между зашифрованным текстом, открытым текстом и ключами не выявил каких-либо зависимостей среди оставших-ся БСШ.
На втором этапе производилось статистическое исследование представленнх криптоал-горитмов на версиях с меньшим числом циклов. Целью такого исследования было определе-ние, на каком числе циклов перестанут появляться статистические зависимости. Результаты этого исследования сведены в табл. 4, где указывается количество циклов, после которого данный критерий удовлетворяет необходимому условию.
Таблица 4
Наименование шифра Число бит, которые изменились Полнота, dc Критерий рас-пространения, da Обнаруженные ли-нейные факторы, dsa
Camellia 0 +0,5 1,000001 +0,5 11,9581422 +0,5 38,4166943 +0,5 58,9529554 + 0,5 63,5554635 + 0,5 64,004316 0,0078120,1796880,5976560,9218751,0000001,000000 0,0156250,1868460,6002610,9208170,9992710,999254 0,0000000,1651060,5780020,9090800,9919950,991951
SAFER++ 0 + 0,5 1,2417751 + 0,5 61,7528572 + 0,5 63,9965233 + 0,5 63,9963954 + 0,5 64,0093395 + 0,5 63,995669 0,0214840,9531251,0000001,0000001,0000001,000000 0,0194030,9516080,9992240,9992760,9992880,999291 0,0027940,9006450,9919440,9919850,9919590,991968
RC6 0,5 1,9342661+0,514,3341772+0,541,7849013+0,560,3015724+0,563,9232825+0,563,994611 0,0868530,4178470,8750001,0000001,0000001,000000 0,0302230,2239720,6528890,9421410,9984790,999273 0,0106450,2139400,6512750,9378450,9916610,992041
Rijndael 0 + 1 4,0400251 + 1 16,0640592 + 1 64,2470143 + 1 64,001791 0,0625000,2500001,0000001,000000 0,0631250,2510010,9961400,999350 0,0591290,2476720,9914660,992043
SHACAL 0 + 0,5 4,1709491 + 0,5 7,8463662 + 0,5 13,5747983 + 0,5 20,9622204 + 0,5 29,4191415 + 0,5 38,4513936 + 0,5 46,8651407 + 0,5 53,5560098 + 0,5 58,3922019 + 0,5 61,32737810 + 0,5 62,93218811+ 0,5 63,63542512+ 0,5 63,90027513+ 0,5 63,980032 0,2521360,4489140,6887210,8610230,9518430,9932860,9998171,0000001,0000001,0000001,0000001,0000001,0000001,000000 0,0651710,1225990,2121060,3275350,4596740,6008030,7322680,8368130,9123780,9582400,9833130,9941990,9982190,999127 0,0454570,0970940,1801490,2864540,4180310,5608780,6984570,8136270,8963130,9485080,9758460,9873820,9909900,991881
Анализ полученных результатов показывает, что для Camellia полнота (dc) наступает по-сле 3 + 0,5 цикла; критерий распространенности выше 0,98 после 3 + 0,5 циклов; линейные факторы исчезают после 4+ 0,5 цикла.
Исследования БСШ SAFER++ показали, что полнота (dc) наступает после 2 + 0,5 цикла; критерий распространенности выше 0,98 после 2 + 0,5 циклов; линейные факторы исчезают после 2 + 0,5 цикла.
Для RC6 получены следующие данные. Полнота (dc) наступает после 4 + 0,5 цикла; кри-терий распространенности выше 0,98 после 4 + 0,5 циклов; линейные факторы исчезают по-сле 3 + 0,5 цикла.
Полнота (dc) для Rijendael наступает после 2 + 1 цикла; критерий распространенности выше 0,98 после 3 + 1 циклов; линейные факторы исчезают после 3 + 1 цикла.
Анализ статистических исследований для SHACAL показывает, что полнота (dc) насту-пает после 8 + 0,5 цикла; критерий распространенности выше 0,98 после 12 + 0,5 циклов; ли-нейные факторы исчезают после 12 + 0,5 цикла.
Было проведено также тестирование криптоалгоритмов в режиме обратной связи по вы-ходу. В рамках этого теста применялись следующие тесты. Частотный (монобитный) тест, тест на выявление коллизий, тест m-мерных перекрытий, тест на наличие интервалов (ну-лей), тест на непрерывающиеся последовательности, универсальный тест Маурера, тест По-кера, быстрый спектральный тест, корреляционный тест, проверка ранга матрицы, проверка линейной сложности, определение максимального порядка сложности, проверка сжатия по алгоритму Лемпеля-Зива, тест двухэлементной сложности (dyadic complexity test), персоля-ционный тест, тест постоянных серий. В виду большого объема полученных данных, они здесь не приводятся. Исследования показали, что представленные последовательности не от-личаются от случайных.
Также было проведено тестирование БСШ Camellia, SAFER++, RC6, Rijndael и SHACAL в режиме счетчика. Для исследований применялись описанные выше тесты. Результаты исследования показали, что гаммы шифрующие и криптограммы не отличаются от случай-ных, что подтверждает их хорошие криптографические свойства.
5 Вычислительная сложность криптографических преобразований при
программной и аппаратной реализации
Производительность БСШ после требований к безопасности криптоалгоритма является второй по важности характеристикой. По требованиям конкурса NESSIE криптоалгоритм должен удовлетворять требованиям программной и аппаратной реализации, сложность кото-рых была бы сопоставима со сложностью DES. Как уже отмечалось выше при программной реализации все криптоалгоритмы сравниваются по размеру кода: на различных языках про-граммирования, размеру исполняемого файла, объему потребляемой программой памяти и скорости выполнения криптографических операций. При аппаратной реализации учитыва-ются площадь, занимаемая реализацией алгоритма на кристалле, и скорость выполнения криптографических операций. Под криптографическими операциями понимаются операции разворачивания ключа, а также выполнения прямых и обратных криптографических преоб-разований.
Тестировались только криптоалгоритмы, относящиеся к высокому уровню безопасности и прошедшие первый тур конкурса NESSIE. Проверка программной реализации проводилась в два этапа. На первом было сгенерировано 100000 случайных ключей и 100000 открытых текстов. На втором этапе генерировалось 100 случайных ключей, которые потом разворачи-вались при использовании схем разворачивания ключей тестируемых криптоалгоритмов. Оценивалось время разворачивания. Далее производилось зашифрование сгенерированных открытых текстов с использованием этих ключей. Оценивалось время, затрачиваемое на за-шифрование информации. Потом производилось расшифрование и производилась оценка времени, затрачиваемого на эту операцию. Полученные после расшифровании тексты сверя-лись с исходными на соответствие. Время измерялось в количестве тактов, необходимых процессору для выполнения криптографического преобразования над одним байтом.
Тестирование выполнялось на процессорах типа Pentium III 850, 256 MB ОЗУ, Windows 2000 with Visual C++; на Pentium III Xeon @550 MHz, Visual C++ 6.0. Результаты сведены в табл. 5.
Таблица 5
Наименование криптоалгоритма Разворачивание ключа,тыс.тактов/ключ Зашифрование,циклов/байт Расшифрование,циклов/байт
Xeon PIII Xeon PIII Xeon PIII
Safer++/128 2,9 6,1 89 160 93 314
Camellia/128 3,0 4,2 172 162 238 212
RC6/128 2,9 6,1 49 53 49 52
Rijndael/256 0,53/2,1 0,68/2,0 59 54 69 56
Shacal/512 1 2,7 62 66 нет нет
SC2000 (128) 1,2 1,5 475 440 480 450
Nush128 2,8 2,3 45 110 42 90
Grandcru/128 150 181 3400 2600 5400 3900
Anubis 4,2 5,5 50 53 51 54
DES 16 17 103 117 98 111
Hierocrypt-3/128 183 605 63 150 70 170
Как видно из таблицы, криптоалгоритмы Grandcru и SC2000 имеют низкие показатели скорости, вследствие чего они не прошли во второй тур. Rijndael имеет две схемы разворачи-вания ключей одну для зашифрования, другую для расшифрования. Наиболее быстрым среди алгоритмов являются БСШ RC6 и Rijendael, которые положительно оценены еще при проведении конкурса AES.
Важным является исследование представленных криптоалгоритмов в аппаратном ис-полнении для выявления возможности реализации в ASIC- и FPGA-исполнении. В табл. 6 приведены некоторые из криптоалгоритмов в быстром исполнении, для сравнения приве-дены некоторые кандидаты из конкурса AES.
Таблица 6
Наименование алгоритма Площадь на кристалле (вентилей) Время разво-рачивания ключа (нс) Скорость (Мб/с)
Зашифрование/расшифрование Общая логика
DES 42,204 54,405 1161,31
Triple-DES 124,888 128,147 407,40
MARS 690,654 2,935,754 1740,99 225,55
RC6 741,641 1,643,037 2112,26 203,96
Rijndael 518,508 612,834 57,39 1950,03
Twofish 200,165 431,857 16,38 394,08
Camellia 216 272,819 24,36 1170,50
В таблице 7 приведены не оптимизированные данные для NESSIE конкурсантов в ASIC-и FPGA-исполнении.
Таблица 7
Криптоалгоритм Тип аппаратной реализации Скорость, Мб/с Детали
Camellia ASIC 0,35 ASIC 0,35 FPGA XC4000XL 1170220122 273 тыс. вентилей11 тыс. вентилей
Hierocrypt-3 ASIC 0,14 126MHz ASIC 0,14 185MHz FPGA 7,4MHz 8978553 81.5 тыс. вентилей26.7 тыс. вентилей
RC6-128 FPGA XCV1000 14MHz FPGA XCV1000 38MHz ASIC 0,5 12724001042200204
Rijndael-128 FPGA XCV1000 14MHz FPGA XCV1000 32MHz ASIC 0,5 300194052451001950 613 тыс. вентилей
Анализ представленных в табл. 6 и 7 данных, позволяет сделать вывод, что при аппарат-ной реализации имеют предпочтение Camellia и Rijndael.
6 Описание криптографических схем среди БСШ 1-го класса стойкости,
прошедших первый тур конкурса NESSIE
Первоначально к рассмотрению были допущены следующие криптоалгоритмы: CS-Cipher, Hierocrypt-L1, IDEA, Khazad, MISTY1, Nimbus (алгоритмы, относящиеся к 3-й кате-гории), Grand Cru, Noekeon, SHACAL (алгоритмы, относящиеся ко 2-й категории), NUSH, SAFER++, Hierocrypt-3, Q, RC6, SC2000, Anubis, Camellia, Rijndael-256 (алгоритмы, относя-щиеся к 1-й частично ко 2-й категории).
К сентябрю 2001 года была завершена первая фаза конкурса и отобраны следующие криптоалгоритмы: нормального и высокого уровня стойкости SAFER++, Camellia, RC6, Rijndael-256, SHACAL. Удовлетворительного уровня стойкости IDEA, Khazad, MISTY1.
На основе представленных в предыдущих разделах материалов можно выявить причи-ны, по которым не прошли конкурс те или иные криптоалгоритмы. CS-Cipher был отброшен вследствие низкой скорости (для всех кандидатов предъявлялись требования по скорости, сопоставимые со скоростями участников AES), Hierocrypt-L1 и Hierocrypt-3 имеют в основе одинаковую схему, но на них была проведена SQUARE-подобная атака, которая прошла на 3,5- и 6-цикловом вариантах данного криптоалгоритма. Также проведенные исследования показали, что алгоритм имеет плохие показатели скорости и были найдены слабые места в схеме разворачивания ключей. Криптоалгоритм Nimbus был успешно атакован при помощи атаки на основе выбранных открытых текстов. Росийский криптоалгоритм NUSH, предло-женный компанией ЛАН-Крипто, показал предельно минимальный уровень безопасности и атака с помощью линейного криптоанализа имеет меньшую сложность, чем атака грубая сила, вследствие чего криптоалгоритм не прошел во второй тур. Среди высокостойких блочных криптоалгоритмов сложилась следующая ситуация. Grand Cru, базируется на AES, однако показал плохие результаты по скорости. На Q была найдена атака намного быстрее, чем атака грубая сила. Noekeon показал плохие результаты против атаки на связанных ключах. Криптоалгоритмы SC2000 и Anubis качественно не отличаются от AES Rijendael.
Рассмотрим кратко оставшиеся криптоалгоритмы высокого уровня стойкости, их конст-руктивные особенности, преимущества и недостатки.
В криптоалгоритме SAFER++ не используется структура типа цепи Фейстеля. Шифр ра-ботает с блоками длинной 128 бит и длинами ключей 128, 256 и 512 бит. Процедуры зашиф-рования/расшифрования представляют собой последовательность итераций, число которых зависит от длины ключа и равно 8, 12 и 16 соответственно. В общем, работу шифра можно описать следующим образом: итерация зашифрования состоит из слоя подмешивания под-ключа, слоя нелинейной замены и еще одного слоя подмешивания ключа и линейного обра-тимого преобразования [10]. Интересным является решение линейного обратимого переме-шивания, которое реализовано в виде умножения текстового блока на специальную невыро-жденную матрицу. Это преобразование называется точечным псевдопреобразованием Ада-мара. При этом все операции выполняются побайтно по модулю 256. Достоинствами крипто-алгоритма является то, что он не использует сложных вычислительных операций, а исполь-зует побайтовые операции, что является предпочтительным при аппаратной реализации. Од-нако алгоритм не является инволютивным, т.е. при расшифровании необходимы другие опе-рации (вычитание), что увеличивает затраты на реализацию. Криптоалгоритм имеет откры-тую и легкоанализируемую структуру. В частности, проведенные Nakahara J.Jr [11] исследо-вания на устойчивость данной структуры против линейного криптоанализа подтвердили стойкость. К недостаткам данного алгоритма можно отнести следующее. Он имеет низкие показатели по скорости при реализации на 32- и 64-битных процессорах. SAFER++ имеет за-путанную и сложную схему разворачивания ключа, что приводит к большим затратам вре-мени при разворачивании ключа, а также может стать причиной ошибок при реализации. Это приводит к тому, что криптографическая безопасность алгоритма основана только на надеж-ности используемой математической базы. Потому для данного алгоритма отсутствуют дока-зательства полной защиты. SAFER++ является дальнейшим развитием давно известного SAFER-К64 и представленного на конкурсе AES SAFER+. Как показали исследования на схему разворачивания ключа SAFER+ [10], была успешно осуществлена атака со связанными ключами. В настоящий момент схема претерпела некоторые несущественные изменения, од-нако в самой основе она аналогична SAFER+.
Другим претендентом среди БСШ является RC6, который выдвигался еще на AES [12]. Этот криптоалгоритм является полностью параметризованным. Во всех вариантах RC6 рабо-тает с четырьмя n-битными блоками, используя 6 базовых операций: сложение и вычитание по модулю 2w, сложение по модулю 2, целочисленное умножение по модулю 2w и цикличе-ские сдвиги вправо и влево. В целом криптоалгоритм имеет легкоанализируемую и нагляд-ную схему. Алгоритм обладает высокой скоростью при реализации на широкораспростра-ненных процессорах РII, PIII, Athlon (см. табл. 5). Он подходит также и для программной реализации, в частности на языке Java. Однако использование модулярных операций сложе-ния и умножения плохо реализуется на некоторых 8-битовых процессорах, используемых в смарт-картах, что также играет немаловажную роль (табл. 1).
Структура алгоритма Camellia выбрана, исходя из возможности эффективной как про-граммной, так и аппаратной реализации [13]. Цикловое преобразование построено на основе хорошо известной схемы Фейстеля, что позволило разработчикам получить инволютивный шифр и значительно сократить затраты на его аппаратную реализацию. Однако в отличие от классической цепи Фейстеля, через каждые 6 циклов итеративного преобразования в обеих ветвях цепи выполняется Фейстель-подобное линейное преобразование над четвертушка-ми блока. Такая модификация не нарушает свойство инволютивности шифра, и по утвер-ждению разработчиков, позволяет увеличить сложность атак линейного и дифференциально-го криптоанализа за счёт того, что линейные и дифференциальные характеристики (и соот-ветствующие им вероятности) становятся ключезависимыми. Алгоритм является байт-ориентированным и может быть реализован на основе байтовых таблиц подстановки (реали-зация S-блоков) и простых логических операций, которые могут быть легко реализованы на большинстве современных платформ. Поэтому алгоритм может быть эффективно реализован как на высокопроизводительных 32- и 64-битных процессорах, так и на 8-битных процессо-рах, используемых в смарт-картах. Все S-блоки могут быть легко получены непосредственно из основной таблицы подстановки во время работы алгоритма, что значительно снижает за-траты на память и что важно при аппаратной реализации. Интересное решение используется разработчиками в схеме разворачивания ключей все подключи генерируются налету, т.е. нет необходимости генерировать их заранее с последующим сохранением в памяти. Хотя Camellia незначительно уступает некоторым другим конкурсантам в производительности на мощных 32-, 64-битных процессорах, он обеспечивает значительные результаты при реали-зации на спецпроцессорах (табл. 1).
Алгоритм Rijndael, представлен вариантом с длиной блока 256 бит и достаточно описан в различной литературе. Все операции, используемые в криптоалгоритме, проводятся в поле Галуа GF (28). Данный алгоритм достаточно хорошо исследован и показал приемлемые ре-зультаты по всем тестам. Алгоритм обладает приемлемой скоростью работы как при про-граммной, так и при аппаратной реализации. Он незначительно проигрывает при аппаратной реализации Camellia по занимаемой на кристалле площади. Недостатками алгоритма можно считать не совсем удачную схему разворачивания ключа. Алгоритм не имеет открытой легко анализируемой структуры, что не исключает в нем закладок или ошибок. Другой недоста-ток это восприимчивость к атакам, связанным с реализацией. Также исследования NESSIE указали, что данный криптоалгоритм имеет низкую границу безопасности. Это может сни-зить время безопасности криптоалгоритма до появления улучшенных методов и средств криптоанализа.
8 Выводы
Стойкость БСШ против криптоаналитических атак является определяющей его характе-ристикой. В настоящее время наибольшую угрозу для БСШ представляют аналитические атаки, постороенные на основе дифференциального и линейного криптоанализа, как правило на их видоизменениях. В проекте NESSIE принята практическая модель криптоанализа, при которой основными являются следующие параметры: время в виде количества тактов, необ-ходимый объем памяти и количество текстов, которые необходимы для выполнения крип-тоанализа.
Атака на БСШ может считаться успешной, если ее сложность не меньше сложности ата-ки типа грубая сила. Найти аналитическую атаку на полноцикловый БСШ сегодня практи-чески невозможно. Поэтому сравнение БСШ по стойкости можно проводить на уменьшен-ном числе циклов.
Лучшими по показателю реальной и статистической безопасности могут быть БСШ Ca-mellia, Rijndael, SAFER++, RC6 и SHACAL.
Статистическая безопасность названных БСШ проверялась с использованием корреля-ционного теста, а также тестов линейной аппроксимации и линейных факторов. Было также проведено статистическое тестирование БСШ в режимах счетчика и обратной связи по шифртексту. Результаты исследования показали, что гаммы шифрующие и криптограммы не отличаются от случайных, что подтверждает их хорошие свойства.
Основным недостатком БСШ SAFER++ является то, что он не является инволютивным, имеет худшие показатели по скорости при реализации на 32- и 64-битных процессорах. Кро-ме того, SAFER++ имеет запутанную и сложную схему разворачивания ключа. Поэтому вряд ли БСШ SAFER++ станет победителем, хотя он обеспечивает высокую стойкость.
БСШ RC6 обеспечивает высокую стойкость, имеет легко анализируемую и наглядную схему, обеспечивает высокую скорость при реализации на широко распространенных про-цессорах. Он эффективно может быть реализован программно. Однако модулярные опера-ции сложения и умножения плохо реализуются на некоторых 8-битовых процессорах.
Проведенные исследования и изложенное выше позволяют сделать вывод о предпочти-тельности БСШ Rijndael (AES), Camellia и SHACAL.
Список литературы: 1. Report on the NESSIE call. 1999. 2. Description of Methodology for Security Evalua-tion//NESSIE home page. , 1999. 3. Bart VanRompay, Vincent Rijment, Jorge Nakahara. A first report on CS-Ciper, Hierocrypt, Grand Cru, SAFER++ and SHACAL /NESSIE home page. , 2001. 4. Lars R. Knudsen A Differential Attack on Reduced-Round SC2000, Department of Informatics, University of Bergen, 2001. 5. Ali Biham. Differential cryptoanalisis of Q //NESSIE home page. , 2001. 6. Ali Biham. Preliminary report on the NESSIE submission Anubis, Camellia, Q, Nimbus. // NESSIE home page. , 2001. 7. NESIE security report // NESSIE home page., 2003. 8. Потий А.В., Орлова С.Ю. и др. Статистическое тестирование генераторов случайных и псевдослучайных чисел с использованием набора статистических тестов NIST STS. //Радиотехника: Всеукр межвед. науч.-техн. сб. 2000. Вып. 114. С. 14. 9. Nomination of SAFER++ as candidate algorithm for the NESSIE, 2000. 10. Nakahara J. Jr. Cryptanalysis of reduced-round SAFER++, 2001. 11. Schneier B., Kelsey J. Key-Schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, 2001. 12. RC6 Block Cipher, 2000. 13. Ca-mellia: A 128 bit block cipher suitable for multiple platforms, 2000.