Атака знаходження першовзору

Атака знаходження першовзору — це різновид атак на геш-функції для знаходження повідомлення із певним геш-значенням.

Існує два типи атак знаходження першовзору:

Перша: маючи певний геш h, знайти повідомлення m (першовзір), такий що hash(m) = h.
Друга: для певного повідомлення m1, знайти відмінне повідомлення m2 (другий першовзір), такий що hash(m2) = hash(m1).

Також тут згадаймо колізійну атаку, яка має метою знайти два довільні різні повідомлення m1 і m2, такі що hash(m2) = hash(m1).^[1]

Для ідеальної геш-функції, найшвидший спосіб вирахування першого або другого першовзору — це використання атаки повного перебору. Для n-бітового гешу, складність обчислення атаки становить 2ⁿ, яка розглядається як завелика для типового геш-значення в 160 біт. Якщо така складність найкраще, що може досягти супротивник, тоді геш-функція вважається стійкою до атаки знаходження першовзору.

Швидші атаки можна знайти за допомогою криптоаналізу певних геш-функцій, і є особливими для цих функцій. Декілька важливих атак вже знайдено, але вони досі непрактичні. Якщо знайдуть практично застосовну атаку, це значно вплине на багато інтернет-протоколів. В нашому випадку «практична» означає, що вона може бути виконана за розумний час і гроші. Атака знаходження першовзору яка вимагає трильйони і займає десятиріччя для знаходження першовзору одного геш-значення або повідомлення не є практичною; та що потребує кількох тисяч доларів і кілька тижнів обчислень може бути дуже практичною.

Всі наразі відомі практичні атаки на MD5 і SHA-1 це колізійні атаки. Здебільшого, колізійна атака легша до застосування ніж атака знаходження першовзору.

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

Примітки ред.

↑ Rogaway, P.; Shrimpton, T. (2004). Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance (PDF). Fast Software Encryption. Lecture Notes in Computer Science. Т. 3017. Springer-Verlag. с. 371—388. doi:10.1007/978-3-540-25937-4_24. ISBN 978-3-540-22171-5. Процитовано 9 лютого 2024.

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

IETF RFC 4270: Attacks on Cryptographic Hashes in Internet Protocols

Це незавершена стаття з криптографії.
Ви можете допомогти проєкту, виправивши або дописавши її.

[crypto-hash-def-1] Rogaway, P.; Shrimpton, T. (2004). Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance (PDF). Fast Software Encryption. Lecture Notes in Computer Science. Т. 3017. Springer-Verlag. с. 371—388. doi:10.1007/978-3-540-25937-4_24. ISBN 978-3-540-22171-5. Процитовано 9 лютого 2024.

[1]