ГОСТ 28147-89

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
ГОСТ 28147-89
изображение
Создатель:

КГБ, 8-е управление

Создан:

1989 г.

Опубликован:

1990 г.

Размер ключа:

256 бит

Размер блока:

64 бит

Число раундов:

32\16

Тип:

сеть Фейстеля

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

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

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

Описание[править | править вики-текст]

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

Режим простой замены[править | править вики-текст]

Функция f(Ai, Ki), используемая в сети Фейстеля

Для зашифровывания в этом режиме 64-битный блок открытого текста сначала разбивается на две половины (младшие биты — A, старшие биты — B[3]). На i-ом цикле используется подключ Ki:

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

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

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

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

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

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

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

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

Режим простой замены имеет следующие недостатки:

  • Может применяться только для шифрования открытых текстов с длиной, кратной 64 бит [2]
  • При шифровании одинаковых блоков открытого текста получаются одинаковые блоки шифротекста, что может дать определенную информацию криптоаналитику.

Таким образом, применение ГОСТ 28147-89 в режиме простой замены желательно лишь для шифрования ключевых данных. [2]

Гаммирование[править | править вики-текст]

Схема работы в режиме гаммирования

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

Выработка гаммы происходит на основе ключа и так называемой синхропосылки, которая задает начальное состояние генератора. Алгоритм выработки следующий:

  1. Синхропосылка шифруется с использованием описанного алгоритма простой замены, полученные значения записываются во вспомогательные 32-разрядные регистры N3 и N4 - младшие и старшие биты соответственно.
  2. N3 суммируется по модулю 232 с константой C2 = 101010116
  3. N4 суммируется по модулю 232-1 с константой C1 = 101010416
  4. N3 и N4 переписываются соответственно в N1 и N2, которые затем шифруются с использованием алгоритма простой замены. Полученный результат является 64 битами гаммы.
  5. Шаги 2-4 повторяются в соответствии с длиной шифруемого текста.

Для расшифровывания необходимо выработать такую же гамму, после чего побитно сложить ее по модулю 2 с зашифрованным текстом. Очевидно, для этого нужно использовать ту же синхропосылку, что и при шифровании. При этом, исходя из требований уникальности гаммы, нельзя использовать одну синхропосылку для шифрования нескольких массивов данных. Как правило, синхропосылка тем или иным образом передается вместе с шифротекстом.

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

Гаммирование с обратной связью[править | править вики-текст]

Схема работы в режиме гаммирования с обратной связью

Алгоритм шифрования похож на режим гаммирования, однако гамма формируется на основе предыдущего блока зашифрованных данных, так что результат шифрования текущего блока зависит также и от предыдущих блоков. По этой причине данный режим работы также называют гаммированием с зацеплением блоков.

Алгоритм шифрования следующий:

  1. Синхропосылка заносится в регистры N1 и N2
  2. Содержимое регистров N1 и N2 шифруется в соответствии с алгоритмом простой замены. Полученный результат является 64-битным блоком гаммы.
  3. Блок гаммы побитно складывается по модулю 2 с блоком открытого текста. Полученный шифротекст заносится в регистры N1 и N2
  4. Операции 2-3 выполняются для оставшихся блоков требующего шифрования текста.

При изменении одного бита шифротекста, полученного с использованием алгоритма гаммирования с обратной связью, в соответствующем блоке расшифрованного текста меняется только один бит, так же затрагивается последующий блок открытого текста. При этом все остальные блоки остаются неизменными.[2]

Режим выработки имитовставки[править | править вики-текст]

Схема выработки имитовставки

Этот режим не является в общепринятом смысле режимом шифрования. При работе в режиме выработки имитовставки создаётся некоторый дополнительный блок, зависящий от всего текста и ключевых данных. Данный блок используется для проверки того, что в шифротекст случайно или преднамеренно не были внесены искажения. Это особенно важно для шифрования в режиме гаммирования, где злоумышленник может изменить конкретные биты, даже не зная ключа; однако и при работе в других режимах вероятные искажения нельзя обнаружить, если в передаваемых данных нет избыточной информации.

Имитовставка вырабатывается для M ≥ 2 блоков открытого текста по 64 бит. Алгоритм следующий:

  1. Блок открытых данных записывается в регистры N1 и N2, после чего подвергается преобразованию, соответствующему первым 16 циклам шифрования в режиме простой замены
  2. К полученному результату побитно по модулю 2 прибавляется следующий блок открытых данных. Последний блок при необходимости дополняется нулями. Сумма также шифруется в соответствии с пунктом 1.
  3. После добавления и шифрования последнего блока из результата выбирается имитовставка длиной L бит: с бита номер 32-L до 32(отсчет начинается с 1). Стандарт рекомендует выбирать L исходя из того, что вероятность навязывания ложных данных равна 2-L. Имитовставка передается по каналу связи после зашифрованных блоков.

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

Следует отметить, что выработка имитовставки может проводиться параллельно шифрованию с использованием одного из описанных выше режимов работы.[2]

Узлы замены (S-блоки)[править | править вики-текст]

Все восемь S-блоков могут быть различными. Некоторые считают, что они могут являться дополнительным ключевым материалом, увеличивающим эффективную длину ключа; однако существуют применимые на практике атаки, позволяющие их определить.[4] Впрочем, и необходимости в увеличении длины ключа нет, 256 бит вполне достаточно в настоящее время.[5] Как правило, таблицы замен являются долговременным параметром схемы, общим для определенной группы пользователей.


Узлы замены определенные документом RFC 4357


Идентификатор: id-GostR3411-94-TestParamSet

Номер S-блока Значение
0 1 2 3 4 5 6 7 8 9 A B C D E F
1 4 A 9 2 D 8 0 E 6 B 1 C 7 F 5 3
2 E B 4 C 6 D F A 2 3 8 1 0 7 5 9
3 5 8 1 D A 3 4 2 E F C 7 6 0 9 B
4 7 D A 1 0 8 9 F E 4 6 C B 2 5 3
5 6 C 7 1 5 F D 8 4 A 9 E 0 3 B 2
6 4 B A 0 7 2 1 D 3 6 8 5 9 C F E
7 D B 4 1 3 F 5 9 0 A E 7 6 8 2 C
8 1 F D 0 5 7 A 4 9 2 3 E 6 B 8 C

Этот узел замены определен ГОСТ Р 34.11-94 для целей тестирования. Данный узел замен используется в криптографических приложениях ЦБ РФ.[5]


OID: 1.2.643.2.2.31.1

Идентификатор: id-Gost28147-89-CryptoPro-A-ParamSet

Номер S-блока Значение
0 1 2 3 4 5 6 7 8 9 A B C D E F
1 9 6 3 2 8 B 1 7 A 4 E F C 0 D 5
2 3 7 E 9 8 A F 0 5 2 6 C B 4 D 1
3 E 4 6 2 B 3 D 8 C F 5 A 0 7 1 9
4 E 7 A C D 1 3 9 0 2 B 4 F 8 5 6
5 B 5 1 9 8 D F 0 E 4 2 3 C 7 A 6
6 3 A D C 1 2 0 B 7 5 9 4 8 F E 6
7 1 D 2 9 7 A 6 0 8 C 4 5 F 3 B E
8 B A F 5 0 C E 8 6 2 3 9 1 7 D 4

Данный узел замен используется криптопровайдером CryptoPRO CSP по умолчанию. Так же данный узел замен используется в ПО "Верба-О"[6]


OID: 1.2.643.2.2.31.2

Идентификатор: id-Gost28147-89-CryptoPro-B-ParamSet

Номер S-блока Значение
0 1 2 3 4 5 6 7 8 9 A B C D E F
1 8 4 B 1 3 5 0 9 2 E A C D 6 7 F
2 0 1 2 A 4 D 5 C 9 7 3 F B 8 6 E
3 E C 0 A 9 2 D B 7 5 8 F 3 6 1 4
4 7 5 0 D B 6 1 2 3 A C F 4 E 9 8
5 2 7 C F 9 5 A B 1 4 0 D 6 8 E 3
6 8 3 2 6 4 D E B C 1 7 F A 0 9 5
7 5 2 A B 9 1 C 3 7 4 D 0 6 F 8 E
8 0 4 B E 8 3 7 1 A 2 9 6 F D 5 C

Данный узел замен используется криптопровайдером CryptoPRO CSP


OID: 1.2.643.2.2.31.3

Идентификатор: id-Gost28147-89-CryptoPro-C-ParamSet

Номер S-блока Значение
0 1 2 3 4 5 6 7 8 9 A B C D E F
1 1 B C 2 9 D 0 F 4 5 8 E A 7 6 3
2 0 1 7 D B 4 5 2 8 E F C 9 A 6 3
3 8 2 5 0 4 9 F A 3 7 C D 6 E 1 B
4 3 6 0 1 5 D A 8 B 2 9 7 E F C 4
5 8 D B 0 4 5 1 2 9 3 C E 6 F A 7
6 C 9 B 1 8 E 2 4 7 3 6 5 A 0 F D
7 A 9 6 8 D E 2 0 F 3 5 B 4 1 C 7
8 7 4 0 5 A 2 F E C 6 1 B D 9 3 8

Данный узел замен используется криптопровайдером CryptoPRO CSP


OID: 1.2.643.2.2.31.4

Идентификатор: id-Gost28147-89-CryptoPro-D-ParamSet

Номер S-блока Значение
0 1 2 3 4 5 6 7 8 9 A B C D E F
1 F C 2 A 6 4 5 0 7 9 E D 1 B 8 3
2 B 6 3 4 C F E 2 7 D 8 0 5 A 9 1
3 1 C B 0 F E 6 5 A D 4 8 9 3 7 2
4 1 5 E C A 7 0 D 6 2 B 4 9 3 F 8
5 0 C 8 9 D 2 A B 7 3 6 5 4 E F 1
6 8 0 F 3 2 5 E B 1 A 4 7 C 9 D 6
7 3 0 6 F 1 E 9 2 D 8 C 4 B A 5 7
8 1 A 6 8 F B 0 4 C 3 5 9 7 D 2 E

Данный узел замен используется криптопровайдером CryptoPRO CSP


Узел замены определенный комитетом по стандартизации ТК26 Росстандарта [7]

OID: 1.2.643.7.1.2.5.1.1

Идентификатор: id-tc26-gost-28147-param-A

Номер S-блока Значение
0 1 2 3 4 5 6 7 8 9 A B C D E F
1 C 4 6 2 A 5 B 9 E 8 D 7 0 3 F 1
2 6 8 2 3 9 A 5 C 1 E 4 7 B D 0 F
3 B 3 5 8 2 F A D E 1 7 4 C 9 6 0
4 C 8 2 1 D 4 F 6 7 0 A 5 3 E 9 B
5 7 F 5 A 8 1 6 D 0 9 3 E B 4 2 C
6 5 D F 6 9 2 C A B 7 8 1 4 3 E 0
7 8 E 2 5 6 9 1 C F 4 B 0 D A 3 7
8 1 7 E D 0 5 8 3 4 F A 6 9 C B 2

Данный узел замен предлагался комитетом ТК 26 Росстандарта при международной стандартизации ГОСТ 28147-89 в составе стандарта шифрования ISO/IEC 18033-3 и рекомендуется отечественным разработчикам.


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

Достоинства ГОСТа[править | править вики-текст]

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

Криптоанализ[править | править вики-текст]

Считается,[8] что ГОСТ устойчив к таким широко применяемым методам, как линейный и дифференциальный криптоанализ. Обратный порядок использования ключей в последних восьми раундах обеспечивает защиту от атак скольжения (slide attack) и отражения (reflection attack). Ростовцев А.Г., Маховенко Е.Б., Филиппов А.С., Чечулин А.А. в своей работе [9] описали вид криптоанализа, который сводится к построению алгебраической целевой функции и нахождению ее экстремума. Были выделены классы слабых ключей, в частности, показано, что разреженные ключи (со значительным преобладанием 0 или 1) являются слабыми. По мнению авторов, их метод в любом случае лучше, чем полный перебор, однако без численных оценок.

В мае 2011 года известный криптоаналитик Николя Куртуа доказал существование атаки на данный шифр, имеющей сложность в 28 (256) раз меньше сложности прямого перебора ключей при условии наличия 264 пар открытый текст/закрытый текст. [10][11]Данная атака не может быть осуществлена на практике ввиду слишком высокой вычислительной сложности. Более того, знание 264 пар открытый текст/закрытый текст, очевидно, позволяет читать зашифрованные тексты, даже не вычисляя ключа. В большинстве других работ также описываются атаки, применимые только при некоторых предположениях, таких как определенный вид ключей или таблиц замен, некоторая модификация исходного алгоритма, или же требующие все еще недостижимых объемов памяти или вычислений. Вопрос о наличии применимых на практике атак без использования слабости отдельных ключей или таблиц замены остается открытым.[4]

Критика ГОСТа[править | править вики-текст]

Основные проблемы ГОСТа связаны с неполнотой стандарта в части генерации ключей и таблиц замен. Считается, что у ГОСТа существуют «слабые» ключи и таблицы замен[9], но в стандарте не описываются критерии выбора и отсева «слабых».

В октябре 2010 года на заседании 1-го объединенного технического комитета Международной организации по стандартизации (ISO/IEC JTC 1/SC 27) ГОСТ был выдвинут на включение в международный стандарт блочного шифрования ISO/IEC 18033-3. В связи с этим в январе 2011 года были сформированы фиксированные наборы узлов замены и проанализированы их криптографические свойства. Однако ГОСТ не был принят в качестве стандарта, и соответствующие таблицы замен не были опубликованы [12]

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

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

Возможные применения[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Об организации - Межгосударственный Совет по стандартизации, метрологии и сертификации. Проверено 28 января 2013. Архивировано из первоисточника 1 февраля 2013.
  2. 1 2 3 4 5 6 7 А. Винокуров. Алгоритм шифрования ГОСТ 28147-89, его использование и реализация для компьютеров платформы Intel x86
  3. В описании стандарта ГОСТ обозначены как N1 и N2 соответственно
  4. 1 2 Панасенко С. П. Стандарт шифрования ГОСТ 28147-89
  5. 1 2 Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си, 2-е издание — М.: Триумф, 2002, 14.1
  6. Идентификаторы криптографических параметров алгоритмов
  7. Методические рекомендации по заданию узлов замены блока подстановки алгоритма шифрования ГОСТ 28147-89
  8. Vitaly V. Shorin, Vadim V. Jelezniakov and Ernst M. Gabidulin Linear and Differential Cryptanalysis of Russian GOST // Electronic Notes in Discrete Mathematics. — 2001. — С. 538-547.
  9. 1 2 Ростовцев А.Г., Маховенко Е.Б., Филиппов А.С., Чечулин А.А. О стойкости ГОСТ 28147–89 // Проблемы информационной безопасности. Компьютерные системы. — 2003. — С. 75-83.
  10. Nicolas T. Courtois. Security Evaluation of GOST 28147-89 In View Of International Standardisation. Архивировано из первоисточника 7 декабря 2012.. Cryptology ePrint Archive: Report 2011/211
  11. SecurityLab: Взломан блочный шифр ГОСТ 28147-89. Архивировано из первоисточника 7 декабря 2012.
  12. Технический комитет по стандартизации (ТК 26) "Криптографическая защита информации" О деятельности по международной стандартизации алгоритма шифрования ГОСТ 28147-89.
  13. Leontiev S., Chudov G. Using the GOST 28147-89, GOST R 34.11-94, GOST R 34.10-94, and GOST R 34.10-2001 Algorithms with Cryptographic Message Syntax (CMS) (англ.) (May 2006). — RFC 4490. Проверено 21 июня 2009. Архивировано из первоисточника 24 августа 2011.
  14. Leontiev, S., Ed. and G. Chudov, Ed. GOST 28147-89 Cipher Suites for Transport Layer Security (TLS) (англ.) (December 2008). — Internet-Drafts, work in progress. Проверено 21 июня 2009. Архивировано из первоисточника 24 августа 2011.
  15. S. Leontiev, P. Smirnov, A. Chelpanov. Using GOST 28147-89, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms for XML Security (англ.) (December 2008). — Internet-Drafts, work in progress. Проверено 21 июня 2009. Архивировано из первоисточника 24 августа 2011.

См. также[править | править вики-текст]


Литература[править | править вики-текст]

  • Мельников В. В. Защита информации в компьютерных системах. — М.: Финансы и статистика, 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.
  • Popov, V., Kurepkin, I., and S. Leontiev Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms (англ.) // RFC 4357. — IETF, January 2006.

Ссылки[править | править вики-текст]