הצפנה פוסט-קוונטית - אלגוריתם חדש "נעלם תוך 60 דקות"

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

למקרה שפספסתם את כל ההתרגשות התקשורתית של השנים האחרונות לגבי מה שנקרא מחשוב קוונטי...

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

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

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

• אלגוריתם החיפוש הקוונטי של גרובר. בדרך כלל, אם אתה רוצה לחפש סדרה אקראית של תשובות כדי לראות אם שלך נמצא ברשימה, אתה מצפה לחרוש את כל הרשימה, במקרה הרע, לפני שתקבל תשובה סופית. לדוגמה, אם תרצה למצוא את מפתח פענוח AES 128 סיביות כדי לבטל את ערבול מסמך, תצטרך לחפש ברשימת כל המפתחות האפשריים, החל מ- 000..001, ..2, ..3, וכן הלאה, כל הדרך עד FFF..FFF (בשווי 16 בתים של FF), כדי להיות בטוחים בהשלמת הבעיה. במילים אחרות, אתה צריך תקציב כדי לנסות את כל השניים¹²⁸ מפתחות אפשריים לפני מציאת המפתח הנכון, או קביעה שלא היה אחד. לעומת זאת, האלגוריתם של גרובר, בהינתן מחשב קוונטי גדול וחזק מספיק, טוען שהוא מסוגל להשלים את אותו הישג עם שורש ריבועי מהמאמץ הרגיל, ובכך לפצח את הקוד, בתיאוריה, ב-2 בלבד⁶⁴ מנסה במקום.
• אלגוריתם הפירוק הקוונטי של שור. כמה אלגוריתמי הצפנה עכשוויים מסתמכים על העובדה שכפל שני מספרים ראשוניים גדולים יחד יכול להיעשות במהירות, בעוד שחלוקת המוצר שלהם בחזרה לשני המספרים שאיתם התחלת היא כמעט בלתי אפשרית. כדי לקבל תחושה לגבי זה, נסה להכפיל 59×87 באמצעות עט ונייר. זה עשוי לקחת דקה בערך להוציא את זה (5133 היא התשובה), אבל זה לא כל כך קשה. עכשיו נסה את הדרך אחרת. חלקו, נניח, את 4171 חזרה לשני הגורמים שלו. הרבה יותר קשה! (זה 43×97.) כעת דמיינו לעשות זאת עם מספר שאורכו 600 ספרות. באופן רופף, אתה תקוע בניסיון לחלק את המספר בן 600 הספרות בכל מספר ראשוני אפשרי של 300 ספרות עד שתזכה בקופה, או שתגלה שאין תשובה. האלגוריתם של שור, לעומת זאת, מבטיח לפתור בעיה זו עם לוֹגָרִיתְם מהמאמץ הרגיל. לפיכך, עיבוד של מספר של 2048 ספרות בינאריות צריך לקחת רק פי שניים יותר מאשר פירוק של מספר של 1024 סיביות, לא פי שניים מאשר פירוק מספר של 2047 סיביות, המייצג מהירות עצומה.

התמודדות עם האיום

ניתן להתמודד עם האיום מהאלגוריתם של גרובר פשוט על ידי הגדלת גודל המספרים שבהם אתה משתמש על ידי ריבוע אותם, כלומר הכפלת מספר הביטים ב-hash ההצפנה שלך או מפתח ההצפנה הסימטרי שלך. (במילים אחרות, אם אתה חושב ש-SHA-256 בסדר עכשיו, שימוש ב-SHA-512 במקום יספק אלטרנטיבה עמידה ל-PQC.)

אבל לא ניתן להתנגד לאלגוריתם של שור כל כך בקלות.

מפתח ציבורי של 2048 סיביות יצטרך להגדיל את גודלו באופן אקספוננציאלי, לא רק על ידי ריבוע, כך שבמקום מפתח של 2×2048=4096 סיביות, או שתצטרך מפתח חדש בגודל הבלתי אפשרי של 2²⁰⁴⁸ פיסות…

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

ובכן, גוף התקנים האמריקאי NIST מפעיל את א PQC "תחרות" מאז סוף 2017.

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

קול קורא. [סגור 2017-11-30]. […] הכוונה היא שתקני ההצפנה החדשים של מפתח ציבורי יציינו חתימה דיגיטלית אחת או יותר לא מסווגת, שנחשפה בפומבי, הצפנת מפתח ציבורי, ואלגוריתמים ליצירת מפתחות הזמינים ברחבי העולם, ומסוגלים להגן על מידע ממשלתי רגיש גם בעתיד הנראה לעין, כולל לאחר הופעת המחשבים הקוונטים.

לאחר שלושה סבבים של הגשות ודיונים, הודיעה NIST, ב-2022-07-05, שהיא בחרה בארבעה אלגוריתמים שנחשבים בעיניה ל"סטנדרטים" עם השפעה מיידית, כולם עם שמות שנשמעים מענג: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, ו SPHINCS+.

הראשון (CRYSTALS-KYBER) משמש בתור מה שנקרא a מנגנון הסכם מפתח (KEM), שבו שני קצוות של ערוץ תקשורת ציבורי רוקחים בצורה מאובטחת מפתח הצפנה פרטי חד פעמי להחלפת נתונים בשווי סשן בסודיות. (פשוט שים: חטטנים פשוט מקבלים כרוב מגורר, אז הם לא יכולים לצותת לשיחה.)

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

דרושים יותר אלגוריתמים

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

אלה היו: BIKE, Classic McEliece, HQC ו SIKE.

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

עם זאת, זה מעולם לא תפס, כי הוא דרש כמויות אדירות של חומר מפתח בהשוואה לאלטרנטיבה הפופולרית של היום, האלגוריתם Diffie-Hellman-Merkle (DHM, או לפעמים רק DH).

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

במאמר מעוות מוח בשם התקפת מפתח יעילה על SIDH (גרסה ראשונית)נראה שהקריפטוגרפים הבלגים ווטר קסטריק ותומס דקרו הטילו מכה קטלנית לאלגוריתם SIKE

למקרה שאתם תוהים, SIKE הוא קיצור של Encapsulation Key Isogeny Supersingular, ו-SIDH מייצג איזוגני על יחיד דיפי-הלמן, שימוש ספציפי ב- אלגוריתם SIKE לפיו שני קצוות של ערוץ תקשורת מבצעים "קריפטודנס" דמוי DHM כדי להחליף חבורה של נתונים ציבוריים המאפשרים לכל קצה להפיק ערך פרטי לשימוש כמפתח הצפנה סודי חד פעמי.

לא ננסה להסביר את המתקפה כאן; רק נחזור על מה שהעיתון טוען, כלומר:

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

אבל הפלט שחולץ (המידע המכונה האיזוגניה φ למעלה) אמור להיות החלק שמעולם לא נחשף בתהליך - המפתח הפרטי כביכול.

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

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

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

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

מה לעשות?

שום דבר!

(אלה החדשות הטובות.)

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

(אלה החדשות הרעות.)

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

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

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

אם אלגוריתם PQC כמו SIKE שרד בדיקה ובדיקה של מומחים מרחבי העולם במשך יותר מחמש שנים, למרות שנחשף במיוחד כדי שיוכל להיות נתון לביקורת ציבורית...

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

---