KASUMI
KASUMI[1] הוא צופן בלוקים שפותח ב-1999 על ידי 3GPP כתקן לאבטחת שיחה סלולרית מהדור השלישי בטכנולוגיות UMTS, GSM ו-GPRS. ב-UMTS, הצופן משמש בשני רבדים: באלגוריתם f8 להגנה על פרטיות שיחה סלולרית ובאלגוריתם f9 לאימות והבטחת שלמות השיחה. ב-GSM/GPRS הצופן מהווה חלק אינטגרלי מאלגוריתם A5/3 בתור מחולל זרם מפתח שנקרא KGCORE שהוא מצב הפעלה OFB.
צופן KASUMI פותח על ידי SAGE שהוא חלק מגוף התקינה האירופאי ETSI. בשל לוח זמנים לחוץ הוחלט בעצה אחת עם TGS (הצוות הטכני של 3GPP) להסתמך על אלגוריתם קיים במקום לפתח אלגוריתם חדש והצופן MISTY1 של מיצובישי נבחר כבסיס. כדי להתאימו לחומרה בוצעו מספר שינויים וניתן לו השם KASUMI שהוא תרגום mist (ערפל) ליפנית.
ביטחון
עריכההיתרון של KASUMI הוא שהוא מבוסס על צופן MISTY1 שפותח על בסיס תאורטי שלטענת המפתחים מספק ביטחון מוכח נגד קריפטואנליזה דיפרנציאלית וליניארית וכן שהוא ממוטב במיוחד לחומרה.
ב-2001 פורסמה התקפה תאורטית טובה מכוח גס שנקראת התקפת דיפרנציאלים בלתי אפשריים[2] נגד גרסה מצומצמת של MISTY הישימה גם נגד KASUMI, בשישה סבבים בסיבוכיות זמן של ומקום בסדר גודל של .
התקפה יותר מעשית פורסמה על ידי Teruo Saito[3] גם כן בשישה סבבים בזמן של ועם טקסטים. יש לזכור שב-KASUMI שמונה סבבים. ב-2005 פרסמו אור דונקלמן, אלי ביהם ונתן קלר מהטכניון התקפת מפתחות קשורים (related key) בשילוב עם התקפת בומרנג (סוג של התקפה דיפרנציאלית) נגד KASUMI שמסוגלת לשבור את הצופן בגרסה המלאה עם הצפנות ועם כמות של טקסטים נבחרים שהוצפנו עם 4 מפתחות קשורים. למרות שההתקפה תאורטית, היא סותרת את טענת המפתחים לגבי הוכחת ביטחון האלגוריתם. ב-2010 הציגו אותם חוקרים התקפה[4] משופרת בהרבה שהייתה מספיק פרקטית עד שהצליחו להמחישה על מחשב ביתי בזמן של מספר שעות, אפילו עם גרסה לא ממוטבת של הצופן. למרות זאת החוקרים ציינו שההתקפה אינה מעשית נגד אלגוריתם A5/3 שבשימוש GSM בשל אופן מימושו. על כל פנים ההתקפה אינה אפשרית נגד MISTY, מה שמוכיח כי השינויים שביצעו מפתחי KASUMI השפיעו לרעה על ביטחון הצופן וזאת בניגוד לטענתם.
תיאור הצופן
עריכהKASUMI הוא צופן בלוקים בסגנון רשת פייסטל בשמונה סבבים. הקלט הוא בלוק דטה באורך 64 סיביות ומפתח הצפנה סודי באורך 128 סיביות והפלט הוא בלוק מוצפן באורך 64 סיביות. הצופן בנוי בצורה רקורסיבית.
- הפונקציה מבצעת כדלהלן:
- 1. תחילה בלוק הקלט מחולק לשני חצאים באורך 32 סיביות כל אחד.
- 2. מפעילים את פונקציית הסבב על חצי השמאלי ומחליפים מקומות עם החצי הימני שמונה פעמים. דהיינו עבור מבצעים:
- 3. הפלט הוא .
הוא החלק המפתח המתאים לסבב (לפי הטבלה המופיעה להלן). הסמל מייצג שרשור והסמל מייצג XOR.
פונקציית הסבב
עריכההפונקציה הראשית מקבלת קלט באורך 32 סיביות וקטע מתאים מהמפתח המורחב (להלן) שנקרא "מפתח הסבב" ומחזירה את הפלט . מפתח הסבב מורכב משלושה תת-מפתחות הראשון באורך 32 סיביות ושני האחרים באורך 48 סיביות כל אחד. והיא משתמשת בשתי תת-שגרות ו- . כשהמפתח מועבר לפונקציה והמפתחות מועברים לפונקציה .
פונקציית הסבב הראשית מופיעה בשתי צורות בהתאם לסבב זוגי או אי זוגי. עבור סבב זוגי היא בנויה כך:
בסבב אי זוגי כך:
כלומר בסבב זוגי הפונקציה מופעלת לאחר הפונקציה (כלומר הפלט של הופך לקלט של ) ובסבב אי זוגי ההפך.
הפונקציה FL
עריכהבהינתן הקלט באורך 32 סיביות ותת-מפתח גם הוא באורך 32 סיביות, הפונקציה מחלקת תחילה את תת-המפתח לשני חצאים באורך 16 סיביות כל אחד, כך שמתקיים ואת הקלט לשני חצאים כך שמתקיים ומבצעת:
והפלט הוא . הפונקציה היא הזזה מעגלית לשמאל סיבית אחת. הסמל מייצג AND והסמל מייצג OR.
הפונקציה FO
עריכהבהינתן קלט באורך 32 סיביות ושני תת-מפתחות באורך 48 סיביות כל אחד, הפונקציה מחלקת תחילה את הקלט לשני חצאים ואת שני תת-המפתחות לשישה חלקים באורך 16 סיביות כל אחד בהתאמה ומבצעת שלוש פעמים, עבור :
והפלט הוא .
הפונקציה FI
עריכהבהינתן הקלט באורך 16 סיביות ותת-מפתח הפונקציה מחלקת תחילה את הקלט לשני חלקים לא שווים באורכם, באורך 9 סיביות ו- באורך 7 סיביות, באותו אופן מחלקת את תת-המפתח לשני חלקים באורך 9 סיביות והחלק באורך 7 סיביות ומבצעת:
|
|
![{\displaystyle L_{1}=R_{0},R_{1}=S9[L_{0}]\oplus ZE(R_{0})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e53efeebf8c9649e76907acddffc6f8f0bce11a)
![{\displaystyle L_{2}=R_{1}\oplus KI_{i,j,2},R_{2}=S7[L_{1}]\oplus TR(R_{1})\oplus KI_{i,j,1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3dc10b5cb3147b19c491583cac117f7921a7d2ca)
![{\displaystyle L_{3}=R_{2},R_{3}=S9[L_{2}]\oplus ZE(R_{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7ada30a8e1a466d0ab65a5a50bfd1e0ed0d0df9)
![{\displaystyle L_{4}=S7[L_{3}]\oplus TR(R_{3}),R_{4}=R_{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fec1d417fcd24cd4b6057f6376c4495617575e85)
והפלט הוא . כאשר הפונקציות ו- קיצור של ZeroExtend ו-Truncate בהתאמה הן פונקציות שנועדו להמיר את הערך מ-7 סיביות ל-9 סיביות וההפך. ההרחבה מתבצעת על ידי הוספת אפסים משמאל (בצד המשמעותי של המספר) והחיתוך מתבצע על ידי הסרת שתי הסיביות המשמעותיות של המספר.
תיבות החלפה
עריכהלצופן נילוות שתי תיבות החלפה בסיביות שנקראות S7 ו-S9 והן עוצבו כך שניתן יהיה לממשן בשני אופנים. קומבינציה לוגית וטבלת אחזור (lookup table) בהתאם לסיטואציה. למשל בחומרה מוגבלת בזיכרון הגישה הראשונה עדיפה. טבלאות חיפוש מהירות יותר והן עדיפות כאשר הזיכרון זמין. בגישה הלוגית ההחלפה מתבצעת על ידי קומבינציה של השערים הלוגיים AND ו-XOR. להלן שתי תיבות ההחלפה בשני האופנים האמורים. הערך בייצוג בינארי הוא מחרוזת של 7 סיביות (או 9 בטבלה הבאה) המיוצגות על ידי (הביטוי פירושו ):
|
|
טבלת החלפה S7 עם ערכים עשרוניים:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 54, 50, 62, 56, 22, 34, 94, 96, 38, 6, 63, 93, 2, 18,123, 33,
1 55,113, 39,114, 21, 67, 65, 12, 47, 73, 46, 27, 25,111,124, 81,
2 53, 9,121, 79, 52, 60, 58, 48,101,127, 40,120,104, 70, 71, 43,
3 20,122, 72, 61, 23,109, 13,100, 77, 1, 16, 7, 82, 10,105, 98,
4 117,116, 76, 11, 89,106, 0,125,118, 99, 86, 69, 30, 57,126, 87,
5 112, 51, 17, 5, 95, 14, 90, 84, 91, 8, 35,103, 32, 97, 28, 66,
6 102, 31, 26, 45, 75, 4, 85, 92, 37, 74, 80, 49, 68, 29,115, 44,
7 64,107,108, 24,110, 83, 36, 78, 42, 19, 15, 41, 88,119, 59, 3
|
השערים הלוגיים של S9:
|
|
טבלת ההחלפה S9 עם ערכים עשרוניים:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
00 167,239,161,379,391,334, 9,338, 38,226, 48,358,452,385, 90,397,
01 183,253,147,331,415,340, 51,362,306,500,262, 82,216,159,356,177,
02 175,241,489, 37,206, 17, 0,333, 44,254,378, 58,143,220, 81,400,
03 95, 3,315,245, 54,235,218,405,472,264,172,494,371,290,399, 76,
04 165,197,395,121,257,480,423,212,240, 28,462,176,406,507,288,223,
05 501,407,249,265, 89,186,221,428,164, 74,440,196,458,421,350,163,
06 232,158,134,354, 13,250,491,142,191, 69,193,425,152,227,366,135,
07 344,300,276,242,437,320,113,278, 11,243, 87,317, 36, 93,496, 27,
08 487,446,482, 41, 68,156,457,131,326,403,339, 20, 39,115,442,124,
09 475,384,508, 53,112,170,479,151,126,169, 73,268,279,321,168,364,
10 363,292, 46,499,393,327,324, 24,456,267,157,460,488,426,309,229,
11 439,506,208,271,349,401,434,236, 16,209,359, 52, 56,120,199,277,
12 465,416,252,287,246, 6, 83,305,420,345,153,502, 65, 61,244,282,
13 173,222,418, 67,386,368,261,101,476,291,195,430, 49, 79,166,330,
14 280,383,373,128,382,408,155,495,367,388,274,107,459,417, 62,454,
15 132,225,203,316,234, 14,301, 91,503,286,424,211,347,307,140,374,
16 35,103,125,427, 19,214,453,146,498,314,444,230,256,329,198,285,
17 50,116, 78,410, 10,205,510,171,231, 45,139,467, 29, 86,505, 32,
18 72, 26,342,150,313,490,431,238,411,325,149,473, 40,119,174,355,
19 185,233,389, 71,448,273,372, 55,110,178,322, 12,469,392,369,190,
20 1,109,375,137,181, 88, 75,308,260,484, 98,272,370,275,412,111,
21 336,318, 4,504,492,259,304, 77,337,435, 21,357,303,332,483, 18,
22 47, 85, 25,497,474,289,100,269,296,478,270,106, 31,104,433, 84,
23 414,486,394, 96, 99,154,511,148,413,361,409,255,162,215,302,201,
24 266,351,343,144,441,365,108,298,251, 34,182,509,138,210,335,133,
25 311,352,328,141,396,346,123,319,450,281,429,228,443,481, 92,404,
26 485,422,248,297, 23,213,130,466, 22,217,283, 70,294,360,419,127,
27 312,377, 7,468,194, 2,117,295,463,258,224,447,247,187, 80,398,
28 284,353,105,390,299,471,470,184, 57,200,348, 63,204,188, 33,451,
29 97, 30,310,219, 94,160,129,493, 64,179,263,102,189,207,114,402,
30 438,477,387,122,192, 42,381, 5,145,118,180,449,293,323,136,380,
31 43, 66, 60,455,341,445,202,432, 8,237, 15,376,436,464, 59,461
|
הרחבת מפתח
עריכההמפתח הסודי המסופק על ידי המשתמש מורחב ומחולק לשני מערכים בני שמונה כניסות באורך 16 סיביות כל אחת (בסך הכול 256 סיביות). תחילה מציבים בשמונה הכניסות של המערך הראשון את המפתח ומציבים במערך הנוסף עבור את: , כאשר הם קבועים המוגדרים בטבלה להלן. מתוך שני המערכים הללו גוזרים את מפתחות כל הסבבים לפי הטבלה הבאה:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
הסימן הוא הזזה מעגלית של לשמאל (rotate left), במספר סיביות לפי הערך המצוין מימין. למשל בסבב השני המפתח הוא הערך בכניסה לאחר הזזה מעגלית שמונה סיביות.
טבלת הקבועים בערכים הקסדצימליים. הערכים נקבעו שרירותית באופן שקל להיווכח שלא הייתה כוונה סודית בבחירתם:
| קבוע | ערך |
|---|---|
ראו גם
עריכההערות שוליים
עריכה- ^ 3G Security; Specification of the 3GPP confidentiality and integrity algorithms; Document 2: Kasumi specification
- ^ [www.iacr.org/archive/eurocrypt2001/20450323.pdf Cryptanalysis of Reduced-Round MISTY]
- ^ A Single-Key Attack on 6-Round KASUMI
- ^ A Practical-Time Attack on the A5/3 Cryptosystem Used in Third Generation GSM Telephony