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

Изследователи от френския държавен институт за изследвания в информатиката и автоматизацията (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, особено в сертификати и цифрови подписи.

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

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