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

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\wedge l)\vee (\neg {m}\wedge 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\wedge l)\vee (m\wedge k)\vee (l\wedge k)$	Неможливо розібрати вираз (SVG (MathML можна ввімкнути через плагін браузера): Недійсна відповідь («Math extension cannot connect to Restbase.») від сервера «http://localhost:6011/uk.wikipedia.org/v1/»:): {\displaystyle 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, так звана атака з ідентичним префіксом (англ. identical-prefix collision attack), яка потребує (теоретично) 2⁶¹ обчислень SHA-1. На практиці, очікувалось, що знадобиться 2^63.1 обчислень SHA-1^[13].

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

\mathrm {SHA-1} (P||M_{1}^{(1)}||M_{2}^{(1)}||S)=\mathrm {SHA-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 — для перевірки цілісності даних при завантаженні.

Примітки

↑ Schneier, Bruce (18 лютого 2005). Schneier on Security: Cryptanalysis of SHA-1. Архів оригіналу за 14 квітня 2017. Процитовано 21 лютого 2017.
↑ NIST.gov - Computer Security Division - Computer Security Resource Center. Архів оригіналу за 25 червня 2011. Процитовано 21 лютого 2017.
↑ Bruce Schneier (8 жовтня 2015). SHA-1 Freestart Collision. Schneier on Security. Архів оригіналу за 28 січня 2017. Процитовано 21 лютого 2017.
↑ Windows Enforcement of Authenticode Code Signing and Timestamping. Microsoft. 24 вересня 2015. Архів оригіналу за 5 жовтня 2016. Процитовано 7 серпня 2016.
↑ Intent to Deprecate: SHA-1 certificates. Google. 3 вересня 2014. Процитовано 4 вересня 2014.
↑ Safari and WebKit ending support for SHA-1 certificates - Apple Support. Apple Inc. 24 січня 2017. Процитовано 4 лютого 2017.
↑ Bug 942515 - stop accepting SHA-1-based SSL certificates with notBefore >= 2014-03-01 and notAfter >= 2017-01-01, or any SHA-1-based SSL certificates after 2017-01-01. Mozilla. Архів оригіналу за 7 вересня 2014. Процитовано 4 вересня 2014.
↑ CA:Problematic Practices - MozillaWiki. Mozilla. Архів оригіналу за 6 травня 2017. Процитовано 9 вересня 2014.
↑ Phasing Out Certificates with SHA-1 based Signature Algorithms | Mozilla Security Blog. Mozilla. 23 вересня 2014. Архів оригіналу за 25 квітня 2017. Процитовано 24 вересня 2014.
↑ ^а ^б Marc Stevens (CWI Amsterdam), Elie Bursztein (Google), Pierre Karpman (CWI Amsterdam), Ange Albertini (Google), Yarik Markov (Google), Alex Petit Bianco (Google), Clement Baisse (Google) (23 лютого 2017). Announcing the first SHA1 collision. Google Security Blog. Архів оригіналу за 24 квітня 2017. Процитовано 23 лютого 2017.
↑ NIST Comments on Cryptanalytic Attacks on SHA-1 (англ.). Архів оригіналу за 13 жовтня 2012. Процитовано 29 серпня 2016.
↑ NIST Hash Competition (PDF) (англ.). Архів оригіналу (PDF) за 13 жовтня 2012. Процитовано 29 серпня 2016.
↑ ^а ^б ^в ^г ^д ^е ^ж Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov. The first collision for full SHA-1 (PDF). CWI Amsterdam/Google Research. Архів оригіналу (PDF) за 11 жовтня 2018. Процитовано 24 лютого 2017.

Див. також

Посилання

RFC 3174(англ.)
Огляд SHA-1 від Консорціуму Всесвітньої павутини [Архівовано 4 березня 2005 у Wayback Machine.](англ.)
Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov. The first collision for full SHA-1 (PDF). CWI Amsterdam/Google Research. Архів оригіналу (PDF) за 11 жовтня 2018. Процитовано 24 лютого 2017.
Взлом SHA-1 [Архівовано 5 травня 2017 у Wayback Machine.](англ.)
Доповідь про взлом SHA-1(англ.)
Брюс Шнайер про взлом SHA [Архівовано 1 грудня 2012 у WebCite](англ.)
Наслідки успішних атак на SHA-1 [Архівовано 26 грудня 2008 у Wayback Machine.](англ.)
Generate SHA-1 Online (онлайн сервіс для генерування SHA-1)^{[недоступне посилання з серпня 2019]}(англ.)

Це незавершена стаття з криптографії.
Ви можете допомогти проєкту, виправивши або дописавши її.

Це незавершена стаття про алгоритми.
Ви можете допомогти проєкту, виправивши або дописавши її.

[1] Schneier, Bruce (18 лютого 2005). Schneier on Security: Cryptanalysis of SHA-1. Архів оригіналу за 14 квітня 2017. Процитовано 21 лютого 2017.

[2] NIST.gov - Computer Security Division - Computer Security Resource Center. Архів оригіналу за 25 червня 2011. Процитовано 21 лютого 2017.

[3] Bruce Schneier (8 жовтня 2015). SHA-1 Freestart Collision. Schneier on Security. Архів оригіналу за 28 січня 2017. Процитовано 21 лютого 2017.

[4] Windows Enforcement of Authenticode Code Signing and Timestamping. Microsoft. 24 вересня 2015. Архів оригіналу за 5 жовтня 2016. Процитовано 7 серпня 2016.

[5] Intent to Deprecate: SHA-1 certificates. Google. 3 вересня 2014. Процитовано 4 вересня 2014.

[6] Safari and WebKit ending support for SHA-1 certificates - Apple Support. Apple Inc. 24 січня 2017. Процитовано 4 лютого 2017.

[7] Bug 942515 - stop accepting SHA-1-based SSL certificates with notBefore >= 2014-03-01 and notAfter >= 2017-01-01, or any SHA-1-based SSL certificates after 2017-01-01. Mozilla. Архів оригіналу за 7 вересня 2014. Процитовано 4 вересня 2014.

[8] CA:Problematic Practices - MozillaWiki. Mozilla. Архів оригіналу за 6 травня 2017. Процитовано 9 вересня 2014.

[9] Phasing Out Certificates with SHA-1 based Signature Algorithms | Mozilla Security Blog. Mozilla. 23 вересня 2014. Архів оригіналу за 25 квітня 2017. Процитовано 24 вересня 2014.

[gs.02-10] а ^б Marc Stevens (CWI Amsterdam), Elie Bursztein (Google), Pierre Karpman (CWI Amsterdam), Ange Albertini (Google), Yarik Markov (Google), Alex Petit Bianco (Google), Clement Baisse (Google) (23 лютого 2017). Announcing the first SHA1 collision. Google Security Blog. Архів оригіналу за 24 квітня 2017. Процитовано 23 лютого 2017.

[11] NIST Comments on Cryptanalytic Attacks on SHA-1 (англ.). Архів оригіналу за 13 жовтня 2012. Процитовано 29 серпня 2016.

[12] NIST Hash Competition (PDF) (англ.). Архів оригіналу (PDF) за 13 жовтня 2012. Процитовано 29 серпня 2016.

[shattered-13] а ^б ^в ^г ^д ^е ^ж Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov. The first collision for full SHA-1 (PDF). CWI Amsterdam/Google Research. Архів оригіналу (PDF) за 11 жовтня 2018. Процитовано 24 лютого 2017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]