памяти. Непохоже, чтобы оба этих слуха были правдой.

Еще один слух утверждает, что этапы Skipjack, в отличие от DES, работают не с половиной блока. Это вм е-сте с замечанием о "сдвигах" и случайном заявлении на Crypto 94 о том, что в Skipjack применяется "48-битовая внутренняя структура", позволяет сделать вывод, что алгоритм по своей схеме похож на SHA (см. ра з-дел 18.7), но использует четыре 16-битовых подблока. Три подблока, обработанные зависящей от ключа одн о-направленной функцией, дают 16 битов, которые подвергаются операции XOR с оставшимся подблоком. Затем весь блок циклически сдвигается на 16 битов и поступает на вход следующего этапа, или сдвига. При этом та к-же используются 128 байтов данных S-блока. Я подозреваю, что S-блоки зависят от ключа.

По своей структуре Skipjack вероятно похож на DES. NSA понимает, что его защищенная от взлома аппар а-тура в конце концов будет вскрыта и исследована, они не будут рисковать никакими передовыми криптограф и-ческими методами.

То, что NSA планирует использовать алгоритм Skipjack для шифрования своей Системы защиты сообщений (Defense Messaging System, DMS), свидетельствует о безопасности алгоритма. Чтобы убедить скептиков, NIST разрешил комиссии "уважаемых неправительственных экспертов . . . получить доступ к конфиденциальным подробностям алгоритма, чтобы они исследовали его возможности и опубликовали результаты своих исслед о-

ваний " [812].

В предварительном отчете этой комиссии экспертов [262] (окончательного отчета не было, и возможно ник о-гда не будет) сообщалось:

Принимая во внимание, что стоимость вычислительных мощностей уменьшается в два раза каждые 18 месяцев, сло ж-ность вскрытия Skipjack сравняется с сегодняшней сложностью вскрытия DES только через 36 лет. Следовательно, риск, что Skipjack будет взломан в ближайшие 30-40 лет, незначителен.

Незначителен и риск взлома Skipjack с помощью более быстрых способов вскрытия, включая дифференциальный кри п-тоанализ. У алгоритма не слабых ключей, отсутствует и свойство комплиментарности. Эксперты в отсутствие времени для самостоятельного большого исследования алгоритма изучили представленное NSA описание разработки и проверки алг о-ритма

Устойчивость Skipjack к криптоанализу не зависит от хранения в тайне самого алгоритма.

Итак, участники дискуссии не смогли поработать с алгоритмом достаточно долго, чтобы прийти к каким-нибудь выводам самостоятельно. Все, что они смогли сделать - это взглянуть на результаты, показанные им

NSA.

0стался без ответа вопрос, является ли плоским пространство ключей Skipjack (см. раздел 8.2). Даже если у Skipjack нет ключей, слабых в смысле DES, ряд особенностей процесса использования ключа может сделать одни ключи сильнее других. У Skipjack может быть 270 сильных ключей, гораздо больше чем у DES, вероятность случайно выбрать один из этих сильных ключей будет приблизительно 1 к 1000. Лично я думаю, что пр о-странство ключей Skipjack - плоское, но то, что об этом никто не заявил публично, вызывает тревогу.

Skipjack запатентован, но в соответствии с соглашением о секретности патента [1122] этот патент хранится в тайне. Патент будет опубликован тогда и только тогда, когда алгоритм Skipjack будет успешно восстановлен кем-то посторонним. Это дает возможность правительству воспользоваться и преимуществом защиты патентом, и преимуществом конфеденциальности торгового секрета.

Глава 14

И еще о блочных шифрах

14.1 ГОСТ

ГОСТ - это блочный алгоритм, разработанный в бывшем Советском Союзе [655, 1393]. Название "ГОСТ" является сокращением от "Государственный стандарт", нечто похожее на FIPS за исключением того, что это название могут носить стандарты практически любого типа. (Полным названием является "Государственный стандарт Союза ССР", или "Государственный стандарт Союза Советских Социалистических Республик".) Н о-мер данного стандарта - 28147-89. Все эти стандарты утверждаются Государственным комитетом по стандартам

Союза ССР.

Я не знаю, использовался ли ГОСТ 28147-89 для засекреченного трафика или только для гражданского шифрования. Замечание в начале стандарта гласит, что алгоритм "удовлетворяет всем криптографическим тр е-бованиям, а степень защищаемой информации не ограничивается". Я слышал утверждения, что этот алгоритм первоначально использовался только для очень важных линий связи, включая секретные военные коммуник а-ции, но у меня нет подтверждений.

Описание ГОСТ

ГОСТ является 64-битовым алгоритмом с 256-битовым ключом. ГОСТ также использует дополнительный ключ, который рассматривается ниже. В процессе работы алгоритма на 32 этапах последовательно выполняется простой алгоритм шифрования.

Для шифрования текст сначала разбивается на левую половину L и правую половину R. На этапе i используется подключ Ki. На этапе i алгоритма ГОСТ выполняется следующее:

Li- = Ri-1

Ri- = Li-1 © f(Ri-1, Ki)

Этап ГОСТ показан на Рис. 14-1. Функция f проста. Сначала правая половина и i-ый подключ складываются по модулю 232. Результат разбивается на восемь 4-битовых кусочков, каждый из которых поступает на вход св о-его S-блока. ГОСТ использует восемь различных S-блоков, первые 4 бита попадают в первый S-блок, вторые 4 4 бита - во второй S-блок, и т.д. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Например, S-блок может выглядеть как:

7, 10, 2, 4, 15, 9, 0, 3, 6, 12, 5, 13, 1, 8, 11

Выбор подключа

Подстановка з-блоком

Циклический сдвиг влево

Ri-i

Рис. 14-1. Этап ГОСТ.

В этом случае, если на входе S-блока 0, то на выходе 7. Если на входе 1, на выходе 10, и т.д. Все восемь S-блоков различны, они фактически являются дополнительным ключевым материалом. S-блоки должны хр а-ниться в секрете.

Выходы всех восьми S-блоков объединяются в 32-битовое слово, затем все слово циклически сдвигается влево на 11 битов. Наконец результат объединяется с помощью XOR с левой половиной, и получается новая правая половина, а правая половина становится новой левой половиной. Выполните это 32 раза, и все в поря д-

Генерация подключей проста. 256-битовый ключ разбивается на восемь 32-битовых блоков: k1, k2, . . .k8. На каждом этапе используется свой подключ, как показано в Табл. 14-1. Дешифрирование выполняется также, как и шифрование, но инвертируется порядок подключей ki.

Стандарт Г0СТ не определяет способ генерации S-блоков, говорится только, что блоки должны быть пр е-доставлены каким-то образом [655]. Это породило домыслы о том, что советский производитель может поста в-лять хорошие S-блоки "хорошим" организациям и плохие S-блоки тем организациям, которых производитель собирается надуть. Это вполне может быть так, но неофициальные переговоры с российским производителем микросхем Г0СТ выявили другую альтернативу. Производитель создает перестановки S-блока самостоятельно с помощью генератора случайных чисел.

Табл. 14-1.

Использование подключей на различных этапах ГОСТ

Этап: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Подключ: 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

Этап: 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Подключ: 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1

Совсем недавно стал известным набор S-блоков, используемых в приложениях Центрального Банка РФ. Эти S-блоки также используются в однонаправленной хэш-функции Г0СТ (см. раздел 18.11) [657]. 0ни перечисл е-ны в Табл. 14-2.

Криптоанализ ГОСТ

Вот главные различия между DES и COST.

- DES использует сложную процедуру для генерации подключей из ключей. В Г0СТ эта процедура очень проста.

- В DES 56-битовый ключ, а в Г0СТ - 256-битовый. Если добавить секретные перестановки S-блоков, то полный объем секретной информации Г0СТ составит примерно 610 битов.

- У S-блоков DES 6-битовые входы и 4-битовые выходы, а у S-блоков Г0СТ 4-битовые входы и выходы. В обоих алгоритмах используется по восемь S-блоков, но размер S-блока Г0СТ равен одной четвертой размера S-блока DES.

- В DES используются нерегулярные перестановки, названные P-блоком, а в Г0СТ используется 11-битовый циклический сдвиг влево.

- В DES 16 этапов, а в Г0СТ - 32.

Табл. 14-2. S-блоки ГОСТ

S-блок 1:

4 10 9 2 13 8 0 14 6 11 1 12 7 15 5 3 S-блок 2:

141141261315102381 0759

S-блок 3:

5 8 1 13 10 3 4 2 14 15 12 7 6 0 9 11 S-блок 4:

7 13 10 1 0 8 9 15 14 4 6 12 11 2 5 3 S-блок 5:

61271 51513841091403112

S-блок 6: