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, בשישה סבבים בסיבוכיות זמן של 2100 ומקום בסדר גודל של 255.

התקפה יותר מעשית פורסמה על ידי Teruo Saito[3] גם כן בשישה סבבים בזמן של 265.4 ועם 260 טקסטים. יש לזכור שב-KASUMI שמונה סבבים. ב-2005 פרסמו אור דונקלמן, אלי ביהם ונתן קלר מהטכניון התקפת מפתחות קשורים (related key) בשילוב עם התקפת בומרנג (סוג של התקפה דיפרנציאלית) נגד KASUMI שמסוגלת לשבור את הצופן בגרסה המלאה עם 276.1 הצפנות ועם כמות של 254.6 טקסטים נבחרים שהוצפנו עם 4 מפתחות קשורים. למרות שההתקפה תאורטית, היא סותרת את טענת המפתחים לגבי הוכחת ביטחון האלגוריתם. ב-2010 הציגו אותם חוקרים התקפה[4] משופרת בהרבה שהייתה מספיק פרקטית עד שהצליחו להמחישה על מחשב ביתי בזמן של מספר שעות, אפילו עם גרסה לא ממוטבת של הצופן. למרות זאת החוקרים ציינו שההתקפה אינה מעשית נגד אלגוריתם A5/3 שבשימוש GSM בשל אופן מימושו. על כל פנים ההתקפה אינה אפשרית נגד MISTY, מה שמוכיח כי השינויים שביצעו מפתחי KASUMI השפיעו לרעה על ביטחון הצופן וזאת בניגוד לטענתם.

תיאור הצופן

KASUMI הוא צופן בלוקים בסגנון רשת פייסטל בשמונה סבבים. הקלט הוא בלוק דטה באורך 64 סיביות ומפתח הצפנה סודי באורך 128 סיביות והפלט הוא בלוק מוצפן באורך 64 סיביות. הצופן בנוי בצורה רקורסיבית.

הפונקציה O=𝐊𝐀𝐒𝐔𝐌𝐈(I)K מבצעת כדלהלן:
1. תחילה בלוק הקלט I מחולק לשני חצאים L0,R0 באורך 32 סיביות כל אחד.
2. מפעילים את פונקציית הסבב fi על חצי השמאלי ומחליפים מקומות עם החצי הימני שמונה פעמים. דהיינו עבור 1i8 מבצעים:
  1. Ri=Li1
  2. Li=Ri1fi(Li1,RKi)
3. הפלט הוא O=(L8  R8).

RKi הוא החלק המפתח המתאים לסבב i (לפי הטבלה המופיעה להלן). הסמל מייצג שרשור והסמל מייצג XOR.

פונקציית הסבב

הפונקציה הראשית fi מקבלת קלט I באורך 32 סיביות וקטע מתאים מהמפתח המורחב (להלן) שנקרא "מפתח הסבב" ומחזירה את הפלט O. מפתח הסבב RKi מורכב משלושה תת-מפתחות KLi,KOi,KIi הראשון באורך 32 סיביות ושני האחרים באורך 48 סיביות כל אחד. והיא משתמשת בשתי תת-שגרות FL ו-FO. כשהמפתח KL מועבר לפונקציה FL והמפתחות KO,KI מועברים לפונקציה FO.

פונקציית הסבב הראשית מופיעה בשתי צורות בהתאם לסבב זוגי או אי זוגי. עבור סבב זוגי היא בנויה כך:

fi(I,RKi)=FL(FO(I,KLi),KOi,KIi)

בסבב אי זוגי כך:

fi(I,RKi)=FO(FL(I,KLi),KOi,KIi)

כלומר בסבב זוגי הפונקציה FL מופעלת לאחר הפונקציה FO (כלומר הפלט של FO הופך לקלט של FL) ובסבב אי זוגי ההפך.

הפונקציה FL

בהינתן הקלט I באורך 32 סיביות ותת-מפתח KLi גם הוא באורך 32 סיביות, הפונקציה מחלקת תחילה את תת-המפתח לשני חצאים באורך 16 סיביות כל אחד, כך שמתקיים KLi=KLi,1  KLi,2 ואת הקלט I לשני חצאים כך שמתקיים I=L  R ומבצעת:

R=RROL(LKLi,1)
L=LROL(RKLi,2)

והפלט הוא (L  R). הפונקציה ROL היא הזזה מעגלית לשמאל סיבית אחת. הסמל מייצג AND והסמל מייצג OR.

הפונקציה FO

בהינתן קלט I באורך 32 סיביות ושני תת-מפתחות KOi,KIi באורך 48 סיביות כל אחד, הפונקציה מחלקת תחילה את הקלט לשני חצאים L0,R0 ואת שני תת-המפתחות לשישה חלקים באורך 16 סיביות כל אחד KOi,1,KOi,2,KOi,3,KIi,1,KIi,2,KIi,3 בהתאמה ומבצעת שלוש פעמים, עבור 1j3:

Rj=FI(Lj1KOi,j,KIi,j)Rj1
Lj=Rj1

והפלט הוא (L3  R3).

הפונקציה FI

בהינתן הקלט I באורך 16 סיביות ותת-מפתח KIi,j הפונקציה מחלקת תחילה את הקלט לשני חלקים לא שווים באורכם, L0 באורך 9 סיביות ו-R0 באורך 7 סיביות, באותו אופן מחלקת את תת-המפתח לשני חלקים KIi,j,1 באורך 9 סיביות והחלק KIi,j,2 באורך 7 סיביות ומבצעת:

L1=R0,R1=S9[L0]ZE(R0)
L2=R1KIi,j,2,R2=S7[L1]TR(R1)KIi,j,1
L3=R2,R3=S9[L2]ZE(R2)
L4=S7[L3]TR(R3),R4=R3

והפלט הוא (L4  R4). כאשר הפונקציות ZE ו-TR קיצור של ZeroExtend ו-Truncate בהתאמה הן פונקציות שנועדו להמיר את הערך x מ-7 סיביות ל-9 סיביות וההפך. ההרחבה מתבצעת על ידי הוספת אפסים משמאל (בצד המשמעותי של המספר) והחיתוך מתבצע על ידי הסרת שתי הסיביות המשמעותיות של המספר.

תיבות החלפה

לצופן נילוות שתי תיבות החלפה בסיביות שנקראות S7 ו-S9 והן עוצבו כך שניתן יהיה לממשן בשני אופנים. קומבינציה לוגית וטבלת אחזור (lookup table) בהתאם לסיטואציה. למשל בחומרה מוגבלת בזיכרון הגישה הראשונה עדיפה. טבלאות חיפוש מהירות יותר והן עדיפות כאשר הזיכרון זמין. בגישה הלוגית ההחלפה מתבצעת על ידי קומבינציה של השערים הלוגיים AND ו-XOR. להלן שתי תיבות ההחלפה בשני האופנים האמורים. הערך x בייצוג בינארי הוא מחרוזת של 7 סיביות (או 9 בטבלה הבאה) המיוצגות על ידי x0x1x2x3x4x5x6 (הביטוי x0x1 פירושו x0x1):

y0=x1x3x4x0x1x4x5x2x5x3x4x5x6x0x6x1x6x3x6x2x4x6x1x5x6x4x5x6
y1=x0x1x0x4x2x4x5x1x2x5x0x3x5x6x0x2x6x3x6x4x5x61
y2=x0x0x3x2x3x1x2x4x0x3x4x1x5x0x2x5x0x6x0x1x6x2x6x4x61
y3=x1x0x1x2x1x4x3x4x0x5x0x1x5x2x3x5x1x4x5x2x6x1x3x6
y4=x0x2x3x1x3x1x4x0x1x4x2x3x4x0x5x1x3x5x0x4x5x1x6x3x6x0x3x6x5x61
y5=x2x0x2x0x3x1x2x3x0x2x4x0x5x2x5x4x5x1x6x1x2x6x0x3x6x3x4x6x2x5x61
y6=x1x2x0x1x3x0x4x1x5x3x5x6x0x1x6x2x3x6x1x4x6x0x5x6

טבלת החלפה 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:

y0=x0x2x3x2x5x5x6x0x7x1x7x2x7x4x8x5x8x7x81
y1=x1x0x1x2x3x0x4x1x4x0x5x3x5x6x1x7x2x7x5x81
y2=x1x0x3x3x4x0x5x2x6x3x6x5x6x4x7x5x7x6x7x8x0x81
y3=x0x1x2x0x3x2x4x5x0x6x1x6x4x7x0x8x1x8x7x8
y4=x0x1x1x3x4x0x5x3x6x0x7x6x7x1x8x2x8x3x8
y5=x2x1x4x4x5x0x6x1x6x3x7x4x7x6x7x5x8x6x8x7x81
y6=x0x2x3x1x5x2x5x4x5x3x6x4x6x5x6x7x1x8x3x8x5x8x7x8
y7=x0x1x0x2x1x2x3x0x3x2x3x4x5x2x6x3x6x2x7x5x7x81
y8=x0x1x2x1x2x3x4x1x5x2x5x1x6x4x6x7x2x8x3x8

טבלת ההחלפה 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

הרחבת מפתח

המפתח הסודי K המסופק על ידי המשתמש מורחב ומחולק לשני מערכים בני שמונה כניסות באורך 16 סיביות כל אחת (בסך הכול 256 סיביות). תחילה מציבים בשמונה הכניסות של המערך הראשון את המפתח K ומציבים במערך הנוסף K עבור 1j8 את: Kj=KjCj, כאשר Cj הם קבועים המוגדרים בטבלה להלן. מתוך שני המערכים הללו גוזרים את מפתחות כל הסבבים לפי הטבלה הבאה:

i 1 2 3 4 5 6 7 8
KLi,1 K11 K21 K31 K41 K51 K61 K71 K81
KLi,2 K3' K4' K5' K6' K7' K8' K1' K2'
KOi,1 K25 K35 K45 K55 K65 K75 K85 K15
KOi,2 K68 K78 K88 K18 K28 K38 K48 K58
KOi,3 K713 K813 K113 K213 K313 K413 K513 K613
KIi,1 K5' K6' K7' K8' K1' K2' K3' K4'
KIi,2 K4' K5' K6' K7' K8' K1' K2' K3'
KIi,3 K8' K1' K2' K3' K4' K5' K6' K7'

הסימן הוא הזזה מעגלית של Ki לשמאל (rotate left), במספר סיביות לפי הערך המצוין מימין. למשל בסבב השני המפתח KO2,2 הוא הערך בכניסה K7 לאחר הזזה מעגלית שמונה סיביות.

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

קבוע ערך
C1 0x0123
C2 0x4567
C3 0x89AB
C4 0xCDEF
C5 0xFEDC
C6 0xBA98
C7 0x7654
C8 0x3210

ראו גם

הערות שוליים



הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

KASUMI38751023Q1718415