Безопасность SAFER K-64
Массей показал, что SAFER K-64 после 6 этапов абсолютно защищен от дифференциального криптоанализа после 8 этапов и достаточно безопасен. Уже после 3 этапов против этого алгоритма становится неэффективным и линейный криптоанализ [1010].
Кнудсен (Knudsen) обнаружил слабое место в распределении ключей: практически для каждого ключа существует не меньше одного (а иногда даже девять) другого ключа, который при шифровании какого-то другого открытого текста превращает его в тот же шифротекст [862]. Число различных открытых текстов, которые шифруются одинаковыми шифротекстами, находится в промежутке от 222 до 228. Хотя такое вскрытие не может повлиять на безопасность SAFER как алгоритма шифрования, оно значительно уменьшает его надежность при использовании в качестве однонаправленной хэш-функции. В любом случае Кнудсен рекомендует использовать не меньше 8 этапов.
SAFER был спроектирован для Cylink, а Cylink были предъявлены различные обвинения со стороны NSA [80]. Я рекомендовал бы потратить несколько лет на интенсивный криптоанализ прежде, чем как-либо использовать SAFER.
WAY
3-Way - это блочный шифр, разработанный Джоном Дэйменом (Joan Daemen) [402, 410]. Он использует блок и ключ длиной 96 бит, и его схема предполагает очень эффективную аппаратную реализацию.
3-Way является не сетью Фейстела, а итеративным блочным шифром. У 3-Way может быть n этапов, Дэймен рекомендует 11.
Описание S-Way
Этот алгоритм описать несложно. Для шифрования блока открытого текста x:
For i = 0 to n - 1
x = x XOR Ki
x = theta (x)
x = pi - 1 (x)
x = gamma (x)
x = pi - 2 (x)
x = x Å Kn+1
x = theta (x)
При этом используются следующие функции:
— theta(x) - функция линейной подстановки, в основном набор циклических сдвигов и XOR.
— pi - 1 (x) и pi - 2 (x) - простые перестановки.
— gamma (x) - функция нелинейной подстановки. Именно это действие и дало имя всему алгоритму, оно представляет собой параллельное выполнение подстановки 3-битовых данных.
Дешифрирование аналогично шифрованию за исключением того, что нужно изменить на обратный порядок битов исходных данных и результата. Исходный код, реализующий 3-Way, можно найти в конце этой книги.
Пока об успешном криптоанализе 3-Way неизвестно. Алгоритм незапатентован.
CRAB
Этот алгоритм был разработан Бертом Калиски [Burt Kaliski] и Мэттом Робшоу [Matt Robshaw] из RSA Laboratories [810]. В основе Crab лежит идея использовать методы однонаправленных хэш-функций для создания быстрого алгоритма шифрования. Следовательно, Crab очень похож на MD5, и в этом разделе предполагается, что вы знакомы с материалом раздела 18.5.
У Crab очень большой блок: 1024 байта. Так как Crab был представлен скорее как материал для исследования, а не реальный алгоритм, конкретной процедуры генерации ключей не было предложено. Авторы рассмотрели метод, который позволяет превратить 80-битовый ключ в три вспомогательных подключа, хотя алгоритм позволяет легко использовать ключи переменной длины. В Crab используется два набора больших подключей:
Перестановка чисел с 0 до 255: P0, P1, P2, ..., P255.
Массив из 2048 32-битовых чисел: S0, S1, S2,..., S2047.
Все эти подключи должны быть вычислены до шифрования или дешифрирования. Для шифрования 1024-байтового блока X:
(1) Разделите X на 256 32-битовых подблоков: X0, X1, X2, ..., X255.
(2) Переставьте подблоки X в соответствии с P.
(3) For r=0 to 3
For g = 0 to 63
A = X(4g) <<< 2r
B = X(4g+1) <<< 2r
C = X(4g+2) <<< 2r
D = X(4g+3) <<< 2r
For step s = 0 to 7
A = A Å (B + fr(B, C, D) + S512r+8g+s)
TEMP = D
D = C
C = B
B = A <<< 5
A = TEMP
X(4g) <<< 2r = A
X(4g+1) <<< 2r = B
X(4g+2) <<< 2r = C
X(4g+3) <<< 2r = D
(4) Снова объединить X0, X1, X2, ..., X255, получая шифротекст.
Функции fr(B, C, D) аналогичны используемым в MD5:
f0(B, C, D) = (B Ù C) Ú ((Ø B) Ù D)
f1(B, C, D) = (B Ù D) Ú (C Ù (Ø D))
f2(B, C, D) = B Å C Å D
f3(B, C, D) = C Å (B Ú (Ø D))
Дешифрирование представляет собой обратный процесс. Генерирование подключей является непростой задачей. Вот как по 80-битовому ключу K может быть сгенерирован массив перестановок P.
(1) Проинициализируйте K0, K1, K2, ..., K9 10 байтами K.
(2) For i=10 to 255
Ki = Ki-2 Å Ki-6 Å Ki-7 Å Ki-10
(3) For i=10 to 255, Pi = i
(4) m=0
(5) For j=0 to 1
For i = 256 to 1 step -1
m = (K256-i + K257-i) mod i
K257-i = K257-i <<< 3
Переставить Pi и Pi-1
S-массив из 2048 32-битовых слов может быть сгенерирован аналогичным образом либо по тому же 80_битовому ключу, либо по другому ключу. Авторы предупреждают, что эти детали должны "рассматриваться только в качестве мотивации, могут быть и другие эффективные схемы, обеспечивающие лучшую безопасность" [810].
Crab был предложен как испытательный стенд для новых идей, а не как рабочий алгоритм. Во многом он использует те же приемы, что и MD5. Бихам заметил, что очень большой блок упрощает криптоанализ алгоритма [160]. С другой стороны Crab может позволять эффективно использовать очень большой ключ. В этом случае "упрощение криптоанализа" может ничего не значить.
SXAL8/MBAL
Это 64-битовый блочный алгоритм из Японии [769]. SXAL8 - это основной алгоритм, а MBAL представляет собой расширенную версию с переменной длиной блока. Так как внутри MBAL выполняется ряд умных действий, авторы утверждают, что они могут обеспечить достаточную безопасность за малое число этапов. При длине блока 1024 байта MBAL примерно в 70 раз быстрее, чем DES. К несчастью в [1174] показано, что MBAL чувствителен к дифференциальному криптоанализу, а в [865] - что он чувствителен и к линейному криптоанализу.
RC5
RC5 представляет собой блочный фильтр с большим числом параметров: размером блока, размером ключа и количеством этапов. Он был изобретен Роном Ривестом и проанализирован в RSA Laboratories [1324, 1325].
Используется три действия: XOR, сложение и циклические сдвиги. На большинстве процессоров операции циклического сдвига выполняются за постоянное время, переменные циклические сдвиги являются нелинейной функцией. Эти циклические сдвиги, зависящие и от ключа, и от данных, представляют собой интересную операцию.
RC5 использует блок переменной длины, но в приводимом примере мы остановимся на 64-битовом блоке данных. Шифрование использует 2r+2 зависящих от ключа 32-битовых слов - S0, S1, S2, ... S2r+1 - где r - число этапов. Эти слова мы сгенерируем позднее. Для шифрования сначала разделим блок открытого текста на два 32-битовых слова: A и B. (RC5 предполагает следующее соглашение по упаковке байтов в слова: первый байт занимает младшие биты регистра A, и т.д.) Затем:
A = A + S0
B = B + S1
For i = 1 to r:
A = ((A Å B) <<< B) + S2i
B = ((B Å A) <<< A) + S2i+1
Результат находится в регистрах A и B.
Дешифрирование также просто. Разбейте блок открытого текста на два слова, A и B, а затем:
For i = r down to 1:
B = ((B - S2i+1) >>> A) Å A
A = ((A - S2i) >>> B) Å B
B = B - S1
A = A - S0
Символ ">>>" обозначает циклический сдвиг направо. Конечно же, все сложения и вычитания выполняются по модулю 232.
Создание массива ключей более сложно, но также прямолинейно. Сначала, байты ключа копируются в массив L из c 32-битовых слов, дополняя при необходимости заключительное слово нулями. Затем массив S инициализируется при помощи линейного конгруэнтного генератора по модулю 232:
S0 = P
for i = 1 to 2(r + 1) - 1:
Si = (Si-1 + Q) mod 232
P = 0xb7e15163 и Q = 0x9e3779b9, эти константы основываются на двоичном представлении e и phi.
Наконец, подставляем L в S:
i = j = 0
A = B = 0
выполнить n раз (где n - максимум 2(r + 1) и c):
A = Si = (Si + A + B) <<< 3
B = Li = (Li + A + B) <<< (A + B)
i = (i + 1) mod 2(r + 1)
j = (j + 1 ) mod c
По сути, RC5 представляет собой семейство алгоритмов. Только что мы определили RC5 с 32-битовым словом и 64-битовым блоком, не существуе причин, запрещающих использовать тот же алгоритм с 64-битовым словом и 128-битовым. Для w = 64, P и Q равны 0xb7e151628aed2a6b и 0x9e3779b97f4a7c15, соответственно. Ривест обозначил различные реализации RC5 как RC5-w/r/b, где w - это размер слова, r - число этапов, а b - длина ключа в байтах.
RC5 является новым алгоритмом, но RSA Laboratories потрптила достаточно много времени, анализируя его работу с 64-битовым блоком. После 5 этапов статистика выглядит очень хорошо. После 8 этапов каждый бит открытого текста влияет по крайней мере на один циклический сдвиг. Дифференциальное вскрытие требует 224 выбранных открытых текстов для 5 этапов, 245 для 10 этапов, 253 для 12 этапов и 268 для 15 этапов. Конечно же, существует только 264 возможных открытых текстов, поэтому такое вскрытие неприменимо против алгоритма с 15 и более этапами. Оценка для линейного криптоанализа показывает, что алгоритм безопасен после 6 этапов. Ривест рекомендует использовать не меньше 12 этапов, а лучше 16 [1325]. Это число может меняться.
RSADSI в настоящее время патентует RC5, а это названия заявлено, как торговая марка. Компания утверждает, что плата за лицензирование будет очень мала, но это лучше проверить.
Дата добавления: 2021-01-26; просмотров: 435;