Спеціальні прості числа допомагають пасивно прослухати протокол обміну ключами Діффі-Хеллмана


Слайд з презентації АНБ

В 2013 році завдяки Едварду Сноудену у ЗМІ потрапили документи АНБ. Серед них — замилений слайд презентації, який вказував на можливості АНБ розшифровці трафіку VPN. У АНБ не було причин брехати в засекреченої презентації, так що фахівці сприйняли цю інформацію як свідчення наявності якоїсь фундаментальної уразливості в сучасних системах криптографії з відкритим ключем.

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

Наприклад, ось рекомендоване просте число RFC 2409.



Так і вийшло на практиці: до останнього часу 92% найпопулярніших сайтів HTTPS зі списку Alexa використовували два стандартних простих числа. Протокол Діффі-Хеллмана використовується також для генерації ключів, які використовуються в протоколах SSH, VPN, SMTPS, IPsec та ін

Ці числа вважалися безпечними при досить великій величині простого числа (наприклад, більше 1015). Зараз фахівцям з Пенсільванського університету (США), INRIA, CNRS та Університету Лотарингії (Франція) вдалося-таки довести, що не всі такі числа безпечні, так що у АНБ дійсно є теоретична можливість розшифровки HTTPS-трафіку. Криптографи на практиці продемонстрували, що спеціальним чином сконструйоване велике просте число при використанні в якості модуля p при генерації ключів шифрування може виступати в якості «лазівки» (trapdoor), що дозволяє дізнатися інші, секретні складові ключа і, як наслідок, розшифрувати секретне повідомлення.

Взагалі кажучи, можливість використання великими групами користувачів стандартного простого числа в якості модуля p викликала миттєву критику з боку експертів відразу ж після публікації у 1991 році стандарту Digital Signature Algorithm (DSA), який передбачав таку можливість і, фактично, заохочував таку практику.

DSA — криптографічний алгоритм з використанням відкритого ключа для створення електронного підпису. Підпис складається таємно, але може бути публічно перевірена. Алгоритм базується на обчислювальній складності взяття логарифмів в кінцевих полях, тобто дискретного логарифму.

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

Виявляється, це не зовсім так. Як показали криптографи, при певному числі p для 1024-бітного ключа можна зробити обчислення дискретного логарифма за цілком видимий час — а саме, в 10 000 швидше, ніж теоретично розраховане для простих випадкових чисел. Дослідники зробили це за два місяці на кластері з приблизно 3000 процесорних ядер в університетській мережі (реальна кількість машин змінювалося в процесі виконання завдання).



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

Можливість впровадження спеціально підібраного модуля p стандарт не означає, що АНБ дійсно реалізував цю ідею. Ми не можемо перевірити, «хорошими» або «поганими» є використовувані зараз прості числа, не знаючи алгоритм, який використовує АНБ. Але якщо це правда, то це буде не першою спробою АНБ послабити стандарти публічного шифрування. Ще не стерлася з пам'яті історія з генератором «випадкових» чисел Dual_EC_DRBG — ГВЧ за замовчуванням в RSA BSAFE і Data Protection Manager, серед інших програм. Як показали документи Сноудена, цей генератор спочатку був спроектований з участю АНБ, щоб видавати передбачувані числа.

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

Найпростішою захистом проти можливих вразливостей в алгоритмі шифрування є вибір ключів довжиною більше 1024 біт, говорять автори роботи. За їх розрахунками, обчислення 2048-бітного ключа з таким же «ослабленим» простим числом займе приблизно в 16 млн разів більше часу, ніж для 1024-бітного ключа. Згідно дослідженню SSL Pulse, зараз 27,3% сайтів, що використовують SSL, обмінюються ключами довжиною 1024 біт або менше.

У майбутньому, вважають дослідники, для безпеки всі прості числа повинні публікуватися разом з посівними значеннями.

Загалом, треба брати прості числа лише з надійних джерел.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.