פחות מחצי שעה: קלוד של אנתרופיק פענח סוד הצפנה של ה-NSA שחיכה כמעט 30 שנה
כמעט 30 שנה ניסו קריפטוגרפים להבין מאיפה הגיעו המספרים שעליהם בנויות העקומות האליפטיות של התקן האמריקאי, ובהן P-256, שמגינה על חלק גדול מהתקשורת המוצפנת ברשת. מודל מחקר פנימי של אנתרופיק פתר את השאלה בפחות מחצי שעה. החברה פרסמה את הממצאים יחד עם קוד שמאפשר לכל אחד לשחזר אותם.
הרקע מתחיל בשנת 2000, כשמכון התקנים האמריקאי, NIST, אימץ את תקן החתימה הדיגיטלית ECDSA. לכל עקומה בתקן צורף מספר התחלתי, זרע, שממנו נגזרים המקדמים שלה. את הזרעים סיפקה ה-NSA, סוכנות הביון האלקטרוני של ארה"ב, בלי שום הסבר על מקורם, ואחרי חשיפות סנודן על דלת אחורית בתקן אחר החשד התחזק עוד יותר. ג'רי סוליינס, קריפטוגרף של ה-NSA שנפטר ב-2023, סיפר ב-2015 שהזרעים נוצרו מגיבוב של משפט הומוריסטי, אבל איש לא מצא את המשפט.
קלוד קיבל את השאלה בלי הרמז הזה והניח שמדובר במחולל מספרים אקראיים נפוץ של שפת C משנות ה-90. הוא כתב סורק שבודק דפוסים כאלה, ומצא סימן מסגיר: בארבעה מעשרה זרעים הסיבית העליונה של כל מילה בת 32 סיביות הייתה אפס, דבר שמתאים בדיוק לפונקציה lrand48. משם הוא שחזר את מצב המחולל בחיפוש ממצה ובשיטה מתמטית של צמצום סריגים, ומצא שהזרעים של חמש העקומות של NIST ושל חמש עקומות בתקן מקביל נוצרו כולם באותה דרך.
הידעת?איפה משתמשים בעקומה P-256?
הפונקציה הוזנה בחותמת זמן של מחשב יוניקס, ולכן הזרעים עצמם מסגירים מתי נוצרו: בין מאי 1997 לאפריל 1998. הזרעים של ארבע העקומות הבינאריות נראו בתחילה כאילו נוצרו בפברואר 1984, אבל הכפלה של חותמות הזמן מובילה לאפריל 1998, שבועיים אחרי שנוצרה P-224. נראה שהתוכנה פשוט חילקה את השעון בשתיים. בשביל P-256 התוכנה עברה על 1,842 מועמדים עד שמצאה עקומה מתאימה. קלוד פענח גם את מקור נקודות הבסיס של שש עקומות, שנוצרו בספריית תוכנה מתמטית שהייתה פופולרית באותן שנים. עד עכשיו אף נקודת בסיס של NIST לא קיבלה הסבר, ו-P-192 היא הראשונה.
אנתרופיק מדגישה שאין כאן פריצה, מתקפה חדשה או חולשה בהצפנה. לדבריה, הממצאים מורידים מאוד את הסבירות לדלת אחורית, כי הזרעים נוצרו בתהליך פשוט שכל אחד יכול לשחזר, ומשתמשי התקן לא צריכים לעשות דבר. נשארו גם שאלות פתוחות: התוכנה דילגה על כמה מועמדים תקינים, ול-P-256 למשל התאים כבר המועמד ה-876. מקור הזרע של עקומה אחת והמקור של רוב נקודות הבסיס עדיין לא ידועים.
הידעת?מה זה lrand48 ולמה הוא לא מתאים להצפנה?
הפרס של 36,864 דולר, שהוצע בעבר למי שיפענח את מקור הזרעים, ייתרם לארגון ISRG, שמפעיל את Let's Encrypt ומנפיק חינם תעודות אבטחה לאתרים. זה עוד פרק בסיפור של אנתרופיק, שהפכה תוך כמה שנים לאחת מחברות הבינה המלאכותית היקרות בעולם, ובמקביל לפענוח הזה בנקים וממשלות כבר מחליפים את שיטות ההצפנה לקראת עידן המחשוב הקוונטי.
