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

קריפטוגרפים הניחו במשך עשורים שהדרך היחידה לשבור את RSA היא לפרק לגורמים את המספרים הגדולים שמאחורי המפתחות. צוות מחקר בראשות נדיה הנינגר, פרופסורית באוניברסיטת קליפורניה בסן דייגו, ערער על ההנחה הזו: החוקרים פיתחו התקפת זיוף חתימה שמחשבת חתימות RSA תקפות בלי לפרק את המפתח הפרטי לגורמים. המאמר פורסם בארכיון IACR ePrint וטרם עבר ביקורת עמיתים. בשלב זה אין לאיום משמעות מעשית, למעט אולי במקרים בודדים.

מה עושה ההתקפה

עד כה סברו הקריפטוגרפים שחישוב חתימות RSA תקפות מחייב תחילה שחזור המפתח הפרטי על ידי פירוק לגורמים. עבור RSA של 1024 סיביות זה נחשב ליקר מאוד אך אפשרי כנראה לחברות טכנולוגיה ענקיות או ל-NSA — בסדר גודל של עשרות מיליוני דולרים של זמן מחשוב למפתח בודד; ואילו RSA של 2048 סיביות נחשבה לחלוטין מחוץ להישג יד, לדברי הנינגר.

ההתקפה מורידה את רמת האבטחה המוערכת של RSA ה"ספרייתי" (textbook) ל-2^65, 2^90 ו-2^119 פעולות עבור מפתחות של 1024, 2048 ו-4096 סיביות בהתאמה — סדרי גודל מתחת לרמת 128 הסיביות (יותר מ-2^128 פעולות) שדורשים NSA, ‏NIST ו-ENISA של האיחוד האירופי מכל מערכת הצפנה. לשם השוואה: פירוק מפתח בודד של 1024 סיביות הוערך ב-2^80 פעולות ובין 500 אלף למיליון שנות-ליבה של CPU, בעוד שזיוף חתימה בטכניקת הנפה החדשה דרש 2^65 פעולות ורק 1,380 שנות-ליבה. הצוות כתב את כל הקוד ביד, בלי AI ובלי GPU, והנינגר אמרה שכלים אלה "כמעט בוודאות" יורידו את רמות האבטחה עוד יותר.

למה אין עדיין סכנה מעשית

ההתקפה עובדת רק נגד מימושים של RSA עם חתימה "עיוורת" (blind-signature), הידועה גם כ-RSA ספרייתי. הרוב המכריע של RSA בשימוש כיום משתמש בריפוד PKCS או PSS, שמוסיף נתונים לטקסט לפני ההצפנה ומבטל את החולשה שעליה מתבססת ההתקפה. גם נגד מפתחות 1024 סיביות מיושנים, השיטה דורשת יותר מחשוב ממה שכל גורם מלבד מדינות או חברות ענק יכול להשיג.

הדוגמה המפורסמת ביותר לשימוש אמיתי ב-RSA ספרייתי היא Privacy Pass, פרוטוקול אימות שמאפשר למשתמשים להוכיח את זהותם בלי לחשוף אותה; הוא משמש את Apple ו-Cloudflare. התקפה עליו תחייב לפרוץ שרת של אחת מהן ולייצר 2^43 חתימות — מספר שלדברי הנינגר "נשמע כמו הרבה, אבל הוא באותו סדר גודל של תעבורת הרשת ש-Cloudflare הצהירה שהיא מטפלת בה בכמעט יממה". רוב מימושי Privacy Pass מחליפים מפתחות באופן קבוע, מה שמקטין מאוד — אך לא מבטל לחלוטין — את סיכויי ההצלחה.

למה זה חשוב

קרסטן נוהל, מומחה קריפטוגרפיה וראש החדשנות ב-Allurity, אמר שאם התוצאה תחזיק מעמד בביקורת עמיתים, זה יהיה "פריצת דרך קונספטואלית". בלב השיטה וריאנט של אלגוריתם נפה של שדה המספרים (number field sieve) שהומצא ב-2007, שפועל נגד "אורקל" — חולשה שמעניקה תשובות כן/לא לשאילתות מסוימות. קריפטוגרפים עמלים על חלופות פוסט-קוונטיות, כשהערכות להגעת מחשוב קוונטי מעשי נעות בין 3 ל-20 שנה; ההתקפה החדשה מגבירה את הדחיפות לנטוש את RSA לחלוטין.