Композиции шифров
м. Тачмен предлагает, чтобы отправитель сначала зашифровал
сообщение первым ключом, затем расшифровал вторым, и окончательно
зашифровал первым ключом. Получатель расшифровывает сообщение первым
ключом, затем зашифровывает вторым и, наконец, расшифровывает первым.
С = EK1(DK2(EK1(P)))
P = DK1(EK1(DK1(С)))
Иногда такой режим называют режимом зашифрование-расшифрование-
зашифрование (Encrypt-Decrypt-Encrypt - EDE). Если блочный алгоритм
использует n-битовый ключ, длина ключа описанной схемы составляет 2п бит.
Эта остроумная связка ключей (зашифрования-расшифрования-зашифрования)
разработана в корпорации IBM для совместимости с существующими реализациями
алгоритма: задание двух одинаковых ключей эквивалентно одинарному
шифрованию. Такая схема EDE сама по себе не обеспечивает заведомую
безопасность, однако этот режим использовался для улучшения алгоритма DES в
стандартах Х9.17 и ISO 8732.
Для предотвращения описанной выше атаки «встреча посередине»,
использование ключей ki и K2 чередуется. Если С=ЕK2(ЕК1(ЕК1(Р))), то
криптоаналитик может заранее вычислить ЕК1(ЕК1(Р))) для любого возможного
K1, а затем выполнить вскрытие. Для этого потребуется только 2n+2
шифрований.
Тройное шифрование с двумя ключами устойчиво к такой атаке. Но Меркл и
Хеллман разработали другой способ согласования памяти и времени, который
позволяет взломать и этот алгоритм шифрования за 2n-1 действий, используя
2n блоков памяти.
Для каждого возможного К2 расшифровывают 0 и сохраняют результат в
памяти. Затем расшифровывают 0 для каждого возможного К1, чтобы получить Р.
Выполняют тройное зашифрование Р, чтобы получить С, и затем расшифровывают
С ключом К1. Если полученное значение совпадает со значением (хранящимся в
памяти), полученным при расшифровании 0 ключом К2, то, возможно, пара K1K2
и будет искомым результатом. Проверяют, так ли это. Если нет, продолжают
поиск.
Для выполнения этого вскрытия с подобранным открытым текстом нужна
память огромного объема. Понадобится 2n времени и памяти, а также 2m
подобранных открытых текстов. Атака не слишком практична, но все же
указывает на некоторую слабость этого метода.
Пауль ван Оорсчот (Paul van Oorschot) и Майкл Винер (Michael Wiener)
преобразовали эту атаку к атаке на основе открытых текстов, для которой их
нужно р штук. В примере предполагается использование режима EDE.
1) Предположить первое промежуточное значение а.
2) Используя известный открытый текст, свести в таблицу для каждого
возможного К1 второе промежуточное значение b при первом промежуточном
значении, равном а:
b=DK1(С)
где С - шифртекст, полученный по известному открытому тексту.
3) Для каждого возможного K2 найти в таблице элементы с совпадающим вторым
промежуточным значением b:
b = EK2(a)
4) Вероятность успеха равна р/т, где р - число известных открытых текстов,
а т -размер блока. Если совпадения не обнаружены, нужно выбрать другое
значение а и начать сначала.
Атака требует 2n+m/р времени и р - памяти. Для алгоритма DES это
составляет 2120/р. При р, больших 256, эта атака выполняется быстрее, чем
полный перебор.
4.2.2. Тройное шифрование с тремя ключами
Если используют тройное шифрование, рекомендуется использовать три
разных ключа. Общая длина ключа станет больше, но хранение ключа обычно не
вызывает затруднений. Биты дешевы.
С = EK3(DK2(EK1(P)))
P = DK1(EK2(DK3(С)))
Для наилучшего вскрытия с согласованием памяти и времени, примером
которого служит «встреча посередине», понадобятся 22n операций и 2n блоков
памяти. Тройное шифрование с тремя независимыми ключами настолько надежно,
насколько на первый взгляд кажется надежным двойное шифрование.
4.2.3. Тройное шифрование с минимальным ключом
Известен более надежный метод использования тройного шифрования с
двумя ключами, препятствующий описанной атаке и называемый тройным
шифрованием с минимальным ключом (Triple Encryption with Minimum Key -
TEMK). Фокус в том, чтобы получить три ключа из двух: Х1 и Х2.
K1=EX1(DX2(EX1(T1)))
K2 = EX1(DX2(EX1(T2)))
K3=EX1(DX1(EX1(T3)))
Здесь T1, T2 и Т3 - константы, которые необязательно хранить в секрете. Эта
схема гарантирует, что для любой конкретной пары ключей наилучшим методом
взлома будет вскрытие с известным открытым текстом.
4.2.4. Режимы тройного шифрования
Недостаточно просто определить тройное шифрование, его
можно выполнить несколькими методами. Решение зависит от требуемых
безопасности и эффективности.
Вот два возможных режима тройного шифрования:
Внутренний СВС: Файл зашифровывается в режиме СВС три раза (Рис. 1а). Для
этого нужны три различных вектора инициализации (ВИ).
Ci=EK3(Si( Ci-1); Si=DK2(T( Si-1); Ti=EK1(Pi( Ti-1)
Pi=Ti-1( DK1(Ti); Ti=Si-1( EK2(Si); Si=Ci-1( DK3(Ci)
Где С0, S0 и T0 - векторы инициализации.
Внешний СВС: Файл шифруется с помощью тройного шифрования (один раз) в
режиме СВС (Рис. 5). Для этого нужен один вектор ВИ.
Ci=EK3(DK2(EK1(Pi( Ci-1)))
Pi=Ci-1( DK1(EK2(DK3(Ci)))
[pic]
Рис. 5. Тройное шифрование в режиме СВС
Оба режима требуют больше ресурсов, чем однократное
шифрование: больше аппаратуры или больше времени. Однако при установке
трех шифровальных микросхем производительность внутреннего СВС не меньше,
чем при однократном шифровании. Так как три шифрования СВС независимы, три
микросхемы могут быть загружены постоянно, подавая свой выход себе на вход.
Напротив, во внешнем СВС обратная связь лежит вне трех процессов
шифрования. Это означает, что даже при использовании трех микросхем
производительность составит только треть производительности однократного
шифрования. Чтобы получить ту же производительность для внешнего СВС,
потребуется чередование векторов ВИ.
Сi = EK3(DK2(EK1(Pi( Ci-3)))
где С0, C-1 и С-2 - векторы инициализации. Это не поможет при программной
реализации, разве только при использовании параллельного компьютера.
К сожалению, менее сложный режим также и менее безопасен. Бихам
проанализировал устойчивость различных режимов к дифференциальному
криптоанализу с подобранными шифртекстами и обнаружил, что внутренний СВС
только незначительно надежнее однократного шифрования. Если рассматривать
тройное шифрование как большой единый алгоритм, его внутренние обратные
связи позволяют вводить внешнюю и известную информацию во внутреннюю
структуру алгоритма, что облегчает криптоанализ. Для дифференциальных атак
нужно огромное количество подобранных шифртекстов, что делает эти вскрытия
не слишком практичными, но этих результатов должно хватить, чтобы
насторожить скептически настроенных пользователей. Анализ устойчивости
алгоритмов к вскрытиям «в лоб» и «встречей посередине» показал, что и этом
отношении оба варианта одинаково надежны.
Кроме перечисленных, известны и другие режимы. Можно зашифровать файл
один раз и режиме ЕСВ, затем дважды в СВС, или один раз в СВС, один в ЕСВ и
еще раз в СВС, или дважды в СВС и один раз в ЕСВ. Бихам показал, что эти
варианты отнюдь не устойчивее однократного DES при вскрытии методом
дифференциального криптоанализа с подобранным открытым текстом. Он не
оставил больших надежд и для других вариантов. Если вы собираетесь
применять тройное шифрование, используйте режимы с внешней обратной связью.
4.2.5. Варианты тройного шифрования
Прежде чем было доказано, что DES не образует группу, предлагались
различные схемы многократного шифрования. Одним из способов гарантировать,
что тройное шифрование не выродится в однократное, было изменение
эффективной длины блока. Простой метод предполагает дополнять блок битами.
С этой целью между первым и вторым, а также между вторым и третьим
шифрованиями текст дополняется строкой случайных битов длиной в полблока
(Рис. 6). Если p - это функция дополнения, то:
С = ЕK3(р(ЕК2(р(ЕК1(Р)))))
Дополнение не только маскирует структуру текста, но и обеспечивает
перекрытие блоков шифрования, примерно как кирпичи в стене. Длина сообщения
увеличивается только на один блок.
[pic]
Рис. 6. Тройное шифрование с дополнением
В другом методе, предложенном Карлом Эллисоном (Carl Ellison), между
тремя шифрованиями используется некоторая бесключевая функция перестановки.
Перестановка должна работать с большими блоками - 8 Кбайт или около этого,
что делает эффективный размер блока для этого варианта равным 8 Кбайт. Если
перестановка выполняется быстро, этот вариант ненамного медленнее, чем
базовое тройное шифрование.
C = EK1(T(EK2(T(EK1(P)))))
Т собирает входной (длиной до 8 Кбайт) и использует генератор
псевдослучайных чисел для его перемешивания. Изменение одного входного бита
приводит к изменению восьми байтов результата первого шифрования, до 64
байтов - результата второго шифрования и до 512 байтов - результата
третьего шифрования. Если каждый блочный алгоритм работает в режиме СВС,
как предполагалось первоначально, изменение единичного входного бита,
скорее всего, приведет к изменению всего 8-килобайтового блока, даже если
это не первый блок.
Новейший вариант этой схемы противодействует атаке на внутренний СВС,
предложенной Бихамом, добавлением процедуры отбеливания, позволяющей
замаскировать структуру открытых текстов. Эта процедура представляе
| |  скачать работу |
Композиции шифров |
