Перспективы стандартов на совершенные шифраторы

Юрий Брауде-Золотарев
Независимый эксперт

Алгоритмы абсолютно криптостойких совершенных шифраторов

СШ эквивалентны рекомендованному Шенноном шифр-блокноту с однократным использованием страниц, взлом которого принципиально невозможен и для которого сертификаты не нужны. Преимущества СШ изложены, например, в [1]. Для их реализации нужны генераторы случайных чисел (ГСЧ), создающие действительно случайные числа – true random number sequence (TRNS). Для этого криптография рекомендует ГСЧ на двоичных регистрах сдвига с нестационарными случайными и нелинейными обратными связями (РСННЛ – NLFSR и Random FSR), в которых случайным образом изменяют генераторные полиномы (ГП) и содержимое (ключ), и отмечает трудности поиска таких ГП. Первый СШ с такими ГП реализован по заказу Минобороны СССР на микросхеме БИС Н1515ХМ1-888 с ключом 256 бит. Алгоритм СШ опубликован в [2]. Его реализовал "кроссинговер" с простыми одноразрядными трассировками и переключателями. Алгоритм БИС описан и в более доступной [3], где СШ назван абсолютно криптостойким шифратором (АКШ).

Криптографы НИИ Минобороны, КГБ СССР, а потом и ФАПСИ отметили преимущества СШ-АКШ в сравнении с ГОСТ 28147-89 и сложность программной реализации кроссинговера, которая препятствовала им заменить ГОСТ этим АКШ. Разработку независимого от ГОСТ второго стандарта на базе этой БИС они не рассматривали. Найти ГП, нужные для нового ГОСТ, они надеялись за 3 года. Реорганизация КГБ остановила эти работы. Их продолжил ФГУП СНПО "Элерон". Исследования показали преимущества байтовых ГСЧ на двоичных РС с простейшей нелинейностью на двухвходовых "И" и "ИЛИ" и нестационарными случайными функциями обратной связи с двумя состояниями – парами генераторных полиномов (ПГП). Сначала были найдены ПГП для СШ-АКШ с короткими ключами 39 и 16 бит [4, 5]. Основной трудностью был поиск вручную "хороших" ПГП с двумя циклами и длиной не ниже 50 бит.

ГСЧ-39 [4] содержит четыре байтовых и один 7-разрядный автомат на РС с РСННЛ. Он создает абсолютно криптостойкие TRNS. Объем шифр-блокнота – 2³⁹ байт. Коротких циклов и слабых ключей нет. Ключ 39 бит вводят в РСННЛ (автоматы). Исследованы два варианта. В ГСЧ-39-1 использованы РСННЛ, имеющие два состояния – пары ГП с нелинейным управлением от того же автомата. Его сложность около 800 УВ. В ГСЧ-39-2 цикл CШ увеличен до 2⁵¹ байт. Для этого введены 16 разрядный вектор управления (ВУ), выбирающий пары ГП и другие цепи ГСЧ, и 18-разрядный вектор обновления (ВО) ключа. Но его сложность возросла до 12 тыс. УВ. Поэтому предпочтительнее ГСЧ-39-1.

ГСЧ-16 [5] содержит два байтовых автомата с РСННЛ, формирующие TRNS. Ключ 16 бит вводят в РСННЛ. Исследованы два варианта с разным количеством пар нестационарных ГП n в каждом автомате. Количество переключателей, выбирающих пары, равно (n-1). В ГСЧ-16-1 n = 4, объем шифр-блокнота 2⁴¹ байт, количество УВ в цепях выбора 200 УВ. Сложность около 600 УВ. В ГСЧ-16-2 n = 128, объем шифр-блокнота 2⁵¹ байт, количество УВ в цепях выбора – 8 тыс. и сложность около 9 тыс. УВ.

Позже полным перебором группой ПЭВМ были найдены 164 пары хороших ПГП для байтовых и восемь – для семиразрядных автоматов. Программы поиска и таблицы ПГП опубликованы в [6]. На замену кроссинговера ушли 10 лет. На этих ПГП возможно создание аппаратно и программно простых ГСЧ для СШ с длинами ключей до 256 бит. Для содействия разработке новых стандартов таблица ПГП и структура АКШ с кроссинговером опубликованы и в [3].

В ГСЧ-39 и ГСЧ-16 секретными должны быть не только биты ключа, вводимого в регистры, но и разряды ВО и ВУ. По уточненным оценкам, общая длина "расширенного" ключа у ГСЧ-16-1 – 41 бит и у ГСЧ-16-2 – 51 бит. Но эти уточнения не влияют на их применение, так как шифраторы с ключами, меньшими чем 56 бит, лицензирования не требуют. Проблема уточнений оценок длин ключей – вне задач этой статьи, и поэтому далее будем следовать ошибочным традициям. Например, ключ 256 бит в ГОСТ-28147-89 расширяют на 512 бит в восьми секретных S-блоках по 64 бита каждый, но это увеличение в 3 раза при оценке длины ключа не учитывают.

С парами ГП из таблицы [6] были созданы и исследованы модели аппаратно и программно простых ГСЧ для СШ-АКШ с длинами ключей до 256 бит. Интересен ГСЧ-24 с тремя байтовыми РС, каждый с n = 4, объемом шифр-блокнота около 249 байт и сложностью около 1,2 тыс. УВ, значительно меньшей, чем у ГСЧ-16-2. Испытания АКШ с ключами 16, 24, 39, 64, 128, 256 бит показали, что замена в радиостанции ГП автоматов и обновление разрядов переносят состояние ГСЧ скачком в новую точку полного цикла, что соответствует вводу нового ключа. Интервал обновления ключа у этих АКШ – 1 байт, много меньший "интервала единственности". Величины скачков в полных циклах ГСЧ распределены хаотически. У последовательностей АКШ состояния байтовых РС эргодичны. Математики считают процесс эргодичным, если сдвиг последовательности в пространстве исходов эквивалентен ее сдвигу по времени. Испытания показали, что эти ГСЧ создают действительно случайные последовательности (TRNS) и что они являются АКШ [7].

В [7] дано сравнение АКШ с другими шифраторами, включая стандарты AES (США) и ARIA (Южная Корея), которые, как и БИС ГОСТ-28147-89, работают со сложными многоразрядными вычислениями и трассами, и потребляют в 100–300 раз больше энергии и соответственно менее надежны, чем АКШ. При равных длинах ключей АКШ в 50–100 раз проще шифраторов с многоразрядными трассами, их скорости во много раз выше, чем у других. АКШ на практике подтвердили рекомендации теории о преимуществах СШ на двоичных РС с нестационарными и нелинейными ГП. Отказ от кроссинговера усложнил аппаратную реализацию этих АКШ [2]. Но он проще микросхемы ГОСТ в 40 раз и быстрее ее более чем в 100. Все АКШ с парами ГП из таблицы [6] значительно проще других шифраторов.

Сертификаты и стандарты устаревших или взломанных шифраторов

В статье [7] обоснованы преимущества АКШ в сравнении с наиболее распространенными сертифицированными шифраторами. Их основные параметры приведены ниже:

• COS. Ключи 128, 192 и 256 бит. Сложность для 256 бит – 25 тыс. УВ.
• CHAMELEON. Ключ 256 бит, сложность около 4 млн УВ.
• PANAMA. Ключ 256 бит, сложность около 60 тыс. УВ.
• LEVIATHAN. Ключ 256 бит, сложность – более 60 тыс. УВ.
• SEAL. Ключ 256 бит, сложность более 400 тыс. УВ.
• SNOW. Ключ 256 или 128 бит. Сложность для 256 бит около 20 тыс. УВ.
• SOBER. Ключ 128 бит. Сложность около 18 тыс. УВ.
• SQ1-R. Ключ 256 бит, сложность более 30 тыс. УВ.
• TWOPRIME. Ключ 128 бит, сложность более 25 тыс. УВ.

Наиболее простые из них работают на двоичных РС (COS – на стационарных нелинейных ГП, SOBER и SNOW – на слабых линейных ГП). Другие шифраторы многократно сложнее АКШ. Даже у самых быстрых (CHAMELEON и PANAMA для платного телевидения) скорости на порядок ниже, чем скорости АКШ. В этом перечне нет упомянутых стандартов ГОСТ (100 тыс. УВ), AES (300 тыс. УВ), ARIA и японского стандарта Camellia, работающих с сетями Фейстеля и с другими многоразрядными массивами, нет модных когда-то RSA, эллиптических криптоалгоритмов и других устаревших сложных шифраторов. Центр по лицензированию, сертификации и защите государственной тайны ФСБ России (Центр ЛСЗ) в свой "Список сертифицированных криптосредств" АКШ не включил и не опубликовал алгоритмы включенных. В литературе по криптографии отмечено, что ссылки на криптостойкость неопубликованных алгоритмов надо считать обманом, "создающим иллюзию защищенности". Но многие скрывают алгоритмы рекламируемых шифраторов и до сих пор актуально замечание академика АН СССР А.И. Берга о подобном засекречивании – "для иных структур главным охраняемым секретом является их некомпетентность".

Преимущества СШ известны давно, но многие разработчики в России и за рубежом изготавливают и рекламируют сертифицированные и ненадежные шифраторы. Были вскрыты даже шифраторы государственных структур США. Взломаны шифраторы PIKE, A5/2 (стандарт GSM) и ORIX (стандарт радиосвязи США). Шифраторы WEP, а затем WPA, рекомендованные для защиты Wi-Fi, были взломаны и их заменили на AES. Шифраторы GMR-1 и GMR-2 спутниковой мобильной радиосвязи сетей Inmarsat и GSM с сертификатами Европейского института стандартов связи (ETSI) и ФСБ, выданными в 2010 г., криптоаналитики E. Jaulmes и F. Muller взломали в январе 2012 г. Шифраторы F-FCSR, сертифицированные в 2005 г., взломаны и были заменены на F-FCSR-H (аппаратный) и F-FCSR-8 (программный). Но в сентябре 2008 г. и их исключили из перечня рекомендуемых. Шифраторы WLAN (Wireless Local Area Network) фирмы Cisco, которые использовали более 20 млн жителей Западной Европы, взломали в 2009 г. Рекуррентный шифратор РС-4 с ключом 128 бит рекламировали и использовали широко. Теперь его взламывают за 3 с и в Netscape и в стандартах IEEE его заменили шифратором AES. Для взлома шифраторов Toyocrypt и Lili-128 нужно 2¹³ операций ноутбука (около 1 с).

Рекомендации по разработке стандарта шифрования на базе СШ

Новый стандарт шифрования нужен для большого ($63,6 млрд в 2010 г.) и быстро растущего IT-рынка с высокоскоростной передачей ценной научной, технологической и коммерческой информации, например для операторов мобильной и сотовой связи. В них жертвами мошенников становятся около 20% пользователей, и общий годовой ущерб от них в телекоммуникационной отрасли достигает около $50 млрд [8].

Разработчикам нового ГОСТа поэтому необходимо учесть:

1. Преимущества АКШ – совершенных шифраторов [2, 3, 7], создающих случайные последовательности (TRNS), недоступные для любых атак.
2. Преимущества генераторов случайных чисел TRNS на двоичных регистрах сдвига (РС) с нелинейными и нестационарными (изменяемыми случайно) функциями обратной связи – парами ГП [2, 7].
3. Непригодность псевдослучайных последовательностей (ПСП) с линейными ГП (LFSR), для взлома которых достаточно принять 2n реализаций сигнала, управляемого ПСП, где n – максимальная степень ГП.

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

• использование в пакетной радиосвязи ТСО и ВРС потоковых АКШ в режиме блоковых, взлом которых также принципиально невозможен;
• АКШ на двоичных РС с длиной ключей до 6 байт с нелинейными нестационарными случайными парами ГП – функциями обратной связи;
• обновление ключа сложением обновляющего бита по модулю 2 с выбираемым разрядом РС, эквивалентное полной смене ключа;
• интервалы обновления, много меньшие интервала единственности;
• малоразрядные векторы управления и обновления АКШ с выбором не более восьми адресов обновления ключа и восьми пар нестационарных ГП;
• неравномерное движение РС автоматов в сочетании с этими средствами.

Разработку нового ГОСТа нецелесообразно усложнять задачей замены им ГОСТ 28147-89, который лучше сохранить для пользователей. Нужен новый, независимый от старого. Сотрудники НИИ КГБ СССР считали себя ответственными за разработку нового ГОСТа. Но ФСБ, правопреемник КГБ, за эти годы не смог вложить в новый ГОСТ шифрования давно готовую микросхему АКШ [2] и другие АКШ [7], так как не сохранил специалистов, понимающих преимущества совершенных шифраторов. Описание АКШ [2] в новом ГОСТе им надо было только дополнить внешними взаимодействиями и показать, что шифрованию подлежит только содержательная часть передаваемого сообщения, что затем к ней добавляют служебную информацию для маршрутизации сообщения при его отправке адресату и что такое сообщение не надо расшифровывать и зашифровывать при прохождении через промежуточные узлы сети связи и оно остается зашифрованным на всем пути к получателю.

Первым шагом создания ГОСТа могут быть рекомендации по алгоритмам АКШ для криптозащиты охранных и войсковых радиостанций согласно положению ПКЗ-20051. В ст. 14 и 15 этого ПКЗ указан порядок необходимых НИР и ОКР для разработки шифраторов. Для АКШ НИР и ОКР давно завершены [2, 3, 7]. Новой ОКР может быть модернизация АКШ [2] по новым технологиям микросхем. Эта ОКР облегчила бы второй шаг – разработку рекомендаций по применению ГОСТа на базе АКШ [2] и третий шаг – разработку дополнений к новому ГОСТу на базе АКШ [7]. Заинтересованные пользователи могли бы разработать микросхемы для нового ГОСТа c АКШ [7].

Структуры ФСБ игнорируют преимущества опубликованных аппаратно и программно простых АКШ. За рубежом стандартов с АКШ-СШ пока еще нет.

О реализации шифраторов новых стандартов на микросхемах

Постановление Правительства РФ № 809 от 26.11.2007 "Развитие электронной компонентной базы и радиоэлектроники на 2008–2015 гг.", требует разработок на отечественных микросхемах аппаратуры, конкурентной на мировом уровне. В нем предусмотрено освоение технологий 0,18 и 0,13 мкм в 2012 г. (что уже достигнуто) и 45 нм в 2015 г. Значительно раньше о преимуществах микросхем знали ведущие НИИ Минобороны и КГБ СССР. Поэтому были разработаны упомянутая выше микросхема АКШ [2], а до нее – микросхема помехоустойчивого кодирования для космического челнока "Буран" с ГП, имеющим малую плотность проверок на четность (МППЧ), алгоритм которой (low density parity check codes – LDPC), полезный и для шифрованных связей, позже был признан наилучшим и за рубежом [10].

Совершенные шифраторы на микросхемах (СШМ) имеют и многие другие преимущества:

• обладают большей скоростью и надежностью;
• просты в установке. Телефоны, факсимильные аппараты и модемы радиосетей значительно дешевле снабдить ШМ, чем встраивать в них микрокомпьютеры с ПО.

СШМ легче физически защитить от проникновения извне, а в программу злоумышленник может скрытно внести изменения, незаметно понижающие стойкость криптографического алгоритма. Экран СШМ подавляет электромагнитное излучение, что очень сложно выполнить для компьютера.

Выводы

Ни в России ни за рубежом нет стандартов шифрования на базе СШ, которые обеспечивают АКШ. Главным регулятором в области криптографии – ФСБ – новый ГОСТ шифрования на базе АКШ до сих пор не создан. Хотя опубликованные шифраторы СШ-АКШ по простоте и эффективности лучше шифраторов, выбираемых ею по российским и зарубежным сертификатам.

Литература

1. Зубов А.Ю. Криптографические методы защиты информации. Совершенные шифры. – М.: Гелиос АРВ, 2005. – 192 с.
2. Брауде-Золотарев Ю.М. Генератор случайных чисел с высокой степенью рандомизации / Труды НИИ радио. – 1997.
3. Брауде-Золотарев Ю.М. Криптостойкая защита информации в радиосвязи // Защита информации INSIDE. – 2013. – № 3.
4. Брауде-Золотарев Ю.М. Потоковый шифратор с ключом 39 бит // Электросвязь. – 2004. – № 12.
5. Брауде-Золотарев Ю.М. Возможно ли криптостойкое шифрование с ключом 16 бит? // Электросвязь. – 2009. – № 4.
6. Брауде-Золотарев Ю.М. Программы, генерирующие случайные числа / Cб. науч. тр. ФГУП СНПО "Элерон", 2008.
7. Брауде-Золотарев Ю.М. Абсолютно криптостойкие и самые простые шифраторы // Электросвязь. – 2010. – № 3.
8. Голышко А. Преступные сети для телекоммуникационных операторов // Connect. – 2010. – № 1–2.
9. Брауде-Золотарев Ю.М. Теория и практика защиты радиостанций от средств радиоборьбы // Мир и безопасность. – 2013. – № 3.
10. Брауде-Золотарев Ю.М. О наилучших алгоритмах помехоустойчивого кодирования // Беспроводные технологии. – 2013 – № 1.