ГОСТ 28147-89

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 02:32, 12 июня 2016.

Шаблон:Проверка+

Краткое описание

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

Так же стоит обратить внимание на:

История блочного шифра ГОСТ

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

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

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

Описание

Файл:GOSTDiagram.png
ГОСТ 28147-89

ГОСТ 28147-89 — блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра — Сеть Фейстеля.

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

( = двоичное «исключающее или»)

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

Ключи K9…K24 являются циклическим повторением ключей K1…K8 (нумеруются от младших битов к старшим). Ключи K25…K32 являются ключами K1…K8, идущими в обратном порядке.

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

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

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

Ai и Ki складываются по модулю 232.

Результат разбивается на восемь 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, если 4, то на выходе будет 5, если на входе 12, то на выходе 6 и т. д.

Выходы всех восьми 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-блоков) производится в установленном порядке, то есть разработчиком алгоритма. Сообщество российских разработчиков СКЗИ согласовало используемые в Интернет узлы замены, см. RFC 4357.

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

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

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

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

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

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

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

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

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

ГОСТ 28147-89 vs DES

ГОСТ DES
Внутренняя разработка КГБ, что делает его закрытым для общественности. Является корпоративной разработкой, открыт для общественного пользования.
Удобен в реализации в варианте soft и hardware Легок в реализации в hardware варианте, сложно реализовать в варианте soft продукта.
Учел все предыдущие разработки и ошибки, более прогрессивный, используется в настоящий момент. Не рекомендован к использованию.
Не очень популярен из-за закрытости алгоритма, конкретно S-блоков, которые выдаются в ФСБ по запросу. Обладал высокой популярностью.
Обладает хорошей стойкостью ключа. На данный момент не известны случаи взлома. Был взломан перебором.
Сравнение стойкости ключевого пространства: Block:64, Key 256 - большей запас ключевого пространства. Сравнение стойкости ключевого пространства: Block:64, Key 56 - можно перебрать на современных ЭВМ, за небольшой период времени.

Режимы шифрования в ГОСТ

Описание алгоритма

ГОСТ 28147-89 является отечественным блочным шифром. То есть открытый текст разбивается на блоки (в данном случае 64 бита), и каждый блок преобразовывается отдельно. В основу алгоритма положена сеть Фейстеля, представленная на рисунке ниже. Feistel.jpg

  • Каждый блок разбивается на два «подблока» (левый и правый, соотвественно).
  • Исходное заполнение правого блока записывается в левый блок на выходе.
  • Над правым блоком производится криптографическое преобразование с применением ключевых данных.
  • Левый (исходный) и правый (преобразованный) блоки складываются по модулю 2 в сумматоре по модулю 2.
  • Так повторяется несколько раз.

Структурная схема алгоритма

Gostshem.gif

Данная схема содержит

  • Четыре накопителя по 32 бита: N1, N2, N3, N4.
  • Два 32-разрядных накопителя: N5 и N6, — с записанными в них постоянными заполнениями C2 и C1 соответственно.
  • Ключевое запоминающее устройство (КЗУ) на 256 бит. КЗУ состоит из восьми накопителей по 32 разряда каждый: X, X1, X2, X3, X4, X5, X6, X7.
  • 32-разрядный сумматор по модулю 2: СМ2.
  • Еще один сумматор по модулю 2, который не имеет ограничения на разрядность (но используется 64 бита): СМ5.
  • Два сумматора по модулю 232 разрядности 32 бита: СМ1, СМ3.
  • Сумматор по модулю (232-1): СМ4.
  • Блок подстановки К: восемь узлов замены K1, K2, K3, K4, K5, K6, K7, K8, каждый с памятью на 64 бита.
    • Регистр циклического сдвига влево на 11 бит R.

Ключи

В КЗУ

КЗУ отведено 256 бит, в ГОСТ 28147-89 используется ключ длиной 256 бит. Ключ разбивается на восемь блоков по 32 бита, и каждый бит каждого блока последовательно вводится в накопитель X соответствующего порядка.

То есть, 1-й бит ключа вводится в 1-й разряд накопителя X, 2-й — во 2-й разряд накопителя X, 33-й — в 1-й разряд накопителя X1, 65-й — в 1-й разряд накопителя X2, и так далее, 224-й бит ключа вводится в 1-й разряд накопителя X7, 256-й бит ключа вводится в 32-й разряд накопителя X7.

Считывается же ключ в соответствии с выбранным режимом работы алгоритма, но в следующих частях статьи.

В блоке подстановки K

Блок подстановки содержит в себе таблицу замены размерностью 16x8, которая является долговременным ключом.

Строки таблицы определяют, грубо говоря, что требуется заменить (число от 0 до 15 в шестнадцатиричной системе счисления). Столбцы же указывают, на что заменять. При этом поступающий 32-битовый в блок вектор разбивается на восемь 4-х битовых, каждый из которых и преобразуется в соответствии с таблицой замены.

Ключи как в КЗУ, так и в блоке К, являются секретными, и требуются меры по недопущению их компрометации.

Режимы работы ГОСТ

См. также

  1. Security Evaluation of GOST 28147-89 In View Of International Standardisation
  2. Пас из-за границы — атака на ГОСТ (Алексей Чиликов)
  3. ГОСТ 28147-89