ГОСТ 28147—89

ГОСТ 28147-89
Создатель:	КГБ, 8-е управление
Создан:	1989 г.
Опубликован:	1990 г.
Размер ключа:	256 бит
Размер блока:	64 бит
Число раундов:	32\16
Тип:	Сеть Фейстеля

ГОСТ 28147—89 — советский и российский стандарт симметричного шифрования, введённый в 1990 году. Полное название — «ГОСТ 28147—89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования». Блочный шифроалгоритм. При использовании метода шифрования с гаммированием, может выполнять функции поточного шифроалгоритма.

По некоторым сведениям^[1], история этого шифра гораздо более давняя. Алгоритм, положенный впоследствии в основу стандарта, родился, предположительно, в недрах Восьмого Главного управления КГБ СССР (ныне в структуре ФСБ), скорее всего, в одном из подведомственных ему закрытых НИИ, вероятно, ещё в 1970-х годах в рамках проектов создания программных и аппаратных реализаций шифра для различных компьютерных платформ.

С момента опубликования ГОСТа на нём стоял ограничительный гриф «Для служебного пользования», и формально шифр был объявлен «полностью открытым» только в мае 1994 года. К сожалению, история создания шифра и критерии разработчиков до сих пор не опубликованы.

Описание

ГОСТ 28147—89 — блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра — Сеть Фейстеля. Базовым режимом шифрования по ГОСТ 28147—89 является режим простой замены (определены также более сложные режимы гаммирование, гаммирование с обратной связью и режим имитовставки). Для зашифрования в этом режиме открытый текст сначала разбивается на две половины (младшие биты - A, старшие биты - B^[2]). На i-ом цикле используется подключ K_i:

$~A_{i+1} = B_i \oplus f(A_i, K_i)$ ($\oplus$ = двоичное «исключающее или»)

$~B_{i+1} = A_i$

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: K₁…K₈.

Ключи K₉…K₂₄ являются циклическим повторением ключей K₁…K₈ (нумеруются от младших битов к старшим). Ключи K₂₅…K₃₂ являются ключами K₁…K₈, идущими в обратном порядке.

После выполнения всех 32 раундов алгоритма, блоки A₃₃ и B₃₃ склеиваются (обратите внимание, что старшим битом становится A₃₃, а младшим - B₃₃) - результат есть результат работы алгоритма.

Расшифрование выполняется так же, как и зашифрование, но инвертируется порядок подключей K_i.

Функция f(A_i,K_i) вычисляется следующим образом:

A_i и K_i складываются по модулю 2³².

Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком. Общее количество S-блоков ГОСТа — восемь, т. е. столько же, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая — на вход второго и т. д.

Если S-блок выглядит так:

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

и на входе S-блока 0, то на выходе будет 1, если 5, то на выходе будет 7 и т. д.

Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов.

Все восемь S-блоков могут быть различными. Фактически, они могут являться дополнительным ключевым материалом, но чаще являются параметром схемы, общим для определенной группы пользователей. В ГОСТ Р 34.11-94 для целей тестирования приведены следующие S-блоки:

Номер S-блока	Значение
1	4	10	9	2	13	8	0	14	6	11	1	12	7	15	5	3
2	14	11	4	12	6	13	15	10	2	3	8	1	0	7	5	9
3	5	8	1	13	10	3	4	2	14	15	12	7	6	0	9	11
4	7	13	10	1	0	8	9	15	14	4	6	12	11	2	5	3
5	6	12	7	1	5	15	13	8	4	10	9	14	0	3	11	2
6	4	11	10	0	7	2	1	13	3	6	8	5	9	12	15	14
7	13	11	4	1	3	15	5	9	0	10	14	7	6	8	2	12
8	1	15	13	0	5	7	10	4	9	2	3	14	6	11	8	12

Согласно данным книги Б. Шнайера «Прикладная криптография», эти же блоки используются также Центральным Банком РФ.

В тексте стандарта указывается, что поставка заполнения узлов замены (S-блоков) производится в установленном порядке, т.е. разработчиком алгоритма.

Достоинства ГОСТа

• бесперспективность силовой атаки (XSL-атаки в учёт не берутся, т.к. их эффективность на данный момент полностью не доказана);
• эффективность реализации и соответственно высокое быстродействие на современных компьютерах.
• наличие защиты от навязывания ложных данных (выработка имитовставки) и одинаковый цикл шифрования во всех четырех алгоритмах ГОСТа.

Криптоанализ

Существуют атаки и на полнораундовый ГОСТ 28147—89 без каких-либо модификаций. Одна из первых открытых работ, в которых был проведен анализ алгоритма, использует слабости процедуры расширения ключа ряда известных алгоритмов шифрования. В частности, полнораундовый алгоритм ГОСТ 28147—89 может быть вскрыт с помощью дифференциального криптоанализа на связанных ключах, но только в случае использования слабых таблиц замен. 24-раундовый вариант алгоритма (в котором отсутствуют первые 8 раундов) вскрывается аналогичным образом при любых таблицах замен, однако, сильные таблицы замен делают такую атаку абсолютно непрактичной.

Отечественные ученые А.Г. Ростовцев и Е.Б. Маховенко в 2001 г. предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциальный криптоанализ) путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей алгоритма ГОСТ 28147—89, которые позволяют вскрыть алгоритм с помощью всего 4-х выбранных открытых текстов и соответствующих им шифротекстов с достаточно низкой сложностью. Криптоанализ алгоритма продолжен в работе.

В 2004 г. группа специалистов из Кореи предложила атаку, с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7% 12 бит секретного ключа. Для атаки требуется 2³⁵ выбранных открытых текстов и 2³⁶ операций шифрования. Как видно, данная атака практически бесполезна для реального вскрытия алгоритма.

Критика ГОСТа

Основные проблемы ГОСТа связаны с неполнотой стандарта в части генерации ключей и таблиц замен. Тривиально доказывается, что у ГОСТа существуют «слабые» ключи и таблицы замен, но в стандарте не описываются критерии выбора и отсева «слабых». Также стандарт не специфицирует алгоритм генерации таблицы замен (S-блоков). С одной стороны, это может являться дополнительной секретной информацией (помимо ключа), а с другой, поднимает ряд проблем:

• нельзя определить криптостойкость алгоритма, не зная заранее таблицы замен;
• реализации алгоритма от различных производителей могут использовать разные таблицы замен и могут быть несовместимы между собой;
• возможность преднамеренного предоставления слабых таблиц замен лицензирующими органами РФ;
• потенциальная возможность (отсутствие запрета в стандарте) использования таблиц замены, в которых узлы не являются перестановками, что может привести к чрезвычайному снижению стойкости шифра.

Примечания

1. ↑ А. Винокуров. Алгоритм шифрования ГОСТ 28147-89, его использование и реализация для компьютеров платформы Intel x86
2. ↑ В описании стандарта ГОСТ обозначены как N₁ и N₂ соответственно

См. также

• Гаммирование
• Имитовставка
• Имитозащита
• ГОСТ Р 34.10-2001

Ссылки

• Описание алгоритма, реализация, исходники, статьи и ссылки
• Статья о ГОСТ 28147-89
• Текст ГОСТ 28147-89

Литература

• Мельников В. В. Защита информации в компьютерных системах. — М.: Финансы и статистика, 1997.
• Романец Ю. В.. Тимофеев П. А., Шаньгин В. Ф. Защита информации в компьютерных системах и сетях. — М.: Радио и связь, 1999.
• Харин Ю. С., Берник В. И., Матвеев Г. В. Математические основы криптологии. — Мн.: БГУ, 1999.
• Герасименко В. А., Малюк А. А. Основы защиты информации. — М.: МГИФИ, 1997.
• Леонов А. П., Леонов К. П., Фролов Г. В. Безопасность автоматизированных банковских и офисных технологий. — Мн.: Нац. кн. палата Беларуси, 1996.
• Зима В. М.. Молдовян А. А., Молдовян Н. А. Компьютерные сети и защита передаваемой информации. — СПб.: СПбГУ, 1998.
• Шнайер Б. 14.1 Алгоритм ГОСТ 28147-89 // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 373-377. — 816 с. — 3000 экз. — ISBN 5-89392-055-4