תוכנית קריפטוגרפיה 'פוסט-קוואנטית' נסדקת במחשב נייד

אם פרוטוקולי ההצפנה של היום היו נכשלים, זה היה בלתי אפשרי לאבטח חיבורים מקוונים - לשלוח הודעות סודיות, לבצע עסקאות פיננסיות מאובטחות או לאמת נתונים. כל אחד יכול לגשת לכל דבר; כל אחד יכול להעמיד פנים שהוא כל אחד. הכלכלה הדיגיטלית תתמוטט.

מתי (או if) מחשב קוונטי מתפקד במלואו הופך לזמין, זה בדיוק מה שיכול לקרות. כתוצאה מכך, בשנת 2017 השיק המכון הלאומי לתקנים וטכנולוגיה (NIST) של ממשלת ארה"ב תחרות בינלאומית למציאת הדרכים הטובות ביותר להשיג קריפטוגרפיה "פוסט-קוונטית".

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

ואז ב-30 ביולי, זוג חוקרים חשפו שכן שבור אחד מאותם מועמדים בעוד שעה במחשב נייד. (מאז, אחרים הפכו את ההתקפה למהירה עוד יותר, ושברו את הפרוטוקול תוך דקות ספורות.) "מתקפה שהיא כל כך דרמטית ועוצמתית... הייתה די הלם", אמר סטיבן גלבריית', מתמטיקאי ומדען מחשבים באוניברסיטת אוקלנד בניו זילנד. לא רק שהמתמטיקה בבסיס המתקפה הפתיעה, אלא שהיא הפחיתה את המגוון (הנחוץ) של ההצפנה הפוסט-קוונטית - ביטול פרוטוקול הצפנה שעבד בצורה שונה מאוד מהרוב המכריע של התוכניות בתחרות NIST.

"זה קצת מבאס," אמר כריסטופר פייקרט, קריפטוגרף באוניברסיטת מישיגן.

התוצאות הותירו את קהילת ההצפנה הפוסט-קוונטית מזועזעת ומעודדת כאחד. מזועזע, כי המתקפה הזו (ועוד אחת מסיבוב קודם בתחרות) הפכה פתאום את מה שנראה כמו דלת פלדה דיגיטלית לעיתון רטוב. "זה בא ישר", אמר דסטין מודי, אחד המתמטיקאים המובילים את מאמץ התקינה של NIST. אבל אם סכימת קריפטוגרפיה עומדת להישבר, עדיף שהיא תתרחש הרבה לפני השימוש בה בטבע. "יש הרבה רגשות שעוברים בך," אמר דיוויד ג'או, מתמטיקאי באוניברסיטת ווטרלו בקנדה, שיחד עם חוקר IBM לוקה דה פאו, הציע את הפרוטוקול ב-2011. אין ספק שהפתעה ואכזבה הם ביניהם. "אבל גם," הוסיף ג'או, "לפחות זה נשבר עכשיו."

טיולים סודיים בין עקומות

ג'או ודה-פאו ראו הזדמנות למערכת הצפנה שהייתה דומה לפרוטוקולים ידועים וגם נבדלת באופן הולם. התוכנית שלהם, שנקראה פרוטוקול האיזוגניות העל-סינגולרית Diffie-Hellman (SIDH), עסקה בעקומות אליפטיות - אותם אובייקטים מתמטיים המשמשים באחד מסוגי ההצפנה הנפוצים ביותר שנפרסו כיום. אבל זה השתמש בהם בצורה אחרת לגמרי. זו הייתה גם התוכנית הקומפקטית ביותר ש-NIST שקלה (עם הפשרה שהיא הייתה איטית יותר מרבים מהמועמדים האחרים).

ו"מתמטית, זה ממש אלגנטי," אמר ג'או. "בזמנו, זה נראה כמו רעיון יפה."

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

לגרפים של אליס ובוב יש את אותן נקודות, אבל הקצוות שונים - הם מוגדרים על ידי איזוגניות שונות. אליס ובוב מתחילים באותה נקודה, וכל אחד מהם קופץ לאורך קצוות אקראיים בגרף שלו, ועוקב אחר הנתיב שלהם מנקודה אחת לאחרת. לאחר מכן כל אחד מפרסם את מיקום הסיום שלו אך שומר את דרכו בסוד.

עכשיו הם מחליפים מקומות: אליס הולכת לנקודה האחרונה של בוב, ובוב לאליס. כל אחד חוזר על הליכתו הסודית. הם עושים זאת בצורה כזו ששניהם יגיעו לאותה נקודה.

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

אבל כדי לגרום ל-SIDH לעבוד, אליס ובוב צריכים גם להחליף מידע נוסף על הטיולים שלהם. המידע הנוסף הזה הוא שהוביל לנפילתו של SIDH.

טוויסט חדש במתמטיקה ישנה

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

הם נתקלו במאמר שפרסם המתמטיקאי ארנסט קאני בשנת 1997. היה בו משפט ש"היה ישים כמעט מיד ל-SIDH", אמר קסטרוק. "אני חושב שברגע שהבנו ש... התקיפה הגיעה די מהר, תוך יום או יומיים".

בסופו של דבר, כדי לשחזר את ההליכה הסודית של אליס (ולכן את המפתח המשותף), קסטרוק ודקרו בחנו את התוצר של שתי עקומות אליפטיות - עקומת ההתחלה של אליס והעקומה שהיא שלחה בפומבי לבוב. השילוב הזה מייצר מעין משטח הנקרא משטח אבלי. לאחר מכן הם השתמשו במשטחים האבליים האלה, במשפט קאני (המקשר בין משטחים אבלים לעיקולים אליפטיים), ובמידע הנוסף שאליס נתנה לבוב כדי לחשוף כל צעד שאליס עשתה.

"זה כמעט כמו אות ביות שמאפשר לך להינעל על [משטחים אבליים מסוימים]", אמר ג'או. "והאות הזה אומר לך שזו הדרך שבה אתה צריך ללכת כדי לעשות את הצעד הבא כדי למצוא את [ההליכה הסודית] הנכונה." מה שהוביל אותם היישר אל המפתח המשותף של אליס ובוב.

"זו גישה מאוד לא צפויה, ללכת לאובייקטים מסובכים יותר כדי להפיק תוצאות לגבי האובייקט הפשוט יותר," אמר ג'או.

"התרגשתי מאוד לראות את הטכניקה הזו בשימוש", אמר קריסטין לאוטר, מתמטיקאי וצפנה ב-Meta AI Research שלא רק עזר בפיתוח קריפטוגרפיה מבוססת איזוגניה אלא גם עבד על משטחים אבלים. "אז תתבייש לי שלא חשבתי על זה כעל דרך לשבור את זה."

המתקפה של קסטרוק ודקרו שברה את גרסת האבטחה הנמוכה ביותר של פרוטוקול SIDH תוך 62 דקות ואת רמת האבטחה הגבוהה ביותר תוך קצת פחות מיממה. לאחר מכן, זמן קצר לאחר מכן, מומחה אחר שיפר את המתקפה כך שלקח רק 10 דקות לשבור את הגרסה בעלת האבטחה הנמוכה וכמה שעות לשבור את הגרסה בעלת האבטחה הגבוהה. יותר התקפות כלליות פורסם בשבועות האחרונים להפוך את זה לא סביר שניתן להציל את SIDH.

"זו הייתה הרגשה מיוחדת," ​​אמר קסטררוק, אם כי מרירה מתוקה. "הרגנו את אחת המערכות האהובות עלינו."

רגע קו פרשת מים

אי אפשר להבטיח שמערכת מאובטחת ללא תנאי. במקום זאת, קריפטוגרפים מסתמכים על מספיק זמן שעובר ומספיק אנשים שמנסים לשבור את הבעיה כדי להרגיש בטוחים. "זה לא אומר שלא תתעורר מחר ותגלה שמישהו מצא אלגוריתם חדש לעשות את זה", אמר ג'פרי הופשטיין, מתמטיקאי באוניברסיטת בראון.

מכאן מדוע תחרויות כמו של NIST הן כל כך חשובות. בסבב הקודם של תחרות NIST, וורד באלנס, קריפטוגרף ב-IBM, הגה מתקפה שבר תוכנית בשם קשת בסוף שבוע. כמו קסטרוק ודקרו, הוא הצליח לביים את ההתקפה שלו רק לאחר שראה את הבעיה המתמטית הבסיסית מזווית אחרת. וכמו המתקפה על SIDH, זו שברה מערכת שנשענה על מתמטיקה שונה מרוב הפרוטוקולים הפוסט-קוונטיים המוצעים.

"ההתקפות האחרונות היו רגע פרשת מים", אמר תומס פרסט, קריפטוגרף בסטארט-אפ PQShield. הם מדגישים כמה קשה היא קריפטוגרפיה פוסט-קוונטית, וכמה ניתוח עשוי להיות נחוץ כדי ללמוד את האבטחה של מערכות שונות. "לאובייקט מתמטי יכול להיות שאין מבנה ברור בפרספקטיבה אחת, ויש לו מבנה בר ניצול בפרספקטיבה אחרת", אמר. "החלק הקשה הוא לזהות את נקודת המבט החדשה הנכונה."