SHA-1

1. КАК РАБОТАЕТ SHA-1

2. Защищенная функция хэширования SHA–1 (Secure Hash Algorithm)

• каждый бит хэш-кода зависит от всех битов хэшируемых данных
(практически невероятно, чтобы два набора входных данных
породили один и тот же хэш-код)
• «сведения об успешных криптографических атаках на алгоритм
SHA отсутствуют» Б. Шнайер

3. Защищенная функция хэширования SHA–1 (Secure Hash Algorithm)

• Основное отличие алгоритма SHA от других защищенных
функций хэширования (MD2, MD4, MD5) –
генерирование 160-битового хэш-кода (против 128-битового).
Современные технологии распределенных вычислений и многопроцессорные
компьютеры демонстрируют недостаточную защищенность 128-битовых хэш-кодов.
«Кроме того, были разработаны сценарии целого ряда атак, демонстрирующих
уязвимость MD5 в отношении современных методов криптоанализа»
• Задача поиска двух наборов входных данных с одинаковым значением хэшфункции имеет сложность O(280)
• Задача нахождения набора входных данных с заданным значением имеет
сложность O(2160)

4. Основные характеристики SHA-1

• Длина хэш-кода - 160 бит
• Длина обрабатываемых блоков - 512 бит
• Число шагов алгоритма - 80
(4 раунда по 20 шагов)
• Максимальная длина хэшируемых данных - 264-1
• Число базовых функций - 4
• Число аддитивных констант - 4

5. Алгоритм SHA–1

• 1. На вход поступает k-битовый блок данных, где k < 264.
• 2. k-битовый блок дополняется так, чтобы его длина
стала кратной 512 разрядам (данные обрабатываются
512-битовыми
блоками).
Структура
дополнения
следующая: 100...0 (от 1 до 512 бит).
• 3. К полученному результату добавляется 64-битовое
представление длины исходного блока данных.
• 4. Инициализируются пять 32-разрядных переменных:
A = 0x67452301
B = 0xefcdab89
C = 0x98badcfe
D = 0x10325476
E = 0xc3d2e1f0
• 5. Производится обработка 512-битовых блоков данных
в 4 раунда по 20 операций каждый.

6. Схема одной операции SHA–1

а, b, c, d, e – 32 бита
Wt
ei-1
+
+
+
Kt
ei
+
di
di-1
ci-1
Ft
bi-1
<< 30
<< 5
ai-1
ci
bi
ai

7. Wt = (Wt-3  Wt-8  Wt-14  Wt-16) « 1 (16  t  79). Соответствие аддитивных констант Kt и нелинейных функций Ft номеру

Wt = (Wt-3 Wt-8 Wt-14 Wt-16) « 1 (16 t 79).
Соответствие аддитивных констант Kt и нелинейных функций Ft
номеру операции
80 операций = 4 раунда по 20 шагов
Номер шага (t)
Нелинейная
функция(Ft)
Аддитивная константа (Kt)
0 t 19
(X Y) (( X) Z)
0x5a827999 = 230 21/2
20 t 39
X Y Z
0x6ed9eba1 = 230 31/2
40 t 59
(X Y) (X Z) (Y Z)
0x8f1bbcdc = 230 51/2
60 t 79
X Y Z
0xca62c1d6 = 230 101/2

8. Алгоритм SHA–1 (продолжение)

• 6. Значения переменных a, b, c, d, e добавляются,
соответственно, к A, B, C, D, E.
• 7. Обрабатывается следующий блок данных.
• 8.
Окончательный
результат
получается
конкатенацией значений A, B, C, D, E (32-битовые).
• На выходе получается 160-битовый хэш-код.