Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
На микропроцессоре 80286/10 МГц ассемблерная реализация FEAL-32 может шифровать данные со скор о- стью 220 Кбит/с. FEAL-64 может шифровать данные со скоростью 120 Кбит/с [1104]. fK 64 бита 32 бита 32 бита 32 бита Блок ключа B 0 A 0 fK K 0 , K 1 D 7 D 1 B 1 A 1 K 2 , K 3 fK B 7 A 7 K 14 , K 15 Рис. 13-5. Обработка ключа в FEAL. S 1 S 0 S 1 X 2 Y X 1 S 0 a i , b i - 8 бит 32 бита 32 бита 32 бита a 3 a 2 a 1 a b b 3 f K (a,b) b 2 b 1 b 0 a 0 Y=S 0 (X 1 ,X 2 )=Rot2((X 1 +X 2 ) mod 256) Y=S 1 (X 1 ,X 2 )=Rot2((X 1 +X 2 +1) mod 256) Y: выходные 8 битов, X 1 ,X 2 (8 битов): входы Rot2(Y): циклический сдвиг влево на 2 бита 8-битовых данных Y Рис. 13-6. Функция f K Криптоанализ FEAL Успешный криптоанализ FEAL-4, FEAL с четырьмя этапами, был выполнен с помощью вскрытия с выбра н- ными открытыми текстами [201], а позже слабость этого алгоритма была показана в [1132]. Последнее вскр ы- тие, выполненное Сином Мерфи (Sean Murphy), было первым опубликованным вскрытием, использовавшим дифференциальный криптоанализ, и для него потребовалось только 20 выбранных открытых текстов. Ответом разработчиков стал 8-этапный FEAL [1436, 1437, 1108], криптоанализ которого был представлен Бихамом и Шамиром на конференции SECURICOM '89 [1424]. Для вскрытия FEAL-8 с выбранными открытыми текстами потребовалось только 10000 блоков [610], что заставило разработчиков алгоритма засучить рукава и опред е- лить FEAL-N [1102, 1104], алгоритм с переменным числом этапов (конечно же, большим 8). Бихам и Шамир применили против FEAL-N дифференциальный криптоанализ, хотя они могли бы еще б ы- стрее вскрыть его грубой силой (с помощью менее, чем 2 64 шифрований выбранного открытого текста) для N , меньшего 32. [169]. Для вскрытия FEAL-16 нужно 2 28 выбранных или 2 46.5 известных открытых текстов. Для вскрытия FEAL-8 требуется 2000 выбранных или 2 37.5 известных открытых текстов. FEAL-4 может быть вскрыт с помощью всего 8 правильно выбранных открытых текстов. Разработчики FEAL определили также модификацию FEAL - FEAL-NX, в которой используется 128- битовый ключ (см. 6-й) [1103, 1104]. Бихам и Шамир показали, что для любого значения N FEAL-NX со 128- битовым ключом взламывать не сложнее, чем FEAL-N с 64-битовым ключом [169]. Недавно был предложен FEAL-N(X)S, усиливающий FEAL за счет динамической фун кции обмена местами [1525]. fK 32 бита Обработка бита четности K L K R2 K R2 K R1 K R1 K R Блок ключа (K L |K R ): 128 битов B 0 A 0 fK K 0 , K 1 D 1 Q 2 Q 1 B 1 A 1 K 2 , K 3 D N/2+2 fK B N/2+3 B N/2+2 A N/2+2 K N+4 , K N+5 32 бита D N/2+3 fK A N/2+3 K N+6 , K N+7 fK D 2 Q N/2+4 Q N/2+3 Q 3 B 2 A 2 K 4 , K 5 Q r =K R1 ? K R2 , r=1, 4, 7, ... Q r =K R1 , r=2, 5, 8, ... Q r =K R2 , r=3, 6, 9, ... K 2(r-1) : левая половина B r (16 битов) K 2(r-1)+1 : правая половина B r (16 битов) Число итераций: N/2+4 Рис. 13-7. Обработка ключа в FEAL-NX. Более того. В [1520] было представлено другое вскрытие FEAL-4, требующее только 1000 известных откр ы- тых текстов, и FEAL-8, для которого нужно только 20000 известных открытых текстов. Другие вскрытия прив е- дены в [1549, 1550]. Наилучшим является выполненное Мицуру Мацуи (Mitsuru Matsui) и Атшуиро Ямагиши (Atshuiro Yamagishi) [1020]. Это было первое применение линейного криптоанализа, и оно позволило вскрыть FEAL-4 с помощью 5 известных открытых текстов, FEAL-6 - с помощью 100 известных открытых текстов, а FEAL-8 - с помощью 2 15 известных открытых текстов. Дальнейшие уточнения можно найти в [64]. Диффере н- циальный криптоанализ позволяет вскрывать FEAL-8, используя только 12 выбранных открытых текстов [62]. Кто бы не изобрел новый метод криптоаналитического вскрытия, кажется, что он всегда сначала пробует его на FEAL. Патенты FEAL запатентован в Соединенных Штатах [1438], соответствующие патенты приняты к рассмотрению в Англии, Франции и Германии. Желающий лицензировать использование алгоритма должен связаться с Дера п- таментом интеллектуальной собственности (Intellectual Property Department), NTT, 1-6 Uchisaiwai-cho, 1-chome, Chiyada-ku, 100 Japan. 13.5 REDOC REDOC II представляет собой другой блочный алгоритм, разработанный Майклом Вудом (Michael Wood) для Cryptech, Inc. [1613, 400]. В нем используются 20-байтовый (160-битовый) ключ и 80-битовый блок. REDOC II выполняет все манипуляции - перестановки, подстановки и XOR с ключом - с байтами, этот а л- горитм эффективен при программной реализации. REDOC II использует меняющиеся табличные функции. В отличие от DES, имеющего фиксированный (хотя и оптимизированных для безопасности) набор таблиц подст а- новок и перестановок REDOC II использует зависимые от ключа и открытого текста наборы таблиц (по сути S- блоков). У REDOC II 10 этапов, каждый этап представляет собой сложную последовательность манипуляций с блоком. Другой уникальной особенностью является использование масок, которые являются числами, полученными из таблицы ключей, и используются для выбора таблиц данной функции для данного этапа. Для выбора таблиц функции используются как значение данных, так и маски. При условии, что самым эффективным средством вскрытия этого алгоритма является грубая сила, REDOC II очень надежен: для вскрытия ключа требуется 2 160 операций. Томас Кузик (Thomas Cusick) выполнил крипто а- нализ одного этапа REDOC II, но ему не удалось расширить вскрытие на несколько этапов [400]. Используя дифференциальный криптоанализ, Бихам и Шамир достигли успеха в криптоанализе одного этапа REDOC II с помощью 2300 выбранных открытых текстов [170]. Они не смогли расширить это вскрытие на несколько эт а- пов, но им удалось получить три значения маски после 4 этапов. О других попытках криптоанализа мне не и з- вестно. REDOC III REDOC представляет собой упрощенную версию REDOC II, также разработанную Майклом Вудом [1615]. Он работает с 80-битовым блоком. Длина ключа может меняться и достигать 2560 байтов (20480 битов). Алг о- ритм состоит только из операций XOR для байтов ключа и открытого текста, перестановки или подстановки не используются. (1) Создать таблицу ключей из 256 10-байтовых ключей, используя секретный ключ. (2) Создать 2 10-байтовых блока маски M 1 и M 2 . M 1 представляет собой XOR первых 128 10-байтовых кл ю- чей, а M 2 - XOR вторых 128 10-байтовых ключей. (3) Для шифрования 10-байтового блока: (a) Выполнить XOR для первого байта блока данных и первого байта M 1 . Выбрать ключ из таблицы ключей, рассчитанной на этапе (1). Использовать вычисленное значение XOR в качестве индекса таблицы. Выполнить XOR каждого, кроме первого, байта блока данных с соответствующим байтом выбранного ключа. (b) Выполнить XOR для второго байта блока данных и второго байта M 1 . Выбрать ключ из таблицы ключей, рассчитанной на этапе (1). Использовать вычисленное значение XOR в качестве индекса таблицы. Выполнить XOR каждого, кроме второго, байта блока данных с соответствующим байтом выбранного ключа. (c) Продолжать для всего блока данных (для байтов с 3 по 10), пока каждый байт не будет использован для выбора ключа из таблицы после выполнения для него XOR с соответствующим значением M 1 Затем выполнить XOR с ключом для каждого, кроме использованного для выбора ключа, байта. (d) Повторить для M 2 этапы (a)-(c). Этот алгоритм несложен и быстр. На 33 мегагерцовом процессоре 80386 он шифрует данные со скоростью 2.75 Мбит/с. Вуд оценил, что конвейеризированная реализация на СБИС с 64 битовой шиной данных могла бы шифровать данные со скоростью свыше 1.28 Гбит/с при тактовой частоте 20 МГц. REDOC III не безопасен [1440]. Он чувствителен к дифференциальному криптоанализу. Для восстановления обеих масок нужно всего примерно 223 выбранных открытых текстов. Патенты и лицензии Обе версии REDOC запатентованы в Соединенных штатах [1614]. Рассматриваются и иностранные патенты. При заинтересованности в REDOC II или REDOC III обращайтесь к Майклу Вуду (Michael C. Wood, Delta Computec, Inc., 6647 Old Thompson Rd., Syracuse, NY 13211). 13.6 LOKI LOKI разработан в Австралии и впервые был представлен в 1990 году в качестве возможной альтернативы DES [273]. В нем используются 64-битовый блок и 64-битовый ключ. Общая структура алгоритма и использ о- вания ключа описана в [274, 275], а схема S-блоков - в [1247]. Используя дифференциальный криптоанализ, Бихам и Шамир смогли взломать LOKI с 11 и менее этапами быстрее, чем грубой силой [170]. Более того, алгоритм обладает 9-битовой комплиментарностью, что уменьш а- ет сложность вскрытия грубой силой в 256 раз [170, 916, 917]. Ларс Кнудсен (Lars Knudsen) показал, что LOKI с 14 и менее этапами чувствителен к дифференциальному криптоанализу [852, 853]. Кроме того, если в LOKI используются альтернативные S-блоки, получающийся шифр вероятно также будет чувствителен к дифференциальному криптоанализу. LOKI91 В ответ на эти вскрытия разработчики LOKI вернулись за чертежную доску и пересмотрели свой алгоритм. Результатом было появление LOKI91 [272]. (Предыдущая версия LOKI была переименована в LOKI89.) Чтобы повысить устойчивость алгоритма к дифференциальному криптоанализу и избавиться от комплиме н- тарности, в оригинальный проект были внесены следующие изменения: 1. Алгоритм генерации подключей был изменен так, чтобы половины переставлялись не после каждого, а после каждого второго этапа. 2. Алгоритм генерации подключей был изменен так, чтобы количество позиций циклического сдвига л е- вого подключа было равно то 12, то 13 битам. 3. Были устранены начальная и заключительная операции XOR блока и ключа. 4. Была изменена функция S-блока с целью сгладить XOR профили S-блоков (чтобы повысить их усто й- чивость к дифференциальному криптоанализу), и не допустить, чтобы для какого-то значения выпо л- нялось f(x) = 0, где f - это комбинация E-, S- и P-блоков. Описание LOKI91 Механизм LOKI91 похож на DES (см. Рис. 13-8). Блок данных делится на левую и правую половины и пр о- ходит через 16 этапов, что очень походе на DES. На каждом этапе правая половина сначала подвергается оп е- рации XOR с частью ключа, а затем над ней выполняется перестановка с расширением (см. Табл. 13-1). Ключ К Открытый текст K L 32 K R 32 R 32 L 32 ROL 13 ROL 12 K (2) 32 P S E P S E P S E P S E P S E P S E Шифротекст ROL 13 ROL 12 K (3) 32 K (4) 32 ROL 13 ROL 12 K (15) 32 K (16) 32 Рис. 13-8. LOKI91. Табл. 13-1. Перестановка с расширением 4, 3, 2, 1, 32, 31, 20, 29, 28, 27, 26, 25, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 48-битовый результат делится на четыре 12-битовых блока, для каждого из которых выполняется следующая подстановка с использованием S-блока: берется каждый 12-битовый вход, по 2 крайних левых и крайних пр а- вых бита используются для получения номера r, в 8 центральных бит образуют номер c. Результатом S-блока - O - является следующее значение: O(r,c) = (c + ((r* 17) ? 0xff) & 0xff) 31 mod P r P r приведено в Табл. 13-2. Табл. 13-2. P r r: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 P r : 375, 279, 391, 395, 397, 415, 419, 425, 433, 445, 451, 463, 471, 477, 487, 488 Затем четыре 8-битовых результата снова объединяются, образуя 32-битовое число, которое подвергается операции перестановки, описанной в Табл. 13-3. Наконец для получения новой левой половины выполняется XOR правой половины с прежней левой половиной, а левая половина становится новой правой половиной. П о- сле 16 этапов для получения окончательного шифротекста снова выполняется XOR блока и ключа. Табл. 13-3. Перестановка с помощью P-блока 32, 24, 16, 8, 31, 23, 15, 7, 30, 22, 14, 6, 29, 21, 13, 5, 28, 20, 12, 4, 27, 19, 11, 3, 26, 18, 10, 2, 25, 17, 9, 1 Подключи из ключа выделяются достаточно прямолинейно. 64-битовый ключ разбивается на левую и пр а- вую половины. На каждом этапе подключом является левая половина. Далее она циклически сдвигается влево на 12 или 13 битов, затем после каждых двух этапов левая и правая половины меняются местами. Как и в DES для шифрования и дешифрирования используется один и тот же алгоритм с некоторыми изменениями в испол ь- зовании подключей. Криптоанализ LOKI91 Кнудсен предпринял попытку криптоанализа LOKI91 [854, 858], но нашел, что этот алгоритм устойчив к дифференциальному криптоанализу. Однако ему удалось обнаружить, что вскрытие со связанными ключами для выбранных открытых текстов уменьшает сложность вскрытия грубой силой почти вчетверо. Это вскрытие использует слабость использования ключа и может быть также применено, если алгоритм используется в кач е- стве однонаправленной хэш-функции (см. раздел 18.11). Другое вскрытие со связанными ключами может вскрыть LOKI91 с помощью 2 32 выбранных открытых тек- стов для выбранных ключей или с помощью 2 48 известных открытых текстов для выбранных ключей [158]. Это вскрытие не зависит от числа этапов алгоритма. (В той же работе Бихам вскрывает LOKI89, используя кри п- тоанализ со связанными ключами, с помощью 2 17 выбранных открытых текстов для выбранных ключей или с помощью 2 33 известных открытых текстов для выбранных ключей.) Несложно повысить устойчивость LOKI91 к вскрытию такого типа, усложнив схему использования ключа. Патенты и лицензии LOKI не запатентован. Кто угодно может реализовать алгоритм и использовать его. Исходный код, прив е- денный в этой книге, написан в Университете Нового Южного Уэльса. При желании использовать эту реализ а- цию (или другие реализации, которые на несколько порядков быстрее) в коммерческом продукте обращайтесь к Директору CITRAD, Факультет компьютерных наук, Университетский колледж, Университет Нового Южного Уэльса, Академия австралийских вооруженных сил, Канберра, Австралия (Director CITRAD, Department of Computer Science, University College, UNSW, Australian Defense Force Academy, Canberra ACT 2600, Australia; FAX: +61 6 268 8581. 13.7 KHUFU и KHAFRE В 1990 году Ральф Меркл (Ralph Merkle) предложил два алгоритма. В основе их проектирования лежали следующие принципы [1071]: 1. 56-битовый размер ключа DES слишком мал. Так как стоимость увеличения размера ключа прене б- режимо мала (компьютерная память недорога и доступна), он должен быть увеличен. 2. Интенсивное использование перестановок в DES хотя и удобно для аппаратных реализаций, чрезв ы- чайно затрудняет программные реализации. Наиболее быстрые реализации DES выполняют перест а- новки табличным образом. Просмотр таблицы может обеспечить те же характеристики "рассеяния", что и собственно перестановки, и может сделать реализацию намного более гибкой. 3. S-блоки DES, всего с 64 4-битовыми элементами, слишком малы. Теперь с увеличением памяти должны увеличиться и S-блоки. Более того, все восемь S-блоков используются одновременно. Хотя это и удобно для аппаратуры, для программной реализации это кажется ненужным ограничением. Должны быть реализованы больший размер S-блоков и последовательное (а не параллельное) их и с- пользование. 4. Широко признано, что начальная и заключительная перестановки криптографически бессмысленны, поэтому они должны быть устранены. 5. Все быстрые реализации DES заранее рассчитывают ключи для каждого этапа. При данном условии нет смысла усложнять эти вычисления. 6. В отличие от DES критерии проектирования S-блоков должны быть общедоступны. К этому перечню Меркл, возможно, теперь добавил бы "устойчивость к дифференциальному и линейному криптоанализу", ведь в то время эти способы вскрытия не были известны. Khufu Khufu - это 64-битовый блочный шифр. 64-битовый открытый тест сначала разбивается на две 32-битовые половины, L и R. Над обеими половинами и определенными частями ключа выполняется операция XOR. Затем, аналогично DES, результаты проходят через некоторую последовательность этапов. На каждом этапе младший значащий байт L используется в качестве входных данных S-блока. У каждого S-блока 8 входных битов и 32 выходных бита. Далее выбранный в S-блоке 32-битовый элемент подвергается операции XOR с R. Затем L цик- лически сдвигается не несколько из восьми битов, L и R меняются местами, и этап заканчивается. Сам S-блок не является статическим, но меняется каждые восемь этапов. Наконец после последнего этапа над L и R выпол- няется операция XOR с другими частями ключа, и половины объединяются, образуя блок шифротекста. Хотя части ключа используются для XOR с блоком шифрования в начале и в конце алгоритма, главная цель ключа -генерация S-блоков. Эти S-блоки - секретны, по сути являются они являются частью ключа. Полный размер ключа Khufu равен 512 битам (64 байтам), алгоритм предоставляет способ генерации S-блоков по кл ю- чу. Количество этапов алгоритма остается открытым. Меркл упомянул, что 8-этапный Khufu чувствителен к вскрытию с выбранным открытым текстом и рекомендует 16, 24 или 32 этапа [1071]. (Он ограничивает выбор количества этапов числами, кратными восьми.) Так как в Khufu используются зависимые от ключа и секретные S-блоки, он устойчив к дифференциальному криптоанализу. Существует дифференциальное вскрытие 16-этапного Khufu, которое раскрывает ключ после 2 31 |