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

Чтобы воспользоваться алгоритмом DES для решения разнообразных криптографических задач, разработаны четыре рабочих режима:

· электронная кодовая книга ECB(Electronic Code Book);

· сцепление блоков шифра CBC (Cipher Block Chaining);

· обратная связь по шифртексту CFB (Cipher Feed Back);

· обратная связь по выходу OFB (Output Feed Back).

Режим "Электронная кодовая книга"

Длинный файл разбивают на 64-битовые отрезки (блоки) по 8 байтов. Каждый из этих блоков шифруют независимо с использованием одного и того же ключа шифрования (рис.3.6).

Основное достоинство – простота реализации. Недостаток – относительно слабая устойчивость против квалифицированных криптоаналитиков. Из-за фиксированного характера шифрования при ограниченной длине блока 64 бита возможно проведение криптоанализа "со словарем". Блок такого размера может повториться в сообщении вследствие большой избыточности в тексте на естественном языке.

Рисунок 3.6 – Схема алгоритма DES в режиме электронной кодовой книги

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

Режим "Сцепление блоков шифра"

В этом режиме исходный файл М разбивается на 64-битовые блоки: М = М 1 М 2 ...М n . Первый блок М 1 складывается по модулю 2 с 64‑битовым начальным вектором IV, который меняется ежедневно и держится в секрете (рис.3.7). Полученная сумма затем шифруется с использованием ключа DES, известного и отправителю, и получателю информации. Полученный 64-битовый шифр С 1 складывается по модулю 2 со вторым блоком текста, результат шифруется и получается второй 64‑битовый шифр С 2 , и т.д. Процедура повторяется до тех пор, пока не будут обработаны все блоки текста.

Таким образом, для всех i = 1…n (n – число блоков) результат шифрования С i определяется следующим образом: С i =

DES (М i  C i –1), где С 0 = IV – начальное значение шифра, равное начальному вектору (вектору инициализации).

Очевидно, что последний 64-битовый блок шифртекста является функцией секретного ключа, начального вектора и каждого бита

Рисунок 3.7 – Схема алгоритма DES в режиме сцепления блоков шифра

открытого текста независимо от его длины. Этот блок шифртекста называют кодом аутентификации сообщения (КАС).


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

Достоинство данного режима в том, что он не позволяет накапливаться ошибкам при передаче.

Блок М i является функцией только С i –1 и С i . Поэтому ошибка при передаче приведет к потере только двух блоков исходно-го текста.

Режим "Обратная связь по шифру"

В этом режиме размер блока может отличаться от 64 бит (рис.3.8). Файл, подлежащий шифрованию (расшифрованию), считывается последовательными блоками длиной k битов (k=1…64).

Входной блок (64-битовый регистр сдвига) вначале содержит вектор инициализации, выровненный по правому краю.

Предположим, что в результате разбиения на блоки мы получили n блоков длинойk битов каждый (остаток дописывается нулями или пробелами). Тогда для любого i=1…n блок шифр-текста

С i = M i  P i –1 ,

где Р i–1 обозначает k старших битов предыдущего зашифрованного блока.

Обновление сдвигового регистра осуществляется путем удаления его старших k битов и записи С i в регистр. Восстановление зашифрованных данных также выполняется относительно просто: Р i –1 и С i вычисляются аналогичным образом и

М i = С i  Р i –1 .


Рисунок 3.8 – Схема алгоритма DES в режиме обратной связи по шифртексту

Режим "Обратная связь по выходу"

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

М = М 1 М 2 ... M n .

Для всех i = 1… n

С i = M i  P i ,

где Р i – старшие k битов операции DES (С i –1).

Отличие от режима обратной связи по шифртексту состоит в методе обновления сдвигового регистра.

Это осуществляется путем отбрасывания старших k битов и дописывания справа Р i .

Рисунок 3.9 – Схема алгоритма DES в режиме обратной связи по выходу

3.3. ОбластипримененияалгоритмаDES

Каждому из рассмотренных режимов (ЕСВ, СВС, CFB, OFB) свойственны свои достоинства и недостатки, что обусловливает области их применения.

Режим ЕСВ хорошо подходит для шифрования ключей: режим CFB, как правило, предназначается для шифрования отдельных символов, а режим OFB нередко применяется для шифрования в спутниковых системах связи.

Режимы СВС и CFB пригодны для аутентификации данных. Эти режимы позволяют использовать алгоритм DES для:

· интерактивного шифрования при обмене данными между терминалом и главной ЭВМ;

· шифрования криптографического ключа в практике автоматизированного распространения ключей;

· шифрования файлов, почтовых отправлений, данных спутников и других практических задач.

Первоначально стандарт DES предназначался для шифрования и расшифрования данных ЭВМ. Однако его применение было обобщено и на аутентификацию.

В системах автоматической обработки данных человек не в состоянии просмотреть данные, чтобы установить, не внесены ли в них какие-либо изменения. При огромных объемах данных, проходящих в современных системах обработки, просмотр занял бы слишком много времени. К тому же избыточность данных может оказаться недостаточной для обнаружения ошибок. Даже в тех случаях, когда просмотр человеком возможен, данные могут быть изменены таким образом, что обнаружить эти изменения человеку очень трудно. Например, "do" может быть заменено на "do not", "$1900" – на "$9100". Без дополнительной информации человек при просмотре может легко принять измененные данные за подлинные. Такие опасности могут существовать даже при использовании шифрования данных. Поэтому желательно иметь автоматическое средство обнаружения преднамеренных и непреднамеренных изменений данных.

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

Этот процесс описывает стандарт для аутентификации данных ЭВМ (FIPS 113). Суть стандарта состоит в том, что данные зашифровываются в режиме обратной связи по шифртексту (режим CFB) или в режиме сцепления блоков шифра (режим СВС), в результате чего получается окончательный блок шифра, представляющий собой функцию всех разрядов открытого текста. После этого сообщение, которое содержит открытый текст, может быть передано с использованием вычисленного окончательного блока шифра, служащего в качестве криптографической контрольной суммы.

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

му тексту.

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

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

С помощью алгоритма DES можно также зашифровать файлы ЭВМ для их хранения.

Одним из наиболее важных применений алгоритма DES является защита сообщений электронной системы платежей (ЭСП) при операциях с широкой клиентурой и между банками .

Алгоритм DES реализуется в банковских автоматах, терминалах в торговых точках, автоматизированных рабочих местах и главных ЭВМ. Диапазон защищаемых им данных весьма широк – от оплат $50 до переводов на многие миллионы долларов. Гибкость основного алгоритма DES позволяет использовать его в самых разнообразных областях применения электронной системы платежей.

симметричными ключами .

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

После публикации эскиз строго критиковался по двум причинам. Первая: критиковалась сомнительно маленькая длина ключа (только 56 битов), что могло сделать шифр уязвимым к атаке "грубой силой". Вторая причина: критики были обеспокоены некоторым скрытым построением внутренней структуры DES .

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

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

Общие положения

Как показано на рис. 8.1. , DES - блочный шифр .


Рис. 8.1.

На стороне шифрования DES принимает 64 -битовый исходный текст и порождает 64 -битовый зашифрованный текст; на стороне дешифрования DES принимает 64 -битовый зашифрованный текст и порождает 64 -битовый исходный текст. На обеих сторонах для шифрования и дешифрования применяется один и тот же 56 -битовый ключ.

8.2. Структура DES

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

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

Рисунок 8.3 показывает начальные и конечные перестановки (P -блоки). Каждая из перестановок принимает 64 -битовый вход и переставляет его элементы по заданному правилу. Мы показали только небольшое число входных портов и соответствующих выходных портов. Эти перестановки - прямые перестановки без ключей, которые инверсны друг другу. Например, в начальной перестановке 58 -й бит на входе переходит в первый бит на выходе. Аналогично, в конечной перестановке первый входной бит переходит в 58 -й бит на выходе. Другими словами, если между этими двумя перестановками не существует раунда, 58 -й бит, поступивший на вход устройства начальной перестановки, будет доставлен на 58 -й выход финальной перестановкой.


Рис. 8.2.


Рис. 8.3.

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

Таблица 8.1. Таблица начальных и конечных перестановок
Начальные перестановки Конечные перестановки
58 50 42 34 26 18 10 02 40 08 48 16 56 24 64 32
60 52 44 36 28 20 12 04 39 07 47 15 55 23 63 31
62 54 46 38 30 22 14 06 38 06 46 14 54 22 62 30
64 56 48 40 32 24 16 08 37 05 45 13 53 21 61 29
57 49 41 33 25 17 09 01 36 04 44 12 52 20 60 28
59 51 43 35 27 19 11 03 35 03 43 11 51 19 59 27
61 53 45 37 29 21 13 05 34 02 42 10 50 18 58 26
63 55 47 39 31 23 15 07 33 01 41 09 49 17 57 25

Эти две перестановки не имеют никакого значения для криптографии в

Алгоритм DES

Основные достоинства алгоритма DES:

· используется только один ключ длиной 56 битов;

· зашифровав сообщение с помощью одного пакета, для расшифровки вы можете использовать любой другой;

· относительная простота алгоритма обеспечивает высокую скорость обработки информации;

· достаточно высокая стойкость алгоритма.

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

Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, обратной перестановки битов (рис.1).

Необходимо сразу же отметить, что ВСЕ таблицы, приведенные в данной статье, являются СТАНДАРТНЫМИ, а следовательно должны включаться в вашу реализацию алгоритма в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. Структура алгоритма DES приведена на рис.2.

Рис.2. Структура алгоритма шифрования DES

Пусть из файла считан очередной 8-байтовый блок T, который преобразуется с помощью матрицы начальной перестановки IP (табл.1) следующим образом: бит 58 блока T становится битом 1, бит 50 - битом 2 и т.д., что даст в результате: T(0) = IP(T).

Полученная последовательность битов T(0) разделяется на две последовательности по 32 бита каждая: L(0) - левые или старшие биты, R(0) - правые или младшие биты.

Таблица 1: Матрица начальной перестановки IP

58 50 42 34 26 18 10 02

60 52 44 36 28 20 12 04

62 54 46 38 30 22 14 06

64 56 48 40 32 24 16 08

57 49 41 33 25 17 09 01

59 51 43 35 27 19 11 03

61 53 45 37 29 21 13 05

63 55 47 39 31 23 15 07

Затем выполняется шифрование, состоящее из 16 итераций. Результат i-й итерации описывается следующими формулами:

R(i) = L(i-1) xor f(R(i-1), K(i)) ,

где xor - операция ИСКЛЮЧАЮЩЕЕ ИЛИ.

Функция f называется функцией шифрования. Ее аргументы - это 32-битовая последовательность R(i-1), полученная на (i-1)-ой итерации, и 48-битовый ключ K(i), который является результатом преобразования 64-битового ключа K. Подробно функция шифрования и алгоритм получения ключей К(i) описаны ниже.

На 16-й итерации получают последовательности R(16) и L(16) (без перестановки), которые конкатенируют в 64-битовую последовательность R(16)L(16).

Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP -1 (табл.2).

Таблица 2: Матрица обратной перестановки IP -1

40 08 48 16 56 24 64 32

39 07 47 15 55 23 63 31

38 06 46 14 54 22 62 30

37 05 45 13 53 21 61 29

36 04 44 12 52 20 60 28

35 03 43 11 51 19 59 27

34 02 42 10 50 18 58 26

33 01 41 09 49 17 57 25

Матрицы IP -1 и IP соотносятся следующим образом: значение 1-го элемента матрицы IP -1 равно 40, а значение 40-го элемента матрицы IP равно 1, значение 2-го элемента матрицы IP -1 равно 8, а значение 8-го элемента матрицы IP равно 2 и т.д.

Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP-1, а затем над последовательностью бит R(16)L(16) выполняются те же действия, что и в процессе шифрования, но в обратном порядке.

Итеративный процесс расшифрования может быть описан следующими формулами:

R(i-1) = L(i), i = 1, 2, ..., 16;

L(i-1) = R(i) xor f(L(i), K(i)), i = 1, 2, ..., 16 .

На 16-й итерации получают последовательности L(0) и R(0), которые конкатенируют в 64-битовую последовательность L(0)R(0).

Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP. Результат такой перестановки - исходная 64-битовая последовательность.

Теперь рассмотрим функцию шифрования f(R(i-1),K(i)). Схематически она показана на рис. 3.


Рис.3. Вычисление функции f(R(i-1), K(i))

Для вычисления значения функции f используются следующие функции-матрицы:

Е - расширение 32-битовой последовательности до 48-битовой,

S1, S2, ... , S8 - преобразование 6-битового блока в 4-битовый,

Р - перестановка бит в 32-битовой последовательности.

Функция расширения Е определяется табл.3. В соответствии с этой таблицей первые 3 бита Е(R(i-1)) - это биты 32, 1 и 2, а последние - 31, 32 и 1.

Таблица 3:Функция расширения E

32 01 02 03 04 05

04 05 06 07 08 09

08 09 10 11 12 13

12 13 14 15 16 17

16 17 18 19 20 21

20 21 22 23 24 25

24 25 26 27 28 29

28 29 30 31 32 01

Результат функции Е(R(i-1)) есть 48-битовая последовательность, которая складывается по модулю 2 (операция xor) с 48-битовым ключом К(i). Получается 48-битовая последовательность, которая разбивается на восемь 6-битовых блоков B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). То есть:

E(R(i-1)) xor K(i) = B(1)B(2)...B(8) .

Функции S1, S2, ... , S8 определяются табл.4.

Таблица 4

К табл.4. требуются дополнительные пояснения. Пусть на вход функции-матрицы Sj поступает 6-битовый блок B(j) = b1b2b3b4b5b6, тогда двухбитовое число b1b6 указывает номер строки матрицы, а b2b3b4b5 - номер столбца. Результатом Sj(B(j)) будет 4-битовый элемент, расположенный на пересечении указанных строки и столбца.

Например, В(1)=011011. Тогда S1(В(1)) расположен на пересечении строки 1 и столбца 13. В столбце 13 строки 1 задано значение 5. Значит, S1(011011)=0101.

Применив операцию выбора к каждому из 6-битовых блоков B(1), B(2), ..., B(8), получаем 32-битовую последовательность S1(B(1))S2(B(2))S3(B(3))...S8(B(8)).

Наконец, для получения результата функции шифрования надо переставить биты этой последовательности. Для этого применяется функция перестановки P (табл.5). Во входной последовательности биты перестанавливаются так, чтобы бит 16 стал битом 1, а бит 7 - битом 2 и т.д.

Таблица 5:Функция перестановки P

Такимобразом,

f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))

Чтобы завершить описание алгоритма шифрования данных, осталось привести алгоритм получения 48-битовых ключей К(i), i=1...16. На каждой итерации используется новое значение ключа K(i), которое вычисляется из начального ключа K. K представляет собой 64-битовый блок с восемью битами контроля по четности, расположенными в позициях 8,16,24,32,40,48,56,64.

Для удаления контрольных битов и перестановки остальных используется функция G первоначальной подготовки ключа (табл.6).

Таблица 6

Матрица G первоначальной подготовки ключа

57 49 41 33 25 17 09

01 58 50 42 34 26 18

10 02 59 51 43 35 27

19 11 03 60 52 44 36

63 55 47 39 31 23 15

07 62 54 46 38 30 22

14 06 61 53 45 37 29

21 13 05 28 20 12 04

Результат преобразования G(K) разбивается на два 28-битовых блока C(0) и D(0), причем C(0) будет состоять из битов 57, 49, ..., 44, 36 ключа K, а D(0) будет состоять из битов 63, 55, ..., 12, 4 ключа K. После определения C(0) и D(0) рекурсивно определяются C(i) и D(i), i=1...16. Для этого применяют циклический сдвиг влево на один или два бита в зависимости от номера итерации, как показано в табл.7.

Таблица 7

Таблица сдвигов для вычисления ключа

Номер итерации Сдвиг (бит)
01 1
02 1
03 2
04 2
05 2
06 2
07 2
08 2
09 1
10 2
11 2
12 2
13 2
14 2
15 2
16 1

Полученное значение вновь "перемешивается" в соответствии с матрицей H (табл.8).

Таблица 8:Матрица H завершающей обработки ключа

14 17 11 24 01 05

03 28 15 06 21 10

23 19 12 04 26 08

16 07 27 20 13 02

41 52 31 37 47 55

30 40 51 45 33 48

44 49 39 56 34 53

46 42 50 36 29 32

Ключ K(i) будет состоять из битов 14, 17, ..., 29, 32 последовательности C(i)D(i). Таким образом:

K(i) = H(C(i)D(i))

Блок-схема алгоритма вычисления ключа приведена на рис.4.

Рис.4. Блок-схема алгоритма вычисления ключа K(i)

Восстановление исходного текста осуществляется по этому алгоритму, но вначале вы используете ключ

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

Режимы работы алгоритма DES

Для наиболее полного удовлетворения всем требованиям, предъявляемым к коммерческим системам шифрования, реализованы несколько режимов работы алгоритма DES. Наиболее широкое распространение получили режимы:

· электронный шифроблокнот (Electronic Codebook) - ECB;

· цепочкацифровыхблоков (Cipher Block Chaining) - CBC;

· цифровая обратная связь (Cipher Feedback) - CFB;

· внешняя обратная связь (Output Feedback) - OFB.

В этом режиме исходный файл M разбивается на 64-битовые блоки (по 8 байтов): M = M(1)M(2)...M(n). Каждый из этих блоков кодируется независимо с использованием одного и того же ключа шифрования (рис.5). Основное достоинство этого алгоритма - простота реализации. Недостаток - относительно слабая устойчивость против квалифицированных криптоаналитиков.

  • Tutorial

Привет, %username%!
Многим известно, что стандартом по умолчанию в области симметричного шифрования долгое время считался алгоритм DES. Первая успешная атака на этот неубиваемый алгоритм была опубликована в 1993 году, спустя 16 лет после принятия его в качестве стандарта. Метод, который автор назвал линейным криптоанализом, при наличии 2 47 пар открытых/зашифрованных текстов, позволяет вскрыть секретный ключ шифра DES за 2 43 операций.
Под катом я попытаюсь кратко изложить основные моменты этой атаки.

Линейный криптоанализ

Линейный криптоанализ - особый род атаки на симметричные шифры, направленный на восстановление неизвестного ключа шифрования, по известным открытым сообщениям и соответствующим им шифртекстам.

В общем случае атака на основе линейного криптоанализа сводится к следующим условиям. Злоумышленник обладает большим количеством пар открытый/зашифрованный текст, полученных с использованием одного и того же ключа шифрования K. Цель атакующего восстановить частично или полностью ключ K.

В первую очередь злоумышленник производит исследование шифра и находит т.н. статистический аналог, т.е. уравнение следующего вида, выполняющееся с вероятностью P ≠ 1/2 для произвольной пары открытый/закрытый текст и фиксированного ключа:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1) ,
где P n , C n , K n - n-ые биты текста, шифртекста и ключа.
После того как подобное уравнение будет найдено атакующий может восстановить 1 бит информации о ключе, используя следующий алгоритм

Алгоритм 1
Пусть T - количество текстов, для которых левая часть уравнения (1) равняется 0, тогда
Если T>N/2, где N - число известных открытых текстов.
Предположить, что K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (когда P>1/2) или 1 (когда P<1/2).
Иначе
Предположить, что K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (когда P>1/2) или 0 (когда P<1/2).
Очевидно, что успех алгоритма напрямую зависит от значения |P-1/2| и от количества доступных пар открытый/закрытый текст N. Чем больше вероятность P равенства (1) отличается от 1/2, тем меньше количество открытых текстов N необходимо для атаки.

Возникают две проблемы, которые необходимо решить для успешной реализации атаки:

  • Как найти эффективное уравнение вида (1).
  • Как с помощью такого уравнения получить больше одного бита информации о ключе.
Рассмотрим решение этих вопросов на примере шифра DES.

Описание DES

Но для начала кратко опишем работу алгоритма. О DES сказано уже достаточно. Полное описание шифра можно найти на Википедии . Однако для дальнейшего объяснения атаки нам потребуется ряд определений которые лучше ввести заранее.

Итак, DES это блочный шифр, основанный на сети Фейстеля . Шифр имеет размер блока 64 бита и размер ключа 56 бит. Рассмотрим схему шифрования алгоритма DES.

Как видно из рисунка, при шифровании над текстом производятся следующие операции:

  1. Начальная перестановка бит. На этом этапе биты входного блока перемешиваются в определенном порядке.
  2. После этого перемешанные биты разбиваются на две половины, которые поступают на вход функции Фейстеля. Для стандартного DES сеть Фейстеля включает 16 раундов, но существуют и другие варианты алгоритма.
  3. Два блока, полученных на последнем раунде преобразования объединяются и над полученным блоком производится еще одна перестановка.

На каждом раунде сети Фейстеля 32 младших бита сообщения проходят через функцию f:

Рассмотрим операции, выполняющиеся на этом этапе:

  1. Входной блок проходит через функцию расширения E, которая преобразует 32-битный блок в блок длиной 48 бит.
  2. Полученный блок складывается с раундовым ключом K i .
  3. Результат предыдущего шага разбивается на 8 блоков по 6 бит каждый.
  4. Каждый из полученных блоков B i проходит через функцию подстановки S-Box i , которая заменяет 6-битную последовательность, 4-битным блоком.
  5. Полученный в результате 32-битный блок проходит через перестановку P и возвращается в качестве результата функции f.

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

Анализ S блоков

Каждый S-блок принимает на вход 6-битную последовательность, и для каждой такой последовательности возвращается фиксированное 4-битное значение. Т.е. имеется всего 64 варианта входных и выходных данных. Наша задача показать взаимосвязь между входными и выходными данными S блоков. К примеру, для третьего S-блока шифра DES, 3-й бит входной последовательности равен 3-му биту выходной последовательности в 38 случаях из 64. Следовательно, мы нашли следующий статистический аналог для третьего S-блока:
S 3 (x) = x, который выполняется с вероятность P=38/64.
Обе части уравнения представляют 1 бит информации. Поэтому в случае если бы левая и правая части были независимы друг от друга, уравнение должно было бы выполняться с вероятностью равной 1/2. Таким образом, мы только что продемонстрировали связь между входными и выходными данными 3-го S-блока алгоритма DES.

Рассмотрим как можно найти статистический аналог S-блока в общем случае.

Для S-блока S a , 1 ≤ α ≤ 63 и 1 ≤ β ≤ 15, значение NS a (α, β) описывает сколько раз из 64 возможных XOR входных бит S a наложенных на биты α равны XOR выходных бит, наложенных на биты β, т.е.:
где символ - логическое И.
Значения α и β, для которых NS a (α, β) сильнее всего отличается от 32, описывают самый эффективный статистический аналог S-блока S a .

Наиболее эффективный аналог был найден в 5-ом S-блоке шифра DES для α = 16 и β = 15 NS 5 (16, 15)=12. Это значит, что справедливо следующее уравнение: Z=Y ⊕ Y ⊕ Y ⊕ Y, где Z - входная последовательность S-блока, а Y - выходная последовательность.
Или с учетом того, что в алгоритме DES перед входом в S-блок данные складываются по модулю 2 с раундовым ключом, т.е. Z = X ⊕ K получаем
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, где X и Y - входные и выходные данные функции f без учета перестановок.
Полученное уравнение выполняется на всех раундах алгоритма DES с одинаковой вероятностью P=12/64.
На следующей таблице приведен список эффективных, т.е. имеющих наибольшее отклонение от P=1/2, статистических аналогов для каждого s-блока алгоритма DES.

Построение статистических аналогов для нескольких раундов DES

Покажем теперь каким образом можно объединить статистические аналоги нескольких раундов DES и в итоге получить статистический аналог для всего шифра.
Для этого рассмотрим трехраундовую версию алгоритма:

Применим эффективный статистический аналог 5-го s-блока для вычисления определенных бит значения X(2).
Мы знаем что с вероятностью 12/64 в f-функции выполняется равенство X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, где X - второй входной бит 5-го S-блока, он по сути является 26-м битом последовательности, полученной после расширения входных бит. Анализируя функцию расширения можно установить что на месте 26 бита оказывается 17-й бит последовательности X(1).
Аналогичным образом, Y,…, Y по сути являются 17-м, 18-м, 19-м и 20-м битом последовательности полученной до перестановки P. Исследовав перестановку P, получаем что биты Y,…, Y на самом деле являются битами Y(1), Y(1), Y(1), Y(1).
Бит ключа K вовлеченный в уравнения является 26 битом подключа первого раунда K1 и тогда статистический аналог приобретает следующую форму:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1 .
Следовательно, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) (2) с вероятностью P=12/64.
Зная 3, 8, 14, 25 биты последовательности Y(1) можно найти 3, 8, 14, 25 биты последовательности X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) или с учетом уравнения (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) с вероятностью 12/64.

Найдем подобное выражение используя последний раунд. На этот раз мы имеем уравнение
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) .
Так как
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
получаем, что
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ X(3) ⊕ K3 (4) с вероятностью 12/64.

Приравняв правые части уравнений (3) и (4) получаем
СL ⊕ СL ⊕ СL ⊕ СL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 с вероятностью (12/64) 2 +(1-12/64) 2 .
С учетом того, что X(1) = PR и X(3) = CR получаем статистический аналог
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5) ,
который выполняется с вероятностью (12/64) 2 +(1-12/64) 2 =0.7.
Описанный выше статистический аналог можно представить графически следующим образом (биты на рисунке пронумерованы справа налево и начиная с нуля):

Все биты в левой части уравнения известны атакующему, следовательно он может применить алгоритм 1 и узнать значение K1 ⊕ K3. Покажем как с помощью данного статистического аналога можно вскрыть не 1, а 12 бит ключа шифрования K.

Атака на DES с известным открытым текстом

Приведем способ с помощью которого можно расширить атаку и получить сразу 6 бит подключа первого раунда.
Составляя уравнение (5) мы принимали во внимание тот факт, что нам неизвестно значение F1(PR, K1). Поэтому мы использовали его статистический аналог K1 ⊕ PR.
Вернем вместо выражения K1 ⊕ PR значение F1(PR, K1) и получим следующее уравнение:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , которое будет выполняться с вероятностью 12/64. Вероятность изменилась так как мы оставили только статистический аналог из третьего раунда, все остальные значения фиксированы.

Выше мы уже определили, что на значение F1(PR, K1) оказывают влияние входные биты 5-го S-блока, а именно биты ключа K1 и биты блока PR. Покажем каким образом обладая только набором открытых/закрытых текстов можно восстановить значение K1. Для этого воспользуемся алгоритмом 2.

Алгоритм 2
Пусть N - количество известных перед атакой пар открытый/закрытый текст. Тогда для вскрытия ключа необходимо проделать следующие шаги.
For (i=0; i<64; i++) do
{
For(j=0; j {
if(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) then
T i =T i +1
}
}
В качестве вероятной последовательности K1 принимается такое значение i, при котором выражение |T i -N/2| имеет максимальное значение.

При достаточном количестве известных открытых текстов алгоритм будет с большой вероятностью возвращать корректное значение шести бит подключа первого раунда K1. Объясняется это тем, что в случае если переменная i не равна K1, тогда значение функции F1(PR j , K) будет случайным и количество уравнений для такого значения i, при котором левая часть равна нулю будет стремиться к N/2. В случае же если подключ угадан верно, левая часть будет с вероятностью 12/64 равна фиксированному биту K3. Т.е. будет наблюдаться значительное отклонение от N/2.

Получив 6 бит подключа K1, можно аналогичным образом вскрыть 6 бит подключа K3. Все что для этого нужно, это заменить в уравнении (6) C на P и K1 на K3:
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1 .
Алгоритм 2 возвратит корректное значение K3 потому что процесс расшифровки алгоритма DES идентичен процессу шифрования, просто последовательность ключей меняется местами. Так на первом раунде расшифрования используется ключ K3, а на последнем ключ K1.

Получив по 6 бит подключей K1 и K3 злоумышленник восстанавливает 12 бит общего ключа шифра K, т.к. раундовые ключи являются обычной перестановкой ключа K. Количество открытых текстов необходимых для успешной атаки зависит от вероятности статистического аналога. Для вскрытия 12 бит ключа 3-раундового DES достаточно 100 пар открытых/закрытых текстов. Для вскрытия 12 бит ключа 16-раундового DES потребуется порядка 2 44 пар текстов. Остальные 44 бита ключа вскрываются обычным перебором.

DES (Data Encryption Standart) - Симметричный алгоритм шифрования, в котором один ключ используется, как для шифрования, так и для расшифрования данных. DES разработан фирмой IBM и утвержден правительством США в 1977 году как официальный стандарт (FTPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:
  • режим электронной кодовой книги (ECB - Electronic Code Book),
  • режим сцепления блоков (СВС - Cipher Block Chaining),
  • режим обратной связи по шифротексту (CFB - Cipher Feed Back),
  • режим обратной связи по выходу (OFB - Output Feed Back).

    Блочный шифр

    Входными данными для блочного шифра служат блок размером n бит и k-битный ключ. На выходе, после применения шифрующего преобразования, получается n-битный зашифрованный блок, причём незначительные различия входных данных как правило приводят к существенному изменению результата. Блочные шифры реализуются путём многократного применения к блокам исходного текста некоторых базовых преобразований.
    Базовые преобразования:
  • Сложное преобразование на одной локальной части блока.
  • Простое преобразование между частями блока. Так как преобразование производится поблочно, как отдельный шаг требуется разделение исходных данных на блоки необходимого размера. При этом вне зависимости от формата исходных данных, будь то текстовые документы, изображения или другие файлы, они должны быть интерпретированы в бинарный вид и только после этого разбиты на блоки. Все вышеперечисленное может осуществляться программными, так и аппаратами средствами.

    Преобразования Сетью Фейстеля

    Это преобразование над векторами (блоками) представляющими собой левую и правую половины регистра сдвига. В алгоритме DES используются прямое преобразование сетью Фейстеля в шифровании (см. Рис.1) и обратное преобразование сетью Фейстеля в расшифрование (см. Рис.2).

    Схема шифрования алгоритма DES


    Исходный текст - блок 64 бит.
    Шифрованный текст - блок 64 бит.

    Процесс шифрования состоит в начальной перестановке, 16 циклах шифрования и конечной перестановке.
    Рассмотрим подробную схему алгоритма DES:
    L i R i =1,2\ldots.левая и правая половины 64-битового блока L i R i
    k i - 48 битовые ключи
    f - функция шифрования
    IP - начальная перестановка
    IP -1 - конечная перестановка. По таблице первые 3 бита результирующего блока IP(T) после начальной перестановки IP являются битами 58, 50, 42 входного блока Т, а его 3 последние бита являются битами 23, 15, 7 входного блока. Дальше 64-битовой блок IP(T) участвует в 16-циклах преобразования Фейстеля.

    16 циклов преобразования Фейстеля:

    Разбить IP(T) на две части L 0 ,R 0 , где L 0 ,R 0 - соответствено 32 старших битов и 32 младших битов блока T0 IP(T)= L 0 R 0

    Пусть T i -1 = L i -1 R i -1 результат (i-1) итерации, тогда результат i-ой интерации T i = L i R i определяется:

    L i = R i - 1 Левая половина L i равна правой половине предыдущего вектора L i - 1 R i - 1 . А правая половина R i - это битовое сложение L i - 1 и f(R i - 1 , k i) по модулю 2.

    В 16-циклх преобразования Фейстеля функция f играет роль шифрования. Рассмотрим подробно функцию f.

    Аргументы функции f являются 32 битовой вектор R i - 1 , 48 битовой ключ k i , которые являются результатом преобразования 56 битового исходного ключа шифра k.

    Для вычисления функции f используются фукция расширения Е, преобразование S, состоящее из 8 преобразований S-блоков , и перестановка P.

    Функция Е расширяется 32 битовой вектор R i - 1 до 48 битовой вектор E(R i - 1) путем дублирования некоторых битов из R i - 1 при этом порядок битов вектора E(R i - 1) указан в таблице 2. Первые три бита вектора E(R i - 1) являются битами 32, 1, 2 вектора R i -1 . По таблице 2 видно что биты 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 дублируются. Последние 3 биты вектора E(Ri - 1) - это биты 31, 32, 1 вектора R i - 1 . Полученный после перестановки блок E(R i -1) складывается по модулю 2 с ключами k i и затем представляются в виде восьми последовательных блоков B 1 ,B 2 ,...B 8 .
    E(R i - 1) = B 1 B 2 ...B 8
    Каждый B j является 6-битовым блоком. Далее каждый из блоков B j трансформируется в 4 битовой блок B" j с помощью преобразований S j . Преобразования S j определяется таблицей 3. Предположим что B 3 = 101111 и мы хотим найти B" 3 . Первый и последний разряды B 3 являются двоичной записью числа а, 0Значение функции f(R i - 1 ,k i) (32 бит) получается перестановкой Р, применяемой к 32 битовому блоку B" 1 B" 2 ...B" 8 . Перестановка Р задана таблицей 4.
    f(R i - 1 ,k i) = P(B" 1 B" 2 ...B" 8)
    Согласно таблице 4, первые четыре бита результирующего вектора после действия функции f - это бита 16, 7, 20, 21 вектора B" 1 B" 2 ...B" 8

    Генерирование ключей k i .
    Ключи k i получаются из начального ключа k (56 бит = 7 байтов или 7 символов в АSCII) таким образом. Восемь битов, находящих в позициях 8, 16, 24, 32, 40, 48, 56, 64 добавляются в ключ k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определенна как в таблице 5.

    Эта перестановка определяется двумя блоками C 0 и D 0 по 28 бит каждый. Первые 3 бита C 0 есть биты 57, 49, 41 расширенного ключа. А первые три бита D 0 есть биты 63, 55, 47 расширенного ключа. C i ,D i i=1,2,3…получаются из C i - 1 ,D i - 1 одним или двумя левыми циклическими сдвигами согласно таблице 6.

    Ключ k i , i=1,…16 состоит из 48 бит, выбранных из битов вектора C i D i (56 бит) согласно таблице 7. Первый и второй биты k i есть биты 14, 17 вектора C i D i

    Конечная перестановка IP - 1 действует на T 16 и используется для востановления позиции. Она является обратной к перестановке IP. Конечная перестановка определяется таблицей 8.
    Режимы использования DES DES может используется в четырех режимах.

  • Режим электронной кодовой книги (ЕСВ - Electronic Code Book): обычное использование DES как блочного шифра (см. Рис.7).
  • Режим сцепления блоков (СВС - Cipher Block Chaining) (см. Рис.8). Каждый очередной блок C i i>=1, перед зашифровыванием складывается по модулю 2 со следующим блоком открытого текста M i + 1 . Вектор C 0 - начальный вектор, он меняется ежедневно и хранится в секрете.
  • Режим обратной связи по шифротексту (CFB - Cipher Feed Back) (см. Рис.9). В режиме СFB вырабатывается блочная «гамма» Z 0 ,Z 1 ,...Z i = DESk(C i - 1) . Начальный вектор C 0 сохраняется в секрете.
  • Режим обратной связи по выходу (OFB - Output Feed Back) (см. Рис.10). В режиме OFB вырабатывается блочная «гамма» Z 0 ,Z 1 ,... , i>=1
  • Режим ECB прост в реализации, но возможно проведение критоанализа
  • В режимах ECB и OFB искажение при передаче одного 64-битового блока шифротекста C i приводит к искажению после расшифрования только соответствующего открытого блока M i , поэтому такие режимы используется для передачи по каналам связи с большим числом искажений.
  • В режимах CBC и CFB искажение при передаче одного блока шифрованного текста С i приводит к искажению на приёмнике не более двух блоков открытого текста M i ,M i + 1 . Изменение Mi приводит к изменению всех остальных блоковM i + 1 ,M i + 2 … Это свойство используется для выработки кода аутентификации сообщения.