SHA1

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

SHA-1

Клас	криптографічна хеш-функція

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

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

Історія

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

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

Одна ітерація алгоритму SHA-1

SHA-1 реалізує хеш-функцію, побудовану на ідеї функції стиснення. Входом функції стиснення є блок повідомлення довжиною 512 біт і вихід попереднього блоку повідомлення. Виходом є значення всіх хеш-блоків до цього моменту. Іншими словами хеш блоку ${\displaystyle M_{i}}$ дорівнює ${\displaystyle 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 

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

${\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

Псевдокод алгоритму 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 року і 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 в цифрових підписах.

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

Колізії

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

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

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

${\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)})}$.

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

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

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

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

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

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

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

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 чотири зсуви, що використовуються на кожному етапі, відрізняються від значень, які використовуються на попередніх етапах. В на кожному етапі використовується постійне значення зсуву.
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 (18 лютого 2005). . Архів оригіналу за 14 квітня 2017. Процитовано 21 лютого 2017.
2. . Архів оригіналу за 25 червня 2011. Процитовано 21 лютого 2017.
3. Bruce Schneier (8 жовтня 2015). . Schneier on Security. Архів оригіналу за 28 січня 2017. Процитовано 21 лютого 2017.
4. . 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. . Mozilla. Архів оригіналу за 7 вересня 2014. Процитовано 4 вересня 2014.
8. . Mozilla. Архів оригіналу за 6 травня 2017. Процитовано 9 вересня 2014.
9. . Mozilla. 23 вересня 2014. Архів оригіналу за 25 квітня 2017. Процитовано 24 вересня 2014.
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). . 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.
13. Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov. (PDF). CWI Amsterdam/Google Research. Архів оригіналу (PDF) за 11 жовтня 2018. Процитовано 24 лютого 2017.

Див. також

• Хеш-сума
• SHA-2
• MD5

Посилання

• RFC 3174(англ.)
• Огляд SHA-1 від Консорціуму Всесвітньої павутини [ 4 березня 2005 у Wayback Machine.](англ.)
• Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov. (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]}(англ.)