SAFER — Википедия

SAFER
Создатель	Джеймс Мэсси
Создан	1993 г.
Опубликован	1993 г.
Размер ключа	64 (128, 192, 256) бит
Размер блока	64 (40, 128) бит
Число раундов	6-16
Тип	Подстановочно-перестановочная сеть
Медиафайлы на Викискладе

SÁFER (англ. Secure And Fast Encryption Routine — безопасная и быстрая процедура шифрования) — в криптографии семейство симметричных блочных криптоалгоритмов на основе подстановочно-перестановочной сети. Основной вклад в разработку алгоритмов внёс Джеймс Мэсси. Первый вариант шифра был создан и опубликован в 1993 году.

История[править | править код]

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

Первая разновидность алгоритма — SAFER K-64 была разработана Джэймсом Мэсси для калифорнийской корпорации «Cylinc» в 1993 году^[1]. Опубликованный в том же году, алгоритм имел блок и ключ шифрования длиной в 64 бита. Для него рекомендовалось использовать 6 раундов шифрования. Однако, из-за необходимости увеличить длину ключа до 128 бит (так как была обнаружена слабость в первоначальном варианте алгоритма), Мэсси разработал новый вариант шифра SAFER K-128, который был опубликован на следующий год после SAFER K-64. Новый алгоритм включал в себя расписание ключей, разработанное министерством внутренних дел Сингапура, и в дальнейшем использовался им для различных целей. Также для этого алгоритма рекомендовалось использовать 10 (максимум 12) раундов шифрования.

Спустя некоторое время в первых вариантах алгоритма выявились некоторые слабости, обнаруженные Ларсом Кнудсеном и Шоном Мёрфи^[1]. Это повлекло за собой создание новых версий алгоритма, названных SAFER SK-64 и SAFER SK-128, в которых расписание ключей было изменено в соответствии со схемой, предложенной Кнудсеном. Также был разработан вариант с длиной ключа, уменьшенной до 40 бит — SAFER SK-40. Сокращение «SK» в названии алгоритмов расшифровывается как «Strengthened Key schedule» (Усиленное расписание ключей). Для новых вариантов шифра предлагалось использовать не 6, а по крайней мере 8 (максимум 10) раундов шифрования.

Алгоритм SAFER+ был разработан в 1998 году калифорнийской корпорацией Cylinc совместно с Армянской академией наук для участия в конкурсе AES, на котором прошёл лишь первый отборочный тур. Данный шифр имеет входной блок длиной 128 бит и размер ключа 128, 192 или 256 бит.

Последней из созданных разновидностей алгоритма SAFER является SAFER++, разработанный Мэсси в 2000 году и ставший дальнейшим развитием алгоритма SAFER+. Алгоритм принял участие в европейском конкурсе алгоритмов NESSIE, где был представлен в двух вариантах: шифр с 64-битным блоком и 128-битным блоком. Он прошёл во вторую фазу конкурса, но не был выбран в набор рекомендуемых NESSIE криптографических примитивов. Эксперты сочли, что шифр слишком медленный на всех машинах, кроме 8-битных (таких как смарт-карты), а запас безопасности шифра слишком мал^[2][3].

Алгоритмы SAFER не являются частной собственностью и не защищены авторскими правами, то есть могут быть использованы без каких либо ограничений. Поскольку они целиком состоят из простых байтовых операций (за исключением поворота байтов при генерации ключей), эти алгоритмы могут быть реализованы процессорами с малой разрядностью^[4].

Ниже приведена сводная таблица всех существующих вариантов шифра SAFER

SAFER K-64[править | править код]

Алгоритм шифрования[править | править код]

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

Структура одного раунда алгоритма представлена на схеме. Опишем алгоритм поэтапно (ниже i пробегает значения от 1 до r, где r — число раундов шифрования):

1. Входной блок B и оба ключа ${\displaystyle K_{2i-1}}$ и ${\displaystyle K_{2i}}$ разбиваются на 8 частей длиной по одному байту (8 бит). Соответствующие подблоки входного текста и ключа ${\displaystyle K_{2i-1}}$ либо складываются по модулю два (операция XOR) — для подблоков № 1, 4, 5 и 8, либо складываются по обычным правилам (операция сложения байтов по модулю 256) — для подблоков № 2, 3, 6 и 7.
2. Результаты сложения проходят через так называемые S-блоки (S-boxes). Их содержимое представляет собой одну из нелинейных операций: ${\displaystyle y=45^{x}{\mbox{ mod }}257}$ (где y = 0 когда x = 128) либо ${\displaystyle y=log_{45}x}$ (y = 128 когда x = 0). Здесь x — входной байт, y — выходной байт. Данные операции являются операциями в конечном поле GF(257), где 45 — примитивный элемент поля. Поскольку каждый раз рассчитывать результаты этих операций в практических реализациях алгоритма весьма неудобно, как правило используются специально составляемые таблицы для получения результатов их действия.
3. Над результатами предыдущего действия производится операция, аналогичная п.1, с той лишь разницей, что используется второй подключ ${\displaystyle K_{2i}}$, а операции XOR и сложения по модулю 256 меняются местами.
4. Полученные байты проходят через многоуровневую систему преобразований, взаимно складываясь в различном порядке. Это делается для достижения лучшего лавинного эффекта, то есть увеличения зависимости выходных битов от всех битов входного блока. На схеме преобразования представлены в виде сети операций сложения по модулю 256. Эта сеть эквивалентна трём уровням псевдопреобразований Адамара (Pseudo-Hadamard Transform, PHT)^[5]. Каждое преобразование действует таким образом, что при входных байтах ${\displaystyle a_{1}}$ и ${\displaystyle a_{2}}$ на выходе получим:

   ${\displaystyle b_{1}=(2a_{1}+a_{2}){\mbox{ mod }}256}$

   ${\displaystyle b_{2}=(a_{1}+a_{2}){\mbox{ mod }}256}$

По завершении ${\displaystyle r}$ последовательных раундов, над полученным результатом применяется операция, аналогичная п.1, где в качестве ключа используется последний подключ.

Автор алгоритма рекомендует использовать ${\displaystyle r=6}$ раундов, но можно увеличить их количество для увеличения надёжности^[5].

Алгоритм расшифрования[править | править код]

Расшифрование производятся в обратном порядке, но при этом операции заменяются обратными. Так, операции сложения по модулю 256 заменяются операциями вычитания, а сложение по модулю 2 выполняется точно так же, как и при зашифровании. Операции ${\displaystyle 45^{x}{\mbox{ mod }}257}$ и ${\displaystyle log_{45}x}$ меняются местами. Псевдопреобразования Адамара заменяются обратными (Inverse PHT, IPHT), действующими следующим образом:

${\displaystyle a_{1}=(b_{1}-b_{2}){\mbox{ mod }}256}$

${\displaystyle a_{2}=(-b_{1}+2b_{2}){\mbox{ mod }}256}$

Генерация ключей[править | править код]

Первый ключ шифрования ${\displaystyle K_{1}}$ является секретным ключом, задаваемым пользователем. Каждый последующий ключ шифрования ${\displaystyle K_{i+1}}$ получается из предыдущего ${\displaystyle K_{i}}$ по формуле ${\displaystyle K_{i+1}=\left({K_{1}<<<3i}\right)+B_{i+1}}$ (сложение производится по модулю 256, при этом байты складываются отдельно). Здесь операция «${\displaystyle <<<3}$» — побайтовый циклический сдвиг влево на 3 бита, то есть сдвиг происходит внутри каждого отдельного байта ключа. Величина ${\displaystyle B_{i}}$ называется константой этапа шифрования. Получить её можно следующим образом: если ${\displaystyle B_{ij}}$ — j-й байт константы i-го этапа, то все константы этапов выражаются следующей формулой: ${\displaystyle B_{ij}=45^{45^{((9i+j){\mbox{ mod }}256)}{\mbox{ mod }}257}{\mbox{ mod }}257}$^[5]. Получаемые таким образом константы этапов с хорошей точностью ведут себя как случайные числа. Как правило, значения для всех этих констант хранят в специальных таблицах, чтобы уменьшить время на вычисления.

Формальное описание алгоритма генерации ключей:^[6]

ВХОД: 64-битовый ключ ${\displaystyle K=k_{1},\dots ,k_{64}}$; количество раундов ${\displaystyle r}$.

ВЫХОД: 64-битовые подключи ${\displaystyle K_{1},\dots ,K_{2r+1}}$. Байт ${\displaystyle K_{i}[j]}$ — ${\displaystyle j}$-байт ключа ${\displaystyle K_{i}}$ (нумерация слева направо).

1. Пусть ${\displaystyle R[i]}$ — 8-битовые величины. Пусть ${\displaystyle C_{i}[j]}$ — j-й байт константы i-го этапа шифрования.
2. ${\displaystyle (R[1],R[2],\dots ,R[8])\leftarrow (k_{1}\dots k_{8},k_{9}\dots k_{16},k_{57}\dots k_{64})}$.
3. ${\displaystyle (K_{1}[1],K_{1}[2],\dots ,K_{1}[8])\leftarrow (R[1],R[2],\dots ,R[8])}$.
4. Для ${\displaystyle i}$ от ${\displaystyle 2}$ до ${\displaystyle 2r+1}$:
   • для ${\displaystyle j}$ от 1 до 8: ${\displaystyle R[j]\leftarrow R[j]<<<3}$.
   • для ${\displaystyle j}$ от 1 до 8: ${\displaystyle K_{i}[j]\leftarrow R[j]+B_{i}[j]{\mbox{ mod }}256}$.

Криптоанализ алгоритма[править | править код]

Джэймс Мэсси доказал, что после шести раундов шифрования алгоритмом SAFER K-64 обеспечивается абсолютная устойчивость к дифференциальному криптоанализу^[5]. При этом, уже после трёх раундов шифрования линейный криптоанализ также становится неэффективным для взлома^[5].

Несмотря на это, в 1995 году Ларсом Кнудсеном была обнаружена слабость в алгоритме генерации ключей для SAFER K-64. Он показал^[5], что для любого ключа шифрования ${\displaystyle K_{1}}$ можно найти один или несколько (вплоть до девяти) ключей ${\displaystyle K_{2}}$ (отличающихся от него значением лишь одного байта), таких, что при зашифровании двух различных исходных текстов ${\displaystyle M_{1}}$ и ${\displaystyle M_{2}}$ получается один и тот же шифротекст, что можно записать в виде ${\displaystyle E(M_{1},K_{1})=E(M_{2},K_{2})}$. Число различных открытых текстов M, из которых получается один и тот же шифротекст, лежит в промежутке между ${\displaystyle 2^{22}}$ и ${\displaystyle 2^{28}}$ из возможных ${\displaystyle 2^{64}}$ текстов. Таким образом, путём анализа от ${\displaystyle 2^{44}}$ до ${\displaystyle 2^{47}}$ открытых текстов можно вычислить 8 бит секретного ключа длиной 64-бита. Эта атака в дальнейшем была значительно усилена Джоном Келси, Брюсом Шнайером и Дэвидом Вагнером^[en] (англ. David A. Wagner). Авторы атаки утверждали, что алгоритм легко поддаётся атакам на связанных ключах за счёт очень простой и однообразной процедуры генерации подключей^[7].

Это свойство значительно уменьшает надёжность алгоритма SAFER K-64 при использовании его в качестве однонаправленной хеш-функции. Его надёжность как алгоритма шифрования при этом не уменьшается. Тем не менее, эта слабость алгоритма, вместе с атакой, в дальнейшем опубликованной Мёрфи, побудили Мэсси улучшить алгоритм генерации ключей. В результате в сентябре 1995 года им был опубликован алгоритм SAFER SK-64.

Ещё одна сертифицированная атака на алгоритм SAFER K-64 была осуществлена Ларсом Кнудсеном и Томасом Бёрсоном^[en] (англ. Thomas A. Berson)^[6]. Она была рассчитана на исходный текст длиной ${\displaystyle 2^{45}}$, зашифрованный 5 раундами алгоритма SAFER K-64. Хотя эта атака и не была способна взломать шифротекст уже при 6 раундах шифрования, она показала, что криптостойкость алгоритма меньше, чем изначально заявлял Мэсси (он утверждал, что алгоритм является абсолютно стойким к методам линейного криптоанализа).

Французский криптограф Серж Водено^[fr] (фр. Serge Vaudenay) показал, что при замене содержимого S-блоков случайными перестановками, алгоритм SAFER K-64 становится менее криптостойким^[6].

SAFER K-128[править | править код]

Алгоритм отличается от SAFER K-64 только длиной пользовательского ключа и, соответственно, самим способом генерации ключей. Этот способ был разработан Министерством внутренних дел Сингапура^[5] и впоследствии использован Джеймсом Мэсси в его алгоритме.

Генерация ключей[править | править код]

В этом алгоритме вместо одного ключа длиной 64 бита используется ключ длиной 128 бит, что эквивалентно заданию двух ключей длиной по 64 бита. Из этих двух ключей по методу, крайне схожему с использованным в шифре SAFER K-64, генерируются две независимые последовательности подключей. Ключи из этих последовательностей попеременно используются на всех раундах шифрования.

Как видно из схемы, на каждом этапе происходит побитовый сдвиг байтов ключа не на 3, а на 6 бит. Это приводит к тому, что, задавшись одинаковыми начальными ключами ${\displaystyle K_{a}=K_{b}}$, получим, что 128-битовый ключ совместим с 64-битовым ключом ${\displaystyle K_{a}}$. То есть, используя ключ вида ${\displaystyle K_{a}K_{a}}$ в алгоритме SAFER K-128 и ключ ${\displaystyle K_{a}}$ в SAFER K-64, получим одинаковые последовательности подключей, а значит и само шифрование в SAFER K-128 ничем не будет отличаться от такового в SAFER K-64.

Криптоанализ[править | править код]

При всей схожести алгоритма SAFER K-128 с его предшественником, существует и ряд отличий. Так, в новой версии алгоритма Джеймс Мэсси рекомендует использовать уже не 6, а 10 (максимум 12) раундов шифрования^[7]. Это связано с тем, что при меньшем количестве итераций алгоритм, так же как и SAFER K-64, подвержен атаке, осуществлённой Ларсом Кнудсеном. Напомним, что она касается использования алгоритма в качестве основы для хеш-функции. Увеличение же количества раундов шифрования, по мнению автора, значительно повышает криптостойкость алгоритма в этом смысле^[7].

SAFER SK-64[править | править код]

Данный алгоритм отличается от SAFER K-64 лишь способом генерации подключей. Этот способ был предложен Ларсом Кнудсеном, после того как им же была найдена атака на алгоритм SAFER K-64. Рекомендуемое количество раундов шифрования увеличено по сравнению с изначальным вариантом с 6 до 8^[7]. Различия в способах расширения ключа хорошо видны при формальном описании алгоритма:

Формальное описание алгоритма генерации ключей:^[6]

ВХОД: 64-битовый ключ ${\displaystyle K=k_{1},\dots ,k_{64}}$; количество раундов ${\displaystyle r}$.

ВЫХОД: 64-битовые подключи ${\displaystyle K_{1},\dots ,K_{2r+1}}$. Байт ${\displaystyle K_{i}[j]}$ — ${\displaystyle j}$-байт ключа ${\displaystyle K_{i}}$ (нумерация слева направо).

1. Пусть ${\displaystyle R[i]}$ — 8-битовые величины. Пусть ${\displaystyle B_{i}[j]}$ — ${\displaystyle j}$-байт константы ${\displaystyle i}$-го этапа шифрования.
2. ${\displaystyle (R[1],R[2],\dots ,R[8])\leftarrow (k_{1}\dots k_{8},k_{9}\dots k_{16},k_{57}\dots k_{64})}$; ${\displaystyle R[9]\leftarrow R[1]+R[2]+\dots +R[8]}$ (сложение производится по модулю 2).
3. ${\displaystyle (K_{1}[1],K_{1}[2],\dots ,K_{1}[8])\leftarrow (R[1],R[2],\dots ,R[8])}$
4. Для ${\displaystyle i}$ от ${\displaystyle 2}$ до ${\displaystyle 2r+1}$:
   • для ${\displaystyle j}$ от 1 до 9: ${\displaystyle R[j]\leftarrow R[j]<<<3}$.
   • для ${\displaystyle j}$ от 1 до 8: ${\displaystyle K_{i}[j]\leftarrow R[((i+j-2){\mbox{ mod }}9)+1]+B_{i}[j]{\mbox{ mod }}256}$.

Главной отличительной чертой этого алгоритма является использование дополнительного байта ${\displaystyle R[9]}$, который получается из побитового сложения восьми байт ключа. Далее, на каждом этапе алгоритма происходит циклический сдвиг этих байтов, в результате получается, что подключ ${\displaystyle K_{1}}$ зависит от байтов ${\displaystyle R[1],R[2],\dots ,R[8]}$, подключ ${\displaystyle K_{2}}$ — от байтов ${\displaystyle R[2],R[3],\dots ,R[9]}$, подключ ${\displaystyle K_{3}}$ — от байтов ${\displaystyle R[3],\dots ,R[9],R[1]}$ и т. д. Побитовый сдвиг на 3 бита и структура констант шифрования остаются без изменений.

Криптоанализ[править | править код]

Такие, казалось бы, незначительные изменения в алгоритме генерации ключей, значительно повышают криптостойкость алгоритма. В настоящее время не известны атаки на алгоритмы SAFER SK-64 и SAFER SK-128 более эффективные, чем полный перебор ключей^[7].

При этом существуют атаки, направленные на урезанные версии этих алгоритмов. Приведём некоторые из них:^[7]

• Атака на SAFER SK-64 с 3,75 раундами. Имеется в виду, что при шифровании таким алгоритмом сначала осуществляются 3 раунда, а в четвёртом раунде опускаются линейные преобразования PHT. В ней используется метод т. н. невозможных дифференциалов^[8], относящийся к методам дифференциального криптоанализа. Для его применения нужно задействовать ${\displaystyle 2^{32}}$ пробных открытых текстов и ${\displaystyle 2^{62}}$ тестовых операций шифрования^[9].
• Square-атака на SAFER SK-64 и SK-128 с 3,25 раундами. Здесь имеется в виду, что на четвёртом раунде происходит лишь подмешивание первого из двух ключей. Она использует ${\displaystyle 2^{10,3}}$ пробных открытых текстов и ${\displaystyle 2^{38}}$ тестовых операций шифрования.^[9]
• Атака на SAFER SK-128 с 4,75 раундами, применяющая методы линейного криптоанализа. Атака требует ${\displaystyle 2^{64}}$ открытых текстов и ${\displaystyle 2^{90}}$ тестовых операций шифрования^[10].

Как видно, все эти атаки не очень практичны, поскольку требуют достаточно больших ресурсов и времени.

SAFER SK-128[править | править код]

Данный алгоритм шифрования отличается от SAFER SK-64 точно таким же образом, каким SAFER K-128 отличается от SAFER K-64. А именно, сами алгоритмы шифрования и генерации подключей остаются прежними, но вместо одного исходного ключа длиной в 64 бита используется два таких ключа, для каждого из которых независимо формируются последовательности подключей, которые затем применяются поочерёдно. При этом каждая последовательность для чётных и для нечётных ключей аналогична по структуре алгоритму расширения ключа в SAFER SK-64. В ней точно так же на первом этапе вводится дополнительный байт, являющийся суммой по модулю 2 остальных восьми байт, и затем на каждом этапе происходит побайтовый циклический сдвиг.

Как и для алгоритмов SAFER K-64 и SAFER K-128, при использовании пользовательского ключа вида ${\displaystyle K_{a}K_{a}}$ в SAFER SK-128 и ключа ${\displaystyle K_{a}}$ в SAFER SK-64, действие алгоритмов оказывается совершенно одинаковым. При этом количество раундов шифрования, рекомендуемое для SAFER SK-128, остаётся таким же, как и в SAFER K-128, и равно 10^[7].

SAFER SK-40[править | править код]

Данный вариант шифра использует уменьшенный ключ длиной всего 40 бит (5 байт). Это позволяло алгоритму обойти экспортные ограничения, существовавшие на тот момент в США. Алгоритм работает практически таким же образом, как и SAFER SK-64, с одним небольшим отличием на начальном этапе генерации подключей.

В алгоритме SAFER SK-64 к 8 байтам исходного ключа приписывался девятый байт, равный их побитовой сумме по модулю 2. В SAFER SK-40 эти 9 байт получаются совершенно иначе. Обозначим их ${\displaystyle KI_{1}}$, ${\displaystyle KI_{2}}$, … ${\displaystyle KI_{9}}$. Первые 5 из них — это байты исходного ключа. Остальные 4 байта получаются из первых следующим образом^[11]:

${\displaystyle KI_{6}=KI_{1}\oplus KI_{3}\oplus 129}$,

${\displaystyle KI_{7}=KI_{1}\oplus KI_{4}\oplus KI_{5}\oplus 66}$,

${\displaystyle KI_{8}=KI_{2}\oplus KI_{3}\oplus KI_{5}\oplus 36}$,

${\displaystyle KI_{9}=KI_{2}\oplus KI_{4}\oplus 24}$;

Первый подключ ${\displaystyle K_{1}}$ получается из первых восьми полученных байт. Последующие подключи генерируются с их использованием точно таким же образом, как и в алгоритме SAFER SK-64.

SAFER+[править | править код]

SAFER+ представляет собой улучшенный вариант алгоритмов семейства SAFER. Алгоритм разработан в 1998 году для участия в конкурсе на стандарт AES. Над его созданием совместно трудились специалисты из калифорнийской корпорации Cylinc (Джеймс Мэсси) и Академии наук республики Армении (Гурген Хачатрян и Мельсик Курегян)^[2].

В конкурсе AES алгоритм прошёл первый отборочный тур наряду с 14 другими алгоритмами. В финал конкурса, к которому допускались лишь 5 алгоритмов, SAFER+ не прошёл, поскольку по результатам тщательного анализа оказалось, что он подвержен ряду атак и имеет низкую скорость выполнения^[12]. Алгоритм создавался для работы на 8-битных процессорах, и как следствие, достаточно медленно работает на 32-битных процессорах^[3].

SAFER+ обрабатывает данные 128-битным блоком. Алгоритм поддерживает 128, 192 и 256-битные ключи в соответствии с требованиями, предъявленными Национальным институтом стандартов и технологий США (NIST)^[13]. Количество раундов шифрования зависит от размера ключа:

• 8 раундов для 128-битного ключа;
• 12 раундов для 192-битного ключа;
• 16 раундов для 256-битного ключа.

Алгоритм шифрования[править | править код]

По структуре алгоритм SAFER+ напоминает SAFER K-64. Он состоит из тех же основных этапов, несколько отличающихся по своей структуре. На каждом раунде работы алгоритма сначала происходит подмешивание одного подключа, после этого байты проходят через блоки нелинейной замены, затем подмешивается второй подключ и происходит линейное перемешивание байтов. Подключи последовательно генерируются с использованием входного ключа. Ниже приведено более подробное описание работы одной итерации (i — номер итерации):

1. Наложение ключа ${\displaystyle K_{2i-1}}$: байты входного блока складываются с байтами ключа ${\displaystyle K_{2i-1}}$, причём используется сложение по модулю 2 для байтов с номерами 1, 4, 5, 8, 9, 12, 13 и 16, и сложение по модулю 256 для байтов с номерами 2, 3, 6, 7, 10, 11, 14 и 15.
2. Нелинейное преобразование: к байтам с номерами 1, 4, 5, 8, 9, 12, 13 и 16 применяется операция ${\displaystyle 45^{x}(mod257)}$ (причём ${\displaystyle 45^{128}(mod257)=256}$ заменяется нулём). К байтам с номерами 2, 3, 6, 7, 10, 11, 14 и 15 применяется операция ${\displaystyle log_{45}(x)}$ (причём ${\displaystyle log_{45}(0)=128}$). результаты действия этих операций как и для других разновидностей алгоритма SAFER на практике часто хранят в специальных таблицах. В данном случае для этого требуется 512 байт.
3. Наложение ключа ${\displaystyle K_{2i}}$: байты входного блока складываются с байтами ключа ${\displaystyle K_{2i}}$, но в отличие от п.1 операции сложения по модулю 2 и по модулю 256 меняются местами.
4. Линейное преобразование: умножение 16-байтного блока данных справа на специальную невырожденную матрицу M (все операции при этом байтовые и производятся по модулю 256). Умножение на эту матрицу эквивалентно четырём уровням преобразования PHT, между которыми выполняются некоторые байтовые перестановки^[2]. Эта часть алгоритма является наиболее громоздкой с вычислительной точки зрения.

После проведения r раундов шифрования производится подмешивание ключа ${\displaystyle K_{2r+1}}$, аналогичное подмешиванию ключей ${\displaystyle K_{2i-1}}$.

Алгоритм расшифрования[править | править код]

Операции в алгоритме расшифрования подобны операциям шифрования и производятся в обратном порядке. Разница состоит в следующем:

1. Вместо матрицы ${\displaystyle M}$ умножение происходит с обратной ей матрицей ${\displaystyle M^{-1}}$;
2. Все операции сложения по модулю 256 заменяются операциями вычитания;
3. Операции ${\displaystyle 45^{x}{\mbox{ (mod }}257)}$ и ${\displaystyle log_{45}x}$ (являющиеся обратными друг другу) меняются местами.

При расшифровании используется обратная матрица ${\displaystyle M^{-1}}$:^[13]

2	−2	1	−2	1	−1	4	−8	2	−4	1	−1	1	−2	1	−1
−4	4	−2	4	−2	2	−8	16	−2	4	−1	1	−1	2	−1	1
1	−2	1	−1	2	−4	1	−1	1	−1	1	−2	2	−2	4	−8
−2	4	−2	2	−2	4	−1	1	−1	1	−1	2	−4	4	−8	16
1	−1	2	−4	1	−1	1	−2	1	−2	1	−1	4	−8	2	−2
−1	1	−2	4	−1	1	−1	2	−2	4	−2	2	−8	16	−4	4
2	−4	1	−1	1	−2	1	−1	2	−2	4	−8	1	−1	1	−2
−2	4	−1	1	−1	2	−1	1	−4	4	−8	16	−2	2	−2	4
1	−1	1	−2	1	−1	2	−4	4	−8	2	−2	1	−2	1	−1
−1	1	−1	2	−1	1	−2	4	−8	16	−4	4	−2	4	−2	2
1	−2	1	−1	4	−8	2	−2	1	−1	1	−2	1	−1	2	−4
−1	2	−1	1	−8	16	−4	4	−2	2	−2	4	−1	1	−2	4
4	−8	2	−2	1	−2	1	−1	1	−2	1	−1	2	−4	1	−1
−8	16	−4	4	−2	4	−2	2	−1	2	−1	1	−2	4	−1	1
1	−1	4	−8	2	−2	1	−2	1	−1	2	−4	1	−1	1	−2
−2	2	−8	16	−4	4	−2	4	−1	1	−2	4	−1	1	−1	2

Генерация ключей[править | править код]

Излагаемый алгоритм применим для входных ключей длиной в 128, 192 и 256 бит (16, 24 и 32 байт соответственно). Первый подключ ${\displaystyle K_{1}}$ представляет собой первые 16 байт входного ключа. Генерация остальных ключей производится следующим образом: сначала исходный ключ целиком записывается в ключевой регистр длиной на 1 байт длиннее самого ключа (то есть длина регистра равна для разных входных ключей 17, 25 или 33 байтам). Все байты ключа суммируются по модулю 2 поразрядно, результат записывается в последний байт регистра. Для получения каждого следующего ключа над содержимым регистра выполняются следующие операции (для i от 2 до 2r+1):

1. Содержимое байтов ключевого регистра циклически сдвигается влево на 3 позиции (сдвиг происходит внутри байтов в отдельности, а не регистра как целого);
2. Из регистра выбираются 16 байт. При этом для ключа ${\displaystyle K_{i}}$ выбираются байты регистра начиная с i-го и далее по циклу.
3. Отобранные 16 байт складываются по модулю 256 с байтами слова смещения ${\displaystyle B_{i}}$ (смотри ниже). Результат сложения и будет являться подключом ${\displaystyle K_{i}}$.

Слова смещения ${\displaystyle B_{i}}$ — это 16-байтные константы, вычисляемые по следующей формуле: ${\displaystyle B_{i,j}={\begin{cases}45^{45^{17i+j}{\mbox{ mod }}257}{\mbox{ mod }}257,&i{\mbox{ = 2,3,... 17; }}j{\mbox{ = 1,3,... 16}}\\45^{17i+j}{\mbox{ mod }}257,&i{\mbox{ = 18,19,... 33; }}j{\mbox{ = 1,3,... 16}}\end{cases}}}$

${\displaystyle B_{i,j}}$ — j-й байт i-го слова смещения. Если ${\displaystyle B_{i,j}=256}$ то этот байт заменяется на 0.

Понятно, что поскольку для различных длин ключей количество итераций шифрования различно (и равно 8, 12 и 16 для ключей длиной 128, 192 и 256 бит соответственно), то и использованы будут не все блоки смещения. Так, при длине ключа в 128 бит будут использованы только ${\displaystyle B_{2}}$, … ${\displaystyle B_{17}}$, для ключа в 192 бита — ${\displaystyle B_{2}}$, … ${\displaystyle B_{25}}$, а для ключа в 256 бит — все слова смещения.

Криптоанализ[править | править код]

В связи с участием алгоритма SAFER+ в конкурсе AES, к его криптоанализу было обращено весьма пристальное внимание криптологов. В результате было найдено несколько атак на алгоритм. Перечислим некоторые из них:

• Атака на SAFER+ с длиной входного ключа равной 256. Для её осуществления необходимо знать всего 3 открытых текста и соответствующих им шифротекста, но при этом требуется провести ${\displaystyle 2^{240}}$ тестовых операций шифрования. Понятно, что такое колоссальное количество операций делает атаку абсолютно непрактичной. Тем не менее, она показывает, что алгоритм SAFER+ обладает недостаточным запасом прочности^[14].
• Атака на связанных ключах, требующая около ${\displaystyle 2^{200}}$ тестовых операций шифрования. Также является неосуществимой с практической точки зрения. Сами авторы этих двух атак предложили способ усиления алгоритма SAFER+, полностью защищающий от этих атак.^[14] Способ заключается в усилении процедуры генерации подключей.
• Атака методами дифференциального криптоанализа по потребляемой мощности^[15][16].
• Атаки на усечённые версии SAFER+^[9][10].

В ходе конкурса AES алгоритм SAFER+ был охарактеризован следующим образом:^[2]

• Плюсы алгоритма:
  1. большой запас криптостойкости (особенно с применением усиленной процедуры расширения ключей);
  2. низкие требования к вычислительным ресурсам, что позволяет применять алгоритм в маломощных устройствах, таких как смарт-карты;
• Недостатки алгоритма:
  1. низкая скорость шифрования, достаточно медленная процедура генерации подключей;
  2. уязвимость для атак по потребляемой мощности.

SAFER++[править | править код]

Алгоритм является дальнейшим развитием SAFER+, и практически полностью наследует его структуру. Различия заключаются в основном в оптимизации (с точки зрения облегчения вычислений) некоторых участков алгоритма. Он использует меньшее число раундов: семь для 128-битного ключа и десять для 256-битного ключа. Длина блока в этом шифре равна 128 битам, но помимо этого предусматривается режим «обратной совместимости» при использовании блоков длиной 64 бита.

Алгоритм прошёл во вторую фазу конкурса NESSIE, но не был выбран в набор рекомендуемых NESSIE криптографических примитивов. Эксперты сочли, что шифр слишком медленный на всех машинах, кроме смарт-карт, а запас безопасности шифра слишком мал^[17].

Алгоритм[править | править код]

Значительная часть процедуры шифрования ничем не отличается от таковой в алгоритме SAFER+. Главное различие заключается в процедуре линейного преобразования, которая была значительно оптимизирована с вычислительной точки зрения (в SAFER+ необходимо производить перемножение с матрицей размеров 16x16, что требует большого количества операций побайтового сложения).

Линейное преобразование, как видно из схемы, состоит из следующих этапов:

1. 16 входных байтов перемешиваются в следующем порядке: [9, 6, 3, 16, 1, 14, 11, 8, 5, 2, 15, 12, 13, 10, 7, 4];
2. Байты в новом порядке разбиваются на группы по 4. Каждая группа подвергается 4-точечному псевдопреобразованию Адамара;
3. После преобразования байты вновь перемешиваются в том же порядке, что и в п.1;
4. Аналогично п.2 байты снова проходят через псевдопреобразования Адамара. Результат подаётся на выход.

Псевдопреобразование Адамара заключается в умножении 4-байтовой строки на невырожденную матрицу 4x4, которая имеет следующую структуру:

${\displaystyle H_{4}={\begin{bmatrix}2&1&1&1\\1&2&1&1\\1&1&2&1\\1&1&1&1\end{bmatrix}}}$.

Обратная матрица, используемая при расшифровании, имеет вид

${\displaystyle H_{4}^{-1}={\begin{bmatrix}1&0&0&-1\\0&1&0&-1\\0&0&1&-1\\-1&-1&-1&4\end{bmatrix}}}$

Преимущество такого подхода по сравнению с умножением на матрицу 16x16, используемую в SAFER+, состоит в том, что для линейного преобразования, в силу структуры матриц преобразования Адамара, требуется значительно меньшее количество элементарных операций. А именно, при умножении 16-байтовой строки на матрицу 16x16 в общем случае требуется 15*16 операций сложения и 16*16 операций умножения. Умножение же на матрицу Адамарова преобразования требует всего лишь 6 операций сложения:^[13]

Если a, b, c, d — входные байты, A, B, C, D — выходные байты, то вычисления представимы формулами (сложение производится по модулю 256):

${\displaystyle D=a+b+c+d}$ (3 операции сложения),

${\displaystyle A=D+a}$ (1 операция сложения),

${\displaystyle B=D+b}$ (1 операция сложения),

${\displaystyle C=D+c}$ (1 операция сложения).

Таким образом, даже принимая во внимание, что умножение на матрицу ${\displaystyle H_{4}}$ производится 8 раз, получаем всего 6*8=48 операций, что значительно меньше, чем в SAFER+ (даже с учётом всех производимых байтовых перестановок в алгоритме SAFER++).

Всю структуру линейного преобразования можно, так же, как и в SAFER+, представить в виде невырожденной матрицы 16x16. Однако, большинство элементов в этой матрице будет равно единице. В обратной матрице, необходимой для совершения процедуры расшифрования, большинство элементов будет равно нулю.

Генерация ключей[править | править код]

Существуют также некоторые отличия от SAFER+ в алгоритме генерации подключей, используемых на различных раундах шифрования. В этом плане различия между SAFER+ и SAFER++ подобны различиям между SAFER K-64 и SAFER K-128, в том смысле, что в SAFER++ чётные и нечётные подключи генерируются независимо друг от друга. Рассмотрим алгоритм более детально.

Используются 2 ключевых регистра длиной 16+1=17 байт. В случае, если длина пользовательского ключа равна 128 битам (16 байт), в оба регистра изначально записывается этот ключ. Если же длина ключа равна 256 битам (32 байта), в первый регистр вписываются байты ключа с 1-го по 16-й, а во второй — с 17-го по 32-й. На место 17-го байта в каждый регистр вписывается байтовая контрольная сумма от первых 16-и байт. После этого для i от 1 до ${\displaystyle 2r+1}$ (r — количество раундов шифрования) производятся следующие действия (для i = 1,3, … 2r+1 рассматривается первый регистр, для i = 2,4, … 2r — второй регистр):

1. Выбираются 16 байт из регистра, начиная с номера i и далее по циклу. Так, для ключа с номером i=5 байты будут выбраны следующим образом: [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 1, 2, 3],
2. Полученные байты складываются с соответствующим словом смещения ${\displaystyle B_{i}}$ (смотри ниже)
3. Содержимое всех байтов регистра циклически сдвигается на 6 бит в случае нечётного i, и на 3 бита в случае чётного i.

Слова смещения вычисляются практически так же, как и в SAFER+, с той лишь разницей, что изменяются диапазоны изменения параметра i: ${\displaystyle B_{i,j}={\begin{cases}45^{45^{17i+j}{\mbox{ mod }}257}{\mbox{ mod }}257,&i{\mbox{ = 2,3,... 15; }}j{\mbox{ = 1,2,... 16}}\\45^{17i+j}{\mbox{ mod }}257,&i{\mbox{ = 16,17,... 21; }}j{\mbox{ = 1,2,... 16}}\end{cases}}}$

Криптоанализ[править | править код]

В рамках конкурса NESSIE алгоритм SAFER++ был тщательно исследован на криптостойкость. По заключению экспертов уязвимости предшествующего ему алгоритма SAFER+ не были унаследованы. Для полнораундового алгоритма SAFER++ не было найдено никаких новых атак. При этом был осуществлён ряд атак на варианты шифра с уменьшенным числом раундов шифрования^[9][18][19] Одна из них, будучи неосуществимой вследствие огромного числа необходимых вычислений, теоретически способна взломать SAFER++ с 5,5 раундами вместо семи.^[20]. Эта атака послужила одной из основных причин, по которым алгоритм не победил в конкурсе. Также, по мнению некоторых экспертов, алгоритм вполне может содержать невыявленные на настоящий момент слабости. Основной же причиной явилось недостаточное быстродействие алгоритма при реализации на многоразрядных устройствах.

Практическое использование[править | править код]

Хотя алгоритмы SAFER не получили статуса стандартов в США или ЕС, они нашли весьма широкое применение. В частности, SAFER+ используется в качестве основы протокола аутентификации в Bluetooth. Однако, в самом алгоритме шифрования в Bluetooth этот алгоритм не используется^[1].

Несмотря на то, что в названии алгоритма фигурирует слово «fast» (быстрый), по современным меркам алгоритмы семейства SAFER являются достаточно медленными.

С точки зрения криптостойкости даже самая первая версия алгоритма SAFER K-64 является абсолютно устойчивой к дифференциальному криптоанализу. Последний алгоритм семейства — SAFER++, будучи значительно модифицированным с учетом множества атак, осуществленных на более ранние версии алгоритма, стал ещё более устойчивым. В настоящее время никаких реально осуществимых атак на алгоритм не найдено^[1].

Учитывая, насколько далеко продвинулись алгоритмы SAFER за время своего существования — от SAFER K-64 до SAFER++, можно предположить, что на этом развитие этих алгоритмов не закончено^[2].

Примечания[править | править код]

Литература[править | править код]

• Massey J. SAFER K-64: A byte-oriented block-ciphering algorithm (англ.) // Fast Software Encryption: Cambridge Security Workshop Cambridge, U. K., December 9–11,1993 Proceedings / R. J. Anderson — Berlin: Springer Berlin Heidelberg, 1994. — P. 1—17. — (Lecture Notes in Computer Science; Vol. 809) — ISBN 978-3-540-58108-6 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-58108-1_1
• Menezes A. J., Oorschot P. v., Vanstone S. A. Handbook of Applied Cryptography (англ.) — CRC Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0
• Biham E., Shamir A. Power Analysis of the Key Scheduling of the AES Candidates (англ.) // Second Advanced Encryption Standard Candidate Conference: Rome, Italy, March 22–23, 1999 — Gaithersburg: NIST, 1999.
• Chari S., Jutla C., Rao J. R., Rohatgi P. A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards (англ.) // Second Advanced Encryption Standard Candidate Conference: Rome, Italy, March 22–23, 1999 — Gaithersburg: NIST, 1999. — P. 133—147.
• Kelsey J., Schneier B., Wagner D. A. Key Schedule Weakness in SAFER+ (англ.) // Second Advanced Encryption Standard Candidate Conference: Rome, Italy, March 22–23, 1999 — Gaithersburg: NIST, 1999.
• Шнайер Б. Глава 14. И ещё блочные шифры // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 382—384. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• Mukherjee S., Ganguly D., Naskar S. A New Generation Cryptographic Technique (англ.) // International Journal of Computer Theory and Engineering — Singapore: 2009. — Vol. 1, Iss. 2. — P. 284—287. — ISSN 1793-8201
• Баричев С. Г., Гончаров В. В., Серов Р. Е. Основы современной криптографии — 3-е изд. — М.: Диалог-МИФИ, 2011. — С. 36—41. — 176 с. — ISBN 978-5-9912-0182-7

Ссылки[править | править код]

На русском языке[править | править код]

• Панасенко С.П. Эволюция алгоритмов шифрования  (рус.) (15 июня 2007). — Статья с подробным рассмотрением алгоритмов SAFER K-64/128 и SAFER SK-64/128. Дата обращения: 12 ноября 2009. (недоступная ссылка)
• Горбенко И.Д., Головашич С.А., Лепеха А.Н. Сравнительный анализ симметричных шифров  (рус.) (2004). — сравнительный анализ блочных симметричных шифров, представленных в проекте NESSIE (включая SAFER++). Дата обращения: 12 ноября 2009. Архивировано из оригинала 16 июня 2012 года.

На других языках[править | править код]

• NESSIE New European Schemes for Signatures, Integrity, and Encryption (англ.). — Официальный сайт «NESSIE». Дата обращения: 12 ноября 2009.
• NIST official site (англ.). — Официальный сайт NIST. Дата обращения: 12 ноября 2009. Архивировано 18 августа 2011 года.
• Edward Roback, Morris Dworkin. first advanced encryption standsrd (AES) candidate conference (англ.) (20 августа 1998). — перечень участников конкурса AES, включая SAFER+. Дата обращения: 12 ноября 2009. Архивировано 30 января 2012 года.
• John Savard. Towards the 128-bit Era: AES Candidates, SAFER+ (англ.). — описание алгоритма SAFER+. Дата обращения: 12 ноября 2009. Архивировано 30 января 2012 года.
• John Savard. SAFER (Secure And Fast Encryption Routine) (англ.). — описание алгоритмов SAFER K и SAFER SK. Дата обращения: 12 ноября 2009. Архивировано 30 января 2012 года.
• SCAN’s entry for SAFER K (англ.). Дата обращения: 12 ноября 2009. Архивировано 28 января 2012 года.
• SCAN’s entry for SAFER SK (англ.). Дата обращения: 12 ноября 2009. Архивировано 28 января 2012 года.
• SCAN’s entry for SAFER+ (англ.). Дата обращения: 12 ноября 2009. Архивировано 28 января 2012 года.
• SCAN’s entry for SAFER++ (англ.). Дата обращения: 12 ноября 2009. Архивировано 28 января 2012 года.
• Lars Knudsen. Announcement by James L. Massey of a strengthened key schedule for the cipher SAFER (англ.) (12 сентября 1995). — описание усиленного алгоритма расширения ключа для SAFER SK, примеры реализации, исходные коды. Дата обращения: 12 ноября 2009.
• Gilles Piret and Jean-Jacques Quisquater. Integral Cryptoanalysis on reduced-round SAFER++ (англ.). — Интегральный криптоанализ SAFER++. Дата обращения: 12 ноября 2009. Архивировано 30 января 2012 года.
• James L. Massey. On the Optimality of SAFER+ Diffusion. (англ.). Cylink Corporation, Sunnyvale, CA, USA. — Анализ оптимальности диффузионной части алгоритма SAFER+. Дата обращения: 12 ноября 2009. Архивировано 18 августа 2011 года.
• Gustaf Dellkrantz. Cryptanalysis of Symmetric Block Ciphers — Breaking Reduced KHAZAD and SAFER++ (англ.). — криптоанализ урезанной версии SAFER++. Дата обращения: 12 ноября 2009. Архивировано 30 января 2012 года.
• Gurgen Khachatrian, Melsik Kuregian, Karen Ispiryan, James Massey. Differential analysis of SAFER++ algorithm // Second NESSIE workshop, Egham, UK. — Сентябрь 12-13, (2001).
• Richard De Moliner. Block-cipher algorithm SAFER (англ.). — Реализация на языке C алгоритмов SAFER-K64, SAFER-K128, SAFER-SK64, SAFER-SK128. (недоступная ссылка)
• James L. Massey, Gurgen H. Khachatrian, Melsik K. Kuregian. Nomination of SAFER+ as Candidate Algorithm for the Advanced Encryption Standatd (AES) (англ.) (pdf) (12 июня 1998). — Описание алгоритма SAFER+. Дата обращения: 24 декабря 2009. Архивировано 30 января 2012 года.
• Gurgen Khachatrian, Melsik Kuregian, Karen Ispiryan, James Massey, «Differential analysis of SAFER++ algorithm» — Second NESSIE workshop, Egham, UK, September 12-13, (2001)
• Karen Ispiryan «Some family of coordinate permutation for SAFER++» CSIT September 17-20, 2001 Yerevan, Armenia

Эта статья входит в число хороших статей русскоязычного раздела Википедии.