פגיעות בהטמעות של אלגוריתם ההצפנה הפוסט-קוונטי Kyber

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

מהות הפגיעות, שקיבלה את שם הקוד KyberSlash, היא בשימוש בפעולת החלוקה "t = (((t < 1) + KYBER_Q/2)/KYBER_Q) & 1;" בתהליך פענוח הודעה , שבו הדיבידנד מכיל את הערך הסודי "t" עם סוג "כפול", והמחלק הוא הערך הציבורי הידוע KYBER_Q. הבעיה היא שזמן פעולת החלוקה אינו קבוע, ובסביבות שונות מספר מחזורי המעבד המבוצעים לחלוקה תלוי בנתוני הקלט. לפיכך, בהתבסס על שינויים בזמני הפעולה, ניתן לקבל מושג על אופי הנתונים המשמשים בחלוקה.

דניאל ג'יי ברנשטיין, מומחה ידוע בתחום הקריפטוגרפיה, הצליח להכין הדגמה עובדת של הוכחה לכך שניתן לבצע את התקיפה בפועל. בשניים משלושת הניסויים שנערכו, בעת הפעלת קוד על לוח Raspberry Pi 2, ניתן היה ליצור מחדש לחלוטין את המפתח הפרטי Kyber-512 בהתבסס על מדידת זמן פענוח הנתונים. ניתן להתאים את השיטה גם למפתחות Kyber-768 ו-Kyber-1024. כדי לבצע תקיפה בהצלחה, יש צורך שטקסט הצופן שצוין על ידי התוקף יעובד באמצעות אותו זוג מפתחות וניתן למדוד במדויק את זמן הביצוע של הפעולה.

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

הפגיעות כבר תוקנה בספריות:

• zig/lib/std/crypto/kyber_d00.zig (22 בדצמבר),
• pq-crystals/kyber/ref (30 בדצמבר),
• symbolicsoft/kyber-k2so (19 בדצמבר),
• cloudflare/circl (8 בינואר),
• aws/aws-lc/crypto/kyber (4 בינואר),
• liboqs/src/kem/kyber (8 בינואר).

ספריות שלא הושפעו מלכתחילה מהפגיעות:

• boringssl/crypto/kyber,
• filippo.io/mlkem768,
• formosa-crypto/libjade/tree/main/src/crypto_kem,
• kyber/common/amd64/avx2,
• formosa-crypto/libjade/tree/main/src/crypto_kem/kyber/common/amd64/ref,
• pq-crystals/kyber/avx2,
• pqclean/crypto_kem/kyber*/avx2.

הפגיעות נשארת ללא תיקון בספריות:

• antontutoveanu/crystals-kyber-javascript,
• Argyle-Software/kyber,
• debian/src/liboqs/unstable/src/kem/kyber,
• kudelskisecurity/crystals-go,
• mupq/pqm4/crypto_kem/kyber* (ב-20 בדצמבר תוקנה רק גרסה אחת של הפגיעות),
• PQClean/PQClean/crypto_kem/kyber*/aarch64,
• PQClean/PQClean/crypto_kem/kyber*/clean,
• randombit/botan (ב-20 בדצמבר תוקנה רק פגיעות אחת),
• rustpq/pqcrypto/pqcrypto-kyber (תיקון נוסף ל-libsignal ב-5 בינואר, אך הפגיעות עדיין לא תוקנה ב-pqcrypto-kyber עצמה).

מקור: OpenNet.ru