Русская Википедия:SHARK

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Карточка блочного шифра SHARK (Шаблон:Lang-en — безопасный хеширующий алгоритм с воссоздающимися ключами) — симметричный алгоритм блочного шифрования, разработанный группой криптографов, среди которых Винсент Рэймен, — автор шифра 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 (Шаблон:Lang-en) и SHARK-E (Шаблон:Lang-en), получившие название благодаря различным способам введения раундовых ключей.

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

Файл:SHARK.png

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

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

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

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

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

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

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

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

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

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

Если <math>w_h(a) = 1</math>, то <math>B \leq n + 1</math>. <math>B = n + 1</math> называют оптимальным числом скачка (Шаблон:Lang-en). В основной статье авторы показали, что с помощью MDS-кодов можно сконструировать обратимое линейное преобразование с оптимальном числом скачка. В реализации используются <math>(2n, n, n + 1)</math> коды Рида-Соломона.

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

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

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

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

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

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

Расписание ключей (Шаблон:Lang-en) позволяет расширить исходный ключ <math>K</math>, получив <math>R + 1</math> раундовых ключей <math>K_i</math>. Хорошее планирование позволяет получить раундовые ключи с максимальной энтропией. Авторами предлагаются два способа ввести раундовый ключ:

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

Exor

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

Affine Transformation

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

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

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

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

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

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

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

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

<math>\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>T_i</math> размерности <math>m \times mn </math>, определяемые по формуле <math>T_i[X] = \begin{pmatrix} a_{1i}\cdot S_i[X_i] \\ ... \\ a_{ni}\cdot S_i[X_i] \end{pmatrix} </math>, можно записать преобразование в простом виде: <math>\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>n</math> поисков по таблице и <math>n - 1</math> бинарных операций. Однако, из-за того что при длине блока <math>8n</math> бит таблицы занимают <math>n^2 \times 256 </math> байт, алгоритм для блоков длины 128 бит и более оказывался неэффективным для большинства процессоров того времени (1996 год), отсюда происходит существующее ограничение на длину блока в 64 бит (<math>n = 8, m = 8</math>).

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

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

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

<math>(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>a_{k'}(X) = k' \cdot X \oplus K' = ( A \cdot k \cdot A^{-1}) \cdot X \oplus (A \cdot K) </math>

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

<math>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>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>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 году Шаблон:Iw и Ларс Кнудсен показали, что 64-битная реализация SHARK-E (SHARK с exor стратегией введения раундового ключа) теоретически уязвима для интерполяционной атаки при ограничении на количество раундов до 5, а также 128-битная реализация — при ограничении до 8 раундов. Но они также показали, что для достаточной безопасности необходимо по крайней мере 6 раундов.
• В 2013 году Янг Ши (Шаблон:Lang-en) и Хонгвей Фан (Шаблон:Lang-en) показали, что White-Box реализация SHARK недостаточно безопасна и может быть взломана с фактором работы примерно 1.5 * (2 ^ 47).

Литература

• Vincent Rijmen, Joan Daemen, Bart Preneel, Antoon Bosselaers, Erik De Win The Cipher SHARK. — The cipher SHARK Шаблон:Wayback.
• Joan Daemen, Vincent Rijmen The Design of Rijndael. — The Design of Rijndael Шаблон:Wayback.
• Thomas Jakobsen, Lars R. Knudsen The interpolation attack on block ciphers. — The interpolation attack on block ciphers Шаблон:Wayback.
• Yang Shi, Hongfei Fan On Security of a White-Box Implementation of SHARK. — On Security of a White-Box Implementation of SHARK Шаблон:Wayback.
• Шаблон:Книга