Хеш-функции на основе клеточных автоматов

Хеш-функции на основе клеточных автоматов — разновидность хеш-функций, использующая для вычисления клеточные автоматы. Использование клеточных автоматов обеспечивает высокий уровень параллелизма и, следовательно, позволяет достичь высоких скоростей, что необходимо в условиях ограниченных вычислительных мощностей и жестких требований к энергопотреблению (например, Интернет вещей). Хеш-функции на основе клеточных автоматов обладают хорошим лавинным эффектом. Использование клеточных автоматов позволяет добиться устойчивости к атакам временного анализа.

В криптографии наибольший интерес представляют аддитивные клеточные автоматы (сочетание операций XOR и XNOR в его переходной функции) благодаря таким свойствам, как адаптивность, обратимость и масштабируемость.

Пример Алгоритма

Алгоритм получает на вход сообщение $c$ произвольного размера и ключ $k$, размером: 128, 192 или 256 бит и возвращает хешированное значение ключа.

Базовое описание алгоритма

1. Первоначальное сообщение $c$ должно быть дополнено следующим образом:

   $size(c){\text{ mod }}512=0{\text{ and }}size(c)>=512$

   дополнение можно производить простым заполнением недостающих разрядов нулями.

   Обозначим дополненное сообщение как $C$.

2. Аналогично дополняется ключ $k$:

   $size(k){\text{ mod }}512=0{\text{ and }}size(k)>=512$

   Обозначим дополненный ключ как $K$.

3. Сообщение $C$ разбивается на блоки по 512 бит.
4. Каждый 512 битный блок, полученный на предыдущем шаге разбивается ещё раз на 8 подблоков по 64 бита.

   

   Разделение на 64 битные подблоки

5. К каждому 512 блоку применяется правило 30.
6. Выход пункта 5 вместе с 512 битным ключом поступают в функцию трансформации (ФТ).
7. Этот результат подвергается операции XOR с результатом пункта 5 для следующего 512 битного блока.
8. Ключ для последующих раундов получается с помощью поворота ключа предыдущей итерации, который выполняет циклический сдвиг битов на 1.
9. Шаги 6, 7 и 8 повторяются, пока не кончатся блоки сообщения по 512 бит, то есть пока всё сообщение не будет хешировано.

   

   Диаграмма описания работы алгоритма

Описание функции трансформации

Для получения полностью случайного выхода по заданному входу в функции трансформации используются как клеточные автоматы, так и побитовые логические операции.

Схематическое изображение отображения внутри одного раунда

Ниже приведен пример возможной трансформации, оперирующей с отдельными 64 битными подблоками.

1. $a=e$:

   Это означает, что байты из $e$ напрямую отображаются в $a$.

2. $b=J(g,h,K_{1})$ или $b=J(g,h,K_{5})$

   Если раунд нечетный, то используется $a=J(g,h,K_{1})$ иначе $a=J(g,h,K_{5})$.

   $J(x,y,z)=(({\text{ROTL}}^{47}(x){\text{ XOR }}\,Rule\,30({\text{ROTL}}^{37}(y')){\text{ AND }}(({\text{ ROTR}}^{17}(z)))$ .

3. $c=G(e,f,K_{2})$ или $c=G(e,f,K_{6})$

   Если раунд нечетный, то используется $c=G(e,f,K_{2})$ иначе $c=G(e,f,K_{6})$.

   $G(x,y,z)=(Rule134(Rule30(x')){\text{ OR }}y){\text{ XOR }}(Rule30(z'){\text{ AND }}x)$ .

4. $d=F(a,c)$

   $F(x,y)=Rule30(x){\text{ XOR }}y'$ .

5. $e=J(a,d,K_{4})$ или $e=J(a,d,K_{8})$

   Если раунд нечетный, то используется $e=J(a,d,K_{4})$ иначе $e=J(a,d,K_{8})$ .

   Функция $J$ определена в пункте 1.

6. $f=H(b,d)$

   $H(x,y)={\text{ROTL}}^{17}(x){\text{ XOR }}{\text{ ROTL}}^{59}(y)$.

7. $g=I(c,f)$

   $I(x,y)={\text{ROTL}}^{41}(x'){\text{ XOR }}{\text{Rule134}}({\text{ Rule30}}({\text{ ROTL}}^{31}(y')))$.

8. $h=H(a,K_{3})$ или $h=H(a,K_{7})$

   Если раунд нечетный, то используется $h=H(a,K_{3})$ иначе $h=H(c,K7)$

   Функция $H$ определена в пункте 4.

Где ROTL — циклический сдвиг битов влево, ROTR — циклический сдвиг битов вправо.

Внутри этой функции преобразования количество раундов распределяется динамически. Они рассчитываются по формуле:

$rounds$ = количество '1' в блоке сообщения(512 битовом) $+$ количество '0' в ключе (512 битовом) $mod512$.

Анализ безопасности

Наиболее распространенное правило 30, демонстрирующее желаемое поведение, необходимое в криптографических примитивах неспособно обеспечить полный лавинный эффект и случайность. Для улучшения этих параметров применяется объединение других нелинейных правил клеточного автомата с правилом 30. Гибридные правила демонстрируют желательный строгий лавинный критерий для очень большого числа итерации. Введение функции трансформации с комбинацией правил клеточного автомата достигает полного лавинного эффекта за небольшое число итераций и проходит все статистические тесты, распространяемые Национальным институтом Стандартов и технологий.