Trivium

טריוויום (באנגלית: Trivium) הוא צופן זרם אסינכרוני קל משקל המיועד לחומרה ומאפשר איזון גמיש בין תפוקה לשטח (בשערים)^[1]. הוצע במסגרת תחרות צופן זרם שאורגנה על ידי eSTREAM, נבחר ב-2008 ברשימת הצפנים המועדפים ונכלל בפורטפוליו בקטגוריית חומרה^[2]. הוא אינו מוגן בפטנט ונכלל בתקן איזו ISO/IEC 29192-3^[3].

טריוויום מקבל מפתח הצפנה באורך 80 סיביות, ווקטור אתחול (IV) באורך 80 סיביות, הזיכרון הפנימי שלו מכיל 288 סיביות והוא מורכב משלושה אוגרים ממושבים אי-ליניאריים (NLFSR) באורכים: 93, 84 ו-111 סיביות. האלגוריתם מכיל שני מצבי עבודה, מצב אתחול של המפתח וה-IV ומצב עבודה שבו מופק זרם מפתח פסאודו-אקראי. בכל פעימה שלוש סיביות מהמצב הפנימי מעודכנות באמצעות פונקציית משוב אי-ליניארית והפלט הוא סיבית פסאודו-אקראית אחת. בהגדרה הצופן יכול להפיק $2^{64}$ סיביות ממפתח/IV נתונים.

הצופן פותח ב-2005 על ידי Bart Preneel ו-Christophe De Cannière כחלק מניסוי על מנת לברר כמה קטן צופן זרם יכול להיות מבלי לוותר על ביטחון, מהירות או גמישות. בדרך כלל צופן זרם בסגנון LFSR בגלל רגישותו היתרה סביר שיהיה פגיע להתקפות קריפטוגרפיות ייתכן הרסניות לכן המפתחים מקווים שביקורת ציבורית תביא לאימון רב יותר בביטחון הצופן. העיצוב האלגנטי והפשטות שלו משכו תשומת לב רבה מצד הקהילה האקדמית. נכון ל-2017 טרם נמצאה התקפה קריפטוגרפית הרסנית נגד הצופן מלבד התקפת קובייה של עדי שמיר ואיתי דינור^[4] וסוג של קריפטואנליזה דיפרנציאלית^[5] שמוצאת "מפתחות חלשים" (שפוגעים באקראיות הצופן). שתיהן אינן מהוות איום של ממש על הצופן המלא אלא רק על גרסאות מוחלשות שלו.

תיאור הצופן

מחולל זרם המפתח מכיל מצב פנימי בגודל 288 סיביות המיוצגות על ידי המערך $s_{1},...,s_{288}$ וכן תהליך איטרטיבי שמחלץ את ערכן של 15 סיביות ספציפיות מתוך הזיכרון הפנימי איתן הוא מעדכן שלוש סיביות של המצב הפנימי ומחשב סיבית פלט אחת $z_{i}$ . בשלב זה כל סיביות המצב מוזזות במעגליות צעד אחד, התהליך חוזר על עצמו שוב ושוב עד שמתקבלות $2^{64}$ סיביות של זרם מפתח או פחות לפי הצורך, אותו מחברים ב-XOR עם זרם הנתונים המיועד להצפנה. לסיכום הפסאודו קוד הבא מכיל תיאור שלם של האלגוריתם:

{\text{for }}i=1{\text{ to }}N{\text{ do}}

\ \ \ \ t_{1}\leftarrow s_{66}\oplus s_{93}

\ \ \ \ t_{2}\leftarrow s_{162}\oplus s_{177}

\ \ \ \ t_{3}\leftarrow s_{243}\oplus s_{288}

\ \ \ \ z_{i}\leftarrow t_{1}\oplus t_{2}\oplus t_{3}

\ \ \ \ t_{1}\leftarrow t_{1}\oplus s_{91}\land s_{92}\oplus s_{171}

\ \ \ \ t_{2}\leftarrow t_{2}\oplus s_{175}\land s_{176}\oplus s_{264}

\ \ \ \ t_{3}\leftarrow t_{3}\oplus s_{286}\land s_{287}\oplus s_{69}

\ \ \ \ (s_{1},s_{2},...,s_{93})\leftarrow (t_{3},s_{1},...,s_{92})

\ \ \ \ (s_{94},s_{95},...,s_{177})\leftarrow (t_{1},s_{94},...,s_{176})

\ \ \ \ (s_{178},s_{279},...,s_{288})\leftarrow (t_{2},s_{178},...,s_{287})

{\text{end}}

הסימן $\oplus$ הוא האופרטור XOR והסימן $\land$ הוא האופרטור וגם שהן הפעולות המקבילות לחיבור וכפל בשדה הבינארי $GF(2)$ .

הכנת המפתח ווקטור האתחול

האלגוריתם מתחיל בטעינת המפתח ווקטור האתחול לתוך המצב הפנימי ויתרת סיביות המצב הפנימי מאופסות למעט שלוש הסיביות האחרונות: $s_{286}$ , $s_{287}$ ו- $s_{288}$ . המפתח נטען ראשון ואחריו אפסים עד פוזיציה 93. החל מ-פוזיציה 94 טוענים את וקטור האתחול ולאחריו מאפסים את יתרת הסיביות. ואז בדומה לתהליך המתואר לעיל, המצב הפנימי מסובב במשך ארבע פעימות מבלי להפיק סיביות זרם מפתח. המהלך מומחש בפסאודו קוד הבא:

(s_{1},s_{2},...,s_{93})\leftarrow (K_{1},...,K_{80},0,...,0)

(s_{94},s_{95},...,s_{177})\leftarrow (IV_{1},...,IV_{80},0,...,0)

(s_{178},s_{279},...,s_{288})\leftarrow (0,...,0,1,1,1)

{\text{for }}i=1{\text{ to }}4\cdot 288{\text{ do}}

\ \ \ \ t_{1}\leftarrow s_{66}\oplus s_{91}\land s_{92}\oplus s_{93}\oplus s_{171}

\ \ \ \ t_{2}\leftarrow s_{162}\oplus s_{175}\land s_{176}\oplus s_{177}\oplus s_{264}

\ \ \ \ t_{3}\leftarrow s_{243}\oplus s_{286}\land s_{287}\oplus s_{288}\oplus s_{69}

\ \ \ \ (s_{1},s_{2},...,s_{93})\leftarrow (t_{3},s_{1},...,s_{92})

\ \ \ \ (s_{94},s_{95},...,s_{177})\leftarrow (t_{1},s_{94},...,s_{176})

\ \ \ \ (s_{178},s_{279},...,s_{288})\leftarrow (t_{2},s_{178},...,s_{287})

{\text{end}}

היבטי יישום

טריוויום נועד ליישום בחומרה ועוצב בעיקר להשגת סקלביליות, גמישות ותפוקה גבוהה. הוא אמור להיות קטן מאוד במטרה להתאימו להטמעה בחומרה מוגבלת במספר שערים לוגיים וצריכת אנרגיה מינימלית. כדי לאפשר מקביליות גבוהה הצופן פותח כך שכל סיבית מנוצלת פעם אחת ב-64 פעימות לאחר שעודכנה. כך שעל ידי הכפלת השערים (3 שערי AND ו-11 שערי XOR לפעימה) 64 פעמים, אפשר לבצע 64 איטרציות במקביל ולהפיק 64 סיביות זרם מפתח בפעימה אחת. התחשיב של מספר השערים הכולל מסתמך על ההנחה שדרושים 12 שערי NAND עבור פליפ פלופ אחד (יחידת זיכרון אחת) 2.5 שערי NAND עבור XOR אחד ו-1.5 שערי NAND עבור AND אחד. בסך הכול יוצא שבמימוש הרגיל נדרשים 3488 שערי NAND למימוש הצופן כולו ובגרסה המקבילית אפשר להגיע לתצורה שבה עם 5504 שערי NAND יופקו 64 סיביות פלט בבת אחת.

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

ביטחון

קיימת קריפטואנליזה של הצופן^[5] שמוצאת "מפתחות חלשים" שניתנים להבחנה בסיבוכיות מעשית לאחר כ-961 פעימות מתוך 1152.

ראו גם

הערות שוליים

^ Christophe De Cannière, Bart Preneel (2005-04-29). "Trivium specifications" (PDF). eSTREAM submitted papers. Retrieved 2006-10-09
^ Trivium
^ ISO/IEC 29192-3:2012
^ Dinur I., Shamir A. (2009) Cube Attacks on Tweakable Black Box Polynomials. In: Joux A. (eds) Advances in Cryptology - EUROCRYPT 2009. EUROCRYPT 2009. Lecture Notes in Computer Science, vol 5479. Springer, Berlin, Heidelberg
^ ¹ ² Knellwolf S., Meier W., Naya-Plasencia M. (2012) Conditional Differential Cryptanalysis of Trivium and KATAN. In: Miri A., Vaudenay S. (eds) Selected Areas in Cryptography. SAC 2011. Lecture Notes in Computer Science, vol 7118. Springer, Berlin, Heidelberg

[1] Christophe De Cannière, Bart Preneel (2005-04-29). "Trivium specifications" (PDF). eSTREAM submitted papers. Retrieved 2006-10-09

[2] Trivium

[3] ISO/IEC 29192-3:2012

[4] Dinur I., Shamir A. (2009) Cube Attacks on Tweakable Black Box Polynomials. In: Joux A. (eds) Advances in Cryptology - EUROCRYPT 2009. EUROCRYPT 2009. Lecture Notes in Computer Science, vol 5479. Springer, Berlin, Heidelberg

[התקפה_דיפרנציאלית-5] ¹ ² Knellwolf S., Meier W., Naya-Plasencia M. (2012) Conditional Differential Cryptanalysis of Trivium and KATAN. In: Miri A., Vaudenay S. (eds) Selected Areas in Cryptography. SAC 2011. Lecture Notes in Computer Science, vol 7118. Springer, Berlin, Heidelberg

[1]

[2]

[3]

[4]

[5]