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 состоит из [math]\displaystyle{ R }[/math] раундов, дополнительного слоя добавления ключа и дополнительно слоя инвертированной диффузии. Каждый раунд, в свою очередь, состоит из добавления ключа, нелинейной замены и слоя диффузии. Дополнительный слой добавления ключа нужен для того, чтобы злоумышленник не смог отделить последний раунд. Дополнительный слой инвертированной диффузии необходим для упрощения операции дешифрования.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Exor

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

Affine Transformation

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

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

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

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

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

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

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

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

[math]\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} }[/math]

Используя расширенные таблицы замещений [math]\displaystyle{ T_i }[/math] размерности [math]\displaystyle{ m \times mn }[/math], определяемые по формуле [math]\displaystyle{ T_i[X] = \begin{pmatrix} a_{1i}\cdot S_i[X_i] \\ ... \\ a_{ni}\cdot S_i[X_i] \end{pmatrix} }[/math], можно записать преобразование в простом виде: [math]\displaystyle{ \begin{pmatrix} Y_1 \\ ... \\ Y_n \end{pmatrix} = T_1[X_1]\oplus T_2[X_2]\oplus ... \oplus T_n[X_n] }[/math]

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

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

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

[math]\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} }[/math]

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

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

[math]\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) }[/math],

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

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

[math]\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) }[/math]

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

[math]\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) }[/math]

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

[math]\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) }[/math]

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

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

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