www.wikidata.uk-ua.nina.az

SHA 1 Secure Hash Algorithm 1 алгоритм криптографічного хешування Описано в RFC 3174 Для вхідного повідомлення довільної

SHA-1

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

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

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

Історія Редагувати

В 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 біта, що залишилися, записується довжина вихідного повідомлення в бітах (в big-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 в цифрових підписах.

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), яка потребує (теоретично) 261 обчислень SHA-1. На практиці, очікувалось, що знадобиться 263.1 обчислень SHA-1.

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

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

Порівняння з MD5 та SHA-0 Редагувати

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

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

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

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

Порівняння 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 (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 (англ.). Архів оригіналу за 13 жовтня 2012. Процитовано 29 серпня 2016. 
  13. ↑ Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov. . CWI Amsterdam/Google Research. Архів оригіналу за 11 жовтня 2018. Процитовано 24 лютого 2017. 

Див. також Редагувати

Посилання Редагувати

Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки.
Матеріал без джерел може бути піддано сумніву та вилучено. (лютий 2017)


Це незавершена стаття з криптографії.
Ви можете допомогти проєкту, виправивши або дописавши її.
Це незавершена стаття про алгоритми.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Secure Hash Algorithm 1 algoritm kriptografichnogo heshuvannya Opisano v RFC 3174 Dlya vhidnogo povidomlennya dovilnoyi dovzhini maksimum 2 64 1 displaystyle 2 64 1 bit sho priblizno dorivnyuye 2 eksabajti algoritm generuye 160 bitove hesh znachennya vidome takozh dajdzhestom povidomlennya SHA 1Klas kriptografichna hesh funkciyaVvazhayetsya sho SHA 1 ne garantuye dostatnogo zahistu proti atak Vzhe v 2005 doslidnikami buli vidkriti metodi ataki na SHA 1 yaki postavili pid sumniv trivalist vikoristannya cogo algoritmu 1 Tomu vzhe z 2010 roku nizka organizacij ta kompanij stali rekomenduvati vikoristannya SHA 2 abo SHA 3 zamist nogo 2 3 Microsoft 4 Google 5 Apple 6 ta Mozilla 7 8 9 ogolosili sho yihni vebbrauzeri pripinyat prijmati SSL sertifikati z SHA 1 pochinayuchi z 2017 roku 23 lyutogo 2017 roku bula dovedena praktichna dosyazhnist obchislennya kolizij dlya funkciyi SHA 1 bez potrebi zvertatis do povnogo pereboru 10 Zmist 1 Istoriya 2 Opis algoritmu 2 1 Inicializaciya 2 2 Golovnij cikl 2 3 Psevdokod SHA 1 3 Prikladi 4 Kriptoanaliz 4 1 Koliziyi 4 2 Porivnyannya z MD5 ta SHA 0 5 Porivnyannya SHA1 z inshimi algoritmami 5 1 Porivnyannya z MD5 6 Vikoristannya 7 Primitki 8 Div takozh 9 PosilannyaIstoriya RedaguvatiV 1993 roci NSA spilno iz NIST rozrobili algoritm bezpechnogo heshuvannya zaraz vidomij yak SHA 0 opublikovanij v dokumenti FIPS PUB 180 dlya standartu bezpechnogo heshuvannya Odnak nezabarom NSA vidklikalo danu versiyu poslavshis na viyavlenu nimi pomilku yaka tak i ne bula rozkrita I zaminilo jogo vipravlenoyu versiyeyu opublikovanoyu v 1995 roci u dokumenti FIPS PUB 180 1 Cya versiya i vvazhayetsya tim sho nazivayut SHA 1 Piznishe na konferenciyi CRYPTO v 1998 roci dva francuzkih doslidnika predstavili ataku na algoritm SHA 0 yaka ne pracyuvala na algoritmi SHA 1 Mozhlivo ce i bula pomilka vidkrita NSA Opis algoritmu Redaguvati nbsp Odna iteraciya algoritmu SHA 1SHA 1 realizuye hesh funkciyu pobudovanu na ideyi funkciyi stisnennya Vhodom funkciyi stisnennya ye blok povidomlennya dovzhinoyu 512 bit i vihid poperednogo bloku povidomlennya Vihodom ye znachennya vsih hesh blokiv do cogo momentu Inshimi slovami hesh bloku M i displaystyle M i nbsp dorivnyuye h i f M i h i 1 displaystyle h i f M i h i 1 nbsp Hesh znachennyam vsogo povidomlennya ye vihodom ostannogo bloku Inicializaciya Redaguvati Vhidne povidomlennya rozbivayetsya na bloki po 512 bit u kozhnomu Ostannij blok dopovnyuyetsya do dovzhini kratnoyi 512 bit Spochatku dodayetsya 1 a potim nuli shob dovzhina bloku stala rivnoyu 512 64 448 bit V ostanni 64 bita zapisuyetsya dovzhina vihidnogo povidomlennya u bitah v big endian formati Yaksho ostannij blok maye dovzhinu ponad 448 ale menshe 512 bit to dodatok vikonuyetsya v takij sposib spochatku dodayetsya 1 potim nuli azh do kincya 512 bitnogo bloku pislya cogo stvoryuyetsya she odin 512 bitnij blok yakij zapovnyuyetsya azh do 448 bita nulyami pislya chogo v 64 bita sho zalishilisya zapisuyetsya dovzhina vihidnogo povidomlennya v bitah v big endian formati Dopovnennya ostannogo bloku zdijsnyuyetsya zavzhdi navit yaksho povidomlennya vzhe maye potribnu dovzhinu Inicializuyutsya p yat 32 bitovih zminnih A a 0x67452301 B b 0xEFCDAB89 C c 0x98BADCFE D d 0x10325476 E e 0xC3D2E1F0 Viznachayutsya chotiri nelinijni operaciyi i chotiri konstanti F t m l k m l m k displaystyle F t m l k m wedge l vee neg m wedge k nbsp K t displaystyle K t nbsp 0x5A827999 0 t 19F t m l k m l k displaystyle F t m l k m oplus l oplus k nbsp K t displaystyle K t nbsp 0x6ED9EBA1 20 t 39F t m l k m l m k l k displaystyle F t m l k m wedge l vee m wedge k vee l wedge k nbsp K t displaystyle K t nbsp 0x8F1BBCDC 40 t 59F t m l k m l k displaystyle F t m l k m oplus l oplus k nbsp K t displaystyle K t nbsp 0xCA62C1D6 60 t 79Golovnij cikl Redaguvati Golovnij cikl iterativno obroblyaye kozhen 512 bitnij blok Iteraciya skladayetsya z chotiroh etapiv po dvadcyat operacij u kozhnomu Blok povidomlennya peretvoryuyetsya z 16 32 bitovih sliv M i displaystyle M i nbsp u 80 32 bitovih sliv W j displaystyle W j nbsp za nastupnim pravilom W t M t displaystyle W t M t nbsp pri 0 t 15 W t displaystyle W t nbsp W t displaystyle W t nbsp 3 displaystyle oplus nbsp W t displaystyle W t nbsp 8 displaystyle oplus nbsp W t displaystyle W t nbsp 14 displaystyle oplus nbsp W t displaystyle W t nbsp 16 lt lt 1 pri 16 t 79 tut lt lt ce ciklichnij zsuv vlivo dlya t displaystyle t nbsp vid 0 do 79 temp a lt lt 5 F t displaystyle F t nbsp b c d e W t K t displaystyle W t K t nbsp e d d c c b lt lt 30 b a a temp Pislya cogo a b c d e dodayutsya do A B C D E vidpovidno Pochinayetsya nastupna iteraciya Pidsumkovim znachennyam bude ob yednannya p yati 32 bitnih sliv v odne 160 bitove hesh znachennya Psevdokod SHA 1 Redaguvati Psevdokod algoritmu SHA 1 nastupnij Zauvazhennya Vsi vikoristovuvani zminni 32 h bitni Inicializaciya zminnih h0 0x67452301 h1 0xEFCDAB89 h2 0x98BADCFE h3 0x10325476 h4 0xC3D2E1F0 Poperednya obrobka Priyednuyemo bit 1 do povidomlennya Priyednuyemo k bitiv 0 de k najmenshe chislo 0 take shob dovzhina otrimanogo povidomlennya v bitah bula rivna po modulyu 512 iz 448 length mod 512 448 Dodayemo dovzhinu vihidnogo povidomlennya do poperednoyi obrobki yak cile 64 bitove big endian chislo v bitah V procesi povidomlennya rozbivayetsya poslidovno po 512 bit for perebirayemo vsi taki chastini rozbivayemo cyu chastinu she na 16 chastin sliv po 32 bita w i 0 lt i lt 15 16 sliv po 32 bita dopovnyuyutsya do 80 32 bitovih sliv for i from 16 to 79 w i w i 3 xor w i 8 xor w i 14 xor w i 16 ciklichnij zsuv vlivo 1 Inicializaciya hesh znachen ciyeyi chastini a h0 b h1 c h2 d h3 e h4 Osnovnij cikl 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 ciklichnij zsuv vlivo 5 f e k w i e d d c c b ciklichnij zsuv vlivo 30 b a a temp Dodayemo hesh znachennya ciyeyi chastini do rezultatu h0 h0 a h1 h1 b h2 h2 c h3 h3 d h4 h4 e Pidsumkove hesh znachennya digest hash h0 append h1 append h2 append h3 append h4 Zamist originalnogo formulyuvannya FIPS PUB 180 1 navedeni taki ekvivalentni virazi sho mozhut buti vikoristani na komp yuteri f v golovnomu cikli 0 i 19 f d xor b and c xor d alternativa 1 0 i 19 f b and c xor not b and d alternativa 2 0 i 19 f b and c not b and d alternativa 3 40 i 59 f b and c or d and b or c alternativa 1 40 i 59 f b and c or d and b xor c alternativa 2 40 i 59 f b and c d and b xor c alternativa 3 40 i 59 f b and c xor b and d xor c and d alternativa 4 Prikladi RedaguvatiNizhche navedeni prikladi hesh SHA 1 Dlya vsih povidomlen vikoristano koduvannya UTF 8 Hesh ukrayinskoyu movoyu SHA 1 Privit be3ba4d3 aa62fe70 d8aa4acd 4f0d33e2 896d3071 Hesh anglijskoyu movoyu SHA 1 Hello World 0a4d55a8 d778e502 2fab7019 77c5d840 bbc486d0 SHA 1 sha d8f45903 20e1343a 915b6394 170650a8 f35d6926 Nevelika zmina vhidnogo tekstu odna bukva u verhnomu registri prizvodit do silnoyi zmini samogo heshu Ce vidbuvayetsya vnaslidok lavinnogo efektu SHA 1 Sha ba79baeb 9f10896a 46ae7471 5271b7f5 86e74640 Navit dlya porozhnogo ryadka obchislyuyetsya netrivialne hesh znachennya SHA 1 da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709Kriptoanaliz RedaguvatiKriptoanaliz hesh funkcij spryamovanij na doslidzhennya vrazlivostej do riznogo vidu atak Osnovni iz nih znahodzhennya kolizij situaciya koli dvom riznim vhidnim povidomlennyam vidpovidaye odne i te zh hesh znachennya znahodzhennya proobrazu vihidnogo povidomlennya po jogo heshu Pri virishenni metodom gruboyi sili druga zadacha vimagaye 2160 operacij persha zh vimagaye v serednomu 2160 2 280 operacij yaksho vikoristovuvati ataku Dniv narodzhennya Vid stijkosti hesh funkciyi do znahodzhennya kolizij zalezhit bezpeka elektronnogo cifrovogo pidpisu iz vikoristannyam danogo hesh algoritmu Vid stijkosti do znahodzhennya proobrazu zalezhit bezpeka zberigannya heshiv paroliv dlya autentifikaciyi U sichni 2005 roku Vincent Rijmen i Elisabeth Oswald opublikuvali povidomlennya pro ataku na usichenu versiyu SHA 1 53 raundi zamist 80 i yaka dozvolyaye znahoditi koliziyi menshe nizh za 280 operacij U lyutomu 2005 roku Syaoyun Van Icyun Liza In i Hunbo Yuj Xiaoyun Wang Yiqun Lisa Yin Hongbo Yu predstavili ataku na povnocinnij SHA 1 yaka vimagaye menshe 269 operacij Hocha teoretichno SHA 1 vvazhayetsya zlamanim kilkist obchislyuvalnih operacij zmensheno v 280 63 131 000 raziv na praktici podibnij zlom nemozhlivij oskilki zajme p yat milyardiv rokiv Burt Kalinski glava doslidnickogo viddilu v laboratoriyi RSA peredbachaye sho persha ataka po znahodzhennyu proobrazu bude uspishno zdijsnena v najblizhchi 5 10 rokiv Z oglyadu na te sho teoretichni ataki na SHA 1 viyavilisya uspishnimi NIST planuye povnistyu vidmovitisya vid vikoristannya SHA 1 v cifrovih pidpisah 11 2 listopada 2007 rik NIST anonsuvav konkurs z rozrobki novogo algoritmu SHA 3 yakij trivav do 2012 roku 12 Koliziyi Redaguvati 23 lyutogo 2017 roku komanda doslidnikiv z naukovogo institutu CWI Amsterdam ta kompaniyi Google ogolosili pro rozrobku nimi praktichno dosyazhnogo metodu pobudovi kolizij dlya funkciyi SHA 1 Popri te sho dlya stvorennya PDF fajlu z identichnim SHA 1 dajdzhestom yak i u originalnogo yim znadobilos zdijsniti majzhe 9 kvintiljoniv obchislen SHA 1 tochne chislo 9 223 372 036 854 776 000 dlya chogo znadobilos ponad 6610 procesor rokiv neobhidna kilkist obchislen viyavilas majzhe v 100 tisyach raz menshoyu za povnij perebir Chas neobhidnij na obchislennya bulo dodatkovo skorocheno zavdyaki vikoristannyu grafichnih procesoriv Takim chinom doslidniki doveli sho obchislennya kolizij funkciyi SHA 1 stalo praktichno dosyazhnim dlya zlovmisnika zi znachnoyu aparatno materialnoyu pidtrimkoyu 10 Doslidniki virishili skoristatis najkrashoyu vidomoyu atakoyu na SHA 1 tak zvana ataka z identichnim prefiksom angl identical prefix collision attack yaka potrebuye teoretichno 261 obchislen SHA 1 Na praktici ochikuvalos sho znadobitsya 263 1 obchislen SHA 1 13 Ataka polyagaye v poshuku dvoh majzhe kolizijnih blokiv pri zadanomu prefiksi P yaki utvoryuyut koliziyu dlya bud yakogo sufiksu S 13 S H A 1 P M 1 1 M 2 1 S S H A 1 P M 1 2 M 2 2 S displaystyle mathrm SHA 1 P M 1 1 M 2 1 S mathrm SHA 1 P M 1 2 M 2 2 S nbsp Poshuk koliziyi vidbuvavsya u dva kroki Na pershomu kroci obchislennya vidbuvalis na zvichajnih mikroprocesorah iz vikoristannyam silno zminenoyi programi HashClash programa bula istotno zminena dlya mozhlivosti efektivnoyi roboti na bagatoh yadrah ta bagatoh procesorah Na comu kroci bula znajdena para M 1 1 M 1 2 displaystyle M 1 1 M 1 2 nbsp Drugij krok buv realizovanij na grafichnih procesorah Na comu kroci bula znajdena para M 2 1 M 2 2 displaystyle M 2 1 M 2 2 nbsp 13 Porivnyannya z MD5 ta SHA 0 Redaguvati Poshuk koliziyi algoritmom z identichnim prefiksom dlya MD5 SHA 0 ta SHA 1 mayut bagato spilnogo prote istotno vidminnu skladnist 13 Najkrashij vidomij algoritm poshuku koliziyi metodom identichnogo prefiksu vimagaye 216 obchislen MD5 13 Popri istotnu shozhist iz SHA 1 SHA 0 nabagato vrazlivishij do poshuku kolizij Najkrashij vidomij algoritm vimagaye 233 6 obchislen SHA 0 13 Takim chinom poshuk kolizij dlya SHA 0 ta MD5 mozhe vidbuvatis navit iz dopomogoyu suchasnogo smartfonu 13 Porivnyannya SHA1 z inshimi algoritmami RedaguvatiPorivnyannya z MD5 Redaguvati MD5 i SHA 1 ye po suti polipshenimi versiyami MD4 Shozhist Chotiri etapi Kozhna diya dodayetsya do ranishe otrimanogo rezultatu Rozmir bloku obrobki stanovit 512 bit Obidva algoritmi vikonuyut skladannya po modulyu 232 voni rozrahovani na 32 h bitnu arhitekturu Vidminnosti U SHA 1 na chetvertomu etapi vikoristovuyetsya ta zh funkciya f sho i na drugomu etapi V MD5 u kozhnij diyi vikoristovuyetsya unikalna aditivna konstanta U SHA 1 konstanti vikoristovuyutsya povtorno dlya kozhnoyi iz chotiroh grup U SHA 1 dodana p yata zminna SHA 1 vikoristovuye ciklichnij kod vipravlennya pomilok V MD5 chotiri zsuvi sho vikoristovuyutsya na kozhnomu etapi vidriznyayutsya vid znachen yaki vikoristovuyutsya na poperednih etapah V SHA na kozhnomu etapi vikoristovuyetsya postijne znachennya zsuvu V MD5 chotiri riznih elementarnih logichnih funkciyi v SHA 1 tri V MD5 dovzhina dajdzhestu stanovit 128 bit v SHA 1 160 bit SHA 1 mistit bilshe raundiv 80 zamist 64 i vikonuyetsya na 160 bitnomu buferi u porivnyanni iz 128 bitovim buferom MD5 Takim chinom SHA 1 povinen vikonuvatisya priblizno na 25 povilnishe nizh MD5 na tij zhe aparaturi Bryus Shnajer navodit nastupnij visnovok SHA 1 ce MD4 iz dodavannyam rozshiryuyuchogo peretvorennya dodatkovogo etapu i polipshenim lavinnim efektom MD5 ce MD4 iz polipshenim dvijkovim heshuvannyam dodatkovim etapom i polipshenim lavinnim efektom Vikoristannya RedaguvatiHesh funkciyi vikoristovuyutsya v sistemah kontrolyu versij sistemah elektronnogo cifrovogo pidpisu a takozh dlya pobudovi kodiv autentifikaciyi SHA 1 ye najbilsh poshirenim iz usogo simejstva SHA i zastosovuyetsya u riznih shiroko poshirenih kriptografichnih dodatkah i algoritmah SHA 1 vikoristovuyetsya v nastupnih standartah S MIME dajdzhesti povidomlen SSL dajdzhesti povidomlen IPSec dlya algoritmu perevirki cilisnosti v z yednanni tochka tochka SSH dlya perevirki cilisnosti peredanih danih PGP dlya stvorennya elektronnogo cifrovogo pidpisu Git dlya identifikaciyi kozhnogo ob yekta po SHA 1 heshu vid zberezhenoyi v ob yekti informaciyi Mercurial dlya identifikaciyi revizij BitTorrent dlya perevirki cilisnosti danih pri zavantazhenni Primitki Redaguvati Schneier Bruce 18 lyutogo 2005 Schneier on Security Cryptanalysis of SHA 1 Arhiv originalu za 14 kvitnya 2017 Procitovano 21 lyutogo 2017 NIST gov Computer Security Division Computer Security Resource Center Arhiv originalu za 25 chervnya 2011 Procitovano 21 lyutogo 2017 Bruce Schneier 8 zhovtnya 2015 SHA 1 Freestart Collision Schneier on Security Arhiv originalu za 28 sichnya 2017 Procitovano 21 lyutogo 2017 Windows Enforcement of Authenticode Code Signing and Timestamping Microsoft 24 veresnya 2015 Arhiv originalu za 5 zhovtnya 2016 Procitovano 7 serpnya 2016 Intent to Deprecate SHA 1 certificates Google 3 veresnya 2014 Procitovano 4 veresnya 2014 Safari and WebKit ending support for SHA 1 certificates Apple Support Apple Inc 24 sichnya 2017 Procitovano 4 lyutogo 2017 Bug 942515 stop accepting SHA 1 based SSL certificates with notBefore gt 2014 03 01 and notAfter gt 2017 01 01 or any SHA 1 based SSL certificates after 2017 01 01 Mozilla Arhiv originalu za 7 veresnya 2014 Procitovano 4 veresnya 2014 CA Problematic Practices MozillaWiki Mozilla Arhiv originalu za 6 travnya 2017 Procitovano 9 veresnya 2014 Phasing Out Certificates with SHA 1 based Signature Algorithms Mozilla Security Blog Mozilla 23 veresnya 2014 Arhiv originalu za 25 kvitnya 2017 Procitovano 24 veresnya 2014 a b 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 lyutogo 2017 Announcing the first SHA1 collision Google Security Blog Arhiv originalu za 24 kvitnya 2017 Procitovano 23 lyutogo 2017 NIST Comments on Cryptanalytic Attacks on SHA 1 angl Arhiv originalu za 13 zhovtnya 2012 Procitovano 29 serpnya 2016 NIST Hash Competition angl Arhiv originalu za 13 zhovtnya 2012 Procitovano 29 serpnya 2016 a b v g d e zh Marc Stevens Elie Bursztein Pierre Karpman Ange Albertini Yarik Markov The first collision for full SHA 1 CWI Amsterdam Google Research Arhiv originalu za 11 zhovtnya 2018 Procitovano 24 lyutogo 2017 Div takozh RedaguvatiHesh suma SHA 2 MD5Posilannya RedaguvatiRFC 3174 angl Oglyad SHA 1 vid Konsorciumu Vsesvitnoyi pavutini Arhivovano 4 bereznya 2005 u Wayback Machine angl Marc Stevens Elie Bursztein Pierre Karpman Ange Albertini Yarik Markov The first collision for full SHA 1 CWI Amsterdam Google Research Arhiv originalu za 11 zhovtnya 2018 Procitovano 24 lyutogo 2017 Vzlom SHA 1 Arhivovano 5 travnya 2017 u Wayback Machine angl Dopovid pro vzlom SHA 1 angl Bryus Shnajer pro vzlom SHA Arhivovano 1 grudnya 2012 u WebCite angl Naslidki uspishnih atak na SHA 1 Arhivovano 26 grudnya 2008 u Wayback Machine angl Generate SHA 1 Online onlajn servis dlya generuvannya SHA 1 nedostupne posilannya z serpnya 2019 angl Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno lyutij 2017 nbsp Ce nezavershena stattya z kriptografiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi nbsp Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title SHA 1 amp oldid 39425857