MICKEY

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

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

<div class="mw-content-ltr">
:<math>\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,</math>
::::::<math>60,61,63,64,65,66,67,71,72,79,80,81,82,87,88,89,90,91,92,94,95,96,97\}</math>
</div>

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

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

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

:<math>\textstyle C_R(x)=x^{100}+\sum_{i\in \text{RTAPS}} x^i</math>.

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

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

<div class="mw-content-ltr">
*<math>\text{FEEDBACK}\_\text{BIT}=r_{99}\oplus \text{INPUT}\_\text{BIT}\_\text{R}</math>
*<math>\text{For }i=1\text{ to }99\text{ do: } r_i'=r_{i-1}</math>
*<math>r_0'=0</math>
*<math>\text{For each }i\in \text{RTAPS do:}</math>
::<math>r_i'=r_i' \oplus \text{FEEDBACK}\_\text{BIT}</math>
*<math>\text{If CONTROL}\_\text{BIT}\_\text{R}=1\text{ then: }</math>
::<math>\text{For }i=0\text{ to }99\text{ do: } r_i'=r_i'\oplus r_i</math>
</div>

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

<div class="mw-content-ltr">
*<math>\text{FEEDBACK}\_\text{BIT}=s_{99}\oplus \text{INPUT}\_\text{BIT}\_\text{S}</math>
*<math>\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))</math>
*<math>\hat s_0=0,\hat s_{99}=s_{98}</math>
*<math>\text{For }i=0\text{ to }99\text{ do: }s_i'=\hat s_i</math>
*<math>\text{If FEEDBACK}\_\text{BIT}=1\text{ then:}</math>
::<math>\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</math>
::<math>\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</math>
</div>

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

===הפרוצדורה CLOCK_KG===
המחולל המייצר את זרם המפתח שנקרא keystream generator מוגדר כדלהלן; הקלט הוא שני האוגרים <math>S</math> ו-<math>R</math> וכן דגל אתחול שנקרא <math>\text{MIXING}</math> ('1' מציין את שלב אתחול שבו רק מריצים את הצופן ומתעלים מהפלט ו'0' מציין שימוש רגיל) וסיבית קלט <math>\text{INPUT}\_\text{BIT}</math>. הפרמטר סיבית הבקרה של שתי הפונקציות לעיל מוגדרות כך:
:<math>\text{CONTROL}\_\text{BIT}\_\text{R}=s_{34}\oplus r_{67}</math> וכן
:<math>\text{CONTROL}\_\text{BIT}\_\text{S}=s_{67}\oplus r_{33}</math>.

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

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

<div class="mw-content-ltr">
*<math>\text{CLOCK}\_\text{R}(\text{INPUT}\_\text{BIT}\_\text{R}, \text{CONTROL}\_\text{BIT}\_\text{R})</math>
*<math>\text{CLOCK}\_\text{S}(\text{INPUT}\_\text{BIT}\_\text{S}, \text{CONTROL}\_\text{BIT}\_\text{S})</math>
</div>

תוצאת המחולל היא XOR של שתי הסיביות במצבי האפס. כלומר <math>s_0\oplus r_0</math>.

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

<div class="mw-content-ltr">
:<math>\text{For }i=0\text{ to }(ivlength-1)\text{ do: CLOCK}\_\text{KG}(R,S,\text{ TRUE },\text{IV}_i)</math></div>

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

<div class="mw-content-ltr">
:<math>\text{For }i=0\text{ to }79\text{ do: CLOCK}\_\text{KG}(R,S,\text{ TRUE },k_i)</math></div>

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

<div class="mw-content-ltr">
:<math>\text{For }i=0\text{ to }99\text{ do: CLOCK}\_\text{KG}(R,S,\text{ TRUE },0)</math></div>

===הצפנה ופענוח===
שני המצבים התחתונים של האוגרים <math>R</math> ו-<math>S</math> בהתאמה, מחוברים ב-XOR : <math>r_0 \oplus s_0</math> מהם מתקבלת סיבית פסאודו-ראנדומלית אחת המהווה חלק מזרם המפתח המשמש להצפנת המידע. הקריאה לפרוצדורה להפעלת הצופן במקרה זה מבוצעת עם הפרמטר <math>\text{MIXING}=\text{FALSE} </math> וסיבית קלט 0 כלומר עבור כל סיבית מידע <math>m_i</math> מבצעים:

:<math>c_i=\text{CLOCK}\_\text{KG}(R,S,\text{ FALSE },0)\oplus m_i</math>

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

:<math>m_i=\text{CLOCK}\_\text{KG}(R,S,\text{ FALSE },0)\oplus c_i</math>

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

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

==ראו גם==
* צופן זרם

==הערות שוליים==

קטגוריה:צפני זרם