راه تازه‌ای برای شکستن RSA بدون فاکتورگیری
خلاصهٔ کامل‌تر
به گزارش Ars Technica، یه تیم پژوهشی به سرپرستی Laura Shea و با همکاری Nadia Heninger از دانشگاه کالیفرنیا سن‌دیگو روشی معرفی کرده که RSA رو بدون فاکتورگیری می‌شکنه. تا امروز تصور رایج این بود که برای ساختن امضای معتبر RSA باید اول کلید خصوصی رو با تجزیهٔ عدد بزرگ به دست بیاری. این مقاله می‌گه لازم نیست.
حمله از یه نسخهٔ خاص الگوریتم number field sieve (روشی برای تجزیهٔ عددهای بزرگ که سال ۲۰۰۷ معرفی شد) استفاده می‌کنه، همراه با چیزی که بهش oracle می‌گن: یعنی سرویسی که به هر ورودی‌ای بهش بدی، جواب امضاشده برمی‌گردونه. مهاجم با تعداد خیلی زیاد درخواست اون‌قدر اطلاعات جمع می‌کنه که خودش بتونه امضای جعلی بسازه.
عددها تفاوت رو نشون می‌دن. فاکتورگیری یه کلید ۱۰۲۴ بیتی حدود ۲ به توان ۸۰ عملیات و ۵۰۰ هزار تا یک میلیون سال-هستهٔ پردازنده می‌خواد، ولی جعل امضا با این روش ۲ به توان ۶۵ عملیات و فقط ۱۳۸۰ سال-هسته برد. برای کلیدهای ۲۰۴۸ و ۴۰۹۶ بیتی هم سطح امنیت میاد روی ۲ به توان ۹۰ و ۲ به توان ۱۱۹، در حالی که NIST و NSA حداقل ۱۲۸ بیت امنیت می‌خوان.
خبر خوب اینه که اکثر پیاده‌سازی‌های امروزی RSA از padding نوع PKCS یا PSS استفاده می‌کنن و این حمله روشون کار نمی‌کنه. هدف، نسخهٔ blind-signature یا همون RSA کتابیه. معروف‌ترین نمونه‌ش Privacy Pass ـه، پروتکلی که Apple و Cloudflare برای احراز هویت بدون افشای هویت کاربر ازش استفاده می‌کنن. حمله به اون حدود ۲ به توان ۴۳ درخواست توکن لازم داره.
به گفتهٔ Heninger این حجم درخواست زیاد به نظر می‌رسه ولی هم‌مرتبهٔ ترافیک یه روز Cloudflare ـه. چرخش منظم کلیدها ریسک رو خیلی کم می‌کنه اما کامل از بین نمی‌بره. تیم پژوهشی همهٔ کد رو دستی نوشته و از GPU یا هوش مصنوعی استفاده نکرده، پس این سطوح احتمالاً باز هم پایین‌تر می‌ره. نویسندگان مقاله و بقیهٔ پژوهشگرها تأکید می‌کنن خطر عملی فعلاً کمه، ولی فشار برای کوچ کامل از RSA بیشتر میشه.
نکات کلیدی:
- جعل امضا بدون فاکتورگیری، راهی که تا حالا کسی سراغش نرفته بود
- امنیت کلید ۱۰۲۴ بیتی از ۲ به توان ۸۰ به ۲ به توان ۶۵ عملیات رسید
- کلید ۴۰۹۶ بیتی با ۲ به توان ۱۱۹ زیر حد ۱۲۸ بیتی استانداردهای NIST قرار می‌گیره
- فقط blind-signature RSA آسیب‌پذیره، نه پیاده‌سازی‌های PKCS و PSS
- Privacy Pass اپل و Cloudflare مهم‌ترین کاربرد واقعی در معرض خطره
