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

[[Файл:Cryptographic Hash Function.svg|thumb|375px|right|Криптографічна геш-функція (а саме, [[SHA-1]]) в роботі. Зауважте, що навіть мала зміна даних на вході (тут в слові «over») значно змінює вихід, через так званий [[лавиновий ефект]].]]
'''Криптографічна геш-функція'''&nbsp;— це [[геш-функція]], яка є [[алгоритм]]ом, що приймає довільний блок даних і повертає рядок встановленого розміру, ('''криптографічне''') '''геш-значення''', таке що (випадкові або навмисні) зміни даних (з дуже високою ймовірністю) змінять геш-значення. Дані до кодування часто звуть «повідомлення», а геш-значення іноді називають '''дайджест повідомлення''' ({{lang-en|message digest}}) або просто '''дайджест,''' дослівно «стислий виклад».

Ідеальна криптографічна геш-функція має чотири основні властивості:
* легкість обчислення геш-значення для будь-якого повідомлення
* нездійсненно утворити повідомлення для заданого геш-значення
* нездійсненно змінити повідомлення без зміни геша ([[лавиновий ефект]])
* нездійсненно знайти два різних повідомлення з тим самим гешем

Криптографічні геш-функції часто застосовуються в [[Інформаційна безпека|інформаційній безпеці]], особливо в [[цифровий підпис|цифровому підписі]], [[MAC підпис|коді автентифікації повідомлення]] (MAC) та інших формах [[автентифікація|автентифікації]]. Їх також можна використати як звичайну геш-функцію, для індексування даних в [[геш-таблиця|геш-таблиці]], для виявлення повторення даних або унікального ототожнювання файлів і як [[Контрольна сума|контрольну суму]] для виявлення пошкодження даних. Насправді, в розрізі інформаційної безпеки, криптографічні геш-значення іноді називають ('''цифровими''') ''' відбитками пальців,''' '''контрольними сумами''' або просто '''геш-значеннями,'''хоча всі ці терміни означають функції швидше з різними властивостями і цілями.

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

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

* ''Першовзорова стійкість''
*: для певного гешу <math>h\,</math> має бути складно знайти повідомлення <math>m\,</math>, таке що <math>h=\mathrm{hash}(m)\,</math>. Ця концепція стосується [[одностороння функція|односторонньої функції]]. Функції, що не відповідають цій властивості вразливі до [[атака знаходження першовзору|атак знаходження першовзору]].
* ''Друга першовзорова стійкість''
*: Для певного входу <math>m_1\,</math> має бути складно знайти інший вхід <math>m_2\,</math> — де <math>m_1 \ne m_2\,</math>, такий що <math>\mathrm{hash}(m_1) = \mathrm{hash}(m_2)\,</math>. Цю властивість іноді називають ''слабка колізійна стйкість'' ({{lang-en|weak collision resistance}}), і функцій, що не мають цієї властивості вразливі до [[атака знаходження першовзору|атак знаходження першовзору другого роду]].
* ''[[Колізійна стійкість]]''
*: Повинно бути складно знайти два різних повідомлення <math>m_1\,</math> і <math>m_2\,</math>, таких що <math>\mathrm{hash}(m_1) = \mathrm{hash}(m_2)\,</math>. Така двійка зветься криптографічна [[Колізія хеш-функції|геш-колізія]]. Цю властивість іноді називають ''сильна колізійна стійкість'' ({{lang-en|strong collision resistance}}). Воно вимагає щонайменше вдвічі довшого геш-значення ніж потрібно для першовзорової стійкості, інакше колізії можна знайти за допомогою [[атака «днів народження»|атаки «днів народження»]].

Ці властивості мають на увазі, що зловмисник не може змінити вхідні дані без зміни дайджеста. Отже,якщо два рядки мають однаковий дайджест можна бути впевненим, що й самі вони такі.

Функції, що відповідають цим вимогам все ще можуть мати небажані властивості. Наразі{{коли}} популярні криптографічні геш-функції вразливі до атак через ''довжинне доповнення'' ({{lang-en|length-extension}}): знаючи <math>h(m)\,</math> і <math>\mathrm{len}(m)\,</math>, але не знаючи <math>m\,</math>, через вибір відповідного <math>m'\,</math> нападник може обчислити <math>h (m||m')\,</math> де <math>||</math> позначає [[конкатенація|конкатенацію]]<ref name=vudang>{{cite web|url=http://vudang.com/2012/03/md5-length-extension-attack/|archiveurl=https://web.archive.org/web/20141029080820/http://vudang.com/2012/03/md5-length-extension-attack/|title=MD5 Length Extension Attack Revisited - Vũ's Inner Peace|archivedate=29 October 2014|work=vudang.com}}</ref>. Цю властивість можна використати, щоб розбити наївну схему автентифікацію побудовану на геш-функції. [[HMAC]] обходить цю проблему.

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

Алгоритми контрольних сум, такі як [[CRC32]] та інші циклічні надлишкові перевірки, спроектовані із дотриманням набагато слабших вимог, і зазвичай непридатні для використання як криптографічні геш-функції. Наприклад, CRC використовували для цілісності повідомлень в [[WEP]] стандарті шифрування, але була легко віднайдена атака, що використовувала лінійність контрольної суми.

=== Ступінь складності ===
У криптографічній практиці, ''складність'' зазвичай значить ''майже певно поза досяжністю будь-якого супротивника, який не повинен мати змогу зламати систему впродовж часу коли безпека система вважається потрібною.'' Внаслідок цього значення терміна залежить від застосування, бо зусилля, що зловмисник може затратити на задачу зазвичай пропорційне його очікуваній вигоді. Однак, через те, що необхідні зусилля ростуть дуже швидко з довжиною дайджеста, навіть покращення потужності обчислення в тисячі разів можна знешкодити додаванням кількох десятків бітів наприкінці.

У деяких [[Теорія складності обчислень|теоретичних аналізах]] ''складність'' має особливе математичне значення, таке як ''нерозв'язний за асимптотичний [[поліноміальний час]].'' Такі інтерпретації ''складності'' важливі у вивчанні доказово безпечних криптографічних геш-функцій, але зазвичай не мають сильного зв'язку з практичною безпекою. Наприклад, алгоритм експоненці́йного часу іноді може бути досить швидким для здійсненної атаки. І навпаки, алгоритм поліноміального часу (наприклад, такий що вимагає ''n''<sup>20</sup> кроків для ключа в ''n'' цифр) може бути заповільним для практичного використання.

== Приклад використання ==
Покажемо можливе використання криптографічної геш-функції: [[Аліса і Боб|Аліса]] подає складну математичну проблему Бобові, і заявляє, що вона розв'язала її. Боб хотів би розв'язати її самостійно, але також хоче впевнитись що Аліса не блефує. Отже Аліса записує свій розв'язок, додає випадкове криптографічне число. Обчислює геш-значення і передає його Бобу (тоді як розв'язок і випадкове число залишаються в секреті). Тоді, за кілька днів, Боб приходить зі своїм розв'язком, і Аліса може довести, що вона мала розв'язок раніше відкриваючи випадкове число Бобові. (Це приклад простої [[схема зобов'язання|схеми зобов'язання]]).

== Застосування ==
=== Перевірка цілісності файлів або повідомлень ===

Важливим застосуванням безпечних гешів є перевірка [[Цілісність інформації|цілісності повідомлень]]. Визначення чи були внесені якісь зміни в повідомлення  (або файл), наприклад, можна здійснити порівнянням дайджестів до і після передачі (або іншої події).

Пов'язаним застосуванням є перевірка паролів. Зазвичай паролі не зберігаються відкритим текстом, а зберігаються їх геш-значення. Для автентифікації користувача, пароль наданий користувачем гешується і  порівнюється зі збереженим гешем. Це також значить, що первинний пароль неможливо відновити, і при втраті його необхідно замінити новим.

=== Ідентифікатор файлу або даних ===

Геш-значення також може слугувати як спосіб надійного ототожнення файлів; декілька [[Система керування версіями|систем керування версіями]], включно з [[Git]], [[Mercurial]] і [[Monotone]], використовують [[sha1sum]] різнотипного вмісту для унікального ототожнення. Геші використовують для ідентифікації файлів в [[peer-to-peer]] мережах спільного використання файлів. Наприклад, [[ed2k link]], варіант геша [[MD4]] поєднаний із розміром файлу, забезпечує достатню інформацію для знаходження джерела файлу, завантаження файлу і перевірки його вмісту. Інший приклад — це [[magnet-посилання]]. Такі файлові геші часто використовують як кореневі геші [[геш-список|геш-списків]] або [[геш-дерево|геш-дерев]].

Одне з головних застосувань геш-функцій — це можливість швидкого пошуку даних в [[геш-таблиця|геш-таблиці]]. Будучи геш-функцією певного типу, криптографічна геш-функція поводиться добре і тут також.

Однак, порівняно зі стандартною геш-функцією, криптографічна геш-функції тяжіють до більшої обчислювальної складності. Через це, їх більше використовують у випадках, де користувачу необхідно захистити себе від можливої підробки зловмисником.

=== Псевдовипадкова генерація й утворення ключів ===

Геш-функції також можна використати як породжувач [[Псевдовипадкова послідовність|псевдовипадкових]] бітів або для виведення нових ключів чи паролів з одного секретного ключа або пароля.

== Геш-функції засновані на блочних шифрах ==
Існує декілька способів використання [[блочний шифр|блочних шифрів]] для побудови криптографічних геш-функцій, особливо [[одностороння функція стискання|односторонньої функції стискання]].

Методи нагадують режими операцій блочних шифрів зазвичай використовні для шифрування. Всі добре відомі геш-функції, включно з [[MD4]], [[MD5]], [[SHA-1]] і [[SHA-2]] побудовані зі складових подібних до блочних шифрів спроектованих для них, із гарантією, що отримана функція не [[бієкція|бієктивна]].  Серед фіналістів змагання геш-функцій від NIST (SHA-3) присутні геш-функції зі складовими подібними до блочних шифрів (наприклад, [[Skein]], BLAKE) та функції на основі інших дизайнів (Наприклад, [[JH]], [[Keccak]]).

Стандартний блочний шифр такий як [[AES]] можна використати замість цих спеціальних блочних шифрів; це може бути корисним коли [[вбудована система]] має забезпечувати шифрування і гешування з мінімальним за розміром кодом або розміром плати. Однак, такий підхід відбувається на дієвості і безпеці. Шифри в геш-функціях створені для гешування: вони використовують великі ключі і блоки, можуть дієво змінювати ключ щоблока, і розроблені і перевірені на стійкість до атак з пов'язаними ключами.  Шифри загального призначення мають різні цілі. Зокрема, розміри ключа і блоку в AES роблять нетривіальним використання його для утворення довгих геш-значень; шифрування з AES стає менш дієвим коли ключ змінюється щоблока; і атака з пов'язаними ключами робить його менш безпечним для використання в геш-функціях ніж для шифрування.

== Будова Меркла-Демґарда ==
{{Main|Будова Меркла-Демґарда}}
[[Файл:Merkle-Damgard hash big.svg|thumb|400px|right|Будова геша за Мерклом-Демґардом.]]
Геш-функція повинна бути в змозі перевести повідомлення довільної довжини в вихід встановленої довжини. Цього можна досягти через розбиття даних на вході в ряд блоків однакової довжини, і опрацювання їх послідовно із використанням [[Одностороння функція стискання|односторонньої функції стискання]]. Функція стискання може бути розроблена для гешування або утворена з блочного шифру. Геш-функція побудована за будовою Меркла-Демґарда є настільки колізійно стійкою наскільки така її функція стискання; Будь-яку колізію геш-функції в цілому можна прослідити до колізії в функції стискання.

Останній оброблений блок також повинен бути однозначно довжинно-доповненим; це критично для безпеки побудови. Такий підхід зветься — [[будова Меркла-Демґарда]]. Найширше використовні геш-функції, включно з [[SHA-1]] і [[MD5]], мають такий вигляд.

Будова має деякі властиві вади, включно з атаками через довжинне доповнення ({{lang-en|length-extension}}) і створити-і-вставити ({{lang-en|generate-and-paste}}), також не може використати переваги [[Паралельні обчислення|паралельного обчислення]]. Тому, багато{{скільки}} учасників змагання геш-функцій від NIST спроектовані на інших засадах.

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

[[MAC]] (Також відомі як геш-функції з ключем) часто будують з геш-функцій. [[HMAC]] є таким прикладом.

Так само як і блочні шифри можливо використовувати для будови геш-функцій, геш-функції можливо використовувати для побудови шифрів. Будови [[Мережа Фейстеля|Luby-Rackoff]] із використанням геш-функцій можуть бути доказово безпечними, якщо підлегла функція безпечна. Також багато геш-функцій (включно з [[SHA-1]] і [[SHA-2]]) побудовані із використанням спеціально розроблених блочних шифрів в будові Дейвіса-Меєра ({{lang-en|Davies-Meyer}}) або іншій. Див. [[SHACAL]], [[BEAR]] і [[LION]].

[[Генератор псевдовипадкових чисел]] можна побудувати із використанням геш-функції. Це робиться поєднанням (секретного) випадкового зерна з лічильником і наступним гешуванням.

Деякі функції, такі як [[Skein]], [[Keccak]] і [[RadioGatún]] видають довільної довжини потік і їх можна використати як [[потоковий шифр]], хоча потоковий шифр також можна побудувати і з геш-функції з дайджестом встановленого розміру. Часто це роблять спочатку будуючи криптографічно безпечний генератор псевдовипадкових чисел і тоді використовуючи цей потік як ключ. Потоковий шифр [[SEAL (значення)|SEAL]], що використовує [[SHA-1]] для побудови внутрішніх таблиць, які потім використовуються в генераторі ключа.  Не надається гарантії, що SEAL так само сильний або слабкий як SHA-1.

== Конкатенація криптографічних геш-функцій ==
Зчеплюючи виходи кількох геш-функцій ми отримуємо стійкість до колізій настільки високу як у найсильнішого з використаних алгоритмів.  Наприклад, старіші версії [[Transport Layer Security|TLS/SSL]] використовують об'єднані суми [[MD5]] і [[SHA-1]]; це гарантувало, що метод віднайденя колізій в одній з цих функцій не дозволить підробити трафік захищений обома.

Для геш-функцій Меркла-Демгарда, зчеплена функція так само колізійно-стійка як і її найсильніша складова,<ref>Зауважте, що будь-які два повідомлення, які утворюють колізію зчепленої функції, також утворюють колізії для всіх складових через природу дії зчеплення.  Наприклад, якщо concat(sha1(message1), md5(message1)) == concat(sha1(message2), md5(message2)) тоді sha1(message1) == sha1(message2) і md5(message1)==md5(message2).  Зчеплені функції можуть мати інші вади яких не має найсильніша функція — наприклад, вони можуть відкривати інформацію про повідомлення, хоча найсильніша складова ні, або бути виявити невипадковість тоді як найсильніша складова не має такої властивості — але не можуть бути менш колізійно-стійкими.</ref> але не більше.<ref>Загальніше, якщо атака може створити колізію в внутрішньому стані однієї геш-функції, атакування всієї конструкції є лише так само складним як [[атака «днів народження»]] проти інших функцій.  Дивись подробиці в наступних посиланнях на Joux і Finney.</ref> Joux<ref>Antoine Joux. ''Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions''. LNCS 3152/2004, pages 306-316 [http://www.springerlink.com/index/DWWVMQJU0N0A3UGJ.pdf Full text] {{Webarchive|url=https://web.archive.org/web/20170427003948/http://link.springer.com/chapter/10.1007/978-3-540-28628-8_19 |date=2017-04-27 }}.</ref> зауважив, що 2 колізії призводять до n колізій: якщо здійсненно знайти два повідомлення з однаковим гешем MD5, тоді фактично не більш складно знайти скільки завнодно повідомлень з таким самим гешем MD5.  Посеред n повідомлень з однаковим гешем MD5, ймовірно трапиться колізія в SHA-1.  Додаткова робота по знаходженню колізій SHA-1 поліноміальна. Цей довід підсумований [https://web.archive.org/web/20160409095104/http://article.gmane.org/gmane.comp.encryption.general/5154 Finney].  Сучаснішій документ з повним доведенням безпечності такої поєднаної конструкції і чіткішим і повним поясненням викладеного.<ref>{{cite paper |author=Jonathan J. Hoch and Adi Shamir |date=2008-02-20 |title=On the Strength of the Concatenated Hash Combiner when all the Hash Functions are Weak |url=http://eprint.iacr.org/2008/075.pdf |accessdate=18 травня 2012 |archivedate=5 травня 2012 |archiveurl=https://web.archive.org/web/20120505141912/http://eprint.iacr.org/2008/075.pdf }}</ref>

== Криптографічні геш-алгоритми ==
Існує велика кількість криптографічних геш-функцій, багато з них виявили вразливість і не повинні використовуватись. Навіть вдала атака проти послабленого варіанту може підірвати впевненість експертів і призвести до припинення застосування. Наприклад, в серпні 2004 знайшли слабкість в багатьох поширених на той час функціях, включно з SHA-0, RIPEMD і MD5. Це поставило питання про безпечність в перспективі геш-функцій отриамних на їх основі&nbsp;— зокрема, SHA-1 (посилена версія SHA-0), RIPEMD-128 і [[RIPEMD-160]] (посилені версії RIPEMD). Ані SHA-0, ані RIPEMD не використовувались широко, бо були замінені на посилені версії.

Станом на 2009, найвживаніші криптографічні геш-функції це [[MD5]] і [[SHA-1]].  Однак, MD5 зламали; атаку проти них використали для зламу [[Transport Layer Security|SSL]] в 2008.<ref>Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger, [http://www.win.tue.nl/hashclash/rogue-ca/ MD5 considered harmful today: Creating a rogue CA certificate] {{Webarchive|url=https://web.archive.org/web/20170920093616/http://www.win.tue.nl/hashclash/rogue-ca/ |date=20 вересня 2017 }}, accessed March 29, 2009</ref>

Геш-функції [[SHA-0]] і [[SHA-1]] розробило [[Агентство національної безпеки|NSA]].  У лютому 2005, повідомили про успішну атаку на SHA-1, знаходження колізій за приблизно 2<sup>69</sup> операцій гешування, замість 2<sup>80</sup> очікуваних для 160-бітної геш-функції. В серпні 2005, повідомили про іншу успішну атаку на SHA-1, знаходження колізій за 2<sup>63</sup> операцій. Нові застосунки можуть уникнути цього через використання наступних членів сім'ї SHA, таких як [[SHA-2]], або використання підходів на кшталт випадкового гешування за якого вхід опрацьовується із якимсь випадковим значенням перед застосуванням геш-функції,<ref>Shai Halevi, Hugo Krawczyk, [http://csrc.nist.gov/groups/ST/hash/documents/HALEVI_UpdateonRandomizedHashing0824.pdf Update on Randomized Hashing] {{Webarchive|url=https://web.archive.org/web/20110605110209/http://csrc.nist.gov/groups/ST/hash/documents/HALEVI_UpdateonRandomizedHashing0824.pdf |date=5 червня 2011 }}</ref><ref>Shai Halevi and Hugo Krawczyk, [http://www.ee.technion.ac.il/~hugo/rhash/ Randomized Hashing and Digital Signatures] {{Webarchive|url=https://web.archive.org/web/20090620072808/http://www.ee.technion.ac.il/~hugo/rhash/ |date=20 червня 2009 }}</ref> які не потребують колізійної стійкості.

Однак, для гарантування тривалої безпеки застосунків, що використовують геш-функції, запроваджено змагання з метою заміни для SHA-2, нова геш-функція отримає ім'я SHA-3 і стане федеральним стандартом у 2012.<ref>{{Cite web |url=http://csrc.nist.gov/groups/ST/hash/sha-3/index.html |title=NIST.gov - Computer Security Division - Computer Security Resource Center |accessdate=21 травня 2012 |archive-date=9 липня 2011 |archive-url=https://web.archive.org/web/20110709025036/http://csrc.nist.gov/groups/ST/hash/sha-3/index.html }}</ref> NIST випустив SHA-3 у серпні 2015.

У 2015 році в Україні розроблено геш-функцію [[Купина (геш-функція)|Купина]], яку введено в дію як національний стандарт ДСТУ 7564:2014 «Інформаційні технології. Криптографічний захист інформації. Функція хешування»<ref>http://www.dsszzi.gov.ua/dstszi/control/uk/publish/article?art_id=120158&cat_id=119123 {{Webarchive|url=https://web.archive.org/web/20160918234228/http://www.dsszzi.gov.ua/dstszi/control/uk/publish/article?art_id=120158&cat_id=119123 |date=18 вересня 2016 }} Держспецзв’язку впроваджує нові стандарти криптографічного захисту інформації</ref>

== Хешування Біткойна ==
{{Розділ без джерел|дата=грудень 2021}}

Транзакції платіжної системи [[Біткоїн|Біткойна]], які представляються у вигляді деякого масиву даних, об'єднуються в блоки (надалі, сукупність всіх блоків називатимемо [[блокчейн]]ом) і проходять через алгоритм хешування, тобто дані їх полів подаються на вхід криптографічної хеш-функції. Кожна транзакція вказує, звідки списуються кошти та куди вони прямують. Для вказівки адресата використовується його публічний ключ (унікальний ідентифікатор мережі Біткойн). Щоб адресат міг використати отримані гроші в рамках протоколу біткойна (виключаємо продаж власного гаманця&nbsp;— Wallet), він має створити нову транзакцію, яка братиме валюту з попередньої та перенаправлятиме за іншою адресою, використовуючи публічний ключ. Відповідно, нова транзакція разом із транзакціями інших користувачів мережі біткойн потрапить у новий блок. Таким чином число блоків у блокчейні зростає. Проте, кожна транзакція має бути схвалена&nbsp;— система має дійти консенсусу. Для цього є кілька способів, але в Біткойні використовується принцип Proof-of-Work (PoW). Після прийняття транзакції вона вважається справжньою і криптовалюта переходить від одного гаманця до іншого.

Система Біткойна є децентралізованою системою без виділених центрів генерації блоків. Кожен учасник може взяти набір транзакцій, що очікують включення до журналу, та сформувати новий блок. Більше того, у системах типу BitCoin такий учасник (майнер) ще й отримає премію у вигляді певної суми чи комісійних від прийнятих до блоку транзакцій.

Не можна просто сформувати блок у децентралізованих системах. Система має дійти консенсусу, тобто отримати схвалення. Для цього є кілька способів, але в Біткойні використовується принцип Proof-of-Work (PoW). Надійність таких систем полягає саме в тому, що новий блок не можна сформувати швидше (у середньому), ніж за певний час. Наприклад, за десять хвилин (BitCoin).

== Примітки ==
{{reflist|2}}

{{Refimprove|дата=листопад 2017}}
{{ВП-портали|Програмування|Інформаційні технології}}

[[Категорія:Криптографія|геш-функції]]
[[Категорія:Криптографічні примітиви|геш-функції]]
[[Категорія:Криптографічні геш-функції| ]]
[[Категорія:Хешування]]