ГОСТ (блочный шифр)
 Схема ГОСТ | |
| Общий | |
|---|---|
| Дизайнеры | СССР , КГБ , 8-й отдел |
| Впервые опубликовано | 23 мая 1994 г. (рассекречено) |
| Преемники | Хеш-функция ГОСТ , Кузнечик |
| Сертификация | ГОСТ стандарт |
| Деталь шифрования | |
| Размеры ключей | 256 бит |
| Размеры блоков | 64 бита |
| Структура | Сеть Фейстеля |
| Раунды | 32 |
| Лучший публичный криптоанализ | |
| В 2011 году несколько авторов обнаружили более существенные недостатки в ГОСТ, впервые получив возможность атаковать полный 32-раундовый ГОСТ с помощью произвольных ключей. даже назвал его «глубоко ошибочным шифром» Николя Куртуа . [ 1 ] | |
Блочный шифр ГОСТ ( Магма ), определенный в стандарте ГОСТ 28147-89 (RFC 5830), представляет собой советский и российский государственный блочный с симметричным ключом шифр и размером блока 64 бита. Исходный стандарт, опубликованный в 1989 году, не давал шифру никакого названия, но в самой последней редакции стандарта, ГОСТ Р 34.12-2015 (RFC 7801, RFC 8891), указано, что его можно называть Магмой. [ 2 ] хеш- функция ГОСТ На этом шифре основана . Новый стандарт также определяет новый 128-битный блочный шифр под названием «Кузнечик» .
Разработанный в 1970-х годах стандарт имел гриф «Совершенно секретно», а затем в 1990 году ему был присвоен статус «Секретно». Вскоре после распада СССР он был рассекречен и обнародован в 1994 году. ГОСТ 28147 был советским стандартом. альтернатива США стандартному алгоритму DES . [ 3 ] Таким образом, они очень похожи по структуре.
Алгоритм
[ редактировать ]64 бита ГОСТ имеет размер блока и длину ключа 256 бит. Его S-блоки могут быть секретными и содержат около 354 (log 2 (16! 8 )) бит секретной информации, поэтому эффективный размер ключа можно увеличить до 610 бит; однако атака с выбранным ключом может восстановить содержимое S-блоков примерно за 2 32 шифрование. [ 4 ]
ГОСТ представляет собой сеть Фейстеля из 32 витков. Его функция округления очень проста: добавьте 32-битный подраздел по модулю 2. 32 , пропустите результат через слой S-блоков и поверните этот результат влево на 11 бит. Результатом этого является вывод функции округления. На соседней диаграмме одна линия представляет 32 бита.
Подключи выбираются в заранее заданном порядке. Схема ключей очень проста: разбейте 256-битный ключ на восемь 32-битных подразделов, и каждый подраздел используется в алгоритме четыре раза; в первых 24 раундах ключевые слова используются по порядку, в последних 8 раундах они используются в обратном порядке.
S-блоки принимают четырехбитный входной сигнал и выдают четырехбитный выходной сигнал. Замена S-блока в функции раунда состоит из восьми S-блоков 4 × 4. S-блоки зависят от реализации, поэтому стороны, которые хотят защитить свои коммуникации с помощью ГОСТ, должны использовать одни и те же S-блоки. Для дополнительной безопасности S-блоки можно держать в секрете. В исходном стандарте, где был указан ГОСТ, никаких S-box не было, но их надо было как-то поставить. Это привело к предположениям, что организациям, за которыми правительство хотело шпионить, были предоставлены слабые S-блоки. Один производитель чипов ГОСТ сообщил, что он сам генерировал S-блоки с помощью генератора псевдослучайных чисел . [ 5 ]
Например, ЦБ РФ использовал следующие S-box:
| # | S-бокс |
|---|---|
| 1 | 4 А 9 2 Г 8 0 Е 6 Б 1 В 7 Ж 5 3 |
| 2 | ЭБ 4 С 6 ДФА 2 3 8 1 0 7 5 9 |
| 3 | 5 8 1 DA 3 4 2 EFC 7 6 0 9 Б |
| 4 | 7 DA 1 0 8 9 FE 4 6 CB 2 5 3 |
| 5 | 6 С 7 1 5 ФД 8 4 А 9 Е 0 3 Б 2 |
| 6 | 4 BA 0 7 2 1 D 3 6 8 5 9 ДОВСЕ |
| 7 | БД 4 1 3 Ж 5 9 0 АЕ 7 6 8 2 С |
| 8 | 1 ФД 0 5 7 А 4 9 2 3 Е 6 Б 8 С |
Однако в самой последней редакции стандарта, ГОСТ Р 34.12-2015 , добавлена недостающая спецификация S-box и определена она следующим образом. [ 2 ]
| # | ГОСТ Р 34.12-2015 Коробка S-образная. |
|---|---|
| 1 | С 4 6 2 А 5 Б 9 Е 8 Г 7 0 3 Ж 1 |
| 2 | 6 8 2 3 9 А 5 С 1 Е 4 7 BD 0 F |
| 3 | Б 3 5 8 2 ЗАТЕХАНИЕ 1 7 4 С 9 6 0 |
| 4 | В 8 2 1 Г 4 Ж 6 7 0 А 5 3 Е 9 Б |
| 5 | 7 Ж 5 А 8 1 6 Д 0 9 3 ЕВ 4 2 С |
| 6 | 5 DF 6 9 2 КАБИНА 7 8 1 4 3 E 0 |
| 7 | 8 Е 2 5 6 9 1 CF 4 B 0 DA 3 7 |
| 8 | 1 7 ЭД 0 5 8 3 4 FA 6 9 CB 2 |
Криптоанализ ГОСТ
[ редактировать ]Последний криптоанализ ГОСТ показывает, что он безопасен в теоретическом смысле. На практике сложность данных и памяти лучших опубликованных атак достигла практического уровня, в то время как временная сложность даже самой лучшей атаки по-прежнему равна 2. 192 когда 2 64 данные доступны.
С 2007 года было разработано несколько атак на реализации ГОСТ с сокращенным циклом и/или слабые ключи . [ 6 ] [ 7 ]
В 2011 году несколько авторов обнаружили более существенные недостатки в ГОСТ, впервые получив возможность атаковать полный 32-раундовый ГОСТ с помощью произвольных ключей. даже назвал его «глубоко ошибочным шифром» Николя Куртуа . [ 8 ] Первоначальные атаки смогли снизить временную сложность с 2 256 до 2 228 ценой огромных требований к памяти, [ 9 ] и вскоре они были улучшены до 2 178 временная сложность (стоимостью 2 70 память и 2 64 данные). [ 10 ] [ 11 ]
В декабре 2012 года Куртуа, Гавинецкий и Сонг усовершенствовали атаки на ГОСТ, вычислив всего 2 101 ГОСТ патроны. [ 12 ] Исобе уже опубликовал атаку с использованием одного ключа на полный шифр ГОСТ. [ 13 ] который Динур, Дункельман и Шамир улучшили, достигнув 2 224 временная сложность на 2 32 данные и 2 36 память и 2 192 временная сложность на 2 64 данные. [ 14 ]
Поскольку атаки уменьшают ожидаемую силу с 2 256 (длина ключа) примерно до 2 178 , шифр можно считать взломанным. Однако на практике такая атака неосуществима, так как количество тестов, которые необходимо выполнить, равно 2. 178 находится вне досягаемости.
Обратите внимание, что для любого блочного шифра с размером блока n бит максимальный объем открытого текста, который может быть зашифрован перед повторной сменой ключа, равен 2. н/2 блоки, из-за парадокса дня рождения , [ 15 ] и ни одна из вышеупомянутых атак не требует менее 2 32 данные.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^
Куртуа, Николя Т. (9 мая 2011 г.). «Оценка безопасности ГОСТ 28147-89 с учетом международной стандартизации» . Архив электронной печати по криптологии . МАКР .
До 2011 года исследователи единогласно соглашались, что ГОСТ может или должен быть очень безопасным, что было резюмировано в 2010 году такими словами: несмотря на значительные криптоаналитические усилия, затраченные за последние 20 лет, ГОСТ все еще не взломан». быть сломанным и представляет собой глубоко ошибочный шифр
- ^ Jump up to: а б «ГОСТ Р 34.12-2015 (только на русском языке)» (PDF) . Архивировано из оригинала (PDF) 24 сентября 2015 г. Проверено 28 августа 2015 г.
- ^ Флейшманн, Юэн; Горский, Майкл; Хюне, Ян-Хендрик; Удача, Стефан (2009). «Атака с восстановлением ключа на полный блочный шифр ГОСТ с нулевым временем и памятью». Опубликовано как ISO/IEC JTC . 1 .
- ^ Сааринен, Маркку-Юхани (1998). «Атака по выбранному ключу на секретные S-блоки ГОСТа» .
Мы показываем, что простая атака на ГОСТ с использованием выбранного ключа «черного ящика» может восстановить секретные S-блоки с примерно 2 ^ 32 шифрами.
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Шнайер, Брюс (1996). Прикладная криптография: протоколы, алгоритмы и исходный код на C (2-е изд., [Начдр.] изд.). Нью-Йорк [ua]: Уайли. ISBN 978-0-471-11709-4 .
- ^ Эли Бихам; Орр Данкельман; Натан Келлер (2007). «Улучшенные атаки скольжением» (PDF) .
- ^ Орхун Кара (2008). «Отражательный криптоанализ некоторых шифров» .
- ^
Куртуа, Николя Т. (9 мая 2011 г.). «Оценка безопасности ГОСТ 28147-89 с учетом международной стандартизации» . Архив электронной печати по криптологии . МАКР .
До 2011 года исследователи единогласно соглашались, что ГОСТ может или должен быть очень безопасным, что было резюмировано в 2010 году такими словами: несмотря на значительные криптоаналитические усилия, затраченные за последние 20 лет, ГОСТ все еще не взломан». быть сломанным и представляет собой глубоко ошибочный шифр
- ^ Николя Т. Куртуа; Михал Миштал (2011). «Дифференциальный криптоанализ ГОСТ» . МАКР .
- ^ Николя Т. Куртуа (2012). «Улучшенная дифференциальная атака на полный ГОСТ» (PDF) . МАКР .
- ^ Куртуа, Николя Т. (13 июня 2011 г.). «Алгебраическое снижение сложности и криптоанализ ГОСТ» (PDF) . Архив электронной печати по криптологии . МАКР .
- ^ Николя Т. Куртуа; Ежи А. Гавинецкий; Гуанъянь Сун (2012). «ИММУНИТЕТ ПРОТИВОРЕЧИЯ И НАПАДЕНИЯ НА ГОСТ, ПРЕДУГАДАЙТЕ, ЗАТЕМ ОПРЕДЕЛИТЕ» (PDF) . Версита . Проверено 25 августа 2014 г.
- ^ Исобе, Таканори (2011). «Одноключевая атака на полный блочный шифр ГОСТ». Быстрое программное шифрование . Конспекты лекций по информатике. Том. 6733. стр. 290–305. дои : 10.1007/978-3-642-21702-9_17 . ISBN 978-3-642-21701-2 .
- ^ Динур, Итай; Данкельман, Орр; Шамир, Ади (2012). «Улучшенная атака на полный ГОСТ». Быстрое программное шифрование . Конспекты лекций по информатике. Том. 7549. стр. 9–28. дои : 10.1007/978-3-642-34047-5_2 . ISBN 978-3-642-34046-8 .
- ^ «Проект постоянного документа ISO/IEC JTC 1/SC 27 № 12 (SD12) по оценке криптографических методов и длины ключей, 4-е издание» (PDF) . 2016.
Дальнейшее чтение
[ редактировать ]- «Библиотека ГОСТ WebCrypto» . Рудольф Николаев, команда WebCrypto ГОСТ.
- Долматов, Василий (март 2010 г.). «RFC 5830: ГОСТ 28147-89 алгоритмы шифрования, дешифрования и MAC» . IETF.
- Попов Владимир; Леонтьев Сергей; Курепкин, Игорь (январь 2006 г.). «RFC 4357: Дополнительные криптографические алгоритмы для использования с ГОСТ» . IETF.
- Алекс Бирюков и Дэвид Вагнер (май 2000 г.). Продвинутые скользящие атаки (PDF) . Достижения в криптологии, Труды EUROCRYPT 2000. Брюгге : Springer-Verlag. стр. 589–606. дои : 10.1007/3-540-45539-6_41 . Проверено 3 сентября 2007 г.
Внешние ссылки
[ редактировать ]- Описание, тексты стандартных, онлайн-инструментов шифрования и дешифрования ГОСТ.
- Запись СКАН по ГОСТу
- Реализация программного устройства PKCS#11 с открытым исходным кодом и возможностями шифрования по российским стандартам ГОСТ.
- https://github.com/gost-engine/engine — реализация российской криптографии ГОСТ с открытым исходным кодом для OpenSSL.
