Хэш - функции. Логика выполнения SHA -1

1. Лекция №7

Хэш-функции

2. Хэш-функции

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

3. Хэш-функции Семейство алгоритмов MD4

Алгоритм
Число циклов
Число шагов в
цикле
Длина блока n
MD4
3
16
128
MD5
4
16
128
RIPEMD-160
5
16
160
SHA-1
4
20
160
SHA-256
64
1
256
SHA-384
80
1
384
SHA-512
80
1
512
3

4. md4

• Исходное значение M разбивается на блоки Mi длиной
512 бит:
M1, M2,…, MN
• Последний блок формируется путем дописывания к концу
сообщения комбинации 1 0 … 0 до получения блока размером
448 бит, к которому затем добавляют комбинацию из 64 бит –
битовую длину сообщения.
• Вычисляют значение свертки с использованием одношаговой
сжимающей функции F(x,H)=Ex(H) xor H по правилу:
Hi=f(Mi, Hi-1), 1 ≤ I ≤ N,
где
Mi – блок сообщения длиной m бит;
Hi – блоки из n бит;
Ex – некоторое преобразование множества блоков
(структура блочного шифра на основе регистра сдвига);
H0 – значение начального вектора
4

5.

Cj
15 14 …
1
0
Sj
b
c
d
a
f
Mi
Преобразование E алгоритмов MD4, MD5
1
Cj
15 14 …
Mi
9
2
0
a
b
5 5
Преобразование E алгоритма SHA-1
c
30
d
e
f
5

6. Функции

MD4
MD5
SHA-1
3 цикла по 16
шагов
(b˄c)˅( ̚ b˄d)
(b˄c)˅(b˄d) ˅ (c˄d)
b xor c xor d
4 цикла по 16
шагов
(b˄c)˅( ̚ b˄d)
(b˄c)˅(b˄d) ˅ (c˄d)
b xor c xor d
b xor (c ˅ ̚ d)
4 цикла по 20
шагов
(b˄d)˅( c˄ ̚ d)
b xor c xor d
(b˄c)˅(b˄d) ˅ (c˄d)
b xor c xor d
Логические функции
˄ - дизъюнкции
˅ - конъюнкции
̚ - отрицание
6

7. SHA-1

На входе сообщение максимальной длины
7

8. Логика выполнения SHA-1

Шаг 1: добавление недостающих битов
• Длина сообщения кратна 448 по модулю 512).
• Число добавляемых битов находится в
диапазоне от 1 до 512.
• Добавление состоит из единицы, за которой
следует необходимое количество нулей.
8

9. Логика выполнения SHA-1

Шаг 2: добавление длины
• К сообщению добавляется блок из 64 битов,
содержит длину исходного сообщения до
добавления.
• Расширенное сообщение может быть представлено
как последовательность 512-битных блоков Y0, Y1, . .
. , YL-1, так что общая длина расширенного
сообщения есть L * 512 бит.
• Таким образом, результат кратен шестнадцати 32битным словам.
9

10. Логика выполнения SHA-1

Шаг 3: инициализация SHA-1 буфера
• Используется 160-битный буфер для хранения
промежуточных и окончательных результатов хэшфункции.
• Буфер может быть представлен как пять 32-битных
регистров A, B, C, D и E.
• Эти регистры инициализируются следующими
шестнадцатеричными числами:
A = 67452301
B = EFCDAB89
C = 98BADCFE
D = 10325476
E = C3D2E1F0
10

11. Логика выполнения SHA-1

Шаг 4: обработка сообщения в 512-битных (16-словных) блоках
• Основой алгоритма является модуль, состоящий из 80 циклических
обработок, обозначенный как HSHA. Все 80 циклических обработок имеют
одинаковую структуру.
0 ≤ t ≤ 19
Kt = 5A827999
(целая часть числа [230 × 21/2])
20 ≤ t ≤ 39
Kt = 6ED9EBA1
(целая часть числа [230 × 31/2])
40 ≤ t ≤ 59
Kt = 8F1BBCDC
(целая часть числа [230 × 51/2])
60 ≤ t ≤ 79
Kt = CA62C1D6
(целая часть числа [230 × 101/2])
Для получения SHAq+1 выход 80-го цикла складывается по модулю 232 со значением
11
SHAq независимо для каждого из пяти слов в буфере.

12. Логика выполнения SHA-1

Шаг 5: выход
• После обработки всех 512-битных блоков выходом L-ой
стадии является 160-битный дайджест сообщения.
• Каждый цикл (всего 80 циклов обработки):
• A, B, C, D, E (CLS5(A)) +ft(B,C,D) + E + Wt+Kt), A, CLS30(B), C, D
Где, A, B, C, D, E – пять слов из буфера
t – номер цикла, 0≤t ≤79
fi – элементарная логическая функция
CLSs – циклический левый сдвиг 32-битного аргумента на s
битов
• Wt – 32-битное слово, полученное из текущего входного 512битног блока
• Kt – дополнительная константа
• + - сложение по модулю 232
12

13. Логика выполнения отдельного цикла

t - номер цикла, 0≤ t ≤ 79.
ft - элементарная логическая функция
CLSs - циклический левый сдвиг
32-битного аргумента на s битов.
Wt - 32-битное слово, полученное из
текущего входного 512-битного блока.
Kt - дополнительная константа.
+ - сложение по модулю 232.
Wt = Wt-16 xor Wt-14 xor Wt-8 xor Wt-3
Получение входных значений для каждого цикла
13

14. Логика выполнения SHA-1

Алгоритм SHA-1
1. SHA0 = ABCDE
2. SHAq+1 = Σ32 (SHAq , ABCDEq),
где
ABCDEq - результат обработки q-того блока сообщения.
Σ32 - сумма по модулю 232, выполняемая отдельно для
каждого слова буфера.
3. SHA = SHAL-1
где
L - число блоков в сообщении, включая поля добавления и
длины.
SHA - значение дайджеста сообщения
14

15. SHA-1 и MD-5

MD5
SHA-1
128 бит
160 бит
Размер блока обработки
Число итераций
512
64
512
80
Число элементарных
логических функций
4
3
Число дополнительных
констант
64
4
Длина дайджеста
15

16. Функции хэширования SHA-256, SHA-384, SHA-512

Функции хэширования SHA-256, SHA384, SHA-512
• Стойкость функции хэширования к поиску
столкновений равна 2n/2,
где n – длина выходного значения функции.
• В связи с разработкой в США нового стандарта
шифрования AES с длиной ключа 128, 192 и 256
бит, потребовалось создать алгоритмы
хэширования, обеспечивающие такой же уровень
стойкости.
16

17. FIPS-180-3(SHS)

17

18. Хэш-функции ГОСТ Р 34.11-2012 

Хэш-функции ГОСТ Р 34.11-2012
1. Стандарт ГОСТ Р 34.11-2012 был разработан
Центром защиты информации и специальной связи
ФСБ России с участием Открытого акционерного
общества «Информационные технологии и
коммуникационные системы» (ОАО «ИнфоТеКС»).
2. Стандарт утверждён и введён в действие Приказом
Федерального агентства по техническому
регулированию и метрологии от 7 августа 2012 года
No 216-ст.
3. ГОСТ Р 34.11-2012 разработан взамен
национальному стандарту на функцию хеширования
ГОСТ Р 34.11-94.
18

19. Область применения ГОСТ Р 34.11-2012

• Определяет алгоритм и процедуру вычисления хэшфункции для любой последовательности двоичных
символов, которые применяются в криптографических
методах обработки и защиты информации, в том числе
для реализации процедур обеспечения целостности,
аутентичности, электронной цифровой подписи (ЭЦП)
при передаче, обработке и хранении информации в
автоматизированных системах.
• Функция хэширования ГОСТ Р 34.11-2012 используется
при реализации систем электронной цифровой подписи
на базе ассиметричного криптографического алгоритма
по ГОСТ Р 34.10–2012.
19

20. Внутреннее устройство

Семейство хэш-функций Стрибог состоит из двух хэш-функций с длинами
результирующего значения в 256 и 512 бит, которые отличаются начальным
внутренним состоянием и его частью, принимаемой за результат вычислений.
Входное сообщение разбивается на блоки фиксированного размера, для
сообщений размером не кратным длине блока используется дополнение.
Начальное внутреннее состояние хэш-функции обновляется
последовательной обработкой блоков сообщения функцией сжатия.
Параллельно с этим вычисляются число обработанных бит и контрольная
сумма блоков.
После всех блоков сообщения функция сжатия обрабатывает блок с общей
длиной сообщения и блок с контрольной суммой для завершения
вычисления значения хэш-функции.
Размер блоков сообщения и внутреннего состояния хэш-функции составляет
512 бит. Основное отличие хэш-функции Стрибог от своего предшественника
— функция сжатия.
20

21. Функция сжатия

Основная операция функции сжатия обозначается как LPS и состоит из трёх преобразований:
подстановка на байтах,
транспонирование матрицы байт
умножения 64-битных векторов на матрицу 64 × 64 в GF(2):
1. S — нелинейная биекция. 512 бит аргумента рассматриваются как массив из шестидесяти
четырёх байт, каждый из которых заменяется по заданной стандартом таблице подстановки;
2. P — переупорядочивание байт. Байты аргумента меняются местами по определённому в
стандарте порядку;
3. L — линейное преобразование. Аргумент рассматривается как 8 64-битных векторов, каждый
из которых заменяется результатом умножения на определённую стандартом матрицу 64 × 64
над GF(2).
Переупорядочивание байт P, определённое стандартом, является операций транспонирования
матрицы байт размером 8 × 8.
В функции сжатия используются только преобразование LPS и побитовое исключающее ИЛИ над
512-битными блоками. Вместе со сложением по модулю 2^512 они составляют полный набор
операций, использующихся в функции хеширования ГОСТ Р 34.11-2012.
Значение функции сжатия на каждом шаге зависит от предыдущего шага. Поэтому невозможно
обрабатывать блоки одного потока данных параллельно. Это свойство не является особенностью
Стрибога, а присуще многим хэш-функциям.
http://paco2012.ipu.ru/procdngs/F108.pdf
21

22. ГОСТ Р 34.11-2012

http://habrahabr.ru/post/210684/
22

23.

23

24. Криптоанализ ГОСТ Р 34.11-2012

• В конце 2013 г. Технический комитет по стандартизации
«Криптографическая защита информации» (ТК 26), Академия
криптографии Российской Федерации и ОАО «ИнфоТеКС» объявили о
проведении конкурса по криптоанализу отечественного стандарта
хэширования ГОСТ Р 34.11-2012.
• Подробное описание условий конкурса опубликовано на
сайте www.streebog.info. Таким образом, можно считать, что
существующие работы по анализу данного криптостандарта стали
предметом повышенного интереса криптоаналитиков, поскольку они
являются отправной точкой для дальнейших исследований алгоритма
ГОСТ Р 34.11-2012.
• На текущий момент известно несколько работ, посвященных
криптоанализу ГОСТ Р 34.11-2012. Но именно в работе Zongyue Wang,
Hongbo Yu и Xiaoyun Wang «Cryptanalysis of GOST R Hash Function»
предложены наиболее эффективные атаки на данный алгоритм.
http://habrahabr.ru/post/210684/
24

25.

25