SHARK

SHARK
Создатель	Винсент Рэймен, Йоан Даймен, Барт Пренель, Антун Боссэлерс и Эрик де Вин
Создан	1996 г.
Опубликован	1996 г.
Размер ключа	128 бит
Размер блока	64 бит
Число раундов	6(8)
Тип	Подстановочно-перестановочная сеть

SHARK (англ. Secure Hash Algorithm Regenerative Keys — безопасный хеширующий алгоритм с воссоздающимися ключами) — симметричный алгоритм блочного шифрования, разработанный группой криптографов, среди которых Винсент Рэймен, — автор шифра AES. В теории позволяет использовать блоки и ключи различной длины, однако авторская реализация использует 128-битный ключ и 64-битные блоки. Структура схожа со структурой подстановочно-перестановочной сети.

История SHARK

Шифр SHARK — первый в серии алгоритмов, разработанных в ходе исследования по созданию безопасных и эффективных алгоритмов блочного шифрования на основе метода Wide Trail design strategy. Результатом исследования позже стало создание стандартного шифра AES.

Авторы позиционировали SHARK как алгоритм, призванный заменить широко распространенный в то время шифр DES. К новому алгоритму были предъявлены следующие требования:

• высокая производительность — небольшое число раундов. Для сравнения, в шифре DES использовалось 16 раундов. По словам автором, им удались достичь более чем четырёхкратного ускорения по сравнению с шифрами SAFER и IDEA;
• неуязвимость для линейного и дифференциального криптоанализа, для которых был уязвим DES.

Хотя до этого уже существовали шифры на основе SP-сети (MMB, SAFER, 3-Way), SHARK впервые использовал MDS-коды для линейного преобразования, а именно коды Рида-Соломона.

Существует два варианта шифра SHARK: SHARK-A (англ. affine transform) и SHARK-E (англ. exor), получившие название благодаря различным способам введения раундовых ключей.

Дизайн алгоритма

Концептуальная схема шифра SHARK

Алгоритм SHARK состоит из трех компонентов:

• нелинейный слой — основан на S-блоках;
• слой диффузии — основан на MDS-кодах;
• расписание ключей для получения раундовых ключей из исходного ключа.

Каждый компонент алгоритма рассматривается отдельно и каждый должен обладать определёнными свойствами. Так, слой диффузии должен обладать равномерными и хорошими диффузионными свойствами. Нелинейный слой также должен обладать равномерными нелинейными свойствами, причем компоненты алгоритма независимы в следующем смысле: при изменении реализации, например, нелинейного слоя (одни S-блоки заменяются другими S-блоками c такими же характеристиками), защищенность алгоритма остается неизменной. Такая стратегия является вариантом Wide trail strategy, описанной в докторской диссертации Йоана Даймена.

SHARK состоит из $R$ раундов, дополнительного слоя добавления ключа и дополнительно слоя инвертированной диффузии. Каждый раунд, в свою очередь, состоит из добавления ключа, нелинейной замены и слоя диффузии. Дополнительный слой добавления ключа нужен для того, чтобы злоумышленник не смог отделить последний раунд. Дополнительный слой инвертированной диффузии необходим для упрощения операции дешифрования.

Слой нелинейный замены состоит из $n$ S-блоков, каждый из которых представляет собой $m$-битную перестановку. Таким образом, алгоритм способен шифровать блоки длиной $m\cdot n$.

Слой диффузии

На вход слою диффузии приходят $n$ $m$-битных чисел, которые можно рассматривать как элементы над полем $GF(2^m)$. Рассматриваемый слой необходим для создания лавинного эффекта. Этот эффект проявляется в линейном и разностном контекстах:

• Линейный контекст — нет корреляции между линейной комбинации небольшого набора $m$-битных входных данных и линейной комбинации небольшого набора ($m$-битных) выходных данных.
• Разностный контекст — небольшое изменение входных данных влечет значительное изменение данных на выходе, и наоборот, для небольшого изменения выходных данных нужно значительно изменить входные данные.

Пусть $\theta$ — обратимое линейное преобразование, $a$ — элемент поля $GF(2^m)$, $w_h(a)$ — расстояние Хэмминга, тогда количественно лавинный эффект оценивается числом скачка (англ. branch number) $B(\theta )=\stackrel{}{\underset{a\ne 0}{min}}(w_h(a)+w_h(\theta (a)))$.

Если $w_h(a)=1$, то $B\le n+1$. $B=n+1$ называют оптимальным числом скачка (англ. optimal branch number). В основной статье авторы показали, что с помощью MDS-кодов можно сконструировать обратимое линейное преобразование с оптимальном числом скачка. В реализации используются $(2n,n,n+1)$ коды Рида-Соломона.

Нелинейный слой (блоки подстановок)

Нелинейные S-блоки обеспечивают защиту от линейного и дифференциального криптоанализов. Одним из важных численных характеристик безопасности шифра служит матрица эксклюзивных ИЛИ (англ. exor table) $E$ отображения $\gamma$, элементы которой определяются по формуле $E_{ij}=\mathrm{♯}(x|\gamma (x)\oplus \gamma (i\oplus x)=j)$, где $\mathrm{♯}$ — обозначает число удовлетворяющих условию элементов, $x,i,j$ — элементы поля $GF(2^m)$. Большие значения элементов матрицы могут привести к восприимчивости шифра к дифференциальной атаке.

Авторами были выбраны S-блоки, основанные на отображении $F(x)=x^{-1}$ над полем $GF(2^m)$. В этом случае при четном $m$ матрица $E$ обладает следующими свойствами:

• Дифференциальная 4-стабильность — все элементы матрицы не превосходят 4. В действительности, в каждой строке такой матрицы присутствует ровно один элемент, равный 4, а остальные равны 2 либо 0.
• Минимальное расстояние аффинной функции равно $2^{m/2}$.
• Нелинейный порядок любой линейной комбинации выходных битов равен $m+1$.

Для того чтобы удалить фиксированные точки $0\to 0$ и $1\to 1$, используется обратимое аффинное преобразование выходных бит.

Расписание ключей

Расписание ключей (англ. key scheduling) позволяет расширить исходный ключ $K$, получив $R+1$ раундовых ключей $K_i$. Хорошее планирование позволяет получить раундовые ключи с максимальной энтропией. Авторами предлагаются два способа ввести раундовый ключ:

1. Exor — простое исключающее ИЛИ с входными данными в каждом раунде. Соответствующий алгоритм — SHARK-E.
2. Affine Transformation — aффинное преобразование входных данных, зависящее от ключа. Соответствующий алгоритм — SHARK-A.

Exor

Вычисляется простое исключающее ИЛИ $m\cdot n$ входных бит раунда и $m\cdot n$ подключа. Преимущества метода — быстрота и стабильность: никакой ключ не является сильнее или слабее другого. Недостаток метода — энтропия раундового ключа не превосходит $m\cdot n$.

Affine Transformation

Пусть $k_i$ — невырожденная матрица $n\times n$ над полем $GF(2^m)$, зависящая от ключа $K$ (точнее, от его расширения). Введем ключевую операцию над входными данными следующим образом: $Y(X)=k_i\cdot X\oplus K_i$. Это линейная операция, потому она не вводит слабых ключей. Кроме того, энтропия раундовых ключей увеличивается до $O(m{n}^2)$. Однако, это довольно дорогая в смысле производительности операция, поэтому авторами предлагается ограничить $k_i$ на подпространстве диагональных матриц. В этом случае энтропия раундовых ключей становится близкой к $2mn$.

Генерация подключей

В алгоритме SHARK, генерация раундовых ключей осуществляется следующим образом:

1. $R+1$ раундовых $m\cdot n$-битных ключей $K_i$ инициализируются первыми $R+1$ записями в таблице замещений (англ. substitution table).
2. Матрицы $k_i$ инициализируются единичными матрицами.
3. Выбранный пользователем ключ конкатенируется сам с собой до тех пор, пока не будет иметь длину $2(R+1)mn$ бит.
4. К полученной в п. 3 последовательности применяется алгоритм SHARK в режиме CFB.
5. Первые $(R+1)mn$ бит выходных данных используются для формирования раундовых ключей $K_i$.
6. Последние $(R+1)mn$ бит выходных данных интерпретируются как $(R+1)n$ элементов поля $GF(2^m)$, и формируют диагональные элементы матриц $k_i$. Если какой-нибудь элемент равен нулю, то он отбрасываются, а все следующие элементы сдвигаются вниз на единицу. Дополнительные зашифрованные нулевые строки добавляются в конец, чтобы заполнить оставшиеся диагональные элементы.

Механизм генерации подключей в принципе позволяет использовать ключ длины $2(R+1)mn$ бит, но авторы рекомендуют использовать ключ, не превышающий 128 бит.

Заметки по реализации

Таблицы замещений

Для того, чтобы добиться высокой производительности, слой диффузии и блоки подстановок объединяются в одну операцию. Пусть $X_1,...,X_n$ обозначают входные данные раунда; $Y_1,...,Y_n$ — выходные данные; $S_1,...,S_n$ — матрицы перестановок (S-блоки); $A$ — матрица, определяющая слой диффузии; $\oplus$ и $\cdot$ — обозначают сложение и умножение над полем $GF(2^n)$. Тогда

$\left(\begin{array}{c}{Y}_1\\ ...\\ Y_n\end{array}\right)=A\cdot \left(\begin{array}{c}{S}_1[X_1]\\ ...\\ S_n[X_n]\end{array}\right)=\left(\begin{array}{c}{a}_{11}\\ ...\\ a_{n1}\end{array}\right)\cdot S_1[X_1]\oplus ...\oplus \left(\begin{array}{c}{a}_{1n}\\ ...\\ a_{nn}\end{array}\right)\cdot S_n[X_n]=\left(\begin{array}{c}{a}_{11}\cdot S_1[X_1]\\ ...\\ a_{n1}\cdot S_1[X_1]\end{array}\right)\oplus ...\oplus \left(\begin{array}{c}{a}_{1n}\cdot S_n[X_n]\\ ...\\ a_{nn}\cdot S_n[X_n]\end{array}\right)$

Используя расширенные таблицы замещений $T_i$ размерности $m\times mn$, определяемые по формуле $T_i[X]=\left(\begin{array}{c}{a}_{1i}\cdot S_i[X_i]\\ ...\\ a_{ni}\cdot S_i[X_i]\end{array}\right)$, можно записать преобразование в простом виде: $\left(\begin{array}{c}{Y}_1\\ ...\\ Y_n\end{array}\right)=T_1[X_1]\oplus T_2[X_2]\oplus ...\oplus T_n[X_n]$

Таким образом, один раунд требует $n$ поисков по таблице и $n-1$ бинарных операций. Однако, из-за того что при длине блока $8n$ бит таблицы занимают $n^2\times 256$ байт, алгоритм для блоков длины 128 бит и более оказывался неэффективным для большинства процессоров того времени (1996 год), отсюда происходит существующее ограничение на длину блока в 64 бит ($n=8,m=8$).

Матрица MDS-кода

Для $n=8$ можно построить матрицу, определяющую слой диффузии, на основе кода Рида-Соломона.

$A=\left(\begin{array}{cccccccc}CE& E7& B9& D0& 52& 87& 74& 0B\\ 95& FE& DA& 9D& A9& 28& 51& 31\\ 57& 05& 4D& 26& 07& 3A& 15& 7F\\ 82& D2& D1& 2C& 6C& 5A& CF& 86\\ 8A& 52& 9E& 5D& B9& F4& 09& BE\\ 19& C1& 17& 9F& 8F& 33& A4& 05\\ B0& 88& 83& 6D& 70& 0B& 62& 83\\ 01& F1& 86& 75& 17& 6C& 09& 34\end{array}\right)$

Дешифрование

Для описания дешифрования рассмотрим 2-х раундовую версию SHARK. Пусть $l$ — линейная операция, $s$ — нелинейная замена, $a_{k_i}$ — операция добавления ключа для раундового ключа $k_i$. Функция шифрования, в таком случае, равна $Y=(l^{-1}\circ a_{k_3}\circ l\circ s\circ a_{k_2}\circ \underset{r}{\underbrace{l\circ s}}\circ a_{k_1})(X)$, где $r$ — комбинированная из слоя диффузии и S-блоков операция. Так как операция добавления ключа и операция диффузии — линейные операции, их порядок можно поменять местами:

$(l\circ a_k)(X)=A\cdot (k\cdot X\oplus K)=(A\cdot k\cdot X)\oplus (A\cdot K)=((A\cdot k\cdot A^{-1})\cdot (A\cdot X))\oplus (A\cdot K)=(a_{k^{\prime }}\circ l)(X)$,

где введено обозначение $a_{k^{\prime }}(X)=k^{\prime }\cdot X\oplus K^{\prime }=(A\cdot k\cdot A^{-1})\cdot X\oplus (A\cdot K)$

Применим полученную формулу к $l^{-1}\circ a_{k_3}$:

$Y=(a_{{k_3}^{\prime }}\circ l^{-1}\circ l\circ s\circ a_{k_2}\circ r\circ a_{k_1})(X)=(a_{{k_3}^{\prime }}\circ s\circ a_{k_2}\circ r\circ a_{k_1})(X)$

Теперь покажем, что операция дешифрования имеет ту же структуру. Для этого сначала обратим операцию шифрования:

$X=(a_{k_1^{-1}}\circ s^{-1}\circ l^{-1}\circ a_{k_2^{-1}}\circ s^{-1}\circ l^{-1}\circ a_{k_3^{-1}}\circ l)(Y)$

Меняя местами операцию добавления ключа и операцию диффузии, получаем ту же структуру, что и в операции шифрования:

$X=(a_{k_1^{-1}}\circ s^{-1}\circ a_{k_2^{-1^{\prime }}}\circ \underset{r^{\prime }}{\underbrace{l^{-1}\circ s^{-1}}}\circ a_{k_3^{-1^{\prime }}})(Y)$

Известные атаки

На текущий момент не обнаружено уязвимостей у классической реализации алгоритма. Существуют атаки только на вариации алгоритма:

• В 1997 году Томас Якобсен и Ларс Кнудсен показали, что 64-битная реализация SHARK-E (SHARK с exor стратегией введения раундового ключа) теоретически уязвима для интерполяционной атаки при ограничении на количество раундов до 5, а также 128-битная реализация — при ограничении до 8 раундов. Но они также показали, что для достаточной безопасности необходимо по крайней мере 6 раундов.
• В 2013 году Янг Ши (англ. Yang Shi) и Хонгвей Фан (англ. Hongfei Fan) показали, что White-Box реализация SHARK недостаточно безопасна и может быть взломана с фактором работы примерно 1.5 * (2 ^ 47).

Литература

• Vincent Rijmen, Joan Daemen, Bart Preneel, Antoon Bosselaers, Erik De Win The Cipher SHARK. — The cipher SHARK Архивная копия от 14 декабря 2017 на Wayback Machine.
• Joan Daemen, Vincent Rijmen The Design of Rijndael. — The Design of Rijndael Архивная копия от 14 декабря 2017 на Wayback Machine.
• Thomas Jakobsen, Lars R. Knudsen The interpolation attack on block ciphers. — The interpolation attack on block ciphers Архивная копия от 14 декабря 2017 на Wayback Machine.
• Yang Shi, Hongfei Fan On Security of a White-Box Implementation of SHARK. — On Security of a White-Box Implementation of SHARK Архивная копия от 14 декабря 2017 на Wayback Machine.
• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Handbook of Applied Cryptography. — CRC Press, 1996. — С. 281. — 810 с. — ISBN 9781439821916.