MISTY (צופן)

**MISTY** היא משפחה של צפני בלוקים שפותחו על ידי מיצורו מצואי (Mitsuru Matsui) ועמיתיו מתאגיד מיצובישי יפן. הגרסה הראשונה MISTY פותחה ב-1996 והוצעה לפרויקט NESSIE האירופאי ונכללה בשנת 2003 ברשימה המומלצת של הפרויקט. גרסה אחרת של הצופן הנקראת KASUMI פותחה ב-1999 במיוחד עבור תקן 3GPP לתקשורת סלולרית מסוג GSM, GPRS והדור השלישי UMTS להגנה על פרטיות ואימות שיחה סלולרית.

MISTY הוא צופן בלוקים בסגנון רשת פייסטל רקורסיבית המותאם במיוחד לחומרה. הקלט שלו הוא בלוק טקסט קריא באורך 64 סיביות ומפתח סודי באורך 128 סיביות והפלט הוא טקסט מוצפן באורך 64 סיביות. מספר הסבבים בהגדרה יכול להשתנות, אך מקובל בדרך כלל שמונה סבבים. הבסיס התאורטי של הצופן נשען על נוסחה מתמטית המאפשרת הוכחת עמידות נגד קריפטואנליזה דיפרנציאלית וליניארית. ברמה העליונה הצופן כולל שמונה סבבים של פונקציה אי-ליניארית בולאנית שהיא עצמה מורכבת מ"סולם" דמוי רשת פייסטל בשלושה סבבים של פונקציה פנימית אחרת (כמתואר בתרשימים). באותו סגנון הפונקציה הפנימית בתורה מורכבת גם היא ממספר סבבים של החלפה תוך שימוש בשתי תיבות החלפה **S7** ו-**S9** המורכבות מטבלה של 7\times 7 סיביות וטבלה של 9\times 9 סיביות בהתאמה.

שם הצופן יכול להתפרש כראשי התיבות "**M**itsubishi **I**mproved **S**ecurity **T**echnolog**Y**" או האותיות הראשונות של שמות צוות הפיתוח Matsui Mitsuru, Ichikawa Tetsuya, Sorimachi Toru, Tokita Toshio, Yamagishi Atsuhiro.

## גרסאות
400px|ממוזער|מרכז|תרשים סכמטי של צופן MISTY-1 וצופן MISTY-2. ההבדל ביניהם שהימני מאפשר הפעלה מקבילית ולכן ביישום ממוטב יכול להיות מהיר פי שניים מהשמאלי.
בתחילה פותחו הגרסאות MISTY1 ו-MISTY2 שההבדל ביניהן הוא בעיקר ש-MISTY2 מאפשרת הפעלה מקבילית של הפונקציה הפנימית בעוד ש-MISTY1 איננה מקבילית. ב-2005 פותחה הגרסה KASUMI שהיא חלק מ-A5/3, תקן תקשורת מאובטחת לרשתות סלולריות מהדור השלישי שמחליף את האלגוריתמים A5/1 ו-A5/2. ב-1998 פורסם צופן E2 שהיה מועמד ל-AES ובשנת 2000 פותח על בסיס דומה צופן קמליה שנחשב לבטוח ברמה של AES ונכלל בתקנים רבים וב-SSL.

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

כל הגרסאות של הצופן רשומות כפטנט על ידי NTT ומיצובישי אלקטרוניקה, חלקן הותרו לשימוש תחת רישיונות FreeBSD או לשימוש אקדמי/שלא למטרות רווח.

## ביטחון
לפי הצהרת מיצואי, הצופן הוכח בטוח נגד התקפה דיפרנציאלית/ליניארית וכן נגד התקפות מודרניות נוספות. בשמונה סבבים הסיבוכיות הדיפרנציאלית והליניארית שלו הן בסדר גודל של 2^{-140}  בהשוואה ל-DES שהן 2^{-62} ו-2^{-46} בהתאמה. MISTY1 נחקר במשך שנים רבות מאז הוצע לראשונה ולא נמצאו בו פגמים רציניים. ההתקפה הטובה יותר הידועה היא "התקפה אינטגרלית" של קנודסן ווגנר מ-2002 נגד גרסה מצומצמת של הצופן בחמשה סבבים, בסיבוכיות של 2^{48} ובסיבוכיות מקום של 2^{34}. אותה התקפה נגד MISTY2 בשישה סבבים אפשרית בסיבוכיות של 2^{71} ומקום בסדר גודל של 2^{34}. נגד KASUMI התגלו מספר התקפות, חלקן תאורטיות כלומר בסיבוכיות טובה מכוח גס (2^{100} עם 2^{28}) וחלקן מעשיות כמו התקפת Related-key של אור דונקלמן, נתן קלר ועדי שמיר משנת 2010 שהיא בסיבוכיות של 2^{32} ומקום בסדר גודל של 2^{30} עם 4 מפתחות קשורים. ראוי לציין שההתקפה האחרונה אינה ישימה נגד MISTY1, כמו כן היא מסתמכת על כמות נכבדה של טקסט מוצפן בשילוב עם מפתחות קשורים, לכן ייתכן שהיא אינה אפשרית נגד יישום A5/3 בגרסה הנוכחית, אך יש להביא בחשבון את האיום. על כל פנים ההתקפה מוכיחה שהשינויים שנעשו על ידי המפתחים במעבר מ-MISTY ל-KASUMI כדי לשפר ביצועים בחומרה למעשה החלישו את ביטחון הצופן משמעותית. מסיבה זו הוחלט על מעבר לצופן חזק יותר SNOW 3G.

## תיאור הצופן
בפיתוח הצופן הושם דגש בעיקר על יישום יעיל, במיוחד בחומרה. הפעולות הנפוצות בצופן בלוקים מתחלקות לארבע קטגוריות עיקריות; פעולות אריתמטיות, פעולות הזזה (Shift), פעולות לוגיות (כמו XOR) וטבלאות החלפה (S-box). מתוכן שתי הפעולות האחרונות עדיפות מהיבט של חומרה ולכן נבחרו. האסטרטגיה הבסיסית בפיתוח הצופן הייתה בנייה מלמטה למעלה, מהמרכיבים הקטנים לגדולים בצורה רקורסיבית, כך שיהיה קל להעריך את ביטחון ההצפנה במונחים של הסתברות דיפרנציאלית/ליניארית.

כמו ברשת פייסטל טיפוסית, הקלט P באורך 64 סיביות מחולק לשני חצאים בגודל 32 סיביות כל אחד, והפונקציה הפנימית מופעלת על המחצית האחת והפלט שלה משמש כמפתח הצפנה להצפנת המחצית השנייה, תוך שימוש בפעולות XOR ועם שתי תת-שגרות FO ו-FL. פלט הצופן C הוא באורך 64 סיביות. בפונקציה FO מחלקים את הקלט שוב לשני חצאים באורך 16 סיביות, כל אחד מהווה קלט לפונקציה קטנה יותר הנקראת FI המשתמשת בתיבות ההחלפה (להלן), היות ש-16 סיביות הן ערן גדול מדי, מחלקים שוב את הקלט הפעם לשני חלקים לא שווים, 9 סיביות ו-7 סיביות בהתאמה אותם מחליפים לפי תיבות ההחלפה בהתאמה. הסיבה לחלוקה לא מאוזנת זו נובעת מהעובדה שתיבות החלפה המייצגות פונקציה חד-חד-ערכית ועל אי-ליניארית, טובות יותר באורך אי זוגי מהיבט של קריפטואנליזה דיפרנציאלית/ליניארית, אולם מאידך חסרונן הוא בהפחתה ביעילות יישום הן בחומרה והן בתוכנה. לפי בדיקות שנעשו על מחשב פנטיום מהירות ההצפנה הייתה 20Mbps בקירוב, על חומרה המהירויות הן 450Mbps בקירוב. מבנה MISTY2 מאפשר הפעלה מקבילית ולכן מהיר פי שניים בהצפנה, אך לא בפענוח כי הפונקציה ההופכית לא ניתנת להפעלה מקבילית, מסיבה זו MISTY2 עדיף ליישום במצבי הפעלה OFB או CFB הפועלים כצופן זרם בהם נדרשת רק פונקציית ההצפנה.

### תיבות החלפה
תיבות ההחלפה הן למעשה חזקות מעל שדה סופי. התיבות חושבו כך שההסתברות הדיפרנציאלית/ליניארית הממוצעת תהיה מינימלית וכן שיהיו ממעלה גבוהה ככל האפשר ושיהיה להן עיכוב מינימלי בביצוע בחומרה. החיפוש התמקד בפונקציות ליניאריות מהצורה S_i(x)=A \circ x^{\alpha} \ (i=7,9). הטבלה **S7** כוללת אוסף של 7 פונקציות ממעלה 10 מהצורה A\circ x^{\alpha} מעל השדה GF(2^7) בבסיס פולינומי, כאשר \text{GCD}(2^7-1,\alpha)=1. באותה דרך הטבלה **S9** כוללת אוסף של 9 פונקציות ממעלה לכל היותר 13 מעל השדה GF(2^9). אפשר להפעיל את ההחלפה ישירות באמצעות הפונקציות האמורות ללא שימוש בזיכרון (כאשר החומרה מוגבלת משאבים) או שאפשר להמירן לטבלאות חיפוש אם הזיכרון זמין. להלן הטבלאות S7 ו-S9:





### הכנת מפתח
בהינתן המפתח הסודי המסופק על ידי המשתמש באורך 128 סיביות, מרחיבים אותו ל-256 סיביות באמצעות הזזה מעגלית וחיבור XOR עם פונקציה ליניארית. השימוש בו הוא באופן שכל סבב מושפע מכל סיביות המפתח ומחלק גדול של המפתח המורחב. ההגבלה ל-256 סיביות נובעת בשל הצורך בהתחשבות בחומרה מוגבלת משאבים כמו כרטיס חכם. הרחבת המפתח נעשית באופן הבא:


:\text{For }i=0\text{ to }7\text{ do: }
::EK[i]=K[i\cdot 2]\cdot 256 + K[i\cdot 2 + 1]
:\text{For }i=0\text{ to }7\text{ do: }
::EK[i+8]=\mathbf{FI}(EK[i],EK[(i+1)\text{ mod }8]
::EK[i+16]=EK[i+8] \land \text{0x1FF}
::EK[i+24]=EK[i+8] \gg 9


450px|מרכז|ממוזער|תהליך הרחבת המפתח של MISTY

## הצפנה ופענוח
הפונקציה FO מקבלת שני פרמטרים, קלט באורך 32 סיביות FO_IN ואינדקס k לחלק המתאים במפתח המורחב EK ומחזירה את FO_OUT כדלהלן:


:\mathbf{FO}(\mathbf{FO\_IN}, \mathbf{k})
::t_0 = FO\_IN \gg 16
::t_1 = FO\_IN \land \text{0xFFFF}
::t_0 = t_0 \oplus EK[k]
::t_0 = \mathbf{FI}(t_0, EK[(k+5)\text{ mod }8 + 8])
::t_0 = t_0 \oplus t_1
::t_1 = t_1 \oplus EK[(k+2)\text{ mod }8]
::t_1 = \mathbf{FI}(t_1, EK[(k+1)\text{ mod }8+8])
::t_1 = t_1 \oplus t_0
::t_0 = t_0 \oplus EK[(k+7)\text{ mod }8]
::t_0 = \mathbf{FI}(t_0, EK[(k+3)\text{ mod }8+8])
::t_0 = t_0 \oplus t_1
::t_1 = t_1 \oplus EK[(k+4)\text{ mod }8]
::FO\_OUT = (t_1\ll 16) \lor t_0
::\text{Return }FO\_OUT


560px|ממוזער|מרכז|הפונקציות הפנימיות של MISTY

הפונקציה FI מקבלת שני פרמטרים; קלט באורך 16 סיביות F_IN וחלק מהמפתח המורחב FI_KEY ומחזירה פלט באורך 16 סיביות FI_OUT. הפונקציה משתמשת בשני משתני עזר מקומיים d_7 באורך 7 סיביות ו-d_9 באורך 9 סיביות וכן מנצלת את תיבות ההחלפה המתוארות לעיל. בגלל האורך השונה של המשתנים d_7 ו-d_9 יש צורך להפעיל פונקציה כלשהי שמרחיבה או מכווצת את המשתנה בהתאם לפני שמבצעים XOR. הרחבה נעשית על ידי הוספת שני אפסים משמאל (בצד המשמעותי של המספר) וכיווץ נעשה על ידי חיתוך שתי הסיביות המשמעותיות.


:\mathbf{FI}(\mathbf{FI\_IN, FI\_KEY})
::d_9 = FI\_IN \gg 7
::d_7 = FI\_IN \land \text{0x7F}
::d_9 = \text{S9TABLE}[d_9] \oplus d_7
::d_7 = \text{S7TABLE}[d_7] \oplus d_9
::( d_7 = d_7 \land \text{0x7F} )
::d_7 = d_7 \oplus (FI\_KEY \gg 9)
::d_9 = d_9 \oplus (FI\_KEY \land \text{0x1FF})
::d_9 = \text{S9TABLE}[d_9] \oplus d_7
::FI\_OUT = (d_7 \ll 9) \lor d_9
::\text{Return }FI\_OUT


הפונקציה FL מקבלת שני פרמטרים; קלט באורך 32 סיביות FL_IN ואינדקס k לחלק המתאים במפתח המורחב ומחזירה את FL_OUT באורך 32 סיביות.


:\mathbf{FL}(\mathbf{FL\_IN, k})
::d_0 = FL\_IN \gg 16
::d_1 = FL\_IN \land \text{0xFFFF}
::\text{If k is even then: }
:::d_1 = d_1 \oplus (d_0 \land EK[k/2])
:::d_0 = d_0 \oplus (d_1 \lor EK[(k/2+6)\text{ mod }8+8])
::\text{Else}
:::d_1 = d_1 \oplus (d_0 \land EK[((k-1)/2+2)\text{ mod }8+8])
:::d_0 = d_0 \oplus (d_1 \lor EK[((k-1)/2+4)\text{ mod }8])
::FL\_OUT = (d_0\ll 16) \lor d_1
::\text{Return }FL\_OUT


במצבי הפעלה ECB ו-CBC בפענוח צריך להשתמש בפונקציה ההופכית FLINV הבאה:


:\mathbf{FLINV}(\mathbf{FL\_IN, k})
::d_0 = FL\_IN \gg 16
::d_1 = FL\_IN \land \text{0xFFFF}
::\text{If k is even then: }
:::d_0 = d_0 \oplus (d_1 \lor EK[(k/2+6)\text{ mod }8+8])
:::d_1 = d_1 \oplus (d_0 \land EK[k/2])
::\text{Else}
:::d_0 = d_0 \oplus (d_1 \lor EK[((k-1)/2+4)\text{ mod }8])
:::d_1 = d_1 \oplus (d_0 \land EK[((k-1)/2+2)\text{ mod }8+8])
::FL\_OUT = (d_0\ll 16) \lor d_1
::\text{Return }FL\_OUT


באופן רגיל התהליך האמור מבוצע שמונה פעמים. בכל סבב מתבצעת הקריאה לפונקציה FO. בנוסף בכל סבב זוגי מתבצעת קריאה לפונקציה FL. לאחר הסבב האחרון מתבצעת קריאה נוספת לפונקציה FL. לצורך המחשה אם הקלט חולק לשני חצאים R ו-L בהתאמה, שמונה הסבבים של הצופן נראים כך:

## ראו גם
* GSM
* KASUMI

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

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