חוקרים זייפו חתימות RSA של 1024 סיביות בלי לפרק את המפתח לגורמים

חוקרים מ-UC San Diego ומ-Inria Nancy יישמו התקפה שמאפשרת לזייף חתימות RSA של 1024 סיביות באופן שרירותי, בלי לפרק את המפתח לגורמים. המאמר "Forging 1024-bit RSA signatures in nearly SNFS time" הועלה לארכיון IACR ePrint ב-20 בספטמבר, ומחבריו הם לורה שי, מירו הלר, אדם סול, נדיה הנינגר ועמנואל תומה.

העבודה מיישמת אלגוריתם מ-2007 של Joux, Naccache ו-Thomé, שלדברי המחברים זכה לפחות תשומת לב משהיה ראוי לה. זמן הריצה שלו קרוב לזה של נפה מיוחדת של שדה המספרים (SNFS), ונמוך בהרבה מזה של GNFS, שמשמש לקביעת גדלי מפתחות RSA.

מה נדרש להתקפה

מודל האיום הוא התקפת "צהריים" (lunchtime), ובמונחים פורמליים התקפת טקסט מוצפן נבחר לא-אדפטיבית (IND-CCA1): התוקף מקבל גישה זמנית לאורקל גולמי של חתימה או פענוח RSA עבור מפתח מסוים, ואז מאבד אותה. לאחר מכן הוא יכול לזייף כל חתימה שירצה באופן לא מקוון, ולחזור על כך לכל מטרה בלי לשלוח שאילתות נוספות.

סך החישוב ארך 1380 שנות-ליבה של CPU לאורך חמישה חודשים קלנדריים וכ-2^32 שאילתות לאורקל. החישוב המקדים, שתלוי רק במודולוס, תופס כ-1200 שנות-ליבה; כל זיוף בודד לאחר מכן עולה כ-180 שנות-ליבה. לשם השוואה, פירוק לגורמים של מודול RSA של 1024 סיביות מוערך ב-500,000 עד 1,000,000 שנות-ליבה של CPU.

HSM וחתימות עיוורות

המחברים ביצעו את שאילתות האורקל דרך מודול אבטחה חומרתי (HSM), והראו שתוקף עם גישה לתשקיף API של קופסה שחורה יכול להתחזות ל-HSM בלי לחלץ את המפתח. תקן PKCS #11, שנתמך כמעט בכל ה-HSM, חושף בדיוק את פעולות ה-RSA הגולמיות שההתקפה צריכה. גם סכימות חתימה עיוורת מבוססות RSA מספקות אורקל כזה, ולפי המאמר מפתחות של 2048 סיביות הנפוצים בפריסות אמיתיות מספקים מרווח ביטחון נמוך מדי.

15 עד 30 סיביות פחות ביטחון

מאקסטרפולציה של זמני הריצה שנמדדו מסיקים המחברים שהביטחון הקונקרטי של RSA עם אורקל חתימה נמוך ב-15 עד 30 סיביות מההערכות המבוססות על פירוק לגורמים, עבור פרמטרים של 1024 עד 4096 סיביות. עבור RSA של 1024 סיביות, המיוחס לו בדרך כלל ביטחון של 80 סיביות, ההערכה היא כ-2^65. עבור 2048 סיביות (112 סיביות) מתקבלים כ-2^90 ו-2^43 שאילתות, ועבור 4096 סיביות כ-2^119 ו-2^57 שאילתות. כלומר, אפילו RSA של 4096 סיביות אינו מגיע לרמת ביטחון של 128 סיביות במודל הזה.

פער בהנחות היסוד של RSA

המחברים אינם טוענים ש-RSA שבור בשימוש יומיומי: ההתקפה מעשית במובן האקדמי ולא במובן של תוקף מזדמן, ומודל האורקל הגולמי חזק מאוד. ואולם לדבריהם הוא חושף פער: הנחת one-more RSA אינה מתארת התקפות עם חישוב מקדים, והם מציעים לקרוא למצב "delayed-target RSA". NIST מתכננת להפסיק את השימוש ב-RSA עד 2030 ולאסור אותו עד 2035, והמחברים רואים בעבודה שלהם נימוק נוסף לזרז את המעבר. הקוד פורסם ב-GitHub.