Стандарт шифрования данных - Data Encryption Standard

Стандарт шифрования данных
Стандартная блок-схема шифрования данных.svg
Функция Фейстеля (функция F) DES
Общий
Дизайнеров IBM
Впервые опубликовано 1975 г. (Федеральный регистр) (стандартизирован в январе 1977 г.)
Полученный из Люцифер
Преемники Тройной DES , G-DES , DES-X , LOKI89 , ICE
Деталь шифра
Ключевые размеры 56 бит
Размеры блоков 64 бит
Состав Сбалансированная сеть Фейстеля
Раундов 16
Лучший публичный криптоанализ
С самого начала DES считался небезопасным из-за возможности атак методом перебора. Такие атаки были продемонстрированы на практике (см. Взломщик EFF DES ) и теперь доступны на рынке в качестве услуги. По состоянию на 2008 год лучшей аналитической атакой является линейный криптоанализ , который требует 2 43 известных открытых текстов и имеет временную сложность 2 39–43 (Junod, 2001).

Стандарт шифрования данных ( DES / ˌ д я ˌ я ɛ ы , д ɛ г / ) является симметричным ключом алгоритм для шифрования цифровых данных. Хотя его короткая длина ключа в 56 бит делает его слишком небезопасным для приложений, он оказал большое влияние на развитие криптографии .

Алгоритм, разработанный в начале 1970-х годов в IBM и основанный на более ранней разработке Хорста Фейстеля , был представлен в Национальное бюро стандартов (NBS) после приглашения агентства предложить кандидата для защиты конфиденциальных несекретных данных электронного правительства. В 1976 году, после консультации с Агентством национальной безопасности (NSA), NBS выбрало слегка модифицированную версию (усиленную против дифференциального криптоанализа , но ослабленную против атак методом грубой силы ), которая была опубликована в качестве официального Федерального стандарта обработки информации (FIPS) для США в 1977 году.

Публикация стандарта шифрования, одобренного АНБ, привела к его быстрому международному принятию и повсеместному изучению со стороны ученых. Споры возникли из-за засекреченных элементов дизайна, относительно короткой длины ключа блочного шифра с симметричным ключом и участия АНБ, что вызвало подозрения в отношении бэкдора . В S-боксы , которые подтолкнули эти подозрения были разработаны АНБОМ , чтобы удалить лазейку они тайно знали ( дифференциальный криптоанализ ). Тем не менее, АНБ также позаботилось о том, чтобы размер ключа был резко уменьшен, чтобы они могли взломать шифр с помощью атаки грубой силы. Интенсивное научное изучение алгоритма, полученное с течением времени, привело к современному пониманию блочных шифров и их криптоанализа .

DES небезопасен из-за относительно короткого 56-битного размера ключа . В январе 1999 года распределенный.net и Electronic Frontier Foundation объединились, чтобы публично взломать ключ DES за 22 часа 15 минут (см. Хронологию ). Есть также некоторые аналитические результаты, которые демонстрируют теоретические недостатки шифра, хотя на практике они неосуществимы. Считается, что алгоритм практически безопасен в форме Triple DES , хотя есть теоретические атаки. Этот шифр был заменен Advanced Encryption Standard (AES). DES был отменен как стандарт Национальным институтом стандартов и технологий .

Некоторые документы различают стандарт DES и его алгоритм, называя алгоритм DEA ( алгоритм шифрования данных ).

История

Истоки DES относятся к 1972 году, когда исследование компьютерной безопасности правительства США , проведенное Национальным бюро стандартов, выявило потребность в общегосударственном стандарте для шифрования несекретной конфиденциальной информации.

Примерно в то же время инженер Мохамед Аталла в 1972 году основал корпорацию Atalla и разработал первый аппаратный модуль безопасности (HSM), так называемый «Atalla Box», который был коммерциализирован в 1973 году. Он защищал автономные устройства с помощью ключа для генерации безопасного PIN-кода , и имел коммерческий успех. Банки и компании, выпускающие кредитные карты, опасались доминирования Atalla на рынке, что стимулировало разработку международного стандарта шифрования. Аталла был одним из первых конкурентов IBM на банковском рынке, и сотрудники IBM, работавшие над стандартом DES, указали на его влияние. IBM 3624 впоследствии принял подобную систему проверки PIN - кода к более ранней системе Atalla.

15 мая 1973 года, после консультации с АНБ, NBS запросило предложения по шифру, который отвечал бы строгим критериям проектирования. Ни одно из представлений не подходило. Второй запрос был выдан 27 августа 1974 г. На этот раз, IBM представила кандидата , который считается приемлемым-шифром , разработанный в период 1973-1974 годов на основе ранее алгоритма, Файстель «s Люцифер шифра. Команда IBM, занимавшаяся разработкой и анализом шифров, включала Фейстеля, Уолтера Тачмана , Дона Копперсмита , Алан Конхейм, Карл Мейер, Майка Матиаса, Роя Адлера , Эдну Гроссман , Билла Нотца, Линн Смит и Брайанта Такермана .

Участие АНБ в разработке

17 марта 1975 г. предложенный DES был опубликован в Федеральном реестре . Были запрошены комментарии общественности, и в следующем году были проведены два открытых семинара для обсуждения предложенного стандарта. Пионеры криптографии с открытым ключом Мартин Хеллман и Уитфилд Диффи подвергли критике , ссылаясь на укороченную длину ключа и таинственные « S-блоки » как на свидетельство ненадлежащего вмешательства со стороны АНБ. Подозрение заключалось в том, что алгоритм был тайно ослаблен спецслужбами, чтобы они - но никто другой - могли легко читать зашифрованные сообщения. Алан Конхейм (один из разработчиков DES) прокомментировал: «Мы отправили S-блоки в Вашингтон. Они вернулись, и все они были другими». Сенат Соединенных Штатов Комитет по разведке рассмотрел действия АНБ, чтобы определить , имело ли место какое - либо ненадлежащее участие. В несекретном резюме своих выводов, опубликованном в 1978 году, Комитет написал:

При разработке DES АНБ убедило IBM в том, что уменьшенного размера ключа достаточно; косвенно помогал в разработке конструкций S-box; и подтвердили, что окончательный алгоритм DES, насколько им известно, лишен каких-либо статистических или математических недостатков.

Однако было также обнаружено, что

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

Другой член команды DES, Уолтер Тачман, заявил: «Мы полностью разработали алгоритм DES внутри IBM с помощью сотрудников IBM. АНБ не диктовало ни одного провода!» Напротив, рассекреченная книга АНБ по истории криптографии гласит:

В 1973 году NBS обратилась в частную промышленность с просьбой разработать стандарт шифрования данных (DES). Первые предложения разочаровали, поэтому АНБ начало работать над собственным алгоритмом. Затем Ховард Розенблюм, заместитель директора по исследованиям и разработкам, обнаружил, что Уолтер Тачман из IBM работает над модификацией Lucifer для общего пользования. АНБ дало Тухману разрешение и пригласило его для совместной работы с Агентством над его модификацией Люцифера ".

а также

АНБ тесно сотрудничало с IBM над усилением алгоритма защиты от всех атак, кроме грубой силы, и над усилением таблиц подстановки, называемых S-блоками. Наоборот, АНБ пыталось убедить IBM уменьшить длину ключа с 64 до 48 бит. В конечном итоге они взяли 56-битный ключ.

Некоторые из подозрений по поводу скрытых недостатков в S-боксов были развеяны в 1990 году, с независимым открытием и открытой публикации Бихам и Ади Шамира из дифференциального криптоанализа , общий метод разрушения блочных шифров. S-блоки DES были намного более устойчивы к атаке, чем если бы они были выбраны случайным образом, что убедительно свидетельствует о том, что IBM знала об этой технике в 1970-х годах. Это действительно было так; В 1994 году Дон Копперсмит опубликовал некоторые из исходных критериев проектирования S-образных коробов. По словам Стивена Леви , исследователи IBM Watson обнаружили дифференциальные криптоаналитические атаки в 1974 году, и АНБ попросило их сохранить этот метод в секрете. Копперсмит объясняет решение IBM о секретности тем, что «это произошло потому, что [дифференциальный криптоанализ] может быть очень мощным инструментом, используемым против многих схем, и были опасения, что такая информация в открытом доступе может отрицательно повлиять на национальную безопасность». Леви цитирует Уолтера Тачмана: «[t] они просили нас поставить печать на всех наших документах как конфиденциальные ... Мы фактически поставили номер на каждый из них и заперли их в сейфы, потому что они считались секретными правительством США. Они сказали, сделайте это. Итак. Я это сделал". Брюс Шнайер заметил, что «академическому сообществу потребовалось два десятилетия, чтобы понять, что« хитрости »АНБ на самом деле улучшили безопасность DES».

Алгоритм как стандартный

Несмотря на критику, DES был утвержден в качестве федерального стандарта в ноябре 1976 г. и опубликован 15 января 1977 г. как FIPS PUB 46, разрешенный для использования со всеми несекретными данными. Впоследствии он был подтвержден в качестве стандарта в 1983, 1988 (пересмотренный как FIPS-46-1), 1993 (FIPS-46-2) и снова в 1999 году (FIPS-46-3), последний предписывал " Triple DES " ( см. ниже). 26 мая 2002 г. после публичного конкурса DES был окончательно заменен на Advanced Encryption Standard (AES) . 19 мая 2005 года FIPS 46-3 был официально отозван, но NIST одобрил Triple DES до 2030 года для конфиденциальной правительственной информации.

Алгоритм также указан в ANSI X3.92 (сегодня X3 известен как INCITS, а ANSI X3.92 как ANSI INCITS 92), NIST SP 800-67 и ISO / IEC 18033-3 (как компонент TDEA ).

Другая теоретическая атака, линейный криптоанализ, была опубликована в 1994 году, но это была Фонд электронных Frontier «s DES крекер в 1998 году показал , что DES может быть атаковано очень практически, и подчеркнула необходимость разработки алгоритма замены. Эти и другие методы криптоанализа более подробно обсуждаются далее в этой статье.

Внедрение DES считается катализатором академических исследований криптографии, особенно методов взлома блочных шифров. Согласно ретроспективе NIST о DES,

Можно сказать, что DES дал толчок невоенному исследованию и разработке алгоритмов шифрования. В 1970-х было очень мало криптографов, за исключением тех, кто работал в военных или разведывательных организациях, и было мало академических исследований криптографии. Сейчас есть много активных академических криптологов, математических факультетов с сильными программами по криптографии, а также компаний и консультантов по коммерческой информационной безопасности. Поколение криптоаналитиков зарекомендовало себя, анализируя (то есть пытаясь «взломать») алгоритм DES. По словам криптографа Брюса Шнайера , «DES сделал больше для активизации области криптоанализа, чем что-либо еще. Теперь нужно было изучить алгоритм». Поразительная доля открытой литературы по криптографии в 1970-х и 1980-х годах была посвящена DES, и DES является стандартом, с которым с тех пор сравнивается каждый алгоритм с симметричным ключом .

Хронология

Дата Год Мероприятие
15 мая 1973 NBS публикует первый запрос на стандартный алгоритм шифрования
27 августа 1974 г. NBS публикует второй запрос алгоритмов шифрования
17 марта 1975 г. DES опубликован в Федеральном реестре для комментариев.
август 1976 г. Первый семинар по DES
сентябрь 1976 г. Второй семинар, посвященный математическим основам DES.
Ноябрь 1976 г. DES утвержден как стандарт
15 января 1977 г. DES опубликован как стандарт FIPS FIPS PUB 46
июнь 1977 г. Диффи и Хеллман утверждают, что шифр DES может быть взломан грубой силой.
1983 г. DES подтверждается впервые
1986 г. Videocipher II, система скремблирования спутникового телевидения, основанная на DES, начинает использоваться HBO.
22 января 1988 г. DES подтвержден во второй раз как FIPS 46-1, заменяя FIPS PUB 46.
июль 1991 г. Бихам и Шамир заново открывают для себя дифференциальный криптоанализ и применяют его к криптосистеме, подобной DES с 15 циклами.
1992 г. Бихам и Шамир сообщают о первой теоретической атаке с меньшей сложностью, чем грубая сила: дифференциальный криптоанализ . Однако это требует нереально 2 47 выбранных открытых текстов .
30 декабря 1993 г. DES в третий раз подтвержден как FIPS 46-2.
1994 г. Первый экспериментальный криптоанализ DES выполняется с использованием линейного криптоанализа (Matsui, 1994).
июнь 1997 г. Проект DESCHALL впервые публично взламывает сообщение, зашифрованное с помощью DES.
июль 1998 г. EFF «s DES крекер (Deep Crack) нарушает ключ DES в 56 часов.
Январь 1999 г. Вместе Deep Crack и распределенный.net взламывают ключ DES за 22 часа 15 минут.
25 октября 1999 г. DES в четвертый раз подтвержден как FIPS 46-3, который определяет предпочтительное использование тройного DES , при этом одиночный DES разрешен только в устаревших системах.
26 ноября 2001 г. Стандарт Advanced Encryption Standard опубликован в FIPS 197.
26 мая 2002 г. AES вступает в силу
26 июля 2004 г. Отзыв FIPS 46-3 (и нескольких связанных стандартов) предлагается в Федеральном реестре.
19 мая 2005 г. NIST отзывает FIPS 46-3 (см. Федеральный регистр, том 70, номер 96 ).
апрель 2006 г. FPGA -параллельная машина COPACOBANA из университетов в Бохуме и Киле, Германия, брейки DES 9 дней в аппаратной стоимости $ 10,000. В течение года усовершенствования программного обеспечения сократили среднее время до 6,4 дней.
Ноябрь 2008 г. Преемник COPACOBANA , машина RIVYERA, сократила среднее время до менее одного дня.
август 2016 г. Программное обеспечение для взлома паролей с открытым исходным кодом hashcat, добавленное в поиск грубой силы DES на графических процессорах общего назначения. Бенчмаркинг показывает, что единственный готовый к использованию графический процессор Nvidia GeForce GTX 1080 Ti стоимостью 1000 долларов США восстанавливает ключ в среднем за 15 дней (полный исчерпывающий поиск занимает 30 дней). Системы были построены с восемью графическими процессорами GTX 1080 Ti, которые могут восстановить ключ в среднем менее чем за 2 дня.
июль 2017 г. Выбраны по открытому тексту нападение с использованием таблицы радуги может восстановить ключ DES для одного специфического выбранного открытого текста 1122334455667788 за 25 секунд. Новая радужная таблица должна быть рассчитана для открытого текста. Ограниченный набор радужных таблиц доступен для загрузки.

Описание

Initial permutation Feistel function Feistel function Feistel function Feistel function Final permutation XOR XOR XOR XOR
Рисунок 1 - Общая структура Фейстеля DES

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

Ключ номинально хранится или передается как 8 байтов , каждый с нечетной четностью. Согласно ANSI X3.92-1981 (теперь известному как ANSI INCITS 92-1981), раздел 3.5:

Один бит в каждом 8-битном байте KEY может использоваться для обнаружения ошибок при генерации, распределении и хранении ключей. Биты 8, 16, ..., 64 используются для обеспечения того, чтобы каждый байт имел нечетную четность.

Как и другие блочные шифры, DES сам по себе не является безопасным средством шифрования, но вместо этого должен использоваться в рабочем режиме . FIPS-81 определяет несколько режимов для использования с DES. Дополнительные комментарии по использованию DES содержатся в FIPS-74.

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

Общая структура

Общая структура алгоритма показана на рисунке 1: имеется 16 идентичных этапов обработки, называемых раундами . Также существует начальная и конечная перестановки , называемые IP и FP , которые являются обратными (IP «отменяет» действие FP, и наоборот). IP и FP не имеют криптографического значения, но были включены для облегчения загрузки блоков в 8-битное оборудование середины 1970-х годов и обратно.

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

Символ ⊕ обозначает операцию исключающее ИЛИ (XOR). В F-функция карабкается полквартала вместе с некоторыми из ключевых. Выходные данные F-функции затем объединяются с другой половиной блока, и половины меняются местами перед следующим раундом. После финального раунда половинки меняются местами; это особенность структуры Фейстеля, которая делает процессы шифрования и дешифрования схожими.

Функция Фейстеля (F)

F-функция, изображенная на рисунке 2, работает с половиной блока (32 бита) за раз и состоит из четырех этапов:

Expansion function Substitution box 1 Substitution box 2 Substitution box 3 Substitution box 4 Substitution box 5 Substitution box 6 Substitution box 7 Substitution box 8 Permutation XOR
Рисунок 2 - Функция Фейстеля (F-функция) DES.
  1. Расширение : 32-битный полублок расширяется до 48 бит с использованием перестановки раскрытия , обозначенной на схеме буквой E , путем дублирования половины битов. Выходные данные состоят из восьми 6-битных (8 × 6 = 48 бит) частей, каждая из которых содержит копию 4 соответствующих входных битов плюс копию непосредственно соседнего бита из каждой входной части с каждой стороны.
  2. Смешивание ключей : результат объединяется с подключом с помощью операции XOR. Шестнадцать 48-битных подключей - по одному на каждый цикл - выводятся из основного ключа с использованием расписания ключей (описанного ниже).
  3. Замещение : после смешивания в подключе блок делится на восемь 6-битных частей перед обработкой S-блоками или блоками замещения . Каждый из восьми S-блоков заменяет свои шесть входных бит четырьмя выходными битами в соответствии с нелинейным преобразованием, представленным в форме справочной таблицы . S-блоки обеспечивают основу безопасности DES - без них шифр был бы линейным и легко взломаемым.
  4. Перестановка : наконец, 32 выхода из S-блоков переставляются в соответствии с фиксированной перестановкой , P-блоком . Это разработано так, что после перестановки биты с выхода каждого S-блока в этом цикле распределяются по четырем различным S-блокам в следующем цикле.

Чередование подстановки из S-блоков и перестановка битов из P-блока и E-расширения обеспечивает, соответственно, так называемую « путаницу и распространение », концепция, определенная Клодом Шенноном в 1940-х годах как необходимое условие для безопасного пока что практический шифр.

Ключевой график

Permuted choice 1 Permuted choice 2 Permuted choice 2 Permuted choice 2 Permuted choice 2 Left shift by 1 Left shift by 1 Left shift by 1 Left shift by 1 Left shift by 2 Left shift by 2 Left shift by 1 Left shift by 1
Рисунок 3 - Ключевое расписание DES

На рисунке 3 показано расписание ключей для шифрования - алгоритм, который генерирует подключи. Первоначально, 56 бит ключа выбираются из исходного 64 с помощью переставляется Choice 1 ( PC-1 ) -The остальных восемь бит либо отбрасываются или использовать в качестве контроля четности бит проверки. Затем 56 бит делятся на две 28-битные половины; после этого каждая половина обрабатывается отдельно. В последовательных раундах обе половины поворачиваются влево на один или два бита (указываются для каждого раунда), а затем 48 бит подключей выбираются с помощью перестановочного выбора 2 ( PC-2 ) - 24 бита из левой половины и 24 бита из правой. . Вращения (обозначенные на схеме «<<<») означают, что в каждом подключе используется другой набор битов; каждый бит используется примерно в 14 из 16 подключей.

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

Безопасность и криптоанализ

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

Атака грубой силой

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

EFF US $ 250000 «s машина растрескивания DES содержала собственные чипы 1856 и может грубую силу ключа DES в считанные дни-фото показывает схему борт DES Cracker оснащен несколько чипов Deep Crack.

В академических кругах выдвигались различные предложения по машине для взлома DES. В 1977 году Диффи и Хеллман предложили машину стоимостью около 20 миллионов долларов США, которая могла бы найти ключ DES за один день. К 1993 году Винер предложил машину для поиска ключей стоимостью 1 миллион долларов США, которая могла бы найти ключ в течение 7 часов. Однако ни одно из этих ранних предложений так и не было реализовано - или, по крайней мере, ни одна реализация не получила публичного признания. Уязвимость DES была практически продемонстрирована в конце 1990-х годов. В 1997 году RSA Security спонсировала серию конкурсов, предложив приз в размере 10 000 долларов первой команде, взломавшей сообщение, зашифрованное с помощью DES. Этот конкурс был выигран проектом DESCHALL под руководством Рок Верзера, Мэтта Кертина и Джастина Долске, использовавшего циклы простоя тысяч компьютеров в Интернете. Возможность быстрого взлома DES была продемонстрирована в 1998 году, когда Electronic Frontier Foundation (EFF), группа по защите гражданских прав в киберпространстве, построила специальный взломщик DES , который обошелся примерно в 250 000 долларов США (см. Взломщик EFF DES ). Их мотивация заключалась в том, чтобы показать, что DES можно взломать как на практике, так и в теории: « Многие люди не поверят в истину, пока не увидят ее собственными глазами. Показав им физическую машину, которая может взломать DES за несколько секунд. дней - единственный способ убедить некоторых людей в том, что они действительно не могут доверять свою безопасность DES ». Машина подобрала ключ за немногим более двух дней поиска.

Следующим подтвержденным взломщиком DES стала машина COPACOBANA, построенная в 2006 году командами университетов Бохума и Киля , оба в Германии . В отличие от машины EFF, COPACOBANA состоит из коммерчески доступных реконфигурируемых интегральных схем. 120 из этих программируемых вентильных матриц (FPGA) типа XILINX Spartan-3 1000 работают параллельно. Они сгруппированы в 20 модулей DIMM, каждый из которых содержит 6 ПЛИС. Использование реконфигурируемого оборудования делает машину применимой и для других задач взлома кода. Одним из наиболее интересных аспектов COPACOBANA является его стоимость. Одна машина может быть построена примерно за 10 000 долларов. Снижение стоимости примерно в 25 раз по сравнению с машиной EFF является примером постоянного совершенствования цифрового оборудования - см. Закон Мура . Поправка на инфляцию за 8 лет дает еще большее улучшение, примерно в 30 раз. С 2007 года SciEngines GmbH , дочерняя компания двух партнеров по проекту COPACOBANA, усовершенствовала и разработала преемников COPACOBANA. В 2008 году их COPACOBANA RIVYERA сократила время взлома DES до менее одного дня, используя 128 Spartan-3 5000. SciEngines RIVYERA установила рекорд по взлому DES, использовав 128 ПЛИС Spartan-3 5000. Их модель 256 Spartan-6 LX150 на этот раз еще ниже.

В 2012 году Дэвид Халтон и Мокси Марлинспайк анонсировали систему с 48 ПЛИС Xilinx Virtex-6 LX240T, каждая из которых содержит 40 полностью конвейерных ядер DES, работающих на частоте 400 МГц, с общей пропускной способностью 768 гигакейсов в секунду. Система может выполнить исчерпывающий поиск по всему 56-битному ключевому пространству DES примерно за 26 часов, и эта услуга предлагается за плату в режиме онлайн.

Атакует быстрее грубой силы

Известны три атаки, которые могут взломать полные 16 раундов DES с меньшей сложностью, чем поиск методом перебора: дифференциальный криптоанализ (DC), линейный криптоанализ (LC) и атака Дэвиса . Однако эти атаки носят теоретический характер и обычно считаются невозможными на практике; эти типы атак иногда называют слабыми сторонами сертификации.

  • Дифференциальный криптоанализ был заново открыт в конце 1980-х Эли Бихамом и Ади Шамиром ; ранее об этом знали и IBM, и АНБ, и он держался в секрете. Чтобы разорвать полные 16 раундов, дифференциальный криптоанализ требует 2 47 выбранных открытых текстов . DES был разработан, чтобы быть устойчивым к постоянному току.
  • Линейный криптоанализ был открыт Мицуру Мацуи и требует 2 43 известных открытых текстов (Matsui, 1993); этот метод был реализован (Matsui, 1994), и это был первый экспериментальный криптоанализ DES, о котором было сообщено. Нет никаких доказательств того, что DES был адаптирован для защиты от атак этого типа. Обобщение LC - множественный линейный криптоанализ - было предложено в 1994 г. (Калиски и Робшоу) и далее усовершенствовано Бирюковым и другими. (2004); их анализ показывает, что можно использовать множественные линейные аппроксимации для уменьшения требований к данным для атаки как минимум в 4 раза (то есть 2 41 вместо 2 43 ). Подобное снижение сложности данных может быть получено в варианте линейного криптоанализа с выбранным открытым текстом (Knudsen and Mathiassen, 2000). Жюно (2001) выполнили несколько экспериментов , чтобы определить действительную временную сложность линейного криптоанализа, и сообщил , что он был несколько быстрее , чем предполагалось, что требует времени , эквивалентного 2 39 -2 41 оценок DES.
  • Улучшенная атака Дэвиса : в то время как линейный и дифференциальный криптоанализ являются общими методами и могут быть применены к ряду схем, атака Дэвиса - это специализированный метод для DES, впервые предложенный Дональдом Дэвисом в восьмидесятых годах и улучшенный Бихамом и Бирюковым (1997). ). Самая мощная форма атаки требует 2 50 известных открытых текстов , имеет вычислительную сложность 2 50 и вероятность успеха 51%.

Также были предложены атаки против версий шифра с сокращенным числом раундов, то есть версий DES с числом раундов меньше 16. Такой анализ дает представление о том, сколько раундов необходимо для обеспечения безопасности, и какой «запас прочности» сохраняет полная версия.

Дифференциально-линейный криптоанализ был предложен Лэнгфордом и Хеллманом в 1994 году и объединяет дифференциальный и линейный криптоанализ в единую атаку. Усовершенствованная версия атаки может взломать 9-этапный DES с 2 15,8 выбранными открытыми текстами и имеет временную сложность 2 29,2 (Бихам и другие, 2002).

Незначительные криптоаналитические свойства

DES демонстрирует свойство дополняемости, а именно:

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

DES также имеет четыре так называемых слабых ключа . Шифрование ( E ) и дешифрование ( D ) под слабым ключом имеют одинаковый эффект (см. Инволюция ):

или эквивалентно,

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

или эквивалентно,

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

Также было доказано, что DES не является группой , или, точнее, набор (для всех возможных ключей ) при функциональной композиции не является группой и не «близок» к тому, чтобы быть группой. Некоторое время это был открытый вопрос, и если бы это было так, можно было бы взломать DES, а несколько режимов шифрования, таких как Triple DES , не повысили бы безопасность, потому что повторяющееся шифрование (и дешифрование) с разными ключами будет эквивалентно шифрованию с использованием другого единственного ключа.

Упрощенный DES

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

Алгоритмы замены

Опасения по поводу безопасности и относительно медленная работа DES в программном обеспечении побудили исследователей предложить множество альтернативных конструкций блочных шифров , которые начали появляться в конце 1980-х - начале 1990-х годов: примеры включают RC5 , Blowfish , IDEA , NewDES , SAFER , CAST5 и FEAL . В большинстве этих проектов сохранен 64-битный размер блока DES, и они могут выступать в качестве «заменяющей» замены, хотя обычно они используют 64-битный или 128-битный ключ. В Советском Союзе ГОСТ 28147-89 алгоритм был введен с 64-битным размером блока и 256-битный ключ, который также был использован в России позже.

Сам DES может быть адаптирован и повторно использован в более безопасной схеме. Многие бывшие пользователи DES теперь используют Triple DES (TDES), который был описан и проанализирован одним из патентообладателей DES (см. FIPS Pub 46-3); он включает в себя трехкратное применение DES с двумя (2TDES) или тремя (3TDES) разными ключами. TDES считается достаточно безопасным, хотя и довольно медленным. Менее затратной с точки зрения вычислений альтернативой является DES-X , который увеличивает размер ключа путем выполнения операции XOR с дополнительным ключевым материалом до и после DES. GDES был вариантом DES, предложенным как способ ускорения шифрования, но было показано, что он подвержен дифференциальному криптоанализу.

2 января 1997 года NIST объявили о своем желании выбрать преемника DES. В 2001 году после международного конкурса NIST выбрал новый шифр, Advanced Encryption Standard (AES), в качестве замены. Алгоритм, который был выбран в качестве AES, был представлен его разработчиками под именем Rijndael . Среди других финалистов конкурса NIST AES были RC6 , Serpent , MARS и Twofish .

Смотрите также

Примечания

использованная литература

внешние ссылки