Евтушенко Владимир. Тройной DES. Новый стандарт?

Секретные письма Макиавелли, пляшущие человечки Шерлока Холмса, книжный шифр Штирлица, защита сотовых телефонов GSM, шифрование клиентских пин-кодов в банкоматах и многое другое,- реальное и вымышленное, - объединяет одно общее - применение криптографии. Наука о "тайном письме" в нашей стране долгое время была закрыта и служила исключительно интересам государства. Однако, со временем узкий круг посвященных стал расширяться: появились новые действующие лица со своими собственными секретами, не менее важными, чем государственные. Появились новые понятия - коммерческая информация и коммерческая тайна. Появился спрос, появилось и предложение - можно говорить, что в России в исключительно короткие сроки сложился и энергично развивается рынок криптографических услуг.

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

DES - Data Encryption Standard, был анонсирован в 1977 году Национальным бюро стандартов США, и был официально признан как результат работы подкомитета X3.92 Национального института стандартов США в 1981 году (ANSI X3.92-1981, American National Standards Data Encryption Algorithm, © American National Standards Institute, 1981.)

Статус DES как национального стандарта США, вызвал к нему широкий интерес во всем мире как со стороны разработчиков оборудования, так и со стороны криптографов - теоретиков. DES взят за основу национальных стандартов в некоторых других странах мира, например в Австралии это - Australian Standard AS2805.5-1985.

В Россию DES проник и достаточно широко практически используется как неотъемлемая деталь различных программных и аппаратных средств, из которых наиболее широко известны система S.W.I.F.T., секретные модули VISA и EUROPAY, секретные модули банкоматов и торговых терминалов, и, наконец, смарт-карты. Особенное напряжение дискуссий вокруг алгоритмов шифрования данных вызвано именно смарт-картами. При этом есть серьезные основания считать, что надежность отечественных крипто-систем конверсионного происхождения будет превосходить зарубежные аналоги.

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

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

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

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

Рассмотрим конкретную разновидность DES - шифрование на ключах длиной 56 бит (на самом деле - 8 байт, но каждый младший бит - проверочный и не используется при шифровании). Поскольку мы, похоже, настроились взломать такой шифр, то вооружимся калькулятором и прикинем во что нам это обойдется.

Исходные данные: необходимо попробовать расшифровать имеющийся у нас зашифрованный текст на 256 возможных вариантов ключей, т.е. выполнить расшифрование DES приблизительно 1015 раз. Поскольку операция DES - довольно длительная, сразу обзаведемся специализированным процессором, который выполняет 105 - сто тысяч операций DES в 1 секунду по цене 20 долларов США за один чип. Взлом шифров дело серьезное, поэтому построим вычислительную систему из тысячи таких чипов.

Результат: простой подсчет показывает, что нам понадобится 10 миллионов секунд работы такой системы, т.е. около 3 тысяч часов. Победа ! В течение всего 115 суток шифр взломан. Можно с сомнением относиться к возможности создания описанной крипто-системы, однако, шутки в сторону, для скептиков приведем справку: некто Matsui предпринял успешную атаку на однократный DES, шифр был взломан через 50 дней с помощью 12 рабочих станций HP 9735. Применялись специальные методы понижения теоретической стойкости - вопрос не данной статьи.

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

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

Тем не менее, обстоятельность и известный максимализм российского рынка криптосредств способствовали утверждению однозначного вывода: DES с длиной ключа 56 бит практически стойким не является.

Такой же вывод, но еще в 1988 году был сделан специалистами французской компании NET1 Products - Сержем Беламантом и Андре Мансвелтом при проектировании патентованной технологии безналичных расчетов на базе смарт-карт под названием U.E.P.S. Они же предложили и выход - двукратное последовательное применение DES на паре ключей.

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

Простой подсчет показывает, что если в спроектированной нами супер-системе каждый чип будет выполнять 10 миллионов (!) операций DES в 1 секунду, то на весь процесс уйдет 25 тысяч раз по 10 миллиардов лет. Неплохой результат ? В таких случаях удовлетворенные результатом криптографы предпочитают изъясняться космическим категориями, например, в периодах жизни солнечной системы.

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

Двойной DES выглядит очень привлекательно и возможно его было бы достаточно. Однако, как быть с системами, по-прежнему использующими однократное шифрование, как обеспечить совместимость схем распределении ключей и аппаратных решений ? Найден весьма оригинальный ответ. В последнее время де-факто утвердился стандарт шифрования - тройной DES на паре ключей.

Идея использования тройного DES с парой ключей очень проста: если ключи одинаковы, то результат шифрования эквивалентен однократному шифрованию. Это обеспечивает полную совместимость с существующими системами распределения и использования ключей как на однократном, так и на двойном DES. (Двойной DES - последовательное применение однократного).

Соответственно, если ключи разные и их два, то стойкость составляет уже описанные 2112. Для любителей формул тройной DES выглядит так:

EK1(DK2(EK1(Data8))),

EK1- операция шифрования (Encryption) DES на ключе K1,

DK2- операция дешифрования (Decryption) DES на ключе K2,

Data8 - данные длиной 8 байт.

Здесь видно, что если K1=K2, то DK2(EK1(Data8))=Data8 как результат последовательного за- и расшифрования на одном и том же ключе.

Согласно сообщению Центра общественных технологий США от 13 февраля 1995 года (Center for Democratic Technology - CDT), разработкой нового стандарта, основанного на трехкратном применении DES (triple-DES) занимается подкомитет X9 комитета Accredited Standards Committee (ASC), осуществляющего стандартизацию защиты данных в финансовой и банковской сфере США. Кроме того AT&T и VLSI Technologies, - крупные разработчики специального оборудования и элементной базы,- анонсировали свои планы относительно создания приложений на базе triple-DES.

Можно добавить, что ведущий мировой производитель смарт-карт GEMPLUS International уже заявил о переходе на новый стандарт шифрования triple DES для новой линии своих продуктов - карт серии MPCOS.

Какие же практические выводы можно сделать:

  1. Если ключи хранятся надежно идлина ключа (пары ключей) составляет 112 бит, то алгоритм шифрования DES обеспечивает достаточнуюстойкость.
  2. Тройное шифрование DES на паре ключей по стойкости не превосходит двойного шифрования на той же паре и обеспечивает полную совместимость как с одинарным, так и двойным DES.
  3. Тройной DES стал де-факто стандартом для защиты информации в банковской и финансовой сферах. В ближайшем будущем следует ожидать появления соответствующего стандарта ANSI.