Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С

• Название: Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
• Дата: 29.04.2022
• Размер: 3.25 Mb.
• Имя файла: Shnayer_Prikladnaya-kriptografiya.352928.pdf
• Тип: Протокол; #504484
• страница: 32 из 78

грубой силой скоро станут по карману всем организациям.
Предложенные Бихамом зависимые от ключа S-блоки DES будут безопасны в течение по крайней мере н е- скольких лет, может быть за исключением использования против самых хорошо обеспеченных противников.
Если необходимая безопасность должна быть обеспечена на десятилетия, или вы опасаетесь криптоаналитич е- ских усилий правительств великих держав, воспользуйтесь тройным DES с тремя независимыми ключами.
Небеполезны и другие алгоритмы. Мне нравится Blowfish, потому что он быстр, и потому что я его прид у- мал. Неплохо выглядит 3-WAY, возможно все в порядке и с ГОСТом. Проблема посоветовать что-нибудь с о- стоит в том, что NSA почти наверняка обладает набором эффективных криптоаналитических приемов, которые до сих пор засекречены, и я не знаю, какие алгоритмы могут быть вскрыты. В Табл. 14.3 для сравнения прив е- дены временные соотношения для некоторых алгоритмов.
Мой любимый алгоритм - IDEA. Его 128-битовый ключ в сочетании с устойчивостью к общеизвестным средствам криптоанализа - вот источники моего теплого и нежного чувства к этому алгоритму. Этот алгоритм анализировался различными группами, и никаких серьезных замечаний не было опубликовано. В отсутствие необычайных криптоаналитических прорывов я сегодня ставлю на IDEA.
Табл. 14-3.
Скорости шифрования для некоторых блочных шифров на i486SX/33 МГц
Алгоритм
Скорость шифрования
(Кбайт/с)
Алгоритм
Скорость шифрования
(Кбайт/с)
Blowfish (12 этапов)
182
MDC (с MD4)
186

Blowfish (16 этапов)
135
MDC (с MD5)
135
Blowfish (20 этапов)
110
MDC (с SHA)
23
DES
35
NewDES
233
FEAL-8 300
REDOC II
1
FEAL-16 161
REDOC III
78
FEAL-32 91
RC5-32/8 127
ГОСТ
53
RC5-32/12 86
IDEA
70
RC5-32/16 65
Khufu (16 этапов)
221
RC5-32/20 52
Khufu (24 этапов)
153
SAFER (6 этапов)
81
Khufu (32 этапов)
115
SAFER (8 этапов)
61
Luby-Rackoff (с MD4)
47
SAFER (10 этапов)
49
Luby-Rackoff (с MD5)
34
SAFER (12 этапов)
41
Luby-Rackoff (с SHA)
11 3-Way
25
Lucifer
52
Тройной DES
12

Глава 15
Объединение блочных шифров
Существует множество способов объединять блочные алгоритмы для получения новых алгоритмов. Стиму- лом создавать подобные схемы является желание повысить безопасность, не пробираясь через тернии создания нового алгоритма. DES является безопасным алгоритмом, он подвергался криптоанализу добрых 20 лет и, тем не менее, наилучшим способом вскрытия остается грубая сила . Однако ключ слишком короток. Разве не плохо было бы использовать DES в качестве компонента другого алгоритма с более длинным ключом ? Это позволило бы получить преимущества длинного ключа с гарантией двух десятилетий криптоанализа .
Одним из способов объединения является многократное шифрование - для шифрования одного и того же блока открытого текста алгоритм шифрования используется несколько раз с несколькими ключами . Шифрова- ние каскадом похоже на многократное шифрование, но использует различные алгоритмы . Существуют и другие методы.
Повторное шифрование блока открытого текста одним и тем же ключом с помощью того же или другого а л- горитма неразумно. Повторное использование того же алгоритма не увеличивает сложность вскрытия грубой силой. (Не забывайте, мы предполагаем, что алгоритм, включая количество шифрований, известен криптоан а- литику.) При различных алгоритмах сложность вскрытия грубой силой может возрастать, а может и остаться неизменной. Если вы собираетесь использовать методы, описанные в этой главе, убедитесь, что ключи для п о- следовательных шифрований различны и независимы.
15.1 Двойное шифрование
Наивным способом повысить безопасность алгоритма является шифрование блока дважды с двумя разли ч- ными ключами. Сначала блок шифруется первым ключом, а затем получившийся шифротекст шифруется вт о- рым ключом. Дешифрирование является обратным процессом .
C E E P
K
K
=
2 1
(
( ))
P D D C
K
K
=
1 2
(
( ))
Если блочный алгоритм образует группу (см. раздел 11.3), то всегда существует K
3
, для которого
C E E P
E P
K
K
K
=
=
2 1
3
(
( ))
( )
Если алгоритм не образует группу, то при помощи исчерпывающего поиска взломать получающийся дважды зашифрованный блок шифротекста намного сложнее . Вместо 2
n
(где n - длина ключа в битах), потребуется 2 2n попыток. Если алгоритм использует 64-битовый ключ , для обнаружения ключей, которыми дважды зашифр о- ван шифротекст, потребуется 2 128
попыток.
Но при вскрытии с известным открытым текстом это не так . Меркл и Хеллман [1075] придумали способ об- менять память на время, который позволяет вскрыть такую схему двойного шифрования за 2
n+1
шифрований, а не за 2 2n
. (Они использовали эту схему против DES, но результаты можно обобщить на все блочные алгоритмы.) Это вскрытие называется "встреча посередине", с одной стороны выполняется шифрование а с другой - дешифрирование, получившиеся посередине результаты сравниваются .
В этом вскрытии криптоаналитику известны P
1
, C
1
, P
2
и C
2
, такие что
C
E E P
K
K
1 1
2 1
=
(
( ))
C
E E P
K
K
2 2
2 1
=
(
( ))
Для каждого возможного K (или K
1
, или K
2
), криптоаналитик рассчитывает E
K
(P
1
) и сохраняет результат в памяти. Собрав все результаты, он для каждого K вычисляет D
K
(C
1
) и ищет в памяти такой же результат. Если такой результат обнаружен, то возможно, что текущий ключ - K
2
, а ключ для результата в памяти - K
1
. Затем криптоаналитик шифрует P
1 с помощью K
1 и K
2
. Если он получает C
2
, то он может гарантировать (с вероятно- стью успеха 1 к 2 2n-2m
, где m - размер блока), что он узнал и K
1
,
и K
2
. Если это не так, он продолжает поиск.
Максимальное количество попыток шифрования, которое ему , возможно, придется предпринять, равно 2*2
n
,
или 2
n+1
. Если вероятность ошибки слишком велика, он может использовать третий блок шифротекста, обесп е- чивая вероятность успеха 1 к 2 2n-3m
. Существуют и другие способы оптимизации [912].
Для такого вскрытия нужен большой объем памяти: 2
n блоков. Для 56-битового ключа нужно хранить 2 56 64- битовых блоков, или 10 17
байтов. Такой объем памяти пока еще трудно себе представить, но этого хватает, чт о- бы убедить самых параноидальных криптографов в том, что двойным шифрованием пользоваться не стоит .

При 128-битовом ключе для хранения промежуточных результатов потребуется 10 39
байтов. Если предполо- жить, что есть способ хранить бит информации, используя единственный атом алюминия , устройство памяти,
нужное для выполнения такого вскрытия, будет представлять собой алюминиевый куб с ребром, длиной 1 км .
Кроме того, вам понадобится куда-то его поставить ! Вскрытие "встреча посередине" кажется невозможным для ключей такого размера.
Другим способом двойного шифрования, который иногда называют Davies-Price, является вариантом CBC
[435].
C
E P E C
P D C
E C
i
K
K
i i
K
i
K
i
=
?
=
?
?
?
1 2
1 2
1 1
1
(
(
))
( )
(
))
Утверждается, что "у этого режима нет никаких особых достоинств ", к тому же он, по видимому, так же чув- ствителен ко вскрытию "встреча посередине" как и другие режимы двойного шифрования .
15.2
Тройное шифрование с двумя ключами
В более интересном методе, предложенном Тачменом в [1551], блок обрабатывается три раза с помощью двух ключей: первым ключом, вторым ключом и снова первым ключом . Он предлагает, чтобы отправитель сначала шифровал первым ключом, затем дешифрировал вторым, и окончательно шифровал первым ключом .
Получатель расшифровывает первым ключом, затем шифрует вторым и, наконец, дешифрирует первым .
C E D E P
P D E D C
K
K
K
K
K
K
=
=
1 2
1 1
2 1
(
(
( )))
(
(
( )))
Иногда такой режим называют шифрование-дешифрирование-шифрование (encrypt-decrypt-encrypt, EDE)
[55]. Если блочный алгоритм использует n-битовый ключ, то длина ключа описанной схемы составляет 2n бит.
Любопытный вариант схемы шифрование-дешифрирование-шифрование был разработан в IBM для совмести- мости с существующими реализациями алгоритма : задание двух одинаковых ключей эквивалентно одинарному шифрованию. этим ключом. Схема шифрование-дешифрирование-шифрование сама по себе не обладает ник а- кой безопасностью, но этот режим был использован для улучшения алгоритма DES в стандартах X9.17 и ISO
8732 [55, 761].
K
1
и K
2
чередуются для предотвращения описанного выше вскрытия "встреча посередине" . Если
C E E E P
K
K
K
=
1 1
1
(
(
( )))
, то криптоаналитик для любого возможного K
1
может заранее вычислить
E E P
K
K
1 1
(
( ))
и затем выполнить вскрытие. Для этого потребуется только 2
n+2
шифрований.
Тройное шифрование с двумя ключами устойчиво к такому вскрытию . Но Меркл и Хеллман разработали другой способ размена памяти на время, который позволяет взломать этот метод шифрования за 2
n-1
действий,
используя 2
n блоков памяти [1075].
Для каждого возможного K
2
расшифруйте 0 и сохраните результат. Затем расшифруйте 0 для каждого воз- можного K
1
, чтобы получить P. Выполните тройное шифрование P, чтобы получить C, и затем расшифруйте C
ключом K
1
. Если полученное значение совпадает с значением (хранящемся в памяти), полученным при деши ф- рировании 0 ключом K
2
, то пара K
1
K
2
является возможным результатом поиска . Проверьте, так ли это. Если нет, продолжайте поиск.
Выполнение этого вскрытия с выбранным открытым текстом требует огромного объема памяти . Понадобит- ся 2
n времени и памяти, а также 2
m выбранных открытых текстов. Вскрытие не очень практично, но все же чу в- ствительность к нему является слабостью алгоритма .
Пауль ван Оорсчот (Paul van Oorschot) и Майкл Винер (Michael Wiener) преобразовали это вскрытие ко вскрытию с известным открытым текстом , для которого нужно p известных открытых текстов. В примере пред- полагается, что используется режим EDE.
(1) Предположить первое промежуточное значения a.
(2) Используя известный открытый текст, свести в таблицу для каждого возможного K
1
второе промежуточ- ное значение b, при первом промежуточном значении, равном a:
b =
D C
K
1
( )
где C - это шифротекст, полученный по известному открытому тексту .
(3) Для каждого возможного K
2
найти в таблице элементы с совпадающим вторым промежуточным значение

b:
b =
E a
K
2
( )
(4) Вероятность успеха равно p/m, где p - число известных открытых текстов, а m - размер блока. Если совпа- дения не обнаружены, выберите другое a и начните сначала.
Вскрытие требует 2
n+m
/p времени и p - памяти. Для DES это равно 2 120
/p [1558]. Для p, больших 256, это вскрытие быстрее, чем исчерпывающий поиск .
Тройное шифрование с тремя ключами
Если вы собираетесь использовать тройное шифрование , я рекомендую три различных ключа. Общая длина ключа больше, но хранение ключа обычно не является проблемой . Биты дешевы.
C E D E P
P D E D C
K
K
K
K
K
K
=
=
3 2
1 1
2 3
(
(
( )))
(
(
( )))
Для наилучшего вскрытия с разменом памяти на время, которым является "встреча посередине", потребуется
2 2n действий и 2
n блоков памяти [1075]. Тройное шифрование с тремя независимыми ключами безопасно н а- столько, насколько на первый взгляд кажется безопасным двойное шифрование .
Тройное шифрование с минимальным ключом (TEMK)
Существует безопасный способ использовать тройное шифрование с двумя ключами, противостоящий описанному вскрытию и называемый
Тройным шифрованием с минимальным ключом (Triple Encryption with Minimum Key,
TEMK) [858]. Фокус в тои, чтобы получить три ключа из: X
1
и X
2
K
E D E T
K
E D E T
K
E D E T
X
X
X
X
X
X
X
X
X
1 1
2 2
3 3
1 2
1 1
2 1
1 2
1
=
=
=
(
(
( )))
(
(
( )))
(
(
( )))
T
1
, T
2
и T
3 представляют собой константы, которые необязательно хранить в секрете . Эта схема гарантирует,
что для любой конкретной пары ключей наилучшим будет вскрытие с известным открытым текстом .
Режимы тройного шифрования
Недостаточно просто определить тройное шифрование, нужно выбрать один из способов его использования .
Решение зависит от требуемых безопасности и эффективности . Вот два возможных режима тройного шифров а- ния:
Внутренний CBC: Файл три раза шифруется в режиме CBC (см. 14tha). Для этого нужно три различных IV.
C
E S
C
S
D T S
T E P T
P T
D T T S
E S S
C
D C
i
K
i i
i
K
i i
i
K
i i
i i
K
i i
i
K
i i
i
K
i
=
?
=
?
=
?
=
?
=
?
=
?
?
?
?
?
?
?
3 2
1 1
2 3
1 1
1 1
1 1
(
);
(
);
(
)
( );
( );
( )
C
0
, S
0
и T
0
являются IV.
Внешний CBC: Файл троекратно шифруется в режиме CBC (см. 14thb). Для этого нужен один IV.
C
E D E P C
P C
D E D C
i
K
K
K
i i
i i
K
K
K
i
=
?
=
?
?
?
3 2
1 1
2 3
1 1
(
(
(
)))
(
(
( )))

E
K
1
D
K
2
E
K
3
E
K
1
D
K
2
E
K
3
E
K
1
D
K
2
E
K
3
E
K
1
D
K
2
E
K
3
E
K
1
D
K
2
E
K
3
E
K
1
D
K
2
E
K
3
(b) Внешний CBC
(а) Внутренний CBC
Рис. 15-1. Тройное шифрование в режиме CBC.
Для обоих режимов нужно больше ресурсов, чем для однократного шифрования: больше аппаратуры или больше времени. Однако при трех шифрующих микросхемах производительность внутреннего CBC не меньше,
чем при однократном шифровании. Так как три шифрования CBC независимы, три микросхемы могут быть загружены постоянно, подавая свой выход себе на вход.
Напротив во внешнем CBC обратная связь находится снаружи по отношению к трем шифрованиям . Это оз- начает, что даже с тремя микросхемами производительность будет равна только одной трети производительн о- сти при однократном шифровании. Чтобы получить ту же производительность для внешнего CBC, потребуется чередование IV (см. раздел 9.12):
C
E D E P C
i
K
K
K
i i
=
?
?
3 2
1 3
(
(
(
)))
В этом случае C
0
, C
-1
и C
-2
являются IV. Это не поможет при программной реализации, разве только при и с- пользовании параллельного компьютера.
К сожалению менее сложный режим является также и менее безопасным . Бихам проанализировал различ- ные режимы по отношению к дифференциальному криптоанализу и обнаружил, что безопасность внутреннего
CBC по сравнению с однократным шифрованием увеличивается незначительно . Если рассматривать тройное шифрование как единый большой алгоритм , то внутренние обратные связи позволяют вводить внешнюю и и з- вестную информацию внутрь алгоритма, что облегчает криптоанализ . Для дифференциальных вскрытий нужно огромное количество выбранных шифротекстов, что делает эти вскрытия не слишком практичными, но этих результатов должно хватить, чтобы насторожить параноидальных пользователей . Анализ устойчивости алго- ритмов к вскрытиям грубой силой и "встречей посередине" показал, что оба варианта одинаково безопасны
[806].
Кроме этих существуют и другие режимы . Можно зашифровать файл один раз в режиме ECB, затем дважды в CBC, или один раз в CBC, один в ECB и еще раз в CBC, или дважды в CBC и один раз в ECB. Бихам показал,
что эти варианты не безопаснее, чем однократный DES, против вскрытия дифференциальным криптоанализом с выбранным открытым текстом [162]. Он не оставил больших надежд и для других вариантов . Если вы собирае- тесь применять тройное шифрование, используйте внешнюю обратную связь .
Варианты тройного шифрования
Прежде, чем появились доказательства того, что DES не образует группу, для многократного шифрования предлагались различные схемы. Одним из способов обеспечить то, что тройное шифрование не выродится в однократное, было изменение эффективной дины блока . Простым методом является добавление бита- заполнителя. Между первым и вторым, а также между вторым и третьим шифрованиями текст дополняется

строкой случайных битов (см. Рис. 15.2). Если PP - это функция дополнения, то:
C E PP E
PP E P
K
K
K
=
3 2
1
(
(
(
(
( )))))
Это дополнение не только разрушает шаблоны, но также обеспечивает перекрытие блоков шифрования, как кирпичей в стене. К длине сообщения добавляется только один блок .
Открытый текст
Шифрование
Запо лнит ель
Запо лнит ель
Шифротекст
Шифрование
Шифрование
Рис. 15-2. Тройное шифрование с заполнением.
Другой метод, предложенный Карлом Эллисоном ( Carl Ellison), использует некоторую функцию независ и- мой от ключа перестановки между тремя шифрованиями . Перестановка должна работать с большими блоками -
8 Кбайт или около этого, что делает эффективный размер бока для этого варианта равным 8 Кбайтам . При ус- ловии, что перестановка выполняется быстро, этот вариант ненамного медленнее, чем базовое тройное шифр о- вание.
C E T E T E P
K
K
K
=
3 2
1
( (
( (
( )))))
T собирает входные блоки (до 8 Кбайт в длину) и использует генератор псевдослучайных чисел для их пер е- мешивания. Изменение одного бита входа приводит к изменению 8 байтов результата первого шифрования, к изменению до 64 байтов результата второго шифрования и к изменению до 512 байтов результата третьего шифрования. Если каждый блочный алгоритм работает в режиме CBC, как было первоначально предложено, то изменение единичного бита входа скорее всего приведет к изменению всего 8-килобайтового блока, даже если этот блок не является первым.
Самый последний вариант этой схемы отвечает на вскрытие внутреннего CBC, выполненное Бихамом, до- бавлением процедуры отбеливания, чтобы замаскировать структуру открытых текстов . Эта процедура представ- ляет собой потоковую операцию XOR с криптографически безопасным генератором псевдослучайных чисел и ниже обозначена как R. T мешает криптоаналитику определить a priori, какой ключ используется для шифрова- ния любого заданного байта входа последнего шифрования . Второе шифрование обозначено nE (шифрование с циклическим использованием n различных ключей):