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

ГОСТ

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

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

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

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

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

L_i = R_i-1

R_i = L_i-1 Å f(R_i-1, K_i)

Этап ГОСТ показан на Рис. 14-1. Функция f проста. Сначала правая половина и i-ый подключ складываются по модулю 2³². Результат разбивается на восемь 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-битовых блоков: k₁, k₂, . . .k₈. На каждом этапе используется свой подключ, как показано в Табл. 14-1. Дешифрирование выполняется также, как и шифрование, но инвертируется порядок подключей k_i.

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

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

Совсем недавно стал известным набор 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:

S-блок 2:

S-блок 3:

S-блок 4:

S-блок 5:

S-блок 6:

S-блок 7:

S-блок 8:

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

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

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

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

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-битового ключа. Если k₁, k₂, . . .k₈ - это 8 байтов ключа, то на этапах алгоритма используются следующие подключи:

Этап 1: k₁, k₂

Этап 2: k₃, k₄

Этап 3: k₅, k₆

Этап 4: k₇, k₈

Этап 5: k₄, k₃

Этап 6: k₂, k₁

Этап 7: k₈, k₇

Этап 8: k₆, k₅

Сила этого алгоритма заключена в его S-блоках. У CAST нет фиксированных S-блоков, для каждого приложения они конструируются заново. Критерии проектирования описаны в [10], изогнутыми функциями являются столбцы S-блоков, обеспечивающие необходимые свойства S-блоков (см. раздел 14.10). Созданный для данной реализации CAST S‑блоков уже больше никогда не меняется. S-блоки зависят от реализации, а не от ключа.

В [10] было показано, что CAST устойчив к дифференциальному криптоанализу, а в [728] - что CAST устойчив и к линейному криптоанализу. Неизвестно иного, чем грубая сила, способа вскрыть CAST.

Northern Telecom использует CAST в своем пакете программ Entrust для компьютеров Macintosh, PC и рабочих станций UNIX. Выбранные ими S-блоки не опубликованы. Канадское правительство считает CAST новым стандартом шифрования. Патентная заявка на CAST находится в процессе рассмотрения.

BLOWFISH

Blowfish - это алгоритм, разработанный лично мной для реализации на больших микропроцессорах [1388, 1389]. Алгоритм незапатентован, и его код на языке C приведен в конце этой книги для широкого пользования. При проектировании Blowfish я использовал следующие критерии:

1. Скорость. Blowfish шифрует данные на 32-битовых микропроцессорах со скоростью 26 тактов на байт.

2. Компактность. Blowfish может работать менее, чем в 5 Кбайт памяти.

3. Простота. Blowfish использует только простые операции: сложение, XOR и выборка из таблицы по 32-битовому операнду. Анализ его схемы несложен, что делает при реализации алгоритма уменьшает количество ошибок [1391].

4. Настраиваемая безопасность. Длина ключа Blowfish переменна и может достигать 448 битов.

Blowfish оптимизирован для тех приложений, в которых нет частой смены ключей, таких как линии связи или программа автоматического шифрования файлов. При реализации на 32-битовых микропроцессорах с большим кэшем данных, таких как Pentium и PowerPC, Blowfish заметно быстрее DES. Blowfish не подходит для использования в приложениях с частой сменой ключей, например, при коммутации пакетов, или для использования в качестве однонаправленной хэш-функции. Большие требования к памяти делают невозможным использование этого алгоритма в интеллектуальных платах.

Описание Blowfish

Blowfish представляет собой 64-битовый блочный шифр с ключом переменной длины. Алгоритм состоит из двух частей: развертывание ключа и шифрование данных. Развертывание ключа преобразует ключ длиной до 448 битов в несколько массивов подключей, общим объемом 4168 байтов.

Шифрование данных состоит из простой функции, последовательно выполняемой 16 раз. Каждый этап состоит из зависимой от ключа перестановки и зависимой от ключа и данных подстановки. Используются только сложения и XOR 32-битовых слов. Единственными дополнительными операциями на каждом этапе являются четыре извлечения данных из индексированного массива.

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

P-массив состоит из 18 32-битовых подключей:

P1, P2, . . ., P18

Каждый из четырех 32-битовых S-блоков содержит 256 элементов:

S_1,0, S_1,1, . . ., S_1,255

S_2,0, S_2,2, . . ., S_2,255

S_3,0, S_3,3, . . ., S_3,255

S_4,0, S_4,4, . . ., S_4,255

Точный метод, используемый при вычислении этих подключей описан в этом разделе ниже.

Рис. 14-2. Blowfish.

Blowfish является сетью Фейстела (Feistel) (см. раздел 14.10), состоящей из 16 этапов. На вход подается 64-битовый элемент данных x. Для шифрования:

Разбейте x на две 32-битовых половины: x_L, x_R

Для i = 1 по 16:

x_L = x_L Å P₁₈

x_R = F(x_L) Å x_R

Переставить x_L и x_R (кроме последнего этапа.)

x_R = x_R Å P₁₇

x_L = x_L Å P₁₈

Объединить x_L и x_R

Рис. 14-3. Функция F.

Функция F представляет собой следующее (см. Рис. 14-3):

Разделить x_L на четыре 8-битовых части: a, b, c и d
F(x_L) = ((S_1,a + S_2,b mod 2³²) Å S_3,c)+ S_4,d mod 2³²

Дешифрирование выполняется точно также, как и шифрование, но P₁, P₂, . . ., P₁₈ используются в обратном порядке.

В реализациях Blowfish, для которых требуется очень большая скорость, цикл должен быть развернут, а все ключи должны храниться в кэше. Подробности приведены в [568].

Подключи рассчитываются с помощью специального алгоритма. Вот какова точная последовательность действий.

(1) Сначала P-массив, а затем четыре S-блока по порядку инициализируются фиксированной строкой. Эта строка состоит из шестнадцатиричных цифр p.

(2) Выполняется XOR P₁ с первыми 32 битами ключа, XOR P₂ со вторыми 32 битами ключа, и так далее для всех битов ключа (до P₁₈). Используется циклически, пока для всего P-массива не будет выполнена операция XOR с битами ключа.

(3) Используя подключи, полученные на этапах (1) и (2), алгоритмом Blowfish шифруется строка из одних нулей.

(4) P₁ и P₂ заменяются результатом этапа (3).

(5) Результат этапа (3) шифруется с помощью алгоритма Blowfish и измененных подключей.

(6) P₃ и P₄ заменяются результатом этапа (5).

(7) Далее в ходе процесса все элементы P-массива и затем по порядку все четыре S-блока заменяются выходом постоянно меняющегося алгоритма Blowfish.

Всего для генерации всех необходимых подключей требуется 521 итерация. Приложения могут сохранять подключи - нет необходимости выполнять процесс их получения многократно.