SHARK

SHARK(англ.Secure Hash Algorithm Regenerative Keys— безопасный хеширующий алгоритм с воссоздающимися ключами) —симметричный алгоритмблочного шифрования, разработанный группой криптографов, среди которыхВинсент Рэймен, — автор шифраAES. В теории позволяет использовать блоки и ключи различной длины, однако авторская реализация использует 128-битный ключ и 64-битные блоки. Структура схожа со структуройподстановочно-перестановочной сети.
ШифрSHARK— первый в серии алгоритмов, разработанных в ходе исследования по созданию безопасных и эффективных алгоритмов блочного шифрования на основе методаWide Trail design strategy. Результатом исследования позже стало создание стандартного шифра AES.
Авторы позиционировали SHARK как алгоритм, призванный заменить широко распространенный в то время шифрDES. К новому алгоритму были предъявлены следующие требования:
Хотя до этого уже существовали шифры на основеSP-сети(MMB,SAFER,3-Way),SHARKвпервые использовал MDS-кодыдля линейного преобразования, а именнокоды Рида-Соломона.
Существует два варианта шифраSHARK: SHARK-A (англ.affine transform) и SHARK-E (англ.exor), получившие название благодаря различным способам введения раундовых ключей.
АлгоритмSHARKсостоит из трех компонентов:
Каждый компонент алгоритма рассматривается отдельно и каждый должен обладать определёнными свойствами. Так, слой диффузии должен обладать равномерными и хорошими диффузионными свойствами. Нелинейный слой также должен обладать равномерными нелинейными свойствами, причем компоненты алгоритма независимы в следующем смысле: при изменении реализации, например, нелинейного слоя (одни S-блоки заменяются другими S-блоками c такими же характеристиками), защищенность алгоритма остается неизменной. Такая стратегия является вариантом Wide trail strategy, описанной в докторской диссертации Йоана Даймена.
SHARKсостоит изR{\displaystyle R}раундов, дополнительного слоя добавления ключа и дополнительно слоя инвертированной диффузии. Каждый раунд, в свою очередь, состоит из добавления ключа, нелинейной замены и слоя диффузии. Дополнительный слой добавления ключа нужен для того, чтобы злоумышленник не смог отделить последний раунд. Дополнительный слой инвертированной диффузии необходим для упрощения операции дешифрования.
Слой нелинейный замены состоит изn{\displaystyle n}S-блоков, каждый из которых представляет собойm{\displaystyle m}-битную перестановку. Таким образом, алгоритм способен шифровать блоки длинойm⋅n{\displaystyle m\cdot n}.
На вход слою диффузии приходятn{\displaystyle n}m{\displaystyle m}-битных чисел, которые можно рассматривать как элементы надполемGF(2m){\displaystyle GF(2^{m})}. Рассматриваемый слой необходим для созданиялавинного эффекта. Этот эффект проявляется в линейном и разностном контекстах:
Пустьθ{\displaystyle \theta }— обратимоелинейное преобразование,a{\displaystyle a}— элемент поляGF(2m){\displaystyle GF(2^{m})},wh(a){\displaystyle w_{h}(a)}—расстояние Хэмминга, тогда количественно лавинный эффект оценивается числом скачка (англ.branch number)B(θ)=mina≠0(wh(a)+wh(θ(a))){\displaystyle B(\theta )={\overset {}{\underset {a\neq 0}{min}}}({\displaystyle w_{h}(a)}+{\displaystyle w_{h}(\theta (a))})}.
Еслиwh(a)=1{\displaystyle w_{h}(a)=1}, тоB≤n+1{\displaystyle B\leq n+1}.B=n+1{\displaystyle B=n+1}называют оптимальным числом скачка (англ.optimal branch number). В основной статье авторы показали, что с помощью MDS-кодов можно сконструировать обратимое линейное преобразование с оптимальном числом скачка. В реализации используются(2n,n,n+1){\displaystyle (2n,n,n+1)}коды Рида-Соломона.
Нелинейные S-блоки обеспечивают защиту от линейного и дифференциального криптоанализов. Одним из важных численных характеристик безопасности шифра служит матрица эксклюзивных ИЛИ (англ.exor table)E{\displaystyle E}отображенияγ{\displaystyle \gamma }, элементы которой определяются по формулеEij=♯(x|γ(x)⊕γ(i⊕x)=j){\displaystyle E_{ij}=\sharp (x|\gamma (x)\oplus \gamma (i\oplus x)=j)}, где♯{\displaystyle \sharp }— обозначает число удовлетворяющих условию элементов,x,i,j{\displaystyle x,i,j}— элементы поляGF(2m){\displaystyle GF(2^{m})}. Большие значения элементов матрицы могут привести к восприимчивости шифра к дифференциальной атаке.
Авторами были выбраны S-блоки, основанные на отображенииF(x)=x−1{\displaystyle F(x)=x^{-1}}над полемGF(2m){\displaystyle GF(2^{m})}. В этом случае при четномm{\displaystyle m}матрицаE{\displaystyle E}обладает следующими свойствами:
Для того чтобы удалить фиксированные точки0→0{\displaystyle 0\rightarrow 0}и1→1{\displaystyle 1\rightarrow 1}, используется обратимоеаффинное преобразованиевыходных бит.
Расписание ключей (англ.key scheduling) позволяет расширить исходный ключK{\displaystyle K}, получивR+1{\displaystyle R+1}раундовых ключейKi{\displaystyle K_{i}}. Хорошее планирование позволяет получить раундовые ключи с максимальной энтропией. Авторами предлагаются два способа ввести раундовый ключ:
Вычисляется простое исключающее ИЛИm⋅n{\displaystyle m\cdot n}входных бит раунда иm⋅n{\displaystyle m\cdot n}подключа. Преимущества метода — быстрота и стабильность: никакой ключ не является сильнее или слабее другого. Недостаток метода — энтропия раундового ключа не превосходитm⋅n{\displaystyle m\cdot n}.
Пустьki{\displaystyle k_{i}}— невырожденная матрицаn×n{\displaystyle n\times n}над полемGF(2m){\displaystyle GF(2^{m})}, зависящая от ключаK{\displaystyle K}(точнее, от его расширения). Введем ключевую операцию над входными данными следующим образом:Y(X)=ki⋅X⊕Ki{\displaystyle Y(X)=k_{i}\cdot X\oplus K_{i}}. Это линейная операция, потому она не вводит слабых ключей. Кроме того, энтропия раундовых ключей увеличивается доO(mn2){\displaystyle O(mn^{2})}. Однако, это довольно дорогая в смысле производительности операция, поэтому авторами предлагается ограничитьki{\displaystyle k_{i}}на подпространстведиагональных матриц. В этом случае энтропия раундовых ключей становится близкой к2mn{\displaystyle 2mn}.
В алгоритмеSHARK, генерация раундовых ключей осуществляется следующим образом:
Механизм генерации подключей в принципе позволяет использовать ключ длины2(R+1)mn{\displaystyle 2(R+1)mn}бит, но авторы рекомендуют использовать ключ, не превышающий 128 бит.
Для того, чтобы добиться высокой производительности, слой диффузии и блоки подстановок объединяются в одну операцию. ПустьX1,...,Xn{\displaystyle X_{1},...,X_{n}}обозначают входные данные раунда;Y1,...,Yn{\displaystyle Y_{1},...,Y_{n}}— выходные данные;S1,...,Sn{\displaystyle S_{1},...,S_{n}}— матрицы перестановок (S-блоки);A{\displaystyle A}— матрица, определяющая слой диффузии;⊕{\displaystyle \oplus }и⋅{\displaystyle \cdot }— обозначают сложение и умножение над полемGF(2n){\displaystyle GF(2^{n})}. Тогда
(Y1...Yn)=A⋅(S1[X1]...Sn[Xn])=(a11...an1)⋅S1[X1]⊕...⊕(a1n...ann)⋅Sn[Xn]=(a11⋅S1[X1]...an1⋅S1[X1])⊕...⊕(a1n⋅Sn[Xn]...ann⋅Sn[Xn]){\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}}}
Используя расширенные таблицы замещенийTi{\displaystyle T_{i}}размерностиm×mn{\displaystyle m\times mn}, определяемые по формулеTi[X]=(a1i⋅Si[Xi]...ani⋅Si[Xi]){\displaystyle T_{i}[X]={\begin{pmatrix}a_{1i}\cdot S_{i}[X_{i}]\\...\\a_{ni}\cdot S_{i}[X_{i}]\end{pmatrix}}}, можно записать преобразование в простом виде:(Y1...Yn)=T1[X1]⊕T2[X2]⊕...⊕Tn[Xn]{\displaystyle {\begin{pmatrix}Y_{1}\\...\\Y_{n}\end{pmatrix}}=T_{1}[X_{1}]\oplus T_{2}[X_{2}]\oplus ...\oplus T_{n}[X_{n}]}
Таким образом, один раунд требуетn{\displaystyle n}поисков по таблице иn−1{\displaystyle n-1}бинарных операций. Однако, из-за того что при длине блока8n{\displaystyle 8n}бит таблицы занимаютn2×256{\displaystyle n^{2}\times 256}байт, алгоритм для блоков длины 128 бит и более оказывался неэффективным для большинства процессоров того времени (1996 год), отсюда происходит существующее ограничение на длину блока в 64 бит (n=8,m=8{\displaystyle n=8,m=8}).
Дляn=8{\displaystyle n=8}можно построить матрицу, определяющую слой диффузии, на основе кода Рида-Соломона.
A=(CEE7B9D05287740B95FEDA9DA928513157054D26073A157F82D2D12C6C5ACF868A529E5DB9F409BE19C1179F8F33A405B088836D700B628301F18675176C0934){\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. Пустьl{\displaystyle l}— линейная операция,s{\displaystyle s}— нелинейная замена,aki{\displaystyle a_{k_{i}}}— операция добавления ключа для раундового ключаki{\displaystyle k_{i}}. Функция шифрования, в таком случае, равнаY=(l−1∘ak3∘l∘s∘ak2∘l∘s⏟r∘ak1)(X){\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)}, гдеr{\displaystyle r}— комбинированная из слоя диффузии и S-блоков операция. Так как операция добавления ключа и операция диффузии — линейные операции, их порядок можно поменять местами:
(l∘ak)(X)=A⋅(k⋅X⊕K)=(A⋅k⋅X)⊕(A⋅K)=((A⋅k⋅A−1)⋅(A⋅X))⊕(A⋅K)=(ak′∘l)(X){\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)},
где введено обозначениеak′(X)=k′⋅X⊕K′=(A⋅k⋅A−1)⋅X⊕(A⋅K){\displaystyle a_{k'}(X)=k'\cdot X\oplus K'=(A\cdot k\cdot A^{-1})\cdot X\oplus (A\cdot K)}
Применим полученную формулу кl−1∘ak3{\displaystyle l^{-1}\circ a_{k_{3}}}:
Y=(ak3′∘l−1∘l∘s∘ak2∘r∘ak1)(X)=(ak3′∘s∘ak2∘r∘ak1)(X){\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)}
Теперь покажем, что операция дешифрования имеет ту же структуру. Для этого сначала обратим операцию шифрования:
X=(ak1−1∘s−1∘l−1∘ak2−1∘s−1∘l−1∘ak3−1∘l)(Y){\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)}
Меняя местами операцию добавления ключа и операцию диффузии, получаем ту же структуру, что и в операции шифрования:
X=(ak1−1∘s−1∘ak2−1′∘l−1∘s−1⏟r′∘ak3−1′)(Y){\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)}
На текущий момент не обнаружено уязвимостей у классической реализации алгоритма. Существуют атаки только на вариации алгоритма: