SHA-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

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

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

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

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

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

 для ${\displaystyle t}$ від 0 до 79
	temp = (a << 5) + ${\displaystyle F_{t}}$(b,c,d) + e + ${\displaystyle 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 наступний:

 Зауваження: Всі використовувані змінні 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)

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]:

${\displaystyle \mathrm {SHA-1} (P||M_{1}^{(1)}||M_{2}^{(1)}||S)=\mathrm {SHA-1} (P||M_{1}^{(2)}||M_{2}^{(2)}||S).}$

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

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

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

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

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

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

Схожість:

1. Чотири етапи.
2. Кожна дія додається до раніше отриманого результату.
3. Розмір блоку обробки становить 512 біт.
4. Обидва алгоритми виконують складання по модулю 2³², вони розраховані на 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 із поліпшеним двійковим хешуванням, додатковим етапом і поліпшеним лавинним ефектом.»