Безопасность телекоммуникационных систем Лекция 2 Стандарт шифрования даних DES

Введение Стандарт шифрования данных (DES) блочный шифр с симметричными ключами, разработан Национальным Институтом Стандартов и Технологии (NIST – National Institute of Standards and Technology)

История В l973 году NIST издал запрос для разработки предложения национальной криптографической системы с симметричными ключами. Предложенная IBM модификация проекта, названная Lucifer, была принята как DES. DES были изданы в эскизном виде в Федеральном Регистре в марте 1975 года как Федеральный Стандарт Обработки Информации (FIPS – Federal Information Processing Standard)

Недоверие к стандарту Критиковалась сомнительно маленькая длина ключа (только 56 битов) критики были обеспокоены некоторым скрытым построением внутренней структуры DES Они подозревали, что некоторая часть структуры (S-блоки) может иметь скрытую лазейку, которая позволит расшифровывать сообщения без ключа внутренняя структура стандарта доработана январь 1977 года DES был издан как FIPS 46. Однако FIPS объявил DES как стандарт для использования в неофициальных приложениях. DES был наиболее широко используемым блочным шифром с симметричными ключами, начиная с его публикации. позже NIST предложил новый стандарт (FIPS 46-3), который рекомендует использование тройного DES (трехкратно повторенный шифр DES) для будущих приложений.

Общая схема Ш и ДШ DES блочный шифр Для шифрования и дешифрования применяется один и тот же 56- битовый ключ Рис. 1

Структура DES Процесс шифрования состоит из двух перестановок (P-блоки) они называются начальные и конечные перестановки, и шестнадцати раундов Файстеля. Каждый раунд использует различные сгенерированные 48-битовые ключи.

Общая структура DES Рис. 2

Начальные и конечные шаги перестановки DES Рис. 3

Таблица 1. Таблица начальных и конечных перестановок Начальные перестановкиКонечные перестановки

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

Значение начальных и конечных перестановок Начальные и конечные перестановки – это прямые P-блоки, которые инверсны друг другу. Они не имеют значения для криптографии DES.

Раунды DES использует 16 раундов. Каждый раунд DES применяет шифр Файстеля, как это показано на рис. Рис. 4

Раунды (описание) Раунд принимает LI-1 RI-1 от предыдущего раунда (или начального блока перестановки) и создает для следующего раунда LI И RI, которые поступают на следующий раунд (или конечный блок перестановки). Каждый из этих элементов является обратимым. Устройство замены очевидно обратимо, оно меняет местами левую половину текста с правой половиной. Смеситель является обратимым, потому что операция ИСКЛЮЧАЮЩЕЕ ИЛИ обратима. Все необратимые элементы сосредоточены в функции f (RI-1,KI)

Функция DES Основной блок DES функция DES. Функция DES с помощью 48-битового ключа зашифровывает 32 самых правых бит RI-1, чтобы получить на выходе 32-битовое слово. Эта функция содержит, как это показано на рис. 5, четыре секции:рис. 5 отбеливатель (whitener), P-блок расширения, группу S-блоков прямой P-блок.

P-блок расширения (1/3) Так как вход RI-1 имеет длину 32 бита, а ключ KI длину 48 битов, мы сначала должны расширить RI-1 до 48 бит. RI-1 разделяется на 8 секций по 4 бита. Каждая секция на 4 бита расширяется до 6 бит. Эта перестановка расширения следует по заранее определенным правилам. Для секции значения входных бит 1, 2, 3 и 4 присваиваются битам 2, 3, 4 и 5 соответственно на выходе. Выходной бит 1 формируется на основе входного бита 4 из предыдущей секции; бит выхода 6 формируется из бита 1 в следующей секции. Если секции 1 и 8 рассматривать как соседние секции, то те же самые правила применяются к битам 1 и 32. Рисунок 6 показывает входы и выходы в перестановке расширения.Рисунок 6 Хотя отношения между входом и выходом могут быть определены математически, но чтобы определить этот P-блок, DES использует таблицу 2. Обратите внимание, что число выходов 48, но диапазон значений только от 1 до 32. Некоторые из входов идут к больше чем одному выходу. Например, значение входного бита 5 становится значением битов выхода 6 и 8. таблицу 2

Функция DES Рис. 5

P-блок расширения Схема P-блока расширения Рис. 6

Отбеливатель (whitener) После расширения DES использует операцию XOR (ИСКЛЮЧАЮЩЕЕ ИЛИ) над расширенной частью правой секции и ключом раунда. Заметим, что правая секция и ключ имеют длину 48 бит. Также заметим, что ключ раунда использует только эту операцию.

S-блоки S-блоки смешивают информацию (операция перемешивания). DES использует S- блоки, каждый с 6-ю входными битами и 4- мя выходными Рис. 7

Правила для S- блока Данные из 48 битов от второй операции DES разделены на восемь кусков по 6 битов, и каждый кусок поступает в блок. Результат каждого блока кусок на 4 бита; когда они объединены, результат выражается в 32-битовом тексте. Подстановка в каждом блоке следует по заранее определенным правилам, основанным на таблице из 4-х строк и 16-ти столбцов. Комбинация битов 1 и 6 на входе определяет одну из четырех строк; комбинация битов от 2-го до 5-го определяет один из шестнадцати столбцов, как показано на рис. 8.рис. 8 Рис. 8

Таблицы S-блока Поскольку для каждого S-блока есть собственная таблица, необходимо иметь восемь таблиц, например таких, как это показано в таблице 3. Значение входа (номер строки и номер столбца) и значения выхода даются как десятичные номера, чтобы сэкономить место на странице. В реальности они могут быть заменены двоичными числами. Таблица 3. S-блок

Прямая перестановка Прямая перестановка последняя операция в функции DES прямая перестановка с 32 битами на входе и 32 битами на выходе. Отношения "вход-выход" для этой операции показаны в Таблице 4. Они следуют тем же самым общим правилам, как и предыдущие таблицы перестановки. Например, седьмой бит входа становится вторым битом выхода. Таблица 4. Таблица прямой перестановки

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

DES шифр и обратный шифр для первого способа Левая секция исходного текста на стороне шифрования шифруется L 0 как L 16, и L 16 дешифруется на стороне дешифратора как L 0. Аналогичная ситуация с R 0 и R 16. Нужно запомнить очень важное положение, которое касается шифров: ключи раундов (K 1 и K 16 ) применяются при шифровании и дешифровании в обратном порядке. На стороне шифрования первый раунд применяет ключ K 1, а раунд 16 ключ K 16 ; при дешифровании раунд 1 использует ключ K 16, а раунд 16 ключ K 1. Рис. 9

Альтернативный способ При первом способе раунд 16 отличается от других раундов тем, что там не применяется устройство замены. Это необходимо, чтобы сделать последний и первый смесители в шифре одинаковыми. Мы можем делать все 16 раундов одинаковыми, добавляя к 16-му раунду дополнительное устройство замены (два устройства замены позволяют нейтрализовать друг друга). Упражнение. Разработать схему альтернативного способа.

Генерация ключей Генератор ключей создает шестнадцать ключей по 48 битов из ключа шифра на 56 битов. Однако ключ шифра обычно дается как ключ из 64-х битов, в котором 8 дополнительных битов являются битами проверки. Они отбрасываются перед фактическим процессом генерации ключей, который показан на рис. Рис. 10

Удаление битов проверки Предварительный процесс перед расширением ключей перестановка сжатия, которую мы называем удалением битов проверки. Он удаляет биты четности (биты 8, 16, 24, 32..., 64) из 64-битового ключа и переставляет остальную часть битов согласно таблице. Остающееся значение на 56 битов фактический ключ шифра, который используется, чтобы генерировать ключи раунда. Биты удаляются с помощью перестановки (P- блока сжатия), как это показано в таблтаблицетаб Таблица удаления проверочных битов

Сдвиг влево После прямой перестановки ключ разделен на две части по 28 битов. Каждая часть сдвигается влево (циклический сдвиг) на один или два бита. В раундах 1, 2, 9 и 16 смещение – на один бит, в других раундах на два бита. Затем эти две части объединяются, чтобы создать часть в 56 бит. Таблица показывает число сдвигов манипуляций для каждого раундаТаблица Раунд Число бит Таблица сжатия ключа

Пример Мы выбираем случайный блок исходного текста и случайный ключ и определяем, каким должен быть блок зашифрованного текста (все цифры даны в шестнадцатеричном исчислении). Plaintext: ABCD Key: AABB CCDD Cipher Text: COB7ASD05F3AS29C

Трассировка данных в примере 3 Исходный текст: ABCD После первоначальной перестановки: 14A7D67818CA18D После разбиения: L 0 = 14A7D678 R 0 = 18CA18D РаундЛеваяПраваяКлюч раунда Раунд 118CA18AD5A78E394194CD072DE8C Раунд 25A78E3944A1210F ABCCE Раунд 34A1210F6B EDA4ACF5B5 Раунд 4B C2DA2D032B6EE3 Раунд C2A15A4B8769A629FEC913 Раунд 6A15A4B872E8F9C65C1948E87475E Раунд 72E8F9C65A9FC20A3708AD2DDB3C0 Раунд 8A9FC20A3308BEE9734F822F0C66D Раунд 9308BEE9710AF9D3784BB4473DCCC Раунд 1010AF9D376CA6CB B5BF Раунд 116CA6CB20FF3C485F6D5560AF7CA5 Раунд 12FF3C485F22A5963BC2C1E96A4BF3 Раунд 1322A5963B387CCDAA99C31397C91F Раунд 14387CCDAABD2DD2AB251B8BC717D0 Раунд 15BD2DD2ABCF26B C5D9A36D Раунд 1619BA9212CF26B472181C5D75C66D После объединения: 19BA9212 CF26B472 Зашифрованный текст: C0B7A8D05F3A829C (после конечной перестановки)

Пояснение к таблице Таблица показывает результат 16 раундов, которые включают смешивание и замену (исключая последний раунд). Результаты последних раундов (L 16 и R 16 ) объединены. Наконец, текст проходит конечную перестановку, для того чтобы получить зашифрованный текст. Следует отметить некоторые положения. Правая секция каждого раунда совпадает с левой секцией следующего раунда. Причина в том, что правая секция проходит через смеситель без изменения, а устройство замены переносит ее в левую секцию. Например, R 1 передается через смеситель второго раунда без изменения, но затем, пройдя устройство замены, он становится L 2. Второе интересное положение: на последнем раунде мы не имеем устройства замены. Именно поэтому R 15 становится R 16 вместо того чтобы стать L 16.

Анализ DES. Два желательных свойства блочного шифра эффект лавины и законченность Лавинный эффект означает, что небольшие изменения в исходном тексте (или ключе) могут вызвать значительные изменения в зашифрованном тексте. Было доказано, что DES имеет все признаки этого свойства. Эффект полноты заключается в том, что каждый бит зашифрованного текста должен зависеть от многих битов исходного текста. Рассеивание и перемешивание, произведенное P-блоками и S-блоками в DES, указывает на очень сильный эффект полноты.

Чтобы проверить эффект лавины в DES, попробуем зашифровать два блока исходного текста, которые отличаются только одним битом текста, с помощью одного и того же ключа и определим разницу в числе бит в каждом раунде. Исходный текст: Ключ: ABB23 Зашифрованный текст: 4789FD476E82A5F1 Исходный текст: Ключ: ABB23 Зашифрованный текст: OA4ED5C15A63FEA3 Хотя два блока исходного текста отличаются только самым правым битом, блоки зашифрованного текста отличаются на 29 бит. Это означает, что изменение приблизительно в 1,5 процентах исходного текста создают изменение приблизительно 45 процентов зашифрованного текста.

Проблемы разработок DES. Свойства S-блоков (1/2) 1) Входы каждой строки есть перестановки значений между 0 и 15. 2) S-блоки нелинейные. Другими словами, выход не аффинное преобразование. 3) Если мы изменяем единственный бит на входе, на выходе будут изменены два или больше бита. 4) Если два входа S-блока отличаются только двумя средними битами (битами 3 и 4), выходная информация должна отличаться по крайней мере двумя битами.

Проблемы разработок DES. Свойства S-блоков (1/2) 5) Если два входа в S-блок отличаются первыми двумя битами (биты 1 и 2) и последними двумя битами (5 и 6), два выхода должны быть различны. 6) Есть только 32 шестибитовые пары "вход-выход" (x i и x j ). Эти 32 входных пары создают 32 пары слова выхода по 4 бита. Если мы создаем какие-то различия между 32 выходами, то из этих d должны быть одинаковыми не больше чем 8. 7) Такой же критерий, как в пункте 6, применяется к трем S-блокам. 8) В любом S-блоке, если единственный входной бит сохраняется как константа (0 или 1), то другие биты изменяются случайно так, чтобы разности между числом нулей и единиц были минимизированы

P-блоки (1/2) Между двумя рядами S-блоков (в двух последующих раундах), есть один прямой P-блок (32 на 32) и один P-блок расширения (32 на 48). Эти два P-блока вместе обеспечивают рассеивание битов. В структуре P-блоков были реализованы следующие критерии: 1. Каждый вход S-блока подключается к выходу другого S-блока (в предыдущем раунде). 2. Ни один вход к данному S-блоку не соединяется с выходом от того же самого блока (в предыдущем раунде). 3. Четыре бита от каждого S-блока идут в шесть различных S-блоков (в следующем раунде). 4. Ни один из двух битов выхода от S-блока не идет в тот же самый S-блок (в следующем раунде).

P-блоки (2/2) 5. Если число блоков S-блоков 8, то S 1, S 2,..., S 8. – Выход S j-2 переходит в один из первых двух битов S j (в следующем раунде). – Бит выхода от S i-1 переходит в один из последних двух битов S j (в следующем раунде). – Выход S j +1 переходит в один из двух средних битов S j (в следующем раунде). 6. Для каждого S-блока два бита выхода идут в первые или последние два бита S-блока в следующем раунде. Другие два бита выхода идут в средние биты S-блока в следующем раунде. 7. Если выход от S j переходит в один из средних битов в S k (в следующем раунде), то бит выхода от S k не может идти в средний бит S j. Если мы допускаем j = k, то подразумеваем, что ни один средний бит S-блока не может идти в один из средних битов того же самого S-блока в следующем раунде.

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

Слабости DES (1/2) В течение прошлых нескольких лет критики нашли некоторые слабости в DES. S-блоки. В литературе указываются по крайней мере три проблемы S-блоков. В S-блоке 4 три бита выхода могут быть получены тем же самым способом, что и первый бит выхода: дополнением некоторых из входных битов. Два специально выбранных входа к массиву S-блока могут создать тот же самый выход. Можно получить тот же самый выход в одном единственном раунде, изменяя биты только в трех соседних S-блоках.

Слабости DES (2/2) P-блоки. В структуре P-блока были найдены одна загадка и одна слабость. Не ясно, почему проектировщики DES использовали начальную и конечную перестановки. Эти перестановки не вносят никаких новых свойств с точки зрения безопасности. В перестановке расширения (в функции) первые и четвертые биты последовательностей на 4 бита повторяются.

Слабость в ключе шифра (1/2) Размер ключа. Критики утверждают, что самая серьезная слабость DES это размер ключа (56 битов). Чтобы предпринять атаку грубой силы данного блока зашифрованного текста, злоумышленники должны проверить 2 56 ключей. a. Используя доступную сегодня технологию, можно проверить один миллион ключей в секунду. Это означает, что потребуется более чем две тысячи лет, чтобы выполнить атаку грубой силы на DES, используя компьютер только с одним процессором. b. Если мы можем сделать компьютер с одним миллионом чипов процессоров (параллельная обработка), то сможем проверить все множество ключей приблизительно за 20 часов. Когда был введен DES, стоимость такого компьютера была более чем несколько миллионов долларов, но она быстро снизилась. Специальный компьютер был создан в 1998 году и нашел ключ за 112 часов.

Слабость в ключе шифра (2/2) c. Компьютерные сети могут моделировать параллельную обработку. В 1977 году команда исследователей использовала 3500 компьютеров, подключенных к Internet, чтобы найти ключ RSA за 120 дней. Множество ключей было разделено среди всех этих компьютеров, и каждый компьютер был ответственен за проверку части домена DES. Если 3500 связанных в сеть компьютеров могут найти ключ через 120 дней, то секретное общество из членов может найти ключ через 10 дней. Приведенное выше показывает, что DES с размером ключа шифра 56 битов не обеспечивает достаточной безопасности. Есть одно решение этой проблемы – это использование тройного DES(3DES) с двумя ключами (112 битов) или тройного DES с тремя ключами (биты 16)

Двукратный DES

Трехкратный DES

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

Применение DES DES был национальным стандартом США в гг., но в настоящее время DES используется (с ключом длины 56 бит) только для устаревших систем, чаще всего используют его более криптоустойчивый вид (3DES, 2DES). 3DES является простой эффективной заменой DES, и сейчас он рассмотрен как стандарт.США DES2DES В ближайшее время DES и Triple DES будут заменены алгоритмом AES (Advanced Encryption Standard Расширенный Стандарт Шифрования). Алгоритм DES широко применяется для защиты финансовой информации: так, модуль THALES (Racal) HSM RG7000 полностью поддерживает операции TripleDES для эмиссии и обработки кредитных карт VISA, EuroPay и проч. Канальные шифраторы THALES (Racal) DataDryptor 2000 используют TripleDES для прозрачного шифрования потоков информации. Также алгогритм DES используется во многих других устройствах и решениях THALES-eSECURITY.Triple DES AESTripleDESVISA2000TripleDES