Криптографічні хеш-функції на основі клітинних автоматів
Криптографічні хеш-функції
Алгоритм Keccak
Конструкція губки
Параметри хеш-функції Keccak
Постановка задачі
Клітинні автомати (КA)
Клітинні автомати (КA): правило 30
Одновимірні клітинні автомати (КA)
Двовимірні КА
Схема взаємодії
Різновиди функцій перестановки
Тривимірні КА
ІНІЦІАЛІЗАЦІЯ
Правила взаємодії
FBlock
Результати статистичного тестування NIST
ТЕСТИ NIST STS
ШВИДКОДІЯ
ОДЕРЖАННЯ ХЕШУ
ДЯКУЮ ЗА УВАГУ !
2.22M
Category: informaticsinformatics

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

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

доц. Танасюк Ю.В.
Константинюк Олексій
Мельничук Христина
Петро Бурдейний
Валеріан Гульпак

2. Криптографічні хеш-функції

h
Вхідне повідомлення
2
Хеш
• MD5: n = 128 (Ron Rivest, 1992)
• SHA-1: n = 160 (NSA, NIST, 1995)
• SHA-2: n → {224, 256, 384, 512} (NSA,
NIST, 2001)
2

3. Алгоритм Keccak

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

4. Конструкція губки

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

5. Параметри хеш-функції Keccak

5
Параметри хеш-функції Keccak
• Стандарт SHA-3 використовує стан губки довжиною 1600 бітів.
5
Довжина
хешу,
Z (біти)
Бітова
швидкість,
r (біти)
Потужність,
c (біти)
Рівень
захисту,
N (біти)
224
1152
448
112
256
1088
512
128
384
832
768
192
512
576
1024
256

6.

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

7. Постановка задачі

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

8. Клітинні автомати (КA)

10
Клітинні автомати (КA)
• Самоорганізована статистична система клітин, кожна з яких може
перебувати в одному з двох станів 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, відповідно.

9. Клітинні автомати (КA): правило 30

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

10. Одновимірні клітинні автомати (КA)

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

11. Двовимірні КА

11
Двовимірні КА
• 25 рядків довжиною 64 біти, загальний розмір - 1600 бітів
• Локальний окіл Мура: 8 суміжних клітин
• Крайні клітини замикаються в тор.
W
SW
NW
N
NE
X
E
WS
SE
X
E…
SW
S
SE
...
64 біти
25

12. Схема взаємодії

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

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

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

14.

14
Початок
1
Перетворення повідомлення М до бінарної
форми та доповнення до довжини , кратної r
Всмоктування
Досягнуто
кінця
даних
так
ні
Обчислення S{i}=r XOR M[i]
Віджим
Формування початкового масиву станів S (r+c),
довжиною 1600 бітів
Одержано
хеш
потрібної
довжини
ні
Z[i]=K+Z[i-1]
Виконання раундової
функції f
Виведення
хешу
Застосування раундової функції f
Кінець
1
так

15. Тривимірні КА

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

16. ІНІЦІАЛІЗАЦІЯ

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

17. Правила взаємодії

17
Правила взаємодії
• Правило 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)

18. FBlock

18
FBlock

19. Результати статистичного тестування NIST

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

20. ТЕСТИ NIST STS

20
ТЕСТИ NIST STS

21. ШВИДКОДІЯ

21
ШВИДКОДІЯ

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

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

23. ДЯКУЮ ЗА УВАГУ !

23
ДЯКУЮ ЗА УВАГУ !
English     Русский Rules