Дослідники з французького державного інституту досліджень в інформатиці та автоматиці (INRIA) та Наньянського технологічного університету (Сінгапур) удосконалений на алгоритм SHA-1, що спрощує створення двох різних документів з однаковими хешами SHA-1. Суть методу у зведенні операції повноцінного підбору колізії у SHA-1 до , коли колізія виникає за наявності певних префіксів, незалежно від інших даних у наборі. Іншими словами, можна обчислити два визначені префікси і якщо один приєднати до одного документа, а інший до другого - результуючі хеші SHA-1 для цих файлів будуть однакові.
Даний вид атаки все ще вимагає величезних обчислень і підбір префіксів залишається складнішим, ніж звичайний підбір колізій, але й практична ефективність результату значно вища. Якщо досі найшвидший метод пошуку префіксів колізії в SHA-1 вимагав виконання 277.1 операцій, новий метод знижує число обчислень до діапазону від 266.9 до 269.4. За такого рівня обчислень орієнтовна вартість атаки становить менше ста тисяч доларів, що цілком по кишені спецслужбам та великим корпораціям. Для порівняння на пошук звичайної колізії необхідно виконати приблизно 264.7 операцій.
В Google можливості генерації різних PDF-файлів з однаковим хеш SHA-1 прийом з об'єднанням в один файл двох документів, перемиканням видимого шару і зміщенням мітки вибору шару в область виникнення колізії. При близьких витратах ресурсів (на пошук першої колізії SHA-1 Google витратив рік обчислень на кластері зі 110 GPU) новий метод дозволяє досягти збігу SHA-1 для двох довільних наборів даних. З практичного боку можна підготувати TLS-сертифікати, у яких згадуються різні домени, але збігаються хеші SHA-1. Подібна можливість дозволяє нечистому на руку центру, що засвідчує, створити сертифікат для цифрового підпису, який можна застосовувати для авторизації фіктивних сертифікатів до довільних доменів. Проблема також може бути використана для компрометації протоколів, що покладаються на відсутність колізій, таких як TLS, SSH та IPsec.
Запропонована стратегія пошуку префіксів для колізії передбачає розбиття обчислень на два етапи. У першому етапі виконується пошук блоків, що є межі колізії, шляхом вбудовування випадкових змінних ланцюжків в визначений цільовий набір відмінностей. На другому етапі на рівні окремих блоків отримані ланцюжки відмінностей зіставляються з парами станів, що призводять до колізій, використовуючи методи традиційних атак з підбору колізій.
Незважаючи на те, що теоретична можливість атаки на SHA-1 доведена ще у 2005 році, а на практиці перша колізія була У 2017 році, SHA-1 все ще залишається в побуті та охоплюється деякими стандартами та технологіями (TLS 1.2, Git тощо). Основною метою виконаної роботи було бажання надати ще один вагомий аргумент для негайного припинення використання SHA-1, особливо у сертифікатах та цифрових підписах.
Додатково можна відзначити криптоаналізу блокових шифрів , розроблених АНБ США та у 2018 році затверджених як стандарт .
Дослідникам вдалося розробити метод відновлення закритого ключа на основі двох відомих пар із відкритого тексту та шифротексту. При обмежених обчислювальних ресурсах на вибір ключа потрібно від кількох годин до кількох днів. Теоретичний коефіцієнт успішності атаки оцінюється в 0.25, а практичний для наявного прототипу - 0.025.
Джерело: opennet.ru