Представен е по-ефективен метод за определяне на префикси за колизии при SHA-1

Изследователи от френския държавен институт за изследвания в информатиката и автоматизация (INRIA) и Нанянгския технологичен университет (Сингапур) разработиха усъвършенстван метод атака на алгоритъма SHA-1, който значително опростява създаването на два различни документа с идентични SHA-1 хешове. Същността на метода е да сведe операцията за пълен подбор на колизия в 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, особено в сертификати и цифрови подписи.

Допълнително може да бъде отбелязано публикация резултати криптоанализ на блокови шифри SIMON-32/64, разработени от АНБ на САЩ и одобрени през 2018 г. като стандарт ISO/IEC 29167-21:2018.
На учените им е успяло да разработят метод за възстановяване на частния ключ на основата на две известни двойки от открит текст и шифротекст. При ограничени изчислителни ресурси за подбиране на ключа са необходими от няколко часа до няколко дни. Теоретичният коефициент на успешност на атаката се оценява на 0.25, а практическият за наличния прототип — 0.025.

Източник: opennet.ru