Глава 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(Ri4, 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

/ иЯмВыбор подключа

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

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

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

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

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

Табл. 14-1.

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

Этап:12345678910111213141516

Подключ:1234567812345678

Этап:17181920212223242526272829303132

Подключ:1234567887654321

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

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

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

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

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

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

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

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

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

S-блок 1:

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

1411412613151023810759

S-блок 3:

58 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:

612 7 1 5 15 13 8 4 10 9 14 0 3 11 2

S-блок 6:

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

1311413155901014768212

S-блок 8:

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

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

Другие части ГОСТ такие же, как в DES, или слабее. ГОСТ не использует существующую в DES перест а-новку с расширением. Удаление этой перестановки из DES ослабляет его из-за уменьшения лавинного эффекта, разумно считать, что отсутствие такой операции в ГОСТ ослабляет этот алгоритм. Сложение, используемое в ГОСТ, не менее безопасно, чем используемая в DES операция XOR.

Самым большим различием представляется использование в ГОСТ циклического сдвига вместо перестано в-ки. Перестановка DES увеличивает лавинный эффект. В ГОСТ изменение одного входного бита влияет на один S-блок одного этапа, который затем влияет на два S-блока следующего этапа, три блока следующего этапа, и т.д.. В ГОСТ потребуется 8 этапов прежде, чем изменение одного входного бита повлияет на каждый бит р е-зультата, алгоритму DES для этого нужно только 5 этапов. Это, конечно же, слабое место. Но не забывайте: ГОСТ состоит из 32 этапов, а DES только из 16.

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

14.2 CAST

CAST был разработан в Канаде Карлайслом Адамсом (Carlisle Adams) и Стаффордом Таваресом (Stafford Tavares) [10, 7]. Они утверждают, что название обусловлено ходом разработки и должно напоминать о вероя т-ностном характере процесса, а не об инициалах авторов. Описываемый алгоритм CAST использует 64-битовый блок и 64-битовый ключ.

CAST имеет знакомую структуру. Алгоритм использует шесть S-блоков с 8-битовым входом и 32-битовым выходом. Работа этих S-блоков сложна и зависит от реализации, подробности можно найти в литературе.

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

(1)Разбейте 32-битовый вход на четыре 8-битовых части: a, b, c, d.

(2)Разбейте 16-битовый подключ на две 8-битовых половины: e, f

(3)Подайте a на вход S-блока 1, b - на вход S-блока 2, c - на вход S-блока 3, d - на вход S-блока 4, e - на вход S-блока 5 и f - на вход S-блока 6.

(4)Выполните XOR шести выходов S-блоков, получая 32-битовый результат.

Иначе, 32-битовый вход может быть объединен с помощью XOR с 32 битами ключа, разбит на четыре 8-битовых части, которые обрабатываются S-блоками и затем объединяются с помощью XOR [7]. Безопасность N этапов, организованных таким образом, по видимому, соответствует N + 2 этапам другого варианта.

16-битовые подключи этапов легко получаются из 64-битового ключа. Если k1, k2, . . .k8 - это 8 байтов ключа, то на этапах алгоритма используются следующие подключи:

Этап 1: k1, k2