Дослідники підробили 1024-бітні підписи RSA, не факторизуючи ключ

Дослідники з UC San Diego та Inria Nancy реалізували атаку, яка дозволяє підробити довільний 1024-бітний підпис RSA, не факторизуючи ключ. Препринт «Forging 1024-bit RSA signatures in nearly SNFS time» опубліковано в архіві IACR ePrint 20 вересня; автори — Лора Ши, Міро Галлер, Адам Сул, Надія Генінгер та Еммануель Томе.

Робота реалізує алгоритм Joux, Naccache і Thomé 2007 року, який автори називають недооціненим. Час виконання близький до спеціального методу решета числового поля (SNFS) і суттєво менший за GNFS, на якому базуються оцінки розмірів ключів RSA.

Що потрібно для атаки

Модель загрози — «обідня» атака (lunchtime), формально неадаптивна атака з обраним шифротекстом (IND-CCA1): нападник тимчасово отримує доступ до оракула необроблених, без доповнення, операцій підпису або дешифрування RSA для одного ключа, а потім втрачає його. Після цього він офлайн підробляє будь-який потрібний підпис і повторює це для довільних цілей без нових запитів до оракула.

Загалом обчислення зайняло 1380 ядро-років CPU за п'ять календарних місяців і близько 2^32 запитів. Попередні обчислення, що залежать лише від модуля, — це приблизно 1200 ядро-років; одна підробка потім коштує близько 180 ядро-років. Для порівняння, факторизація 1024-бітного модуля RSA оцінюється у 500 000-1 000 000 ядро-років CPU.

HSM і сліпі підписи

Запити до оракула автори виконували через апаратний модуль безпеки (HSM). Стандарт PKCS #11, який підтримують майже всі HSM, надає саме ті необроблені операції RSA, що потрібні атаці, тож нападник із доступом до API «чорної скриньки» може видавати себе за HSM, не витягуючи ключ. Схеми сліпих підписів на базі RSA дають такий самий оракул; у статті йдеться, що поширені 2048-бітні ключі дають там замалий запас міцності.

Мінус 15-30 біт безпеки

Екстраполюючи виміряний час, автори дійшли висновку: конкретна стійкість RSA з оракулом підпису на 15-30 біт нижча за оцінки, що виходять із факторизації, для ключів від 1024 до 4096 біт. Для 1024-бітного RSA, якому зазвичай приписують 80 біт, атака потребує близько 2^65. Для 2048-бітного (112 біт) виходить приблизно 2^90 і 2^43 запитів, для 4096-бітного — близько 2^119 і 2^57 запитів. Отже, навіть 4096-бітний RSA не досягає 128-бітного рівня в цій моделі.

Прогалина в припущеннях RSA

Автори не стверджують, що RSA зламано в повсякденному вжитку: атака практична в академічному, а не масовому сенсі, а модель із необробленим оракулом дуже сильна. Але, на їхню думку, вона виявляє прогалину — припущення one-more RSA не описує такі атаки з попередніми обчисленнями, і вони пропонують назву «delayed-target RSA». NIST планує відмовитися від RSA до 2030 року й заборонити його до 2035-го, і автори вважають свій результат ще одним аргументом прискорити перехід. Код опубліковано на GitHub.