Криптографічні хеш-функції на основі клітинних автоматів

Криптографічні хеш-функції
MD5: n = 128 (Ron Rivest, 1992)
SHA-1: n = 160 (NSA, NIST, 1995)
SHA-2: n → {224, 256, 384, 512} (NSA, NIST, 2001)
Вхідне повідомлення
2
Хеш
h

Алгоритм Keccak
Переможець конкурсу NIST серед алгоритмів криптографічних хеш-функцій у 2012 р. (www.nist.gov/itl/csd/sha-100212.cfm).
Новий стандарт хешування SHA-3 (2015).
Змінна довжина дайджесту: 224, 256, 384 та 512 бітів.
Програмна й апаратна реалізація.
Базується на конструкції губки та псевдовипадкових перетвореннях.
3

Конструкція губки
Інтерактивна конструкція для реалізації псевдовипадкових перестановок за допомогою низки розроблених функцій f.
S — внутрішній стан фіксованої довжини b (бітів).
b = r + c, де r – бітова швидкість, с — потужність.
S
4
всмоктування
віджим
r
c

Параметри хеш-функції Keccak
Стандарт SHA-3 використовує стан губки довжиною 1600 бітів.
5

Схематичне зображення процедури перестановки Keccak-f стану губки
http:/n/keccak.noekeon.org/
7

Постановка задачі
Стан губки – одно-, дво- та тривимірні клітинні автомати (КА).
Функція перемішування – комбінація правил обробки КА.
Застосовуються на обох стадіях всмоктування та віджиму.
Змінна кількість раундів обробки.
Параметри та довжина хешу відповідають алгоритму Keccak.
Тестування NIST STS та лавинний ефект.
9

Самоорганізована статистична система клітин, кожна з яких може перебувати в одному з двох станів 0 або 1
Розвивається за визначеним правилом, наприклад:
правило 30: C[i]′ = C[i-1] ⊕ (C[i] ∨ C[i+1]) (1)
правило 54: C[i]′=(C[i-1] ∨ C[i+1]) ⊕ C[i] (2)
правило 86: C[i]′ = (C[i-1] ∨ C[i]) ⊕ C[i+1] (3)
правило 150: C[i]′ = C[i-1] ⊕ C[i] ⊕ C[i+1] (4)
правило 158: C[i]′=C[i-1] ⊕ C[i] ⊕ C[i+1] ∨ C[i] ∧ C[i+1] (5)
де C[i] – поточна клітина, C[i]′ - оновлене значення поточної клітини після застосування правила, C[i-1], C[i+1] – попередня і наступна сусідні клітини, та ⊕, ∧, ∨ - бітові операції XOR, AND, та OR, відповідно.
10
Клітинні автомати (КA)

Клітинні автомати (КA): правило 30
C[i]′ = C[i-1] ⊕ (C[i] ∨ C[i+1])

Одновимірні клітинні автомати (КA)
Для оптимізації обробки вектору стану губки RC довжиною 1600 бітів на кожному раунді створювалися два його вектори:
a2’=a1 XOR (a2 OR a3) – правило №30 (1)
Збільшення швидкості обробки у 60 разів
1600 бітів

Двовимірні КА
25 рядків довжиною 64 біти, загальний розмір - 1600 бітів
Локальний окіл Мура: 8 суміжних клітин
Крайні клітини замикаються в тор.
11
25
64 біти

Схема взаємодії
4 способи взаємодії
N,W, NW, NE – попередні
клітини
S, E, SW, SE – наступні.
Гібридні клітинні автомати
Поєднання лінійних (150) та
нелінійних (30, 54, 86, 158) правил.
12
1
2
3
4

Різновиди функцій перестановки
14

Всмоктування
Віджим

Тривимірні КА
arrayRC: масив 5х5 64-бітних векторів

ІНІЦІАЛІЗАЦІЯ

Правила взаємодії
Правило 30:
RCArray[i][j] = (nord xor west xor back) xor RCArray[i][j] | (south xor east xor face)
Правило 86:
RCArray[i][j] = (nord xor west xor back) | RCArray[i][j] xor (south xor east xor face)
Правило 150:
RCArray[i][j] = (nord xor west xor back) xor RCArray[i][j] xor (south xor east xor face)

FBlock

Результати статистичного тестування NIST
RULE_54_150_86, 5 раундів
16
Р
N
N
RULE_54_150_86, 10 раундів
Р
N

ТЕСТИ NIST STS

ШВИДКОДІЯ

ОДЕРЖАННЯ ХЕШУ