SHA-1

Шаблон:Картка алгоритм Secure Hash Algorithm 1 — алгоритм криптографічного хешування. Описано в RFC 3174. Для вхідного повідомлення довільної довжини (максимум $2^{64} - 1$ біт, що приблизно дорівнює 2 ексабайти) алгоритм генерує 160-бітове хеш-значення, відоме також дайджестом повідомлення.

Вважається, що SHA-1 не гарантує достатнього захисту проти атак. Вже в 2005 дослідниками були відкриті методи атаки на SHA-1, які поставили під сумнів тривалість використання цього алгоритму^[1]. Тому вже з 2010 року низка організацій та компаній стали рекомендувати використання SHA-2 або SHA-3 замість нього^[2]^[3]. Microsoft,^[4] Google,^[5] Apple^[6] та Mozilla^[7]^[8]^[9] оголосили, що їхні веббраузери припинять приймати SSL сертифікати з SHA-1 починаючи з 2017 року.

23 лютого 2017 року була доведена практична досяжність обчислення колізій для функції SHA-1 без потреби звертатись до повного перебору^[10].

Історія

В 1993 році NSA спільно із NIST розробили алгоритм безпечного хешування (зараз відомий як SHA-0) (опублікований в документі FIPS PUB 180) для стандарту безпечного хешування. Однак незабаром NSA відкликало дану версію, пославшись на виявлену ними помилку, яка так і не була розкрита. І замінило його виправленою версією, опублікованою в 1995 році у документі FIPS PUB 180-1. Ця версія і вважається тим, що називають SHA-1. Пізніше, на конференції CRYPTO в 1998 році два французьких дослідника представили атаку на алгоритм SHA-0, яка не працювала на алгоритмі SHA-1. Можливо, це і була помилка, відкрита NSA.

Опис алгоритму

SHA-1 реалізує хеш-функцію, побудовану на ідеї функції стиснення. Входом функції стиснення є блок повідомлення довжиною 512 біт і вихід попереднього блоку повідомлення. Виходом є значення всіх хеш-блоків до цього моменту. Іншими словами хеш блоку $M_{i}$ дорівнює $h_{i} = f (M_{i}, h_{i - 1})$ . Хеш-значенням всього повідомлення є виходом останнього блоку.

Ініціалізація

Вхідне повідомлення розбивається на блоки по 512 біт у кожному. Останній блок доповнюється до довжини кратної 512 біт. Спочатку додається 1, а потім нулі, щоб довжина блоку стала рівною (512-64=448) біт. В останні 64 біта записується довжина вихідного повідомлення у бітах (в big-endian форматі). Якщо останній блок має довжину понад 448, але менше 512 біт, то додаток виконується в такий спосіб: спочатку додається 1, потім нулі аж до кінця 512-бітного блоку; після цього створюється ще один 512-бітний блок, який заповнюється аж до 448 біта нулями, після чого в 64 біта, що залишилися, записується довжина вихідного повідомлення в бітах (в big-endian форматі). Доповнення останнього блоку здійснюється завжди, навіть якщо повідомлення вже має потрібну довжину.

Ініціалізуються п'ять 32-бітових змінних:

A = a = 0x67452301
B = b = 0xEFCDAB89
C = c = 0x98BADCFE
D = d = 0x10325476
E = e = 0xC3D2E1F0

Визначаються чотири нелінійні операції і чотири константи.

$F_{t} (m, l, k) = (m \land l) \lor (\neg m \land k)$	$K_{t}$ = 0x5A827999	0≤t≤19
$F_{t} (m, l, k) = m \oplus l \oplus k$	$K_{t}$ = 0x6ED9EBA1	20≤t≤39
$F_{t} (m, l, k) = (m \land l) \lor (m \land k) \lor (l \land k)$	$K_{t}$ = 0x8F1BBCDC	40≤t≤59
$F_{t} (m, l, k) = m \oplus l \oplus k$	$K_{t}$ = 0xCA62C1D6	60≤t≤79

Головний цикл

Головний цикл ітеративно обробляє кожен 512-бітний блок. Ітерація складається з чотирьох етапів по двадцять операцій у кожному. Блок повідомлення перетворюється з 16 32-бітових слів $M_{i}$ у 80 32-бітових слів $W_{j}$ за наступним правилом:

 $W_{t} = M_{t}$                                       при 0≤t≤15
 $W_{t}$  = ( $W_{t}$ _-3  $\oplus$   $W_{t}$ _-8  $\oplus$   $W_{t}$ _-14  $\oplus$   $W_{t}$ _-16) << 1     при 16≤t≤79

тут << — це циклічний зсув вліво

 для  $t$  від 0 до 79
	temp = (a << 5) +  $F_{t}$ (b,c,d) + e +  $W_{t} + K_{t}$ 
	e = d
	d = c
	c = b << 30
	b = a
	a = temp

Після цього a, b, c, d, e додаються до A, B, C, D, E відповідно. Починається наступна ітерація.

Підсумковим значенням буде об'єднання п'яти 32-бітних слів в одне 160-бітове хеш-значення.

Псевдокод SHA-1

Псевдокод алгоритму SHA-1 наступний:

 Зауваження: Всі використовувані змінні 32-х бітні.

Ініціалізація змінних:
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0

Попередня обробка:
Приєднуємо біт '1' до повідомлення
Приєднуємо k бітів '0', де k найменше число ≥ 0 таке, щоб довжина отриманого повідомлення (в бітах) була рівна по модулю 512 із 448 (length mod 512 == 448)
Додаємо довжину вихідного повідомлення (до попередньої обробки) як ціле 64-бітове big-endian число в бітах.

В процесі повідомлення розбивається послідовно по 512 біт:
for перебираємо всі такі частини
    розбиваємо цю частину ще на 16 частин - слів по 32-біта w[i], 0 <= i <= 15

    16 слів по 32-біта доповнюються до 80 32-бітових слів:
    for i from 16 to 79
        w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) циклічний зсув вліво 1

    Ініціалізація хеш-значень цієї частини:
    a = h0
    b = h1
    c = h2
    d = h3
    e = h4

    Основний цикл:
    for i from 0 to 79
        if 0 ≤ i ≤ 19 then
            f = (b and c) or ((not b) and d)
            k = 0x5A827999
        else if 20 ≤ i ≤ 39 then
            f = b xor c xor d
            k = 0x6ED9EBA1
        else if 40 ≤ i ≤ 59 then
            f = (b and c) or (b and d) or (c and d)
            k = 0x8F1BBCDC
        else if 60 ≤ i ≤ 79 then
            f = b xor c xor d
            k = 0xCA62C1D6

        temp = (a циклічний зсув вліво 5) + f + e + k + w[i]
        e = d
        d = c
        c = b циклічний зсув вліво 30
        b = a
        a = temp

    Додаємо хеш-значення цієї частини до результату:
    h0 = h0 + a
    h1 = h1 + b 
    h2 = h2 + c
    h3 = h3 + d
    h4 = h4 + e

Підсумкове хеш-значення:
digest = hash = h0 append h1 append h2 append h3 append h4

Замість оригінального формулювання FIPS PUB 180-1 наведені такі еквівалентні вирази, що можуть бути використані на комп'ютері f в головному циклі:

(0  ≤ i ≤ 19): f = d xor (b and (c xor d))                (альтернатива 1)
(0  ≤ i ≤ 19): f = (b and c) xor ((not b) and d)          (альтернатива 2)
(0  ≤ i ≤ 19): f = (b and c) + ((not b) and d)            (альтернатива 3)
 
(40 ≤ i ≤ 59): f = (b and c) or (d and (b or c))          (альтернатива 1)
(40 ≤ i ≤ 59): f = (b and c) or (d and (b xor c))         (альтернатива 2)
(40 ≤ i ≤ 59): f = (b and c) + (d and (b xor c))          (альтернатива 3)
(40 ≤ i ≤ 59): f = (b and c) xor (b and d) xor (c and d)  (альтернатива 4)

Приклади

Нижче наведені приклади хеш SHA-1. Для всіх повідомлень використано кодування UTF-8.

Хеш українською мовою:

SHA-1("Привіт") 
  = be3ba4d3 aa62fe70 d8aa4acd 4f0d33e2 896d3071

Хеш англійською мовою:

SHA-1("Hello World") 
  = 0a4d55a8 d778e502 2fab7019 77c5d840 bbc486d0

SHA-1("sha")
  = d8f45903 20e1343a 915b6394 170650a8 f35d6926

Невелика зміна вхідного тексту (одна буква у верхньому регістрі) призводить до сильної зміни самого хешу. Це відбувається внаслідок лавинного ефекту.

SHA-1("Sha") 
  = ba79baeb 9f10896a 46ae7471 5271b7f5 86e74640

Навіть для порожнього рядка обчислюється нетривіальне хеш-значення.

SHA-1("") 
  = da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709

Криптоаналіз

Криптоаналіз хеш-функцій спрямований на дослідження вразливостей до різного виду атак. Основні із них:

знаходження колізій — ситуація, коли двом різним вхідним повідомленням відповідає одне і те ж хеш-значення.
знаходження прообразу — вихідного повідомлення — по його хешу.

При вирішенні методом «грубої сили»:

друга задача вимагає 2¹⁶⁰ операцій.
перша ж вимагає в середньому 2^160/2=2⁸⁰ операцій, якщо використовувати атаку Днів народження.

Від стійкості хеш-функції до знаходження колізій залежить безпека електронного цифрового підпису із використанням даного хеш-алгоритму. Від стійкості до знаходження прообразу залежить безпека зберігання хешів паролів для аутентифікації.

У січні 2005 року Vincent Rijmen і Elisabeth Oswald опублікували повідомлення про атаку на усічену версію SHA-1 (53 раунди замість 80-и), яка дозволяє знаходити колізії менше, ніж за 2⁸⁰ операцій.

У лютому 2005 року Сяоюн Ван, Іцюнь Ліза Інь і Хунбо Юй (Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu) представили атаку на повноцінний SHA-1, яка вимагає менше 2⁶⁹ операцій.

Хоча теоретично SHA-1 вважається зламаним (кількість обчислювальних операцій зменшено в 2^80-63=131 000 разів), на практиці подібний злом неможливий, оскільки займе п'ять мільярдів років.

Бурт Калінскі, глава дослідницького відділу в «лабораторії RSA» передбачає, що перша атака по знаходженню прообразу буде успішно здійснена в найближчі 5-10 років.

З огляду на те, що теоретичні атаки на SHA-1 виявилися успішними, NIST планує повністю відмовитися від використання SHA-1 в цифрових підписах.^[11]

2 листопада 2007 рік NIST анонсував конкурс з розробки нового алгоритму SHA-3, який тривав до 2012 року.^[12]

Колізії

23 лютого 2017 року команда дослідників з наукового інституту CWI Amsterdam та компанії Google оголосили про розробку ними практично досяжного методу побудови колізій для функції SHA-1. Попри те, що для створення PDF-файлу з ідентичним SHA-1 дайджестом як і у оригінального їм знадобилось здійснити майже 9 квінтильйонів обчислень SHA-1 (точне число 9 223 372 036 854 776 000), для чого знадобилось понад 6610 процесор-років, необхідна кількість обчислень виявилась майже в 100 тисяч раз меншою за повний перебір. Час необхідний на обчислення було додатково скорочено завдяки використанню графічних процесорів. Таким чином дослідники довели, що обчислення колізій функції SHA-1 стало практично досяжним для зловмисника зі значною апаратно-матеріальною підтримкою^[10].

Дослідники вирішили скористатись найкращою відомою атакою на SHA-1, так звана атака з ідентичним префіксом (Шаблон:Lang-en), яка потребує (теоретично) 2⁶¹ обчислень SHA-1. На практиці, очікувалось, що знадобиться 2^63.1 обчислень SHA-1^[13].

Атака полягає в пошуку двох майже колізійних блоків при заданому префіксі Шаблон:Mvar, які утворюють колізію для будь-якого суфіксу Шаблон:Mvar^[13]:

S H A - 1 (P | | M_{1}^{(1)} | | M_{2}^{(1)} | | S) = S H A - 1 (P | | M_{1}^{(2)} | | M_{2}^{(2)} | | S) .

Пошук колізії відбувався у два кроки. На першому кроці обчислення відбувались на звичайних мікропроцесорах із використанням сильно зміненої програми HashClash — програма була істотно змінена для можливості ефективної роботи на багатьох ядрах та багатьох процесорах. На цьому кроці була знайдена пара $(M_{1}^{(1)}, M_{1}^{(2)})$ . Другий крок був реалізований на графічних процесорах. На цьому кроці була знайдена пара $(M_{2}^{(1)}, M_{2}^{(2)})$ ^[13].

Порівняння з MD5 та SHA-0

Пошук колізії алгоритмом з «ідентичним префіксом» для MD5, SHA-0 та SHA-1 мають багато спільного, проте істотно відмінну складність^[13].

Найкращий відомий алгоритм пошуку колізії методом «ідентичного префіксу» вимагає 2¹⁶ обчислень MD5^[13].

Попри істотну схожість із SHA-1, SHA-0 набагато вразливіший до пошуку колізій. Найкращий відомий алгоритм вимагає 2^33.6 обчислень SHA-0^[13].

Таким чином, пошук колізій для SHA-0 та MD5 може відбуватись навіть із допомогою сучасного смартфону^[13].

Порівняння SHA1 з іншими алгоритмами

Порівняння з MD5

MD5 і SHA-1 є, по суті, поліпшеними версіями MD4.

Схожість:

Чотири етапи.
Кожна дія додається до раніше отриманого результату.
Розмір блоку обробки становить 512 біт.
Обидва алгоритми виконують складання по модулю 2³², вони розраховані на 32-х бітну архітектуру.

Відмінності:

У SHA-1 на четвертому етапі використовується та ж функція f, що і на другому етапі.
В MD5 у кожній дії використовується унікальна адитивна константа. У SHA-1 константи використовуються повторно для кожної із чотирьох груп.
У SHA-1 додана п'ята змінна.
SHA-1 використовує циклічний код виправлення помилок.
В MD5 чотири зсуви, що використовуються на кожному етапі, відрізняються від значень, які використовуються на попередніх етапах. В SHA на кожному етапі використовується постійне значення зсуву.
В MD5 чотири різних елементарних логічних функції, в SHA-1 - три.
В MD5 довжина дайджесту становить 128 біт, в SHA-1 - 160 біт.
SHA-1 містить більше раундів (80 замість 64) і виконується на 160-бітному буфері у порівнянні із 128-бітовим буфером MD5. Таким чином, SHA-1 повинен виконуватися приблизно на 25% повільніше, ніж MD5 на тій же апаратурі.

Брюс Шнайер наводить наступний висновок: «SHA-1 - це MD4 із додаванням розширюючого перетворення, додаткового етапу і поліпшеним лавинним ефектом. MD5 - це MD4 із поліпшеним двійковим хешуванням, додатковим етапом і поліпшеним лавинним ефектом.»

Використання

Хеш-функції використовуються в системах контролю версій, системах електронного цифрового підпису, а також для побудови кодів аутентифікації.

SHA-1 є найбільш поширеним із усього сімейства SHA і застосовується у різних широко поширених криптографічних додатках і алгоритмах.

SHA-1 використовується в наступних стандартах:

S/MIME — дайджести повідомлень.
SSL — дайджести повідомлень.
IPSec — для алгоритму перевірки цілісності в з'єднанні «точка-точка».
SSH — для перевірки цілісності переданих даних.
PGP — для створення електронного цифрового підпису.
Git — для ідентифікації кожного об'єкта по SHA-1-хешу від збереженої в об'єкті інформації.
Mercurial — для ідентифікації ревізій.
BitTorrent — для перевірки цілісності даних при завантаженні.

Примітки

Шаблон:Примітки

Див. також

Посилання

Шаблон:Геш-функції та коди аутентифікації повідомлення Шаблон:ВП-портали Шаблон:Refimprove

Шаблон:Crypto-stub Шаблон:Algorithm-stub

[1] Шаблон:Cite web

[2] Шаблон:Cite web

[3] Шаблон:Cite web

[4] Шаблон:Cite web Шаблон:Webarchive

[5] Шаблон:Cite web

[6] Шаблон:Cite web

[7] Шаблон:Cite web

[8] Шаблон:Cite web

[9] Шаблон:Cite web

[gs.02-10] 10,0 ^10,1 Шаблон:Cite web

[11] Шаблон:Cite web

[12] Шаблон:Citeweb

[shattered-13] 13,0 ^13,1 ^13,2 ^13,3 ^13,4 ^13,5 ^13,6 Шаблон:Cite web

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]