SHA-1

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
SHA-1
Клас криптографічна хеш-функція


Secure Hash Algorithm 1 — алгоритм криптографічного хешування. Описано в RFC 3174. Для вхідного повідомлення довільної довжини (максимум біт, що приблизно дорівнює 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 біт і вихід попереднього блоку повідомлення. Виходом є значення всіх хеш-блоків до цього моменту. Іншими словами хеш блоку дорівнює . Хеш-значенням всього повідомлення є виходом останнього блоку.

Ініціалізація[ред.ред. код]

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

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

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

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

= 0x5A827999 0≤t≤19
= 0x6ED9EBA1 20≤t≤39
= 0x8F1BBCDC 40≤t≤59
= 0xCA62C1D6 60≤t≤79

Головний цикл[ред.ред. код]

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

                                      при 0≤t≤15
 = (-3  -8  -14  -16) << 1     при 16≤t≤79

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


 для  від 0 до 79
        temp = (a << 5) + (b,c,d) + e + 
        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

Криптоаналіз[ред.ред. код]

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

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

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

  • друга задача вимагає 2160 операцій.
  • перша ж вимагає в середньому 2160/2=280 операцій, якщо використовувати атаку Днів народження.

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

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

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

Хоча теоретично SHA-1 вважається зламаним (кількість обчислювальних операцій зменшено в 280-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 775 808), для чого знадобилось понад 6610 процесор-років, необхідна кількість обчислень виявилась майже в 100 тисяч раз меншою за повний перебір. Час необхідний на обчислення було додатково скорочено завдяки використанню графічних процесорів. Таким чином дослідники довели, що обчислення колізій функції SHA-1 стало практично досяжним для зловмисника зі значною апаратно-матеріальною підтримкою[10].

Дослідники вирішили скористатись найкращою відомою атакою на SHA-1, так звана атака з ідентичним префіксом (англ. identical-prefix collision attack), яка потребує (теоретично) 261 обчислень SHA-1. На практиці, очікувалось, що знадобиться 263.1 обчислень SHA-1[13].

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

Пошук колізії відбувався у два кроки. На першому кроці обчислення відбувались на звичайних мікропроцесорах із використанням сильно зміненої програми HashClash — програма була істотно змінена для можливості ефективної роботи на багатьох ядрах та багатьох процесорах. На цьому кроці була знайдена пара . Другий крок був реалізований на графічних процесорах. На цьому кроці була знайдена пара [13].

Порівняння з MD5 та SHA-0[ред.ред. код]

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

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

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

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

Порівняння SHA1 з іншими алгоритмами[ред.ред. код]

Порівняння з MD5[ред.ред. код]

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

Схожість:

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

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

  1. У SHA-1 на четвертому етапі використовується та ж функція f, що і на другому етапі.
  2. В MD5 у кожній дії використовується унікальна адитивна константа. У SHA-1 константи використовуються повторно для кожної із чотирьох груп.
  3. У SHA-1 додана п'ята змінна.
  4. SHA-1 використовує циклічний код виправлення помилок.
  5. В MD5 чотири зсуви, що використовуються на кожному етапі, відрізняються від значень, які використовуються на попередніх етапах. В SHA на кожному етапі використовується постійне значення зсуву.
  6. В MD5 чотири різних елементарних логічних функції, в SHA-1 - три.
  7. В MD5 довжина дайджесту становить 128 біт, в SHA-1 - 160 біт.
  8. 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 — для перевірки цілісності даних при завантаженні.

Примітки[ред.ред. код]

  1. Schneier, Bruce (February 18, 2005). Schneier on Security: Cryptanalysis of SHA-1. 
  2. NIST.gov - Computer Security Division - Computer Security Resource Center. 
  3. Bruce Schneier (8 October 2015). SHA-1 Freestart Collision. Schneier on Security. 
  4. Windows Enforcement of Authenticode Code Signing and Timestamping. Microsoft. 2015-09-24. Процитовано 2016-08-07. 
  5. Intent to Deprecate: SHA-1 certificates. Google. 2014-09-03. Процитовано 2014-09-04. 
  6. Safari and WebKit ending support for SHA-1 certificates - Apple Support. Apple Inc. 2017-01-24. Процитовано 2017-02-04. 
  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. Процитовано 2014-09-04. 
  8. CA:Problematic Practices - MozillaWiki. Mozilla. Процитовано 2014-09-09. 
  9. Phasing Out Certificates with SHA-1 based Signature Algorithms | Mozilla Security Blog. Mozilla. 2014-09-23. Процитовано 2014-09-24. 
  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. 
  11. NIST Comments on Cryptanalytic Attacks on SHA-1 (en). 
  12. NIST Hash Competition (en). 
  13. а б в г д е ж Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov. The first collision for full SHA-1. CWI Amsterdam/Google Research. 

Див. також[ред.ред. код]

Посилання[ред.ред. код]