Не варто панікувати з приводу слабких ключів RSA
Ми змогли видалено скомпрометувати близько 0.4% від усіх відкритих ключів, які використовуються веб-сайтами для SSL. Усі скомпрометовані ключі були неправильно згенеровані, з використанням передбачуваних «рандомних» чисел, які ще й іноді повторювалися. Усього ми можемо виділити два типи проблем: ключі, згенеровані з передбачуваною рандомністю, і підмножина цих ключів, для яких нестача рандомності дозволяє атакуючому швидко факторизувати відкритий ключ і отримати секретний ключ. Маючи секретний ключ, атакуючий зможе видати себе за веб-сайт і може розшифровувати зашифрований трафік направлений на цей сайт. Ми розробили програму, яка за пару годин може факторизувати відкриті ключі та видавати секретні ключі для всіх хостів уразливих до цієї атаки.
Тим не менш, не варто панікувати, оскільки в основному проблема впливає на системи, що вбудовуються, такі як маршрутизатори і VPN, і не стосується повномасштабних серверів. (У всякому разі це точно не причина втрачати довіреність до електронної комерції, як це передбачає New York Times). На жаль, ми знайшли пристрої з цією проблемою практично у кожного виробника і ми підозрюємо, що близько 200.000 пристроїв, що представляють 4.1% від усіх ключів у наших даних, використали погану ентропію для генерації ключів. Будь-який знайдений слабкий ключ згенерований пристроєм передбачає, що весь клас цих пристроїв уразливий для атаки при належному аналізі.
Не хвилюйтеся, ключ вашого банку швидше за все в безпеці.
SSL використовується кожним великим сайтом в Інтернеті, але як показує наш аналіз, ці ключі не схильні до проблем описаних у цьому пості.
Так які жсистеми у небезпеці? Майже всі вразливі ключі були згенеровані і використовувалися в системах, що вбудовуються, таких як, маршрутизатори і брандмауери, і не використовувалися на вебсайтах для банків або e-mail. Тільки один із вразливих ключів SSL був підписаний центром сертифікації і він уже минув. Також ми знайшли кілька підписаних сертифікатів, які використовують повторювані ключі; деякі з яких були згенеровані вразливими пристроями, інші були подані на підпис власниками сайтів як свідомо слабкі і для деяких ми не можемо придумати хороше пояснення.
Всім відомо що у системах, що вбудовуються, є проблеми з ентропією. Однак, до цього часу не було зрозуміло, наскільки ці проблеми були поширені в реальних пристроях, підключених до Інтернету.
Генерація Ключів
Веб-сайти та мережні комп'ютери використовують криптосистеми з відкритими ключами для ідентифікації. Далі ми будемо говорити про тип ідентифікації, коли сервер надає клієнту сертифікат для того, щоб засвідчити клієнта, що він саме той, до кого клієнт хоче підключитися. Якщо атакуючий знає секретний ключ, він може видати себе за реальну систему або здебільшого розшифрувати трафік між клієнтом та сервером.
RSA є найчастіше використовуваною криптосистемою для цих цілей. Захист RSA криптосистеми побудований на факторизації великих чисел. Відкритий ключ RSA складається з пари цілих чисел: відкритої експонентиеі модуляN, що є добутком двох великих простих чиселpіq. Якщо противник зможе факторизуватиNназад уpіq, він також зможе розшифрувати будь-який текст зашифрований відкритим ключем. Однак, навіть використовуючи найшвидші алгоритми для факторизації, ніхто ще не зміг факторизувати1024-бітовий модуль.
Важливою частиною безпеки ключа є наявність рандомних вхідних даних на стадії генерації ключа. Якщо в цих вхідних даних недостатньо ентропії, тоді атакуючий зможе їх вгадати, і таким чином отримати секретний ключ без болісної факторизації числаN.
На сучасних комп'ютерах і серверах, програми для генерації ключів використовують рандомні вхідні дані, отримані з безлічі фізичних джерел (найчастіше за допомогою операційної системи): руху мишки, клавіатури, жорсткого диска, мережевих подій та інших непередбачуваних джерел. Однак, якщо джерел мало то не вистачатиме ентропії, і ключ може виявитися вразливим для атаки. Збирання сильної ентропії та перевірка її сили є дуже складною проблемою, яка породила багато вразливостей упродовж багатьох років.
Дві версії проблеми
Як ми виявили, проблеми з ентропією призводять до двох різних видів слабкостей:
Відкриті ключі, що повторюються.
Близько 1% всіх RSA ключів зустрічалися повторно, швидше за все через проблеми з ентропією. Якщо у двох пристроїв однаковий відкритий ключ, то вони також мають однаковий секретний ключ. Насправді, всі пристрої з однаковим ключем знаходяться в однаковому положенні — атакуючий може скомпрометувати найслабші з цих пристроїв і отримати ключі до всіх інших. Вже давно було відомо про цю проблему, але досі ніхто не документував у відкритій літературі наскільки вона поширена.
Ми вручну перевірили, що 59.000 ключів були повторені через проблеми з ентропією, які представляють близько 1% всіх сертифікатів, або 2,6% всіх самостійно підписаних сертифікатів. Ми також знайшли що 4.6% всіх пристроїв (585,000 сертифікатів) використали сертифікативстановлені за замовчуванням. І хоча ці пристрої не використовували ключі згенеровані з поганою ентропією, вони схильні до такої ж атаки, так як їх секретні ключі однакові на всіх моделях. Ми вручну перевірили всі ці ключі, тому що велика кількість сайтів використовує ключі, що повторюються, в правильних умовах і тому не надає небезпеки для користувача.
Факторизовані відкриті ключі.
Що дивно, ми виявили, що проблеми з ентропією можуть дозволити віддаленому атакуючому, без спеціального доступу, факторизувати значну частину всіх ключів RSA, що використовуються в Інтернеті. Ми змогли факторизувати 0,4% всіх ключів RSA в SSL сертифікатах. Для цього ми визнали найбільший спільний дільник (gcd) для всіх пар модулів з відкритих ключів RSA в Інтернеті.
Ми визначили 1724 спільних дільників, що дозволило нам факторизувати 24816 SSL ключів і 301 загальних дільників для факторизації 2422 SSH ключів. Це означає, що ми змогли порахувати секретні ключі майже для 0.5% RSA ключів, що використовуються для SSL. Далі ми пояснимо, як наш розрахунок працює.
Конкретні вразливі пристрої
Вбудовані системи часто генерують криптографічні ключі при першому завантаженні, коли їх стан може бути зумовлено на заводі. Що може спричинити такі проблеми з ентропією, як описано в цьому дослідженні.
Ми не будемо перераховувати імена пристроїв до того, як ми сповістимо, але нижче можна побачити кілька прикладів:
Брандмауер Х: 52.055 хостів у наших SSL даних 6.730 з однаковими ключами 12.880 з ключами, що факторизуються
Маршрутизатор Y рівня користувача: 26.952 хостів у наших SSL даних 9.345 з однаковими ключами 4.792 з факторизованими ключами
Рішення длявіддаленого доступу Z, для підприємств: 1.648 хостів у наших SSL даних 24 з однаковими ключами 0 з ключами, що факторизуються
Як це могло статися?
Це не зовсім очевидно, як проблеми з ентропією можуть призвести до проблем з ключами, які легко факторизувати. Зараз ми пояснимо чому так відбувається для наших допитливіших читачів.
Ось як програміст може згенерувати модуль для RSA: prgn.seed(seed) p = prgn.generate_random_prime() q = generate_random_prime() N = p*q Якщо зерно для генератора псевдовипадкових чисел має передбачуване значення, тоді кілька різних пристроїв можуть мати однаковий модульN, але ми не думаємо що хороші генератор псевдовипадкових чисел можуть зробити два різні модуліN, із загальним однаковим фактором.
Однак деякі реалізації також додають додаткової рандомності між генерацією простих чиселpіq, з ідеєю підвищення безпеки: prgn.seed(seed) p = prgn.generate_random_prime () prgn.add_randomness(bits) q = generate_random_prime() N = p*q Якщо перше зерно було згенеровано з поганою ентропією, це може призвести до того, що у кількох пристроїв будуть різні модулі, що складаються з однакових факторівpта різних факторівq. Тому ми можемо факторизувати обидва модулі, використовуючи GCD: p = gcd(N1, N2).
Генерація ключів RSA OpenSSL працює наступним чином: після кожного використання рандомних бітів з пулу ентропії для генерації простих чиселpіq, поточний час в секундах додається в пул. Багато, але не всі вразливі ключі були згенеровані з використанням OpenSSL і OpenSSH, який використовує OpenSSL для генерації RSA ключів.
Обчислення GCD для всіх парключів
Якщо будь-яка пара модулів RSAN1іN2має один однаковий фактор, то можна просто факторизувати обидва модулі використовуючи gcd. На моєму настільному комп'ютері операція обчислення gcd для двох 1024 RSA модулів займає близько 17 мікро секунд.
Для людей схильних до математики, зараз я поясню, як ми можемо використовувати цю ідею для факторизації великої кількості ключів.
Простий підхід до факторизації ключів включає обчислення gcd для кожної пари RSA модулів. Але якщо оцінити скільки часу ці обчислення займуть, то ми отримаємо близько 24 років на моєму настільному комп'ютері.
Головний математичний огляд у цій проблемі це те, що ми можемо обчислити gcd для модуляN1разом з іншими модулями використовуючи наступне рівняння: gcd(N1, N2 . Nm) = gcd(N1, (N1 * N2 * .Nm mod N1^2)/N1) Велика проблема в тому як змусити прорахунок цього рівняння проводитися швидко - зауважте що першим кроком цього обчислення є знаходження твору всіх ключів, що складається з 729 мільйонів цифр. Ми змогли досягти факторизації всіх SSL даних за 18 годин на одноядерному процесорі та факторизації SSH даних за 4 години на чотирьох ядерному процесорі.