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 )={\overset {}{\underset {a\neq 0}{min}}}({\displaystyle w_{h}(a)}+{\displaystyle w_{h}(\theta (a))})$.

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

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

Нелинейные S-блоки обеспечивают защиту от линейного и дифференциального криптоанализов. Одним из важных численных характеристик безопасности шифра служит матрица эксклюзивных ИЛИ (англ. exor table) $E$ отображения $\gamma$, элементы которой определяются по формуле $E_{ij}=\sharp (x|\gamma (x)\oplus \gamma (i\oplus x)=j)$, где $\sharp$ — обозначает число удовлетворяющих условию элементов, $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\rightarrow 0$ и $1\rightarrow 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(mn^{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})$. Тогда

${\begin{pmatrix}Y_{1}\\...\\Y_{n}\end{pmatrix}}=A\cdot {\begin{pmatrix}S_{1}[X_{1}]\\...\\S_{n}[X_{n}]\end{pmatrix}}={\begin{pmatrix}a_{11}\\...\\a_{n1}\end{pmatrix}}\cdot S_{1}[X_{1}]\oplus ...\oplus {\begin{pmatrix}a_{1n}\\...\\a_{nn}\end{pmatrix}}\cdot S_{n}[X_{n}]={\begin{pmatrix}a_{11}\cdot S_{1}[X_{1}]\\...\\a_{n1}\cdot S_{1}[X_{1}]\end{pmatrix}}\oplus ...\oplus {\begin{pmatrix}a_{1n}\cdot S_{n}[X_{n}]\\...\\a_{nn}\cdot S_{n}[X_{n}]\end{pmatrix}}$

Используя расширенные таблицы замещений $T_{i}$ размерности $m\times mn$, определяемые по формуле $T_{i}[X]={\begin{pmatrix}a_{1i}\cdot S_{i}[X_{i}]\\...\\a_{ni}\cdot S_{i}[X_{i}]\end{pmatrix}}$, можно записать преобразование в простом виде: ${\begin{pmatrix}Y_{1}\\...\\Y_{n}\end{pmatrix}}=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={\begin{pmatrix}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{pmatrix}}$

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

Для описания дешифрования рассмотрим 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 \underbrace {l\circ s} _{r}\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'}\circ l)(X)$,

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

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

$Y=(a_{k_{3}'}\circ l^{-1}\circ l\circ s\circ a_{k_{2}}\circ r\circ a_{k_{1}})(X)=(a_{k_{3}'}\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'}}\circ \underbrace {l^{-1}\circ s^{-1}} _{r'}\circ a_{k_{3}^{-1'}})(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.