SHARK

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

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

История SHARK

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Exor

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

Affine Transformation

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

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

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

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

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

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

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

Для того, чтобы добиться высокой производительности, слой диффузии и блоки подстановок объединяются в одну операцию[1]. Пусть ${\displaystyle X_{1},...,X_{n}}$ обозначают входные данные раунда; ${\displaystyle Y_{1},...,Y_{n}}$ — выходные данные; ${\displaystyle S_{1},...,S_{n}}$ — матрицы перестановок (S-блоки); ${\displaystyle A}$ — матрица, определяющая слой диффузии; ${\displaystyle \oplus }$ и ${\displaystyle \cdot }$ — обозначают сложение и умножение над полем ${\displaystyle GF(2^{n})}$. Тогда

${\displaystyle {\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}}}$

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

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

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

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

${\displaystyle 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[1]. Пусть ${\displaystyle l}$ — линейная операция, ${\displaystyle s}$ — нелинейная замена, ${\displaystyle a_{k_{i}}}$ — операция добавления ключа для раундового ключа ${\displaystyle k_{i}}$. Функция шифрования, в таком случае, равна ${\displaystyle 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)}$, где ${\displaystyle r}$ — комбинированная из слоя диффузии и S-блоков операция. Так как операция добавления ключа и операция диффузии — линейные операции, их порядок можно поменять местами[1]:

${\displaystyle (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)}$,

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

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

${\displaystyle 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)}$

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

${\displaystyle 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)}$

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

${\displaystyle 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 раундов[6].
• В 2013 году Янг Ши (англ. Yang Shi) и Хонгвей Фан (англ. Hongfei Fan) показали, что White-Box реализация[7] SHARK недостаточно безопасна и может быть взломана с фактором работы примерно 1.5 * (2 ^ 47)[8].

Примечания

1. Винсент Рэймен, Йоан Даймен, Барт Пренель, Антун Боссэлерс, Эрик де Вин. The Cipher SHARK : PDF. Архивировано 9 августа 2017 года.
2. Винсент Рэймен, Йоан Даймен. The Design of Rijndael : PDF. — С. 161—165. Архивировано 27 августа 2017 года.
3. Йоан Даймен. Cipher and Hash Function Design Strategies based on linear and differential cryptanalysis : PDF. Архивировано 16 мая 2018 года.
4. MDS-коды — коды с наибольшим кодовым расстоянием
5. Scan's entry for Shark  (неопр.). Дата обращения: 16 декабря 2017. Архивировано 28 января 2012 года.
6. Томас Якобсен, Ларс Кнудсен. The Interpolation Attack on Block Ciphers  (неопр.). Springer International Publishing AG (17 мая 2006). Дата обращения: 9 февраля 2018. Архивировано 14 декабря 2017 года.
7. White-box attack context — злоумышленник имеет полный доступ к программной реализации шифра.
8. Yang Shi, Hongfei Fan. On Security of a White-Box Implementation of SHARK  (неопр.). Дата обращения: 14 декабря 2017. Архивировано 14 декабря 2017 года.

Литература

• 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.

Ссылки