Композиции шифров
олнения расширения ключа невозможно установить факт
слабости ключа.
Не известны факты успешного криптоанализа алгоритма Blowfish. В целях
безопасности не следует реализовывать Blowfish с уменьшенным числом
раундов. Компания Kent Marsh Ltd. встроила алгоритм Blowfish в свой продукт
FolderBolt, предназначенный для обеспечения защиты Microsoft Windows и
Macintosh. Кроме того, алгоритм входит в Nautilus и PGPfone.
3.8. Алгоритм RC5
RC5 представляет собой блочный шифр с множеством параметров: размером
блока, размером ключа и числом раундов. Он изобретен Роном Ривестом и
проанализирован в RSA Laboratories.
В алгоритме RC5 предусмотрены три операции: XOR, сложение и
циклические сдвиги. На большинстве процессоров операции циклического сдвига
выполняются за постоянное время, переменные циклические сдвиги представляют
собой нелинейную функцию. Эти циклические сдвиги, зависящие как от ключа,
так и от данных - интересная операция.
В RC5 используется блок переменной длины, но в приводимом примере
будет рассмотрен 64-битовый блок данных. Шифрование использует 2r+2
зависящих от ключа 32-битовых слов - S0, S1, S2,... S2r+1 - где r - число
раундов. Для зашифрования сначала нужно разделить блок открытого текста на
два 32-битовых слова: А и В. (При упаковке байтов в слова в алгоритме RC5
соблюдается соглашение о прямом порядке (little-endian) байтов: первый байт
занимает младшие биты регистра А и т.д.) Затем:
A=A + S0
B = B + S0
Для i от 1 до r:
A = ((A( B) <<< B) + S2i
В = ((В( А) <<< А) + S2i+1
Выход находится в регистрах А и В.
Расшифрование тоже несложно. Нужно разбить блок открытого текста на
два слова, А и В, а затем:
Для i от r до 1 с шагом -1:
B = ((B - S2i+1) >>> A)( A
A = ((A - S2i) >>> B)( B
B = B – Si
A = A - S0
Символом «>>>» обозначен циклический сдвиг вправо. Конечно же, все
сложения и вычитания выполняются по модулю 232.
Создание массива ключей сложнее, но тоже прямолинейно. Сначала байты
ключа копируются в массив L из с 32-битовых слов, дополняя при
необходимости заключительное слово нулями. Затем массив S инициализируется
при помощи линейного конгруэнтного генератора по модулю 232:
S0 = Р
Для i от 1 до 2(r + 1) - 1:
Si = (Si-1 + Q) mod 232
где P = 0xb7e15163 и Q = 0x9e3779b9, эти константы основываются на двоичном
представлении е и phi.
Наконец, нужно подставить L в S:
i = j = 0
A = B = 0
Выполнить 3n раз (где п - максимум от 2(r + 1) и с):
A = S i= (Si + A + B) <<< 3
B= Li = (Li + A + B) <<< (A + B)
i = (i + 1) mod 2(r +1)
i = (j +1) mod с
В действительности RC5 представляет собой семейство алгоритмов. Выше
был определен RC5 с 32-битовым словом и 64-битовым блоком, но нет причин,
запрещающих использовать этот же алгоритм с 64-битовым словом и 128-битовым
блоком. Для w=64, Р и Q равны 0xb7e151628aed2a6b и 0x9e3779b97f4a7c15,
соответственно. Ривест обозначил различные реализации RC5 как RC5-w/r/b,
где w - размер слова, r - число раундов, a b - длина ключа в байтах.
RC5 - новый алгоритм, но RSA Laboratories потратила достаточно много
времени, анализируя его работу с 64-битовым блоком. После 5 раундов
статистика выглядит очень убедительно. После 8 раундов каждый бит открытого
текста влияет не менее чем на один циклический сдвиг. Дифференциальная
атака требует 224 подобранных открытых текстов для 5 раундов, 2 - для 10
раундов, 253 - для 12 раундов и 268 - для 15 раундов. Конечно же,
существует только 264 возможных открытых текстов, поэтому такая атака
неприменима к алгоритму с 15 и более раундами. Оценка возможности линейного
криптоанализа показывает, что алгоритм устойчив к нему после 6 раундов.
Ривест рекомендует использовать не менее 12, а лучше 16, раундов. Это число
может меняться.
Компания RSADSI в настоящее время патентует RC5, и его название
заявлено как торговая марка. Компания утверждает, что плата за лицензию
будет очень мала, но эти данные нуждаются в проверке.
4. Объединение блочных шифров
Известно множество путей объединения блочных алгоритмов для получения
новых алгоритмов. Создание подобных схем стимулируется желанием повысить
безопасность, избежав трудности проектирования нового алгоритма. Так,
алгоритм DES относится к надежным алгоритмам, он подвергался криптоанализу
добрых 20 лет и, тем не менее, наилучшим способом взлома остается лобовое
вскрытие. Однако ключ DES слишком короток. Разве не плохо было бы
использовать DES в качестве компонента другого алгоритма с более длинным
ключом? Это позволило бы воспользоваться преимуществами обоих систем:
устойчивостью, гарантированной двумя десятилетиям криптоанализа, и длинным
ключом.
Один из методов объединения - многократное шифрование. В этом случае
для шифрования одного и того же блока открытого текста алгоритм шифрования
используется несколько раз с несколькими ключами. Каскадное шифрование
подобно многократному шифрованию, но использует различные алгоритмы.
Известны и другие методы.
Повторное шифрование блока открытого текста одним и тем же ключом с
помощью того же или другого алгоритма неэффективно. Повторное использование
того же алгоритма не повышает сложность лобового вскрытия. (Мы
предполагаем, что криптоаналитику известны алгоритм и число операций
шифрования). При использовании различных алгоритмов сложность лобового
вскрытия может, как возрастать, так и оставаться неизменной. При этом нужно
убедиться в том, что ключи для последовательных шифрований различны и
независимы.
4.1. Двойное шифрование
К наивным способам повышения надежности алгоритма относится шифрование
блока дважды с двумя различными ключами. Сначала блок зашифровывается
первым ключом, а получившийся шифртекст - вторым ключом. Расшифрование
выполняется в обратном порядке.
С = ЕК1(Ek2(Р))
P = DK1(DK1(C))
Если блочный алгоритм образует группу, всегда существует такой К3, для
которого:
С = ЕК2(ЕК1(Р)) = ЕК3(Р)
Если алгоритм не образует группу, взломать итоговый дважды
зашифрованный блок шифртекста с помощью полного перебора намного сложнее.
Вместо 2n (где п – длина ключа в битах), потребуется 22n попыток. Если
алгоритм использует 64-битовый ключ, для обнаружения ключей, которыми
дважды зашифрован шифртекст, понадобится 2128 попыток.
Однако при атаке с известным открытым текстом это не так. Меркл и
Хеллман предложили способ согласования памяти и времени, который позволяет
вскрыть такую схему двойного шифрования за 2n+1 шифрований, а не за 22n.
(Они использовали эту схему против DES, но результаты можно обобщить на все
блочные алгоритмы). Такая атака называется «встреча посередине»: с одной
стороны выполняется зашифрование, а с другой - расшифрование, а полученные
посередине результаты сравниваются.
В этой атаке криптоаналитику известны значения P1, С1, Р2 и С2, такие
что:
C1=EK2(EK1(Pt))
С2=ЕК2(ЕК1(Р2))
Для каждого возможного К криптоаналитик рассчитывает ЕК(Р1) и
сохраняет результат в памяти. Собрав все результаты, он для каждого К
вычисляет DK(C1) и ищет в памяти такой же результат. Если такой результат
обнаружен, то, возможно, что текущий ключ – К2, а ключ для результата в
памяти – К1. Затем криптоаналитик зашифровывает Р2 ключами К1 и К2. Если он
получает С2, он может почти быть убежденным (с вероятностью 1 к 22m-2n, где
т - размер блока), что он восстановил и К1 и К2. В противном случае он
продолжает поиск. Максимальное количество попыток шифрования, которое ему
придется предпринять, составляет 2*2n, т.е. 2n+1. Если вероятность ошибки
слишком велика, криптоаналитик может использовать третий блок шифртекста,
обеспечивая вероятность успеха 1 к 23m-2n. Существуют и другие способы
оптимизации.
Для такого вскрытия нужен большой объем памяти: 2n блоков. Для 56-
битового ключа нужно хранить 256 64-битовых блоков, или 1017 байт. Такой
объем памяти пока еще трудно себе представить, но этого хватает, чтобы
убедить самых осторожных криптографов в ненадежности двойного шифрования.
При 128-битовом ключе для хранения промежуточных результатов
потребуется огромная память в 1039 байт. Если предположить, что каждый бит
информации хранится на единственном атоме алюминия, запоминающее
устройство, нужное для такого вскрытия, будет представлять собой
алюминиевый куб с ребром 1 км. Кроме того, понадобится куда-то его
поставить. Так что атака «встреча посередине» при ключах такого размера
представляется невозможной.
Другой способ двойного шифрования, который иногда называют методом
Дэвиса-Прайса (Davies-Price), представляет собой вариант режима шифрования
СВС.
Сi =Ek1(Pi( Ek2(Ci-1))
Pi=Dk1(Ci)( Ek2(Ci-1)
Утверждается, что «у этого режима нет никаких особых достоинств», к
тому же он, по-видимому, столь же уязвим к атаке «встреча посередине», как
и другие режимы двойного шифрования.
4.2. Тройное шифрование
4.2.1. Тройное шифрование с двумя ключами
В более удачном методе, предложенном Тачменом, блок обрабатывается три
раза с использованием двух ключей: первым ключом, вторым ключом и снова
первым ключо
| |  скачать работу |
Композиции шифров |
