חוקרים מאוניברסיטת קליפורניה, סן דייגו, פיתחו טכניקת תקיפה משופרת כנגד אלגוריתם ה-RSA, המאפשרת זיוף חתימות דיגיטליות מבלי לפרק את המספרים הראשוניים של ה-RSA הבסיסיים וללא צורך לשחזר את המפתח הפרטי. המשאבים הנדרשים לתקיפת מפתח RSA של 1024 סיביות מוערכים ב-1380 שנות חישוב על ליבת מעבד אחת. באמצעות האשכול הקיים של האוניברסיטה, הדבר איפשר להם לקבוע את הפרמטרים הדרושים ליצירת חתימות RSA מזויפות תוך חמישה חודשים (הניסוי לא השתמש במאיצי בינה מלאכותית או במעבדים גרפיים, אך השימוש בהם יכול להפחית משמעותית את זמן החישוב). לשם השוואה, שיטת הפירוק לגורמים הקלאסית דורשת בין 500,000 למיליון שנות חישוב על ליבת מעבד אחת כדי לשחזר מפתח פרטי מסוג RSA-1024.
ביצוע מתקפה דורש את היכולת לשלוח שוב ושוב בקשות לחתימה על הנתונים שנוצרו על ידי התוקף, לדוגמה, על ידי גישה לשירות הרשאה או מודול HSM. כדי לקבוע פרמטרים של RSA-1024, מספיק לשלוח 232 בקשות כאלה, וכדי לתקוף מפתחות RSA-2048 המשמשים בפרוטוקול Privacy Pass, מספיקות 243. לאחר קבלת מערך של נתונים חתומים, מתחיל תהליך ארוך של חישוב פרמטרים (כ-265 פעולות עבור RSA-1024). לאחר חישוב פרמטרים אלה, התוקף יכול ליצור חתימות מזויפות עבור כל נתונים, תוך השקעת כ-180 שעות חישוב על ליבה אחת לכל חתימה.
השיטה ישימה רק לחתימות RSA שאינן משתמשות בעיצוב או בריפוד לפני הצפנה. מימושים של חתימות עיוורות, כולל אלו המשמשים בפרוטוקול Privacy Pass, פגיעים להתקפה. מימושי ה-RSA הנפוצים ביותר, כולל PKCS#1v1.5 ו-RSA-PSS (המשמשים ב-TLS ו-SSH), משתמשים בריפוד ואינם פגיעים להתקפה.
הצפנת RSA מבוססת על פעולה של העלאת מספר גדול לחזקת מודולו. המפתח הציבורי מכיל את המודולוס ואת החזקה. המודולוס נוצר באמצעות שני מספרים ראשוניים אקראיים הידועים רק לבעל המפתח הפרטי. השיטה המוצעת מבוססת על מחקר שפורסם בשנת 2007 שהראה כי חילוץ שורש של הודעה מוצפנת לחזקה שצוינה במפתח הציבורי ללא ידיעת הגורמים הסודיים היא פעולה פחות עתירת משאבים מאשר פירוק הגורמים עצמם.
באמצעות שיטת שדות מספרים מבוססת מסננת (SNFS), הצליחו החוקרים להפחית את מורכבות הפריצה למפתחות RSA-1024 ל-265 פעולות, מה שאפשר התקפות מעשיות על אשכולות מודרניים. עבור מפתחות RSA של 2048 סיביות, המורכבות מוערכת ב-290, נתון תיאורטית אפשרי עבור תאגידים גדולים או סוכנויות מודיעין. עבור מפתחות של 4096 סיביות, המורכבות היא 2119 פעולות, נתון שאינו ניתן להשגה בפועל כיום, אך נמוך מהמינימום של 2128 המומלץ על ידי ה-NSA, המכון הלאומי לתקנים וטכנולוגיה והסוכנות האירופית לאבטחת רשתות ומידע.
מקור: OpenNet.ru
