З'явилися останнім часом повідомлення про просування в області криптографічного аналізу алгоритму хешування SHA-1, досягнутого фахівцями Китаю, США та інших країн, ставлять перед необхідністю відповісти на ряд питань.

Де і як використовується алгоритм SHA-1 в вітчизняних інформаційних системах? Наскільки впливають останні результати в рішенні проблеми колізій алгоритму SHA-1 на легітимність електронних підписів і їх аналогів в системах захисту інформації, що базуються на цьому алгоритмі? І нарешті, наскільки методи, що застосовуються до SHA-1, можна перенести на російський стандарт функції хешування ГОСТ Р 34.11-94?

Нагадаємо основні криптографічні вимоги, що пред'являються до хеш-функції:

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

Алгоритм SHA-1 розроблений Агентством національної безпеки США в 1995 році і включений Національним інститутом стандартів США в стандарт SHS. Хеш-функції використовуються в інформаційних технологіях в системах електронного підпису, системах контролю цілісності програмного коду і даних, а також для побудови кодів аутентифікації.

SHA-1 використовується в переважній масі продуктів криптографічного захисту, вироблених і використовуваних в США, а також в інших країнах, які підтримують американські стандарти. Так, в операційних системах сімейства Windows вбудований ряд криптографічних служб, які використовують алгоритм SHA-1. Впровадження цього алгоритму в Windows настільки глибоко, що завантаження та використання операційних систем без звернення до нього з штатних криптографічних сервісів неможливі. Стандарт SHS c алгоритмом SHA-1 використовується спільно з іншими криптографічними стандартами США в інфраструктурі відкритих ключів, а також в інших поширених криптографічних протоколах (SSL / TLS, IPSec, Kerberos і ін.).

Разом з тим SHA-1 не використовується в продуктах, що підтримують національні криптографічні стандарти. Зокрема, даний алгоритм не використовується за своїм прямим призначенням в російських інформаційних системах, що оснащуються сертифікованими засобами криптографічного захисту.

Побудова і використання колізій алгоритму хешування розпадається на два завдання:

• криптографічний завдання знаходження колізії;
• практичне завдання використати знайдену колізії для атаки на захищається алгоритмом хешування систему.

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

Хеш-функція реалізує відображення безлічі хешіруемих текстів на безліч значень хеш-функції. Безліч хешіруемих текс розбивається на класи еквівалентності за значеннями хеш-функції. Складність знаходження колізій хеш-функції залежить від аналітичної складності цього відображення.

Математичною моделлю задачі про оцінку складності числа колізій є завдання, відома як «парадокс близнюків»: в безлічі з елементів, кожен з яких характеризується незалежно від інших одним з ознак при його випадковому і равновероятном виборі, середнє число елементів з ознакою, однаковим для фіксованого елемента , так само n / m, середнє число пар елементів з однаковою ознакою одно n / m-2.

У застосуванні до задачі про колізії середнє число колізій в першому випадку дорівнює | B | / | H | у другому | B | / (| H |) -2. За теоретичну оцінку складності знаходження колізій в криптографії приймається величина.

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

До можливості зниження криптографічного складності на три-чотири порядки привів ряд особливостей алгоритму SHA-1. Так, використовувані математичні операції (операція додавання, побітові логічні операції, операція зсуву) в своїй сукупності не дозволяють будувати перетворення з хорошими перемішують властивостями. Крім того, застосовується послідовне хешування тексту блоками по 512 біт зі сверткой блоку до 160 біт. Використовуваний спосіб доповнення останнього неповного блоку хешіруемого тексту до повного створює додаткові можливості для пошуку колізій.

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

Для алгоритму SHA-1 теоретична стійкість дорівнює, однак на практиці стійкість знижується.

Алгоритм SHA-1 з його значенням з самого початку не мав криптографічного запасу і, мабуть, був розрахований на те, що оцінку знизити не вдасться.

На відміну від алгоритму SHA-1 алгоритм ГОСТ Р 34.11-94 характеризується наступними властивостями:

• перетворення блоку інформації при хешуванні здійснюється використанням шифрувального перетворення за алгоритмом ГОСТ 28147-89;
• перетворення хешіруемой інформації проводиться блоками по 256 біт з розміром перетвореного блоку також 256 біт; теоретична стійкість;
• в алгоритмі хешування використовуються спеціальні заходи, що виключають можливість спрощення завдання пошуку колізій при неповному останньому блоці.

У шифрувальні перетворення за алгоритмом ГОСТ 28147-89 на додаток до операцій, характерним для алгоритму SHA-1 і родинних йому, використовується вузол замін, вибором яких вдається ускладнити переміщуючий перетворення і істотно обмежити можливість застосування до алгоритму ГОСТ Р 34.11-94 методів диференціального аналізу для рішення задачі по пошуку колізій. До теперішнього часу такі методи в процесі багаторічних криптографічних досліджень алгоритму ГОСТ Р 34.11-94 не знайдені. На нашу думку, методи побудови колізій, знайдені для алгоритму SHA-1, не застосовуються до алгоритму ГОСТ Р 34.11-94.

Леонід ведення ( [email protected] ) - інженер-аналітик, Володимир Попов ( [email protected] ), Начальник відділу криптографічного аналізу та атестаційних випробувань компанії «Кріпто-Про» (Москва).