MISTY (צופן)

MISTY היא משפחה של צפני בלוקים שפותחו על ידי מיצורו מצואי (Mitsuru Matsui) ועמיתיו מתאגיד מיצובישי יפן. הגרסה הראשונה MISTY פותחה ב-1996 והוצעה לפרויקט NESSIE האירופאי ונכללה בשנת 2003 ברשימה המומלצת של הפרויקט. גרסה אחרת של הצופן הנקראת KASUMI פותחה ב-1999 במיוחד עבור תקן 3GPP לתקשורת סלולרית מסוג GSM, GPRS והדור השלישי UMTS להגנה על פרטיות ואימות שיחה סלולרית. 
MISTY הוא צופן בלוקים בסגנון רשת פייסטל רקורסיבית המותאם במיוחד לחומרה. הקלט שלו הוא בלוק טקסט קריא באורך 64 סיביות ומפתח סודי באורך 128 סיביות והפלט הוא טקסט מוצפן באורך 64 סיביות. מספר הסבבים בהגדרה יכול להשתנות, אך מקובל בדרך כלל שמונה סבבים. הבסיס התאורטי של הצופן נשען על נוסחה מתמטית המאפשרת הוכחת עמידות נגד קריפטואנליזה דיפרנציאלית וליניארית. ברמה העליונה הצופן כולל שמונה סבבים של פונקציה אי-ליניארית בולאנית שהיא עצמה מורכבת מ"סולם" דמוי רשת פייסטל בשלושה סבבים של פונקציה פנימית אחרת  (כמתואר בתרשימים). באותו סגנון הפונקציה הפנימית בתורה מורכבת גם היא ממספר סבבים של החלפה תוך שימוש בשתי תיבות החלפה S7 ו-S9 המורכבות מטבלה של  סיביות וטבלה של  סיביות בהתאמה. 
שם הצופן יכול להתפרש כראשי התיבות "Mitsubishi Improved Security TechnologY" או האותיות הראשונות של שמות צוות הפיתוח Matsui Mitsuru, Ichikawa Tetsuya, Sorimachi Toru, Tokita Toshio, Yamagishi Atsuhiro.

גרסאות

בתחילה פותחו הגרסאות 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 או לשימוש אקדמי/שלא למטרות רווח.

ביטחון

לפי הצהרת מיצואי, הצופן הוכח בטוח נגד התקפה דיפרנציאלית/ליניארית וכן נגד התקפות מודרניות נוספות. בשמונה סבבים הסיבוכיות הדיפרנציאלית והליניארית שלו הן בסדר גודל של  בהשוואה ל-DES שהן  ו- בהתאמה. MISTY1 נחקר במשך שנים רבות מאז הוצע לראשונה ולא נמצאו בו פגמים רציניים. ההתקפה הטובה יותר הידועה היא "התקפה אינטגרלית" של קנודסן ווגנר מ-2002 נגד גרסה מצומצמת של הצופן בחמשה סבבים, בסיבוכיות של  ובסיבוכיות מקום של . אותה התקפה נגד MISTY2 בשישה סבבים אפשרית בסיבוכיות של  ומקום בסדר גודל של . נגד KASUMI התגלו מספר התקפות חלקן תאורטיות כלומר בסיבוכיות טובה מכוח גס ( עם ) וחלקן מעשיות כמו התקפת Related-key של אור דונקלמן, נתן קלר ועדי שמיר משנת 2010 שהיא בסיבוכיות של  ומקום בסדר גודל של  עם 4 מפתחות קשורים. ראוי לציין שההתקפה האחרונה אינה ישימה נגד MISTY1, כמו כן היא מסתמכת על כמות נכבדה של טקסט מוצפן בשילוב עם מפתחות קשורים, לכן ייתכן שהיא אינה אפשרית נגד יישום A5/3 בגרסה הנוכחית, אך יש להביא בחשבון את האיום. על כל פנים ההתקפה מוכיחה שהשינויים שנעשו על ידי המפתחים במעבר מ-MISTY ל-KASUMI כדי לשפר ביצועים בחומרה למעשה החלישו את ביטחון הצופן משמעותית. מסיבה זו הוחלט על מעבר לצופן חזק יותר SNOW 3G.

תיאור הצופן

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