Мифы и реальность современных криптографических алгоритмов

© Панасенко Сергей, 2005

Как и любая другая область знаний, криптология имеет немало мифов. Рассмотрим те два из них, которые вызывают частые дискуссии в данной области, считая, что дойдет очередь и до других.

Выбор криптографических стандартов

Рассмотрим два основных пути, по которым идут уполномоченные на то организации при выборе различных криптографических стандартов:

1. Открытый конкурс по выбору из нескольких представленных алгоритмов того, который наиболее полно отвечает критериям выбора. Один из недавних примеров – конкурс по выбору стандарта шифрования США AES (Advanced Encryption Standard, см. статью «Стандарт шифрования США», «Мир и безопасность» № 6/2003).
2. Разработка криптоалгоритма «в недрах спецслужб». Очевидный пример: отечественный стандарт шифрования ГОСТ 28147-89 (см. статью «Отечественный стандарт шифрования», «Мир и безопасность» № 5/2003).

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

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

Также считается, что никакая спецслужба мира не имеет достаточных ресурсов для всестороннего анализа разрабатываемого алгоритма. Однако, после изучения аналитических исследований специалистов, хранящихся на домашней страничке конкурса [1], предлагаю к рассмотрению следующие аргументы в пользу спецслужб:

• фактически, не менее половины исследований и сообщений выполнено организациями и специалистами, принимавшими участие в разработке присланных на конкурс алгоритмов, т.е. субъектами, заинтересованными в результатах конкурса; в материалах можно наблюдать, практически, устранение алгоритмов-конкурентов, например, [10];
• достаточно много аналитических материалов носило информационно-разъяснительный характер и не имело прямого отношения к цели конкурса; в качестве примера можно привести [3];
• внимание экспертов было «распылено» между 15-ю алгоритмами-участниками конкурса – немало аналитических материалов посвящено анализу алгоритмов, заведомо не подходящих в качестве нового криптостандарта США (например, FROG или Magenta [2]); еще хуже в этом смысле была ситуация на европейском конкурсе NESSIE [7], где выбор алгоритмов производился в нескольких номинациях из четырех десятков претендентов; концентрация же аналитических мощностей спецслужб на одном разрабатываемом криптостандарте, на мой взгляд, является более предпочтительной.

Теперь несколько слов про отечественный стандарт шифрования. Исходя из рассуждений известнейшего криптолога Брюса Шнайера (Bruce Schneier) в [19], невосприимчивость алгоритма ГОСТ 28147-89 к дифференциальному и линейному криптоанализу плюс большое количество раундов означают, что ГОСТ 28147-89 существенно надежнее алгоритма DES. В свою очередь, известно, что за десятки лет использования алгоритма DES, не было найдено способов его вскрытия, заметно более эффективных, чем лобовое вскрытие (наиболее эффективной атакой считается линейный криптоанализ DES на основе 2⁴³ пар «открытый текст – шифртекст» с вероятностью 85%) [5]. Лобовое же вскрытие ГОСТа абсолютно невозможно из-за 256-битного ключа, а также возможности использования секретных значений узла замены.
Если же сравнивать производительность алгоритмов ГОСТ 28147-89 и AES, то на 32-битных платформах ГОСТ медленнее нового криптостандарта США всего на 10-20% [18]. Невпечатляющее преимущество алгоритма AES.
Стоит сказать, что во времена разработки ГОСТ 28147-89 сложно было бы представить себе открытый конкурс на выбор стандарта шифрования СССР. А теперь сравним время, когда данные алгоритмы были разработаны и представлены в виде криптостандартов. И из сравнения следует, что отечественный криптостандарт был принят, фактически, на 10 лет раньше начала конкурса AES. А что такое 10 лет в наше время бурного развития информационных технологий? Это огромный промежуток времени: 10 лет назад в ходу были компьютеры с процессором Pentium Pro, сейчас являющиеся анахронизмом. И пока весь мир шифровал DES’ом с 56-битным ключом или медленным Triple DES’ом, в России использовали сильный и не самый медленный алгоритм – завтрашний день, по сравнению с упомянутыми алгоритмами.
Вывод: отечественные спецслужбы в конце 1980-х годов создали алгоритм шифрования, фактически не уступающий новейшему стандарту США. Можно ли считать, что миф развенчан?
Увы, нет. Алгоритм ГОСТ 28147-89 имеет, как минимум, два следующих недостатка:

• Основные операции алгоритма выполняются над 32-битными «полублоками», что предопределяет высокую скорость работы алгоритма на 32-битных платформах. По сравнению с байт-ориентированным алгоритмом AES на 8-битных платформах ГОСТ проигрывает в скорости в 4 раза [18].
• В тексте стандарта ГОСТ 28147-89 отсутствуют четкие критерии выбора узлов замены. Достаточно часто высказываются опасения, что существуют слабые узлы замены (например, в [15]), хотя тот же Брюс Шнайер называет такие предположения «слухами» [19].

Нельзя сказать и о том, что ведущие экперты в один голос одобрили результаты конкурса AES. Приведу лишь высказывание известного эксперта Ричарда Шреппеля (Richard Schroeppel), автора одного из алгоритмов-претендентов (алгоритм HPC, без криптографических уязвимостей и весьма высокоскоростной на 64-битных платформах, однако, не прошедший во второй этап конкурса из-за высоких требований к памяти) о том, что нельзя выбирать один и тот же алгоритм для новейших многопроцессорных серверов и дешевых смарт-карт: лучше пожертвовать совместимостью и выбрать два криптостандарта, оптимизированных под разные задачи. Аналогичная рекомендация была дана Брайаном Глэдманом (Brian Gladman) в [4]. В связи с этим, кстати, вспомним конкурс NESSIE, где в качестве победителей выбрано было три (!) алгоритма симметричного шифрования, обрабатывающих блоки различного размера [8].
Несомненно, конкурс AES вызвал волну криптоаналитических исследований по всему миру и дал хороший толчок развитию данного направления во всем мире. Но и характеристики алгоритма ГОСТ 28147-89 однозначно доказывают правомочность закрытой разработки криптостандартов. Посмотрим, какие принципы и мнения будут доминировать при принятии следующих стандартов шифрования.

Сертификация

Миф № 2: Сертификация средств криптографической защиты информации является лишь бюрократической процедурой. Хотелось бы сказать несколько слов в защиту сертификации.
Технически достаточно легко на этапе разработки обеспечить наличие в программе шифрования возможности расшифрования информации специальным ключом. Теоретически, такую недокументированную возможность можно обеспечить следующим образом.

Типичная ключевая схема шифрования файлов

Рассмотрим ключевую схему, типичную для программ шифрования файлов (см. рис. 1) [14]. В качестве ключа, на котором выполняется собственно шифрование информации (файловый ключ), используется случайное значение, полученное с программного или аппаратного датчика случайных чисел (ДСЧ). Реализации ДСЧ обычно внедряются в программы шифрования или обеспечивается возможность их подключения, например, в случае с аппаратным ДСЧ.
Для обеспечения возможности последующего расшифрования файловый ключ должен быть сохранен вместе с зашифрованной информацией. Для этого используется долговременный ключ шифрования, который хранится у пользователя. Именно этот ключ предъявляется пользователем программе шифрования. Файловый ключ шифруется на долговременном ключе и в зашифрованном виде (например, в режиме простой замены алгоритма ГОСТ 28147-89) записывается в предусмотренное для него место в структуре данных, называемой заголовком зашифрованного файла. Заголовок содержит информацию, необходимую для расшифрования файла, для зашифрованного файла типичен следующий формат заголовка:

• Файловый ключ, зашифрованный на долговременном ключе пользователя.
• Идентификатор долговременного ключа, необходимый для указания программе, на каком из доступных долговременных ключей следует расшифровывать данный файловый ключ.
• Какая-либо контрольная сумма файлового ключа на долговременном ключе. Необходима для контроля целостности файлового ключа и рассчитывается после расшифрования файлового ключа. Это может быть имитоприставка, рассчитанная по алгоритму ГОСТ 28147-89 в режиме выработки имитоприставки [11].
• Параметры алгоритма шифрования, например, синхропосылка данных при использовании алгоритма ГОСТ 28147-89.
• Контрольная сумма (имитоприставка) данных, рассчитанная на файловом ключе – для контроля целостности зашифрованной информации.

При необходимости расшифровать файл программа анализирует заголовок и выполняет следующие шаги:

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

Использование случайного файлового ключа, которое незначительно усложняет процедуру шифрования, решает две проблемы:

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

Варианты внедрения программной закладки

Теперь предположим, что у злоумышленника есть желание внедрить в программу шифрования "черный ход". Для разработчиков программы нет ничего проще – достаточно лишь в каждый заголовок, помимо перечисленной выше информации, записывать еще и файловый ключ, зашифрованный на некотором "универсальном ключе" (всего-то 32 байта лишней информации). Это уравнивает в возможностях расшифрования информации легальных пользователей и владельцев данного спецключа (см. рис. 2).
В качестве примера приведу файловую систему EFS (Encrypting File System), появившуюся в Microsoft Windows 2000, осуществляющую прозрачное шифрование файлов. Шифрование выполняется на случайном файловом ключе (FEK – File encryption key), который зашифровывается асимметричным алгоритмом на открытом ключе пользователя и хранится вместе с зашифрованным файлом. Однако, помимо этого, FEK зашифровывается и на одном или нескольких открытых ключах агентов восстановления данных и также записывается в файловый дескриптор. Соответственно, агент восстановления данных может в любой момент расшифровать файл с помощью своего секретного ключа. Это весьма полезно при увольнении пользователя или утери им носителя с долговременным секретным ключом, но, по сути, данная схема представляет собой реальный пример использования "черного хода" – зашифрованная пользователем информация в любой момент может быть получена, например, администрацией организации, в которой он работает [12].
Еще одна возможность недобросовестных разработчиков – усечение ключевого множества [13]. Происходит путем внедрения в программу специального ДСЧ, который генерирует не случайные файловые ключи, а ключи из какого-либо ограниченного подмножества ключей. Подмножество может быть достаточно большим по общечеловеческим меркам и содержать, например, миллиард ключей, которые легко переберутся злоумышленником по сравнению с возможными, 2²⁵⁶ (т.е. порядка 10⁷⁷), ключей алгоритма ГОСТ 28147-89. В этом случае долговременный ключ также не интересен злоумышленнику – перебор будет осуществляться непосредственным расшифрованием файла на ключах из ограниченного подмножества.

Противоядие

Самый действенный способ защиты от возможных незадекларированных возможностей программ, в частности, от описанных выше, – это сертификация средств шифрования в ФСБ.
Рассмотрим, какие цели преследует сертификация программных средств шифрования:

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

В процессе проведения сертификационных испытаний эксперты сертифицирующей организации выполняют детальный анализ исходных текстов программных средств, уделяя особенное внимание модулям, осуществляющим криптографические преобразования и обработку ключевой информации.
Таким образом, сертификация средств криптографической защиты информации (СКЗИ), фактически, является единственным возможным способом гарантии качества реализации криптостандартов и отсутствия в средствах защиты намеренно внесенных закладок.
Стоит сказать и о том, что отсутствие сертификата ФСБ на СКЗИ не позволяет его использовать в Государственных органах и организациях РФ, организациях, выполняющих оборонные заказы РФ, и организациях или частных лицах, обменивающихся конфиденциальной информацией с Государственными органами и организациями РФ, а также с организациями, выполняющими оборонные заказы РФ [17]. А Положение ФАПСИ о системе сертификации СКЗИ [16] устанавливает следующее требование к используемым в сертифицируемых СКЗИ криптоалгоритмам: «Заявки на проведение сертификации шифровальных средств принимаются при условии, что в указанных средствах реализованы криптографические алгоритмы, объявленные государственными или отраслевыми стандартами Российской Федерации, иными нормативными документами, утвержденными Советом Министров - Правительством Российской Федерации или ФАПСИ». Т.е. сертифицированное средство шифрования данных должно реализовывать именно отечественный криптостандарт ГОСТ 28147-89.

Литература

1. AES Home Page. www.nist.gov/aes.
2. Biham E. Comment on Selecting the Ciphers for the AES Second Round. // www.nist.gov/aes.
3. Carter G., Dawson E., Nielsen L. Key Schedule Classification of the AES Candidates. // www.nist.gov/aes.
4. Gladman B. The Need for Multiple AES Winners. // www.nist.gov/aes.
5. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996. // www.cacr.math.uwaterloo.ca/hac.
6. Nechvatal J., Barker E., Dodson D., Dworkin M., Foti J., Roback E. Status report on the first round of the development of the advanced encryption standard. // www.nist.gov/aes. - National Institute of Standards and Technology.
7. NESSIE Home Page. www.cryptonessie.org.
8. Portfolio of recommended cryptographic primitives. // www.cryptonessie.org. – NESSIE consortium, February 27, 2003.
9. Schroeppel R. The Hasty Pudding Cipher: One Year Later. // www.cs.arizona.edu - June 12, 1999.
10. Wagner D., Ferguson N., Schneier B. Cryptanalysis of FROG. // www.nist.gov/aes.
11. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования.
12. Зубанов Ф.В. Microsoft Windows 2000. Планирование, развертывание, установка. 2-е издание – М.: "Русская редакция", 2000.
13. Пазизин С. Об угрозах криптографическим ключам. // Банки и технологии. – 2003 - № 1 – с. 73-76.
14. Панасенко С.П. "Черный ход" в программные средства шифрования. // Системы безопасности. – 2002 - № 6 – с. 90-92.
15. Петров А.А. Компьютерная безопасность: криптографические методы защиты. – М.: ДМК, 2000 – 448 с.
16. Положение ФАПСИ. Система сертификации средств криптографической защиты информации. Октябрь 1993. // www.ancud.ru.
17. Приказ ФАПСИ №158. Об утверждении положения о порядке разработки, производства, реализации и использования средств криптографической защиты информации с ограниченным доступом, не содержащей сведений, составляющих государственную тайну. // Российская газета. – 2000 - № 18.
18. Применко Э.А., Винокуров А.А. Сравнение стандарта шифрования алгоритма ГОСТ 28147-89 и алгоритма Rijndael. // Системы безопасности, связи и телекоммуникаций. – 2001 - № 39 - с. 71-72.
19. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – Пер. с англ.: М.: Издательство ТРИУМФ, 2002 – 816 с.

Рисунки:

1. Типичная ключевая схема шифрования файла.
2. Вариант внедрения программной закладки.