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

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

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

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

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

DES небезопасен из-за относительно короткого 56-битный размер ключа. В январе 1999 г. распределенный.net и Фонд электронных рубежей объединились, чтобы публично взломать ключ DES за 22 часа 15 минут (см. хронология ). Есть также некоторые аналитические результаты, которые демонстрируют теоретические недостатки шифра, хотя на практике они невозможны. Считается, что алгоритм практически безопасен в виде Тройной DES, хотя есть теоретические выпады. Этот шифр был заменен Расширенный стандарт шифрования (AES). DES был отменен как стандарт Национальный институт стандартов и технологий.

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

История

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

Примерно в то же время инженер Мохамед Аталла в 1972 г. основан Корпорация Аталла и разработал первые аппаратный модуль безопасности (HSM), так называемый "Atalla Box", который был коммерциализирован в 1973 году. Он защищал автономные устройства с помощью безопасного ШТЫРЬ генерации ключа и имел коммерческий успех. Банки и компании, выпускающие кредитные карты, опасались, что Atalla будет доминировать на рынке, что стимулировало разработку международного стандарта шифрования.[4] Аталла был одним из первых конкурентов IBM на банковском рынке, и сотрудники IBM, работавшие над стандартом DES, указали на его влияние.[5] В IBM 3624 позже принял аналогичную систему проверки PIN-кода к более ранней системе Atalla.[6]

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

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

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

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

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

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

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

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

и

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

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

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

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

Алгоритм также указан в ANSI X3.92 (Сегодня X3 известен как ИНЦИТЫ и ANSI X3.92 как ANSI ИНЦИТЫ 92),[19] НИСТ СП 800-67[18] и ISO / IEC 18033-3[20] (в составе TDEA ).

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

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

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

Хронология

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

Описание

Для краткости в следующем описании опущены точные преобразования и перестановки, которые определяют алгоритм. Подробнее см. Дополнительный материал DES.
Начальная перестановкаФункция ФейстеляФункция ФейстеляФункция ФейстеляФункция ФейстеляОкончательная перестановкаXORXORXORXOR
Рисунок 1 - Общая структура Фейстеля DES

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

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

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

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

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

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

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

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

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

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

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

Функция расширенияПоле для замены 1Поле для замены 2Поле для замены 3Поле для замены 4Поле для замены 5Поле для замены 6Поле для замены 7Поле для замены 8Перестановка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-боксов переставлены согласно фиксированному перестановка, то П-бокс. Это спроектировано так, что после перестановки биты с выхода каждого S-блока в этом раунде распределяются по четырем различным S-блокам в следующем раунде.

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

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

Альтернативный вариант 1Альтернативный вариант 2Альтернативный вариант 2Альтернативный вариант 2Альтернативный вариант 2Сдвиг влево на 1Сдвиг влево на 1Сдвиг влево на 1Сдвиг влево на 1Сдвиг влево на 2Сдвиг влево на 2Сдвиг влево на 1Сдвиг влево на 1
Рисунок 3 - Ключевой график DES

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

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

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

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

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

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

В EFF 250 000 долларов США Крекинг-машина DES содержал 1856 нестандартных микросхем и мог подобрать ключ DES в течение нескольких дней - на фотографии показана печатная плата DES Cracker, оснащенная несколькими микросхемами Deep Crack.

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

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

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

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

Известны три атаки, которые могут разорвать полные 16 циклов DES с меньшей сложностью, чем поиск методом перебора: дифференциальный криптоанализ (ОКРУГ КОЛУМБИЯ),[38] линейный криптоанализ (LC),[39] и Атака Дэвиса.[40] Однако эти атаки носят теоретический характер и обычно считаются невозможными на практике;[41] эти типы атак иногда называют слабыми сторонами сертификации.

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

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

Дифференциально-линейный криптоанализ был предложен Лэнгфордом и Хеллманом в 1994 году и объединяет дифференциальный и линейный криптоанализ в одну атаку.[46] Расширенная версия атаки может взломать 9-раундовый DES за 215.8 выбранные открытые тексты и имеет 229.2 временная сложность (Бихам и др., 2002).[47]

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

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

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

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

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

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

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

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

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

Упрощенный DES

Упрощенный DES (SDES) был разработан только для образовательных целей, чтобы помочь студентам узнать о современных криптоаналитических методах. DES имеет те же свойства и структуру, что и DES, но был упрощен, чтобы значительно упростить выполнение шифрования и дешифрования вручную карандашом и бумагой. Некоторые люди считают, что изучение SDES дает представление о DES и других блочных шифрах, а также о различных криптоаналитических атаках на них.[51][52][53][54][55][56][57][58][59]

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

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

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

2 января 1997 года NIST объявили о своем желании выбрать преемника DES.[60] В 2001 году после международного конкурса NIST выбрал новый шифр, Расширенный стандарт шифрования (AES) в качестве замены.[61] Алгоритм, выбранный в качестве AES, был представлен его разработчиками под названием Rijndael. Другие финалисты NIST Конкурс AES включены RC6, Змея, МАРС, и Twofish.

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

Примечания

  1. ^ а б c d Диффи, Уитфилд; Хеллман, Мартин Э. (июнь 1977 г.). «Исчерпывающий криптоанализ стандарта шифрования данных NBS» (PDF). Компьютер. 10 (6): 74–84. Дои:10.1109 / C-M.1977.217750. S2CID  2412454. Архивировано из оригинал (PDF) на 2014-02-26.
  2. ^ «Наследие DES - Шнайер о безопасности». www.schneier.com. 6 октября 2004 г.
  3. ^ Уолтер Тачман (1997). «Краткая история стандарта шифрования данных». Интернет осажден: противодействие злодеяниям в киберпространстве. ACM Press / Addison-Wesley Publishing Co. Нью-Йорк, Нью-Йорк, США. С. 275–280.
  4. ^ Батис-Лазо, Бернардо (2018). Cash and Dash: как банкоматы и компьютеры изменили банковское дело. Oxford University Press. С. 284 и 311. ISBN  9780191085574.
  5. ^ «Экономические последствия программы стандарта шифрования данных (DES) NIST» (PDF). Национальный институт стандартов и технологий. Министерство торговли США. Октябрь 2001 г.. Получено 21 августа 2019.
  6. ^ Конхейм, Алан Г. (1 апреля 2016 г.). «Банкоматы: их история и протоколы аутентификации». Журнал криптографической инженерии. 6 (1): 1–29. Дои:10.1007 / s13389-015-0104-3. ISSN  2190-8516. S2CID  1706990. Архивировано из оригинал 22 июля 2019 г.. Получено 28 августа 2019.
  7. ^ RSA Laboratories. "Был ли DES сломан?". Архивировано из оригинал на 2016-05-17. Получено 2009-11-08.
  8. ^ Шнайер. Прикладная криптография (2-е изд.). п. 280.
  9. ^ Дэвис, Д. У .; W.L. Цена (1989). Безопасность компьютерных сетей, 2-е изд.. Джон Вили и сыновья.
  10. ^ Роберт Шугарман (редактор) (июль 1979 г.). «О пресечении компьютерных преступлений». IEEE Spectrum.CS1 maint: дополнительный текст: список авторов (связь)
  11. ^ П. Киннукан (октябрь 1978 г.). "Гуру шифрования данных: Тухман и Мейер". Криптология. 2 (4): 371. Дои:10.1080/0161-117891853270.
  12. ^ Томас Р. Джонсон (18 декабря 2009 г.). "Американская криптология во время холодной войны, 1945-1989. Книга III: сокращение и реформа, 1972-1980, стр. 232" (PDF). Национальное Агенство Безопасности, DOCID 3417193 (файл выпущен 18 декабря 2009 г., размещен на nsa.gov). Архивировано из оригинал (PDF) на 2013-09-18. Получено 2014-07-10.
  13. ^ Томас Р. Джонсон (18 декабря 2009 г.). "Американская криптология во время холодной войны, 1945-1989. Книга III: сокращение и реформа, 1972-1980, стр. 232" (PDF). Национальное Агенство Безопасности. Получено 2015-07-16 - через Архив национальной безопасности Запрос FOIA. Эта версия отредактирована иначе, чем версия на веб-сайте АНБ.
  14. ^ Томас Р. Джонсон (18 декабря 2009 г.). "Американская криптология во время холодной войны, 1945-1989. Книга III: сокращение и реформа, 1972-1980, стр. 232" (PDF). Национальное Агенство Безопасности. Получено 2015-07-16 - через Архив национальной безопасности Запрос FOIA. Эта версия отредактирована иначе, чем версия на веб-сайте АНБ.
  15. ^ Конхейм. Компьютерная безопасность и криптография. п. 301.
  16. ^ а б Леви, Крипто, п. 55
  17. ^ Шнайер, Брюс (27 сентября 2004 г.). «Приветствуя наследие шифрования данных». CNet. Получено 2015-07-22.
  18. ^ а б Национальный институт стандартов и технологий, Специальная публикация NIST 800-67 Рекомендации по блочному шифру алгоритма тройного шифрования данных (TDEA), Версия 1.1
  19. ^ Американский национальный институт стандартов, ANSI X3.92-1981 (теперь известный как ANSI ИНЦИТЫ 92-1981)Американский национальный стандарт, алгоритм шифрования данных
  20. ^ «ISO / IEC 18033-3: 2010 Информационные технологии. Методы безопасности. Алгоритмы шифрования. Часть 3. Блочные шифры».. Iso.org. 2010-12-14. Получено 2011-10-21.
  21. ^ Брюс Шнайер, Прикладная криптография, протоколы, алгоритмы и исходный код на языке C, второе издание, John Wiley and Sons, New York (1996), с. 267
  22. ^ Уильям Э. Берр, «Стандарт шифрования данных», в антологии NIST «Век передового опыта в измерениях, стандартах и ​​технологиях: хроника избранных публикаций NBS / NIST, 1901–2000». HTML В архиве 2009-06-19 на Wayback Machine PDF В архиве 2006-08-23 на Wayback Machine
  23. ^ "FR Doc 04-16894". Edocket.access.gpo.gov. Получено 2009-06-02.
  24. ^ С. Кумар, К. Паар, Дж. Пельцль, Г. Пфайфер, А. Рупп, М. Шиммлер, «Как взломать DES за 8 980 евро». 2-й семинар по специализированному оборудованию для атак на криптографические системы - SHARCS 2006, Кельн, Германия, 3–4 апреля 2006 г.
  25. ^ "8x1080Ti.md".
  26. ^ "Crack.sh | Самый быстрый в мире взломщик DES".
  27. ^ «FIPS 81 - Des Modes of Operation». csrc.nist.gov. Получено 2009-06-02.
  28. ^ «FIPS 74 - Руководство по внедрению и использованию данных NBS». Itl.nist.gov. Архивировано из оригинал на 2014-01-03. Получено 2009-06-02.
  29. ^ Шнайер. Прикладная криптография (1-е изд.). п. 271.
  30. ^ Столлингс, В. Криптография и сетевая безопасность: принципы и практика. Прентис Холл, 2006. стр. 73
  31. ^ "Bruting DES".
  32. ^ van Oorschot, Paul C .; Винер, Майкл Дж. (1991), Дамгард, Иван Бьерре (редактор), «Атака с использованием известного открытого текста на двухключевое тройное шифрование», Достижения в криптологии - EUROCRYPT ’90, Берлин, Гейдельберг: Springer Berlin Heidelberg, 473, стр. 318–325, Дои:10.1007/3-540-46877-3_29, ISBN  978-3-540-53587-4
  33. ^ "Приступая к работе, COPACOBANA - оптимизированный по стоимости параллельный взломщик кода" (PDF). 12 декабря 2006 г.. Получено 6 марта, 2012.
  34. ^ Райнхард Вобст (16 октября 2007 г.). Криптология разблокирована. Джон Вили и сыновья.
  35. ^ Взломать DES менее чем за один день [Пресс-релиз фирмы, продемонстрированный на семинаре 2009 г.]
  36. ^ Самый быстрый в мире взломщик DES
  37. ^ Думаете, сложные пароли спасут вас ?, Дэвид Халтон, Ян Фостер, BSidesLV 2017
  38. ^ а б Бихам Э. и Шамир А. (1993). Дифференциальный криптоанализ стандарта шифрования данных. Шамир, Ади. Нью-Йорк: Springer-Verlag. С. 487–496. Дои:10.1007/978-1-4613-9314-6. ISBN  978-0387979304. OCLC  27173465. S2CID  6361693.CS1 maint: несколько имен: список авторов (связь)
  39. ^ а б Мацуи, Мицуру (1993-05-23). «Метод линейного криптоанализа для шифра DES». Достижения в криптологии - EUROCRYPT '93. Конспект лекций по информатике. 765. Шпрингер, Берлин, Гейдельберг. С. 386–397. Дои:10.1007/3-540-48285-7_33. ISBN  978-3540482857. Отсутствует или пусто | название = (помощь)
  40. ^ а б Дэвис, Д. В. (1987). «Исследование потенциальной слабости в алгоритме DES, частные коммуникации». Частные коммуникации.
  41. ^ Alanazi, Hamdan O .; и другие. (2010). «Новое сравнительное исследование DES, 3DES и AES с использованием девяти факторов». Журнал вычислительной техники. 2 (3). arXiv:1003.4085. Bibcode:2010arXiv1003.4085A.
  42. ^ Бирюков Алексей; Канньер, Кристоф Де; Quisquater, Михаэль (2004-08-15). О множественных линейных приближениях. Достижения в криптологии - CRYPTO 2004. Конспект лекций по информатике. Шпрингер, Берлин, Гейдельберг. С. 1–22. Дои:10.1007/978-3-540-28628-8_1. ISBN  9783540226680.
  43. ^ Knudsen, Lars R .; Матиассен, Джон Эрик (2000-04-10). Линейная атака на DES с выбранным открытым текстом. Быстрое программное шифрование. Конспект лекций по информатике. Шпрингер, Берлин, Гейдельберг. С. 262–272. Дои:10.1007/3-540-44706-7_18. ISBN  978-3540447061.
  44. ^ Жюно, Паскаль (16 августа 2001 г.). О сложности атаки Мацуи. Избранные области криптографии. Конспект лекций по информатике. 2259. Шпрингер, Берлин, Гейдельберг. С. 199–211. Дои:10.1007 / 3-540-45537-X_16. ISBN  978-3540455370.
  45. ^ Бихам, Эли; Бирюков, Алексей (01.06.1997). «Улучшение атаки Дэвиса на DES». Журнал криптологии. 10 (3): 195–205. Дои:10.1007 / s001459900027. ISSN  0933-2790. S2CID  4070446.
  46. ^ Langford, Susan K .; Хеллман, Мартин Э. (1994-08-21). Дифференциально-линейный криптоанализ. Достижения в криптологии - CRYPTO '94. Конспект лекций по информатике. Шпрингер, Берлин, Гейдельберг. С. 17–25. Дои:10.1007/3-540-48658-5_3. ISBN  978-3540486589.
  47. ^ Бихам, Эли; Дункельман, Орр; Келлер, Натан (2002-12-01). Улучшение дифференциально-линейного криптоанализа. Достижения в криптологии - ASIACRYPT 2002. Конспект лекций по информатике. Шпрингер, Берлин, Гейдельберг. С. 254–266. Дои:10.1007/3-540-36178-2_16. ISBN  978-3540361787.
  48. ^ Менезеш, Альфред Дж .; van Oorschot, Paul C .; Ванстон, Скотт А. (1996). Справочник по прикладной криптографии. CRC Press. п.257. ISBN  978-0849385230.
  49. ^ Кэмпбелл и Винер, 1992 г.
  50. ^ «Двойной ДЕС» (PDF).
  51. ^ Санджай Кумар; Сандип Шривастава.«Шифрование изображений с использованием упрощенного стандарта шифрования данных (S-DES)» В архиве 2015-12-22 на Wayback Machine.2014.
  52. ^ Аласдер МакЭндрю.«Введение в криптографию с открытым исходным кодом».2012. Раздел «8.8 Упрощенный DES: sDES» .стр. 183 по 190.
  53. ^ Уильям Столлингс.«Приложение G: Упрощенный DES».2010.
  54. ^ Налини Н; Г. Рагхавендра Рао.«Криптоанализ упрощенного стандарта шифрования данных с помощью эвристики оптимизации».2006.
  55. ^ Мин Ван Нгуен.«Упрощенный DES».2009.
  56. ^ Доктор Манодж Кумар.«Криптография и сетевая безопасность».Раздел 3.4: Упрощенная версия DES (S-DES). 96.
  57. ^ Эдвард Ф. Шефер. "Упрощенный стандартный алгоритм шифрования данных".Дои:10.1080/0161-119691884799 1996.
  58. ^ Лавкуш Шарма; Бхупендра Кумар Патхак; и Нидхи Шарма.«Нарушение стандарта упрощенного шифрования данных с помощью оптимизации роя двоичных частиц».2012.
  59. ^ «Исследование криптографии: разработка лучшего способа обучения и изучения расширенного стандарта шифрования».
  60. ^ http://csrc.nist.gov/archive/aes/pre-round1/aes_9701.txt
  61. ^ http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf 26 ноября 2001 г.

Рекомендации

внешняя ссылка