SHA-1

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Secure Hash Algorithm 1 — алгоритм криптографічного хешування. Описано в RFC 3174. Для вхідного повідомлення довільної довжини (максимум біт, що приблизно дорівнює 2 ексабайти) алгоритм генерує 160-бітове хеш-значення, відоме також дайджестом повідомлення. Використовується у багатьох криптографічних додатках і протоколах. Також рекомендований як основний хеш-метод для державних установ в США. Принципи, покладені в основу SHA-1, аналогічні тим, які використовувалися Рональдом Ривестом при проектуванні MD4.

Історія[ред.ред. код]

В 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 leftrotate 5) + f + e + k + w[i]
        e = d
        d = c
        c = b leftrotate 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 в цифрових підписах. [1]

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

Порівняння 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 — для перевірки цілісності даних при завантаженні.

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

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

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