1 [ИНФОРМАЦИОННАЯ БЕЗОПАСТНОСТЬ] [Институт ИИБС, Кафедра ИСКТ] [Шумейко Е.В.] АЛГОРИТМЫ СИММЕТРИЧНОГО ШИФРОВАНИЯ. - презентация

1 1 [ИНФОРМАЦИОННАЯ БЕЗОПАСТНОСТЬ] [Институт ИИБС, Кафедра ИСКТ] [Шумейко Е.В.] АЛГОРИТМЫ СИММЕТРИЧНОГО ШИФРОВАНИЯ

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

3 3 В процессе шифрования используется определенный алгоритм шифрования, на вход которому подаются исходное незашифрованное сообщение, называемое также plaintext, и ключ. Выходом алгоритма является зашифрованное сообщение, называемое также ciphertext. Ключ является значением, не зависящим от шифруемого сообщения. Изменение ключа должно приводить к изменению зашифрованного сообщения. Зашифрованное сообщение передается получателю. Получатель преобразует зашифрованное сообщение в исходное незашифрованное сообщение с помощью алгоритма дешифрования и того же самого ключа, который использовался при шифровании, или ключа, легко получаемого из ключа шифрования. Незашифрованное сообщение будем обозначать P или M, от слов plaintext и message. Зашифрованное сообщение будем обозначать С, от слова ciphertext. Криптография. Основные понятия

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

5 5 Криптография. Основные понятия Клод Шеннон ввел понятия диффузии и конфуции для описания стойкости алгоритма шифрования. Диффузия - это рассеяние статистических особенностей незашифрованного текста в широком диапазоне статистических особенностей зашифрованного текста. Это достигается тем, что значение каждого элемента незашифрованного текста влияет на значения многих элементов зашифрованного текста или, что то же самое, любой элемент зашифрованного текста зависит от многих элементов незашифрованного текста. Конфузия - это уничтожение статистической взаимосвязи между зашифрованным текстом и ключом. Если Х - это исходное сообщение и k - криптографический ключ, то зашифрованный передаваемый текст можно записать в виде Y = Ek[X]. Получатель, используя тот же ключ, расшифровывает сообщение X = Dk[Y] Противник, не имея доступа к K и Х, должен попытаться узнать Х, K или и то, и другое.

6 6 Криптография. Основные понятия Алгоритмы симметричного шифрования различаются способом, которым обрабатывается исходный текст. Возможно шифрование блоками или шифрование потоком. Блок текста рассматривается как неотрицательное целое число, либо как несколько независимых неотрицательных целых чисел. Длина блока всегда выбирается равной степени двойки. В большинстве блочных алгоритмов симметричного шифрования используются следующие типы операций: Табличная подстановка, при которой группа битов отображается в другую группу битов. Это так называемые S-box. Перемещение, с помощью которого биты сообщения переупорядочиваются. Операция сложения по модулю 2, обозначаемая XOR или Операция сложения по модулю 2 32 или по модулю Циклический сдвиг на некоторое число битов.

7 7 Эти операции циклически повторяются в алгоритме, образуя так называемые раунды. Входом каждого раунда является выход предыдущего раунда и ключ, который получен по определенному алгоритму из ключа шифрования K. Ключ раунда называется подключом. Каждый алгоритм шифрования может быть представлен следующим образом: Криптография. Основные понятия

8 8 Криптография. Области применения Стандартный алгоритм шифрования должен быть применим во многих приложениях: Шифрование данных. Алгоритм должен быть эффективен при шифровании файлов данных или большого потока данных. Создание случайных чисел. Алгоритм должен быть эффективен при создании определенного количества случайных битов. Хэширование. Алгоритм должен эффективно преобразовываться в одностороннюю хэш-функцию.

9 9 Криптография. Платформы Стандартный алгоритм шифрования должен быть реализован на различных платформах, которые, соответственно, предъявляют различные требования. Алгоритм должен эффективно реализовываться на специализированной аппаратуре, предназначенной для выполнения шифрования/дешифрования. Большие процессоры. Хотя для наиболее быстрых приложений всегда используется специальная аппаратура, программные реализации применяются чаще. Алгоритм должен допускать эффективную программную реализацию на 32-битных процессорах. Процессоры среднего размера. Алгоритм должен работать на микроконтроллерах и других процессорах среднего размера. Малые процессоры. Должна существовать возможность реализации алгоритма на смарт-картах, пусть даже с учетом жестких ограничений на используемую память.

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

11 11 Сеть Фейштеля Блочный алгоритм преобразовывает n-битный блок незашифрованного текста в n-битный блок зашифрованного текста. Число блоков длины n равно 2n. Для того чтобы преобразование было обратимым, каждый из таких блоков должен преобразовываться в свой уникальный блок зашифрованного текста. При маленькой длине блока такая подстановка плохо скрывает статистические особенности незашифрованного текста. Если блок имеет длину 64 бита, то он уже хорошо скрывает статистические особенности исходного текста. Но в данном случае преобразование текста не может быть произвольным в силу того, что ключом будет являться само преобразование, что исключает эффективную как программную, так и аппаратную реализации. Наиболее широкое распространение получили сети Фейштеля, так как, с одной стороны, они удовлетворяют всем требованиям к алгоритмам симметричного шифрования, а с другой стороны, достаточно просты и компактны.

12 12 Сеть Фейштеля Сеть Фейштеля имеет следующую структуру. Входной блок делится на несколько равной длины подблоков, называемых ветвями. В случае, если блок имеет длину 64 бита, используются две ветви по 32 бита каждая. Каждая ветвь обрабатывается независимо от другой, после чего осуществляется циклический сдвиг всех ветвей влево. Такое преобразование выполняется несколько циклов или раундов. В случае двух ветвей каждый раунд имеет структуру, показанную на рисунке:

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

14 14 В настоящее время все чаще используются различные разновидности сети Фейштеля для 128-битного блока с четырьмя ветвями. Увеличение количества ветвей, а не размерности каждой ветви связано с тем, что наиболее популярными до сих пор остаются процессоры с 32-разрядными словами, следовательно, оперировать 32-разрядными словами эффективнее, чем с 64-разрядными. Основной характеристикой алгоритма, построенного на основе сети Фейштеля, является функция F. Различные варианты касаются также начального и конечного преобразований. Подобные преобразования, называемые забеливанием (whitening), осуществляются для того, чтобы выполнить начальную рандомизацию входного текста. Сеть Фейштеля

15 15 Криптоанализ Процесс, при котором предпринимается попытка узнать Х, K или и то, и другое, называется криптоанализом. Одной из возможных атак на алгоритм шифрования является лобовая атака, т.е. простой перебор всех возможных ключей. Если множество ключей достаточно большое, то подобрать ключ нереально. При длине ключа n бит количество возможных ключей равно 2n. Таким образом, чем длиннее ключ, тем более стойким считается алгоритм для лобовой атаки. Существуют различные типы атак, основанные на том, что противнику известно определенное количество пар незашифрованное сообщение - зашифрованное сообщение. При анализе зашифрованного текста противник часто применяет статистические методы анализа текста. При этом он может иметь общее представление о типе текста, например, английский или русский текст, выполнимый файл конкретной ОС, исходный текст на некотором конкретном языке программирования и т.д. Во многих случаях криптоаналитик имеет достаточно много информации об исходном тексте.

16 16 Криптоанализ Криптоаналитик может иметь возможность перехвата одного или нескольких незашифрованных сообщений вместе с их зашифрованным видом. Или криптоаналитик может знать основной формат или основные характеристики сообщения. Говорят, что криптографическая схема абсолютно безопасна, если зашифрованное сообщение не содержит никакой информации об исходном сообщении. Говорят, что криптографическая схема вычислительно безопасна, если: Цена расшифровки сообщения больше цены самого сообщения. Время, необходимое для расшифровки сообщения, больше срока жизни сообщения.

17 17 Дифференциальный и линейный криптоанализ Рассмотрим в общих чертах основной подход, используемый при дифференциальном и линейном криптоанализе. И в том, и в другом случае предполагается, что известно достаточно большое количество пар (незашифрованнный текст, зашифрованный текст). Понятие дифференциального криптоанализа было введено Эли Бихамом (Biham) и Ади Шамиром (Shamir) в 1990 году. Конечная задача дифференциального криптоанализа - используя свойства алгоритма, в основном свойства S-box, определить подключ раунда. Конкретный способ дифференциального криптоанализа зависит от рассматриваемого алгоритма шифрования.

18 18 Дифференциальный и линейный криптоанализ Если в основе алгоритма лежит сеть Фейштеля, то можно считать, что блок m состоит из двух половин - m0 и m1. Дифференциальный криптоанализ рассматривает отличия, которые происходят в каждой половине при шифровании. (Для алгоритма DES "отличия" определяются с помощью операции XOR, для других алгоритмов возможен иной способ). Выбирается пара незашифрованных текстов с фиксированным отличием. Затем анализируются отличия, получившиеся после шифрования одним раундом алгоритма, и определяются вероятности различных ключей. Если для многих пар входных значений, имеющих одно и то же отличие Х, при использовании одного и того же подключа одинаковыми (Y) оказываются и отличия соответствующих выходных значений, то можно говорить, что Х влечет Y с определенной вероятностью. Если эта вероятность близка к единице, то можно считать, что подключ раунда найден с данной вероятностью. Так как раунды алгоритма независимы, вероятности определения подключа каждого раунда следует перемножать. Как мы помним, считается, что результат шифрования данной пары известен. Результаты дифференциального криптоанализа используются как при разработке конкретных S-box, так и при определении оптимального числа раундов.

19 19 Дифференциальный и линейный криптоанализ Другим способом криптоанализа является линейный криптоанализ, который использует линейные приближения преобразований, выполняемых алгоритмом шифрования. Данный метод позволяет найти ключ, имея достаточно большое число пар (незашифрованный текст, зашифрованный текст). Рассмотрим основные принципы, на которых базируется линейный криптоанализ. Обозначим P[1], …, P[n] - незашифрованный блок сообщения. C[1], …, C[n] - зашифрованный блок сообщения. K[1], …, K[m] - ключ. Целью линейного криптоанализа является поиск линейного уравнения вида

20 20 Дифференциальный и линейный криптоанализ Выполняющееся с вероятностью р 0.5 i, βi и γi - фиксированные позиции в блоках сообщения и ключе. Чем больше р отклоняется от 0.5, тем более подходящим считается уравнение. Это уравнение означает, что если выполнить операцию XOR над некоторыми битами незашифрованного сообщения и над некоторыми битами зашифрованного сообщения, получится бит, представляющий собой XOR некоторых битов ключа. Это называется линейным приближением, которое может быть верным с вероятностью р.

21 21 Дифференциальный и линейный криптоанализ Уравнения составляются следующим образом. Вычисляются значения левой части для большого числа пар соответствующих фрагментов незашифрованного и зашифрованного блоков. Если результат оказывается равен нулю более чем в половине случаев, то полагают, что K[γ1, …, γс] = 0. Если в большинстве случаев получается 1, полагают, что K[γ1, …, γс] = 1. Таким образом получают систему уравнений, решением которой является ключ. Как и в случае дифференциального криптоанализа, результаты линейного криптоанализа должны учитываться при разработке алгоритмов симметричного криптоанализа

22 22 Используемые критерии при разработке алгоритмов Принимая во внимание перечисленные требования, обычно считается, что алгоритм симметричного шифрования должен: Манипулировать данными в больших блоках, предпочтительно размером 16 или 32 бита. Иметь размер блока 64 или 128 бит. Иметь масштабируемый ключ до 256 бит. Использовать простые операции, которые эффективны на микропроцессорах, т.е. исключающее или, сложение, табличные подстановки, умножение по модулю. Не должно использоваться сдвигов переменной длины, побитных перестановок или условных переходов. Должна быть возможность реализации алгоритма на 8-битном процессоре с минимальными требованиями к памяти.

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

24 24 Задействовать подключи, которые являются односторонним хэшем ключа. Это дает возможность использовать большие парольные фразы в качестве ключа без ущерба для безопасности. Не иметь линейных структур, которые уменьшают комплексность и не обеспечивают исчерпывающий поиск. Использовать простую для понимания разработку. Это дает возможность анализа и уменьшает закрытость алгоритма. Используемые критерии при разработке алгоритмов Большинство блочных алгоритмов основано на использовании сети Фейштеля, все имеют плоское пространство ключей, с возможным исключением нескольких слабых ключей.

25 25 Алгоритм DES. Принципы разработки Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technolody США) в качестве стандарта (FIPS PUB 46). DES является классической сетью Фейштеля с двумя ветвями. Данные шифруются 64-битными блоками, используя 56-битный ключ. Алгоритм преобразует за несколько раундов 64-битный вход в 64-битный выход. Длина ключа равна 56 битам. Процесс шифрования состоит из четырех этапов. На первом из них выполняется начальная перестановка (IP) 64-битного исходного текста (забеливание), во время которой биты переупорядочиваются в соответствии со стандартной таблицей.

26 26 Алгоритм DES. Принципы разработки Следующий этап состоит из 16 раундов одной и той же функции, которая использует операции сдвига и подстановки. На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами. Наконец, на четвертом этапе выполняется перестановка IP-1 результата, полученного на третьем этапе. Перестановка IP-1 инверсна начальной перестановке.

27 27 Алгоритм DES. Принципы разработки Общая схема DES Справа на рисунке показан способ, которым используется 56-битный ключ. Первоначально ключ подается на вход функции перестановки. Затем для каждого из 16 раундов подключ Ki является комбинацией левого циклического сдвига и перестановки. Функция перестановки одна и та же для каждого раунда, но подключи Ki для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.

28 28 Алгоритм DES. Шифрование. Начальная перестановка Начальная перестановка и ее инверсия определяются стандартной таблицей. Если М - это произвольные 64 бита, то X = IP (M) - переставленные 64 бита. Если применить обратную функцию перестановки Y = IP-1 (X) = IP-1 (IP(M)), то получится первоначальная последовательность битов. Последовательность преобразований отдельного раунда Теперь рассмотрим последовательность преобразований, используемую в каждом раунде.

29 29 Алгоритм DES. Шифрование Рис I-ый раунд DES

30 30 64-битный входной блок проходит через 16 раундов, при этом на каждой итерации получается промежуточное 64-битное значение. Левая и правая части каждого промежуточного значения трактуются как отдельные 32-битные значения, обозначенные L и R. Каждую итерацию можно описать следующим образом: Алгоритм DES. Шифрование Li = Ri-1 Ri = Li-1F(Ri-1, Ki) Где обозначает операциюXOR. Таким образом, выход левой половины Li равен входу правой половины Ri-1. Выход правой половины Ri является результатом применения операции XOR к Li-1 и функции F, зависящей от Ri-1 и Ki.

31 31 Алгоритм DES. Шифрование Рассмотрим функцию F более подробно. Ri, которое подается на вход функции F, имеет длину 32 бита. Вначале Ri расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Расширение происходит следующим образом. 32 бита разбиваются на группы по 4 бита и затем расширяются до 6 битов, присоединяя крайние биты из двух соседних групп. Например, если часть входного сообщения... efgh ijkl mnop... то в результате расширения получается сообщение... defghi hijklm lmnopq... После этого для полученного 48-битного значения выполняется операция XOR с 48-битным подключом Ki. Затем полученное 48-битное значение подается на вход функции подстановки, результатом которой является 32-битное значение.

32 32 Алгоритм DES. Шифрование Подстановка состоит из восьми S-boxes, каждый из которых на входе получает 6 бит, а на выходе создает 4 бита. Эти преобразования определяются специальными таблицами. Первый и последний биты входного значения S-box определяют номер строки в таблице, средние 4 бита определяют номер столбца. Пересечение строки и столбца определяет 4-битный выход. Например, если входом является , то номер строки равен 01 (строка 1) и номер столбца равен 1101 (столбец 13). Значение в строке 1 и столбце 13 равно 5, т.е. выходом является Далее полученное 32-битное значение обрабатывается с помощью перестановки Р, целью которой является максимальное переупорядочивание битов, чтобы в следующем раунде шифрования с большой вероятностью каждый бит обрабатывался другим S-box.

33 33 Алгоритм DES. Создание подключей Ключ для отдельного раунда Ki состоит из 48 битов. Ключи Ki получаются по следующему алгоритму. Для 56-битного ключа, используемого на входе алгоритма, вначале выполняется перестановка в соответствии с таблицей Permuted Choice 1 (РС-1). Полученный 56-битный ключ разделяется на две 28-битные части, обозначаемые как C0 и D0 соответственно. На каждом раунде Ci и Di независимо циклически сдвигаются влево на 1 или 2 бита, в зависимости от номера раунда. Полученные значения являются входом следующего раунда. Они также представляют собой вход в Permuted Choice 2 (РС-2), который создает 48-битное выходное значение, являющееся входом функции F(Ri-1, Ki). Создание подключей

34 34 Алгоритм DES. Дешифрование Процесс дешифрования аналогичен процессу шифрования. На входе алгоритма используется зашифрованный текст, но ключи Ki используются в обратной последовательности. K16 используется на первом раунде, K1 используется на последнем раунде. Пусть выходом i- ого раунда шифрования будет Li||Ri. Тогда соответствующий вход (16-i)- ого раунда дешифрования будет Ri||Li. После последнего раунда процесса расшифрования две половины выхода меняются местами так, чтобы вход заключительной перестановки IP-1 был R16||L16. Выходом этой стадии является незашифрованный текст. Дешифрование

35 35 Алгоритм DES. Дешифрование Проверим корректность процесса дешифрования. Возьмем зашифрованный текст и ключ и используем их в качестве входа в алгоритм. На первом шаге выполним начальную перестановку IP и получим 64-битное значение Ld 0 ||Rd 0. Известно, что IP и IP-1 взаимнообратны. Следовательно Ld 0 ||Rd 0 = IP (зашифрованный текст) Зашифрованный текст = IP-1(R 16 ||L 16 ) Ld 0 ||Rd 0 = IP(IP-1(R 16 ||L 16 )) = R 16 ||L 16 Таким образом, вход первого раунда процесса дешифрования эквивалентен 32-битному выходу 16-ого раунда процесса шифрования, у которого левая и правая части записаны в обратном порядке.

36 36 Алгоритм DES. Дешифрование Теперь мы должны показать, что выход первого раунда процесса дешифрования эквивалентен 32-битному входу 16-ого раунда процесса шифрования. Во-первых, рассмотрим процесс шифрования. Мы видим,что L 16 = R 15 F(R 15, K 16 ) При дешифровании: L d 1 = R d 0 = L 16 = R 15 R d 1 = L d 0 F(R d 0, K 16 ) = = R 16 F(R d 0, K 16 ) = = (L15F(R 15, K 16 ))

37 37 Алгоритм DES. Дешифрование XORимеет следующие свойства: (A B) C = A (B C) D D = 0 E 0 = E Таким образом, мы имеем L d 1 = R 15 и R d 1 = L 15. Следовательно, выход первого раунда процесса дешифрования есть L 15 ||R 15, который является перестановкой входа 16-го раунда шифрования. Легко показать, что данное соответствие выполняется все 16 раундов. Мы можем описать этот процесс в общих терминах. Для i-ого раунда шифрующего алгоритма: Li = Ri-1 Ri = Li-1F(Ri-1, Ki)

38 38 Алгоритм DES. Дешифрование Эти равенства можно записать по-другому: Ri-1 = Li Li-1 = RiF(Ri-1, Ki) = RiF(Li, Ki) Таким образом, мы описали входы i-ого раунда как функцию выходов. Выход последней стадии процесса дешифрования есть R0||L0. Чтобы входом IP -1 стадии было R0||L0, необходимо поменять местами левую и правую части. Но IP -1 (R 0 ||L 0 ) = IP -1 (IP (незашифрованный текст)) = незашифрованный текст Т.е. получаем незашифрованный текст, что и демонстрирует возможность дешифрования DES.

39 39 Алгоритм DES. Проблемы Проблемы DES Так как длина ключа равна 56 битам, существует 256 возможных ключей. На сегодня такая длина ключа недостаточна, поскольку допускает успешное применение лобовых атак. Альтернативой DES можно считать тройной DES, IDEA, а также алгоритм Rijndael, принятый в качестве нового стандарта на алгоритмы симметричного шифрования. Также без ответа пока остается вопрос, возможен ли криптоанализ с использованием существующих характеристик алгоритма DES. Основой алгоритма являются восемь таблиц подстановки, или S- boxes, которые применяются в каждой итерации. Существует опасность, что эти S-boxes конструировались таким образом, что криптоанализ возможен для взломщика, который знает слабые места S-boxes. В течение многих лет обсуждалось как стандартное, так и неожиданное поведение S-boxes, но все-таки никому не удалось обнаружить их фатально слабые места.

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

41 41 Алгоритм DES Недостатки двойного DES Простейший способ увеличить длину ключа состоит в повторном применении DES с двумя разными ключами. Используя незашифрованное сообщение P и два ключа K1 и K2, зашифрованное сообщение С можно получить следующим образом: C = E k2 [E k1 [P]] Для дешифрования требуется, чтобы два ключа применялись в обратном порядке: P = D k1 [D k2 [C]] В этом случае длина ключа равна 56 * 2 = 112 бит.

42 42 Алгоритм DES Атака "встреча посередине" Для приведенного выше алгоритма двойного DES существует так называемая атака "встреча посередине". Она основана на следующем свойстве алгоритма. Мы имеем С = E k2 [E k1 [P]] Тогда X = E k1 [P] = D k2 [C]. Атака состоит в следующем. Требуется, чтобы атакующий знал хотя бы одну пару незашифрованный текст и соответствующий ему зашифрованный текст: (Р, С). В этом случае, во-первых, шифруется Р для всех возможных 256 значений K1. Этот результат запоминается в таблице, и затем таблица упорядочивается по значению Х. Следующий шаг состоит в дешифровании С, с применением всех возможных 256 значений K2. Для каждого выполненного дешифрования ищется равное ему значение в первой таблице. Если соответствующее значение найдено, то считается, что эти ключи могут быть правильными, и они проверяются для следующей известной пары незашифрованный текст, зашифрованный текст.

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

44 44 Алгоритм DES Тройной DES с двумя ключами Очевидное противодействие атаке "встреча посередине" состоит в использовании третьей стадии шифрования с тремя различными ключами. Это поднимает стоимость лобовой атаки до 2 168, которая на сегодняшний день считается выше практических возможностей. Но при этом длина ключа равна 56 * 3 = 168 бит, что иногда бывает громоздко. В качестве альтернативы предлагается метод тройного шифрования, использующий только два ключа. В этом случае выполняется последовательность зашифрование-расшифрование- зашифрование (EDE). C = E K1 [D K2 [E K1 [P]]]

45 45 Алгоритм DES Рис Шифрование тройным DES Рис Дешифрование тройным DES

46 46 Алгоритм DES Не имеет большого значения, что используется на второй стадии: шифрование или дешифрование. В случае использования дешифрования существует только то преимущество, что можно тройной DES свести к обычному одиночному DES, используя K 1 = K 2 : C = E K1 [D K1 [E K1 [P]]] = E K1 [P] Тройной DES является достаточно популярной альтернативой DES и используется при управлении ключами в стандартах ANSI X9.17 и ISO 8732 и в PEM (Privacy Enhanced Mail). Известных криптографических атак на тройной DES не существует. Цена подбора ключа в тройном DES равна

47 47