MICKEY

שיטת ההיזון (feedback) המשתנה של צופן מיקי.

MICKEY הוא צופן זרם סינכרוני המיועד לפלטפורמת חומרה מוגבלת משאבים, שפותח ב-2006 על ידי סטיב באבג' מחברת וודאפון ומת'יו דוֹד. שם הצופן הוא ראשי התיבות של Mutual Irregular Clocking KEYstream, והוא מבוסס על אוגר זיזה ממושב (LFSR) שמבוקר בטכניקה ייחודית לאיזון בין הצורך במחזוריות גבוהה ופסאודו-אקראיות לבין הצורך בעמידות נגד קריפטואנליזה. הוא מספק רמה גבוהה יחסית של ביטחון לחומרה בעלת סיבוכיות נמוכה. גרסת MICKEY 2.0 נבחרה על ידי eSTREAM כצופן מועדף לשימוש יחד עם מבחר אלגוריתמים נוספים בקטגוריית חומרה. הצופן מקבל מפתח סודי בגודל 80 סיביות ווקטור אתחול בגודל של עד 80 סיביות ומייצר זרם פסאודו-אקראי באורך מרבי של $2^{40}$ סיביות, המשמש כמפתח להצפנת זרם הנתונים באמצעות XOR כבכל צופן זרם.

תיאור הצופן

הצופן מורכב משני אוגרי LFSR המסומנים ב-$R$ ו-$S$ כל אחד בגודל 100 סיביות הנקראות מצבים (states) שמסומנים בקיצור $r_{0},...,r_{99}$ וכן $s_{0},...,s_{99}$ בהתאמה. בכל פעימת שעון (clocking) כל הסיביות או המצבים מוסטים שלב אחד כלפי מטה (ימינה) והפוזיציות הבאות של האוגר $R$ משמשות להיזון חוזר (feedback):

${\text{RTAPS}}=\{0,1,3,4,5,6,9,12,13,16,19,20,21,22,25,28,37,38,41,42,45,46,50,52,54,56,58,$

$60,61,63,64,65,66,67,71,72,79,80,81,82,87,88,89,90,91,92,94,95,96,97\}$

CLOCK_R

פונקציית ההזנה של אוגר R בצופן MICKEY. במקרה שסיבית הבקרה CONTROL_BIT_R היא אפס מתבצעת הזזה (shift) של כל הסיביות פוזיציה אחת וכן מתבצע XOR של סיבית הקלט INPUT_BIT_R עם כל הסיביות בפוזיציות המופיעות ב-RTAPS. כאשר סיבית הבקרה היא אחד, בנוסף לאמור כל סיביות המצב מוזנות בחזרה עם XOR.

הפרוצדורה CLOCK_R (‎clocking מתייחס לעדכון האוגר בכל פעימת שעון) ייחודית בכך שהיא משתנה בהתאם לפרמטר. קלט הפונקציה הוא סיבית-קלט ${\text{INPUT}}\_{\text{BIT}}\_{\text{R}}$ וסיבית בקרה ${\text{CONTROL}}\_{\text{BIT}}\_{\text{R}}$, הסימן $\oplus$ הוא XOR והסיביות $r_{0}',...,r_{99}'$ מייצגות את מצבו החדש של האוגר לאחר העדכון.

בכל פעימה כאשר סיבית הבקרה מאופסת מתבצעת הזזה פוזיציה אחת והזנה (feedback) לפי הפוזיציות המנויות ב-RTAPS. המשמעות של ההזזה במונחים של אלגברה שהיא פועלת כמו כפל אלמנטים בשדה סופי מורחב $GF(2^{100})$ מודולו הפולינום הפרימיטיבי

$\textstyle C_{R}(x)=x^{100}+\sum _{i\in {\text{RTAPS}}}x^{i}$.

כי בעצם אפשר לראות במצבי האוגר כמקדמים בינאריים של פולינום כלשהו ממעלה 100 כאשר המצב השמאלי הוא המקדם המוביל. כאן הכפל הוא בין המצב הנוכחי של האוגר לפולינום $x$ או $p(x)=a_{1}x$ (היות שהמקדמים בינאריים זוהי מחרוזת שבה רק הסיבית השנייה משמאל דלוקה). פעולת כפל זו שקולה למעשה לפעולת ההזזה (shift) של כל סיביות האוגר ימינה. בנוסף מחברים ב-XOR את סיבית-הקלט ${\text{INPUT}}\_{\text{BIT}}\_{\text{R}}$ למצב הנוכחי.

כאשר סיבית הבקרה היא '1', לאחר ההזזה האמורה כל סיביות המצב מחוברת בחזרה ב-XOR (כמתואר בתרשים). במונחי אלגברה בשדה $GF(2^{100})$ פירוש הפעולה הוא כפל בפולינום $x+1$ (הזזה שקולה לכפל ו-XOR שקול לחיבור). הפולינום $C_{R}(x)$ נבחר כך שהוא מתחלק ב-$x^{J}+x+1$ כאשר $J=2^{50}-157$. קריאה לפונקציית ההיזון עם סיבית הבקרה הדינאמית דלוקה שקולה ל-$J$ הזזות. להלן ניסוח פורמלי של הפונקציה:

• ${\text{FEEDBACK}}\_{\text{BIT}}=r_{99}\oplus {\text{INPUT}}\_{\text{BIT}}\_{\text{R}}$
• ${\text{For }}i=1{\text{ to }}99{\text{ do: }}r_{i}'=r_{i-1}$
• $r_{0}'=0$
• ${\text{For each }}i\in {\text{RTAPS do:}}$

$r_{i}'=r_{i}'\oplus {\text{FEEDBACK}}\_{\text{BIT}}$

• ${\text{If CONTROL}}\_{\text{BIT}}\_{\text{R}}=1{\text{ then: }}$

${\text{For }}i=0{\text{ to }}99{\text{ do: }}r_{i}'=r_{i}'\oplus r_{i}$

האוגר S

תחילה מוגדרות ארבע מחרוזות ערכים קבועים: COMP0, COMP1, FB0, FB1 כל אחת באורך 100 סיביות (כמתואר בטבלה המצורפת). הפונקציה לעדכון האוגר $S$ מקבלת כקלט שתי סיביות ${\text{INPUT}}\_{\text{BIT}}\_{\text{S}}$ וכן ${\text{CONTROL}}\_{\text{BIT}}\_{\text{S}}$ ומפיקה ערכי ביניים ${\hat {s}}_{i}$ המשתנים בהתאם לסיבית הבקרה. התוצאה מומרת למערך סיביות הפלט $s_{0}',...,s_{99}'$. הסימן $\odot$ מייצג את הפעולה הלוגית AND. הפונקציה פועלת כדלהלן:

• ${\text{FEEDBACK}}\_{\text{BIT}}=s_{99}\oplus {\text{INPUT}}\_{\text{BIT}}\_{\text{S}}$
• ${\text{For }}i=1{\text{ to }}98{\text{ do: }}{\hat {s}}_{i}=s_{i-1}\oplus ((s_{i}\oplus {\text{ COMP0}}_{i})\odot (s_{i+1}\oplus {\text{ COMP1}}_{i}))$
• ${\hat {s}}_{0}=0,{\hat {s}}_{99}=s_{98}$
• ${\text{For }}i=0{\text{ to }}99{\text{ do: }}s_{i}'={\hat {s}}_{i}$
• ${\text{If FEEDBACK}}\_{\text{BIT}}=1{\text{ then:}}$

${\text{If CONTROL}}\_{\text{BIT}}\_{\text{S}}=0{\text{ then: }}{\text{For }}i=0{\text{ to }}99{\text{ do: }}s_{i}'={\hat {s}}_{i}\oplus {\text{FB0}}_{i}$

${\text{Else if CONTROL}}\_{\text{BIT}}\_{\text{S}}=1{\text{ then: }}{\text{For }}i=0{\text{ to }}99{\text{ do: }}s_{i}'={\hat {s}}_{i}\oplus {\text{FB1}}_{i}$

טבלת ערכי ההזנה של האוגר S בצופן MICKEY

הפרוצדורה CLOCK_KG

המחולל המייצר את זרם המפתח שנקרא keystream generator מוגדר כדלהלן; הקלט הוא שני האוגרים $S$ ו-$R$ וכן דגל אתחול שנקרא ${\text{MIXING}}$ ('1' מציין את שלב אתחול שבו רק מריצים את הצופן ומתעלים מהפלט ו'0' מציין שימוש רגיל) וסיבית קלט ${\text{INPUT}}\_{\text{BIT}}$. הפרמטר סיבית הבקרה של שתי הפונקציות לעיל מוגדרות כך:

${\text{CONTROL}}\_{\text{BIT}}\_{\text{R}}=s_{34}\oplus r_{67}$ וכן

${\text{CONTROL}}\_{\text{BIT}}\_{\text{S}}=s_{67}\oplus r_{33}$.

אם הדגל ${\text{MIXING}}={\text{TRUE}}$ סיבית הקלט של האוגר $R$ תהיה ${\text{INPUT}}\_{\text{BIT}}\_{\text{R}}={\text{INPUT}}\_{\text{BIT}}\oplus s_{50}$ אחרת תהיה ${\text{INPUT}}\_{\text{BIT}}$ עצמה. סיבית הקלט של האוגר $S$ היא ${\text{INPUT}}\_{\text{BIT}}$.

בכל פעימת שעון המחולל קורא לפונקציות הבאות להפקת סיבית מפתח אחת:

• ${\text{CLOCK}}\_{\text{R}}({\text{INPUT}}\_{\text{BIT}}\_{\text{R}},{\text{CONTROL}}\_{\text{BIT}}\_{\text{R}})$
• ${\text{CLOCK}}\_{\text{S}}({\text{INPUT}}\_{\text{BIT}}\_{\text{S}},{\text{CONTROL}}\_{\text{BIT}}\_{\text{S}})$

תוצאת המחולל היא XOR של שתי הסיביות במצבי האפס. כלומר $s_{0}\oplus r_{0}$.

טעינת מפתח

מפתח ההצפנה הסודי שמסופק על ידי המשתמש אינו נטען ישירות לאוגרים כדי למנוע התקפות מסוימות, אלא תחת זאת הטעינה מתבצעת באמצעות הפרוצדורה הבאה. המפתח המיוצג על ידי מחרוזת של 80 סיביות $k_{0},...,k_{79}$ ווקטור האתחול באורך $ivlength$ (עד 80 סיביות) ${\text{IV}}_{0},...,{\text{IV}}_{ivlength-1}$ נטענים למצב הראשוני של האוגרים כדלקמן: תחילה האוגרים מאופסים ואז, לטעינת וקטור האתחול מבצעים:

${\text{For }}i=0{\text{ to }}(ivlength-1){\text{ do: CLOCK}}\_{\text{KG}}(R,S,{\text{ TRUE }},{\text{IV}}_{i})$

לטעינת המפתח מבצעים:

${\text{For }}i=0{\text{ to }}79{\text{ do: CLOCK}}\_{\text{KG}}(R,S,{\text{ TRUE }},k_{i})$

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

${\text{For }}i=0{\text{ to }}99{\text{ do: CLOCK}}\_{\text{KG}}(R,S,{\text{ TRUE }},0)$

הצפנה ופענוח

שני המצבים התחתונים של האוגרים $R$ ו-$S$ בהתאמה, מחוברים ב-XOR ‏: $r_{0}\oplus s_{0}$ מהם מתקבלת סיבית פסאודו-ראנדומלית אחת המהווה חלק מזרם המפתח המשמש להצפנת המידע. הקריאה לפרוצדורה להפעלת הצופן במקרה זה מבוצעת עם הפרמטר ${\text{MIXING}}={\text{FALSE}}$ וסיבית קלט 0 כלומר עבור כל סיבית מידע $m_{i}$ מבצעים:

$c_{i}={\text{CLOCK}}\_{\text{KG}}(R,S,{\text{ FALSE }},0)\oplus m_{i}$

פענוח מתבצע באותה דרך בדיוק:

$m_{i}={\text{CLOCK}}\_{\text{KG}}(R,S,{\text{ FALSE }},0)\oplus c_{i}$

ביטחון

ב-2005 במהלך בדיקת הצופן על ידי eSTREAM התגלו שלוש חולשות בגרסה המקורית.

1. העובדה שהזיכרון הכולל הוא 160 סיביות שהוא המינימלי ביותר האפשרי (מינימום הזיכרון הדרוש כדי להבטיח את ביטחון הצופן מקובל שיהיה פי שנים מגודל המפתח), עדיין מתאפשרת התקפת איזון זמן/זיכרון/דטה שפורסמה לראשונה על ידי אלכס ביריוקוב ועדי שמיר.
2. למרות הצהרת המפתחים שמינימום מחזוריות הצופן היא $2^{40}$, האנטרופיה של המצב הפנימי (הזיכרון) נחלשת עם הזמן ככל שהצופן פועל.
3. המבקרים מציינים שגילו קבוצה קטנה של מפתחות הצפנה שנקראים 'מפתחות חלשים' במובן ששימוש בהם מאפשר לנחש את המצב הפנימי. בכל אופן המפתחים היו מודעים לעובדה זו אך למען שמירה על יעילות בחרו להתעלם מכך בטענה שהסבירות נמוכה מ-$2^{-80}$ שמפתח כזה ייבחר באקראי. אולם למעשה התגלה שהיא גבוהה במעט ממה שהעריכו. גרסת MICKEY 2 המתוארת כאן טובה יותר במובן שההתקפות המתוארות אינן יעילות כנגדה.

בשנת 2013 פותחה התקפה כנגד MICKEY 2.0 שהיא שיפור של התקפת Differential Fault Attack בקיצור DFA שיכולה לחשוף את המצב הפנימי כולו בשלב אתחול הצופן בתוך $2^{16.7}$ הזרקות ובתוך $2^{32.5}$ ניסיונות חישוב בממוצע. ההתקפה מבוססת על יכולת התוקף לגרום לסיביות שגויות אקראיות במצב פנימי של הצופן והיא מנצלת את העובדה שפונקציית הפלט וכן פעולות עדכון מסוימות פשוטות מדי. ייתכן שאפשר לשפר את ביטחון הצופן על ידי כמה התאמות. לדעת מחברי ההתקפה היא ישימה כנגד כל הצפנים שנבחרו על ידי eSTREAM בקטגוריית חומרה.

ראו גם

• צופן זרם