FEAL

בקריפטוגרפיה, FEAL (ראשי תיבות של Fast data Encipherment ALgorithm, בעברית: אלגוריתם הצפנת נתונים מהיר) כולל משפחה של צפני בלוקים במבנה פייסטל שהראשון שבהם הוצע כאלטרנטיבה לצופן DES והוא מהיר ממנו בתוכנה. הגרסה הראשונה פותחה ב-1987 על ידי אקירו שימיזו ושוי מיאגוטשי מתאגיד הטלגרף והטלפון של יפן (NTT)^[1]. ב-1994 התקבל הצופן לתקן בין-לאומי ISO/IEC9979 וב-1999 נבחר לתקן ATM וכן נכלל בתקן יפני לכרטיסים חכמים ב-1998. בשל קריפטואנליזה שמעידה על חולשות הצופן אינו בשימוש כיום. NTT ממליצים להשתמש בצופן מדור חדש כמו קמליה.

קיימות מספר גרסאות של FEAL כולן במבנה פייסטל עם אותה פונקציית סבב פנימית אך עם מספר סבבים שונה או עם מפתח גדול יותר. הצופן מקבל בלוק קלט באורך 64 סיביות ומחזיר בלוק מוצפן באורך 64 סיביות. הגרסה הראשונה שכיום נקראת FEAL-4 משתמשת במפתח הצפנה באורך 64 סיביות וכוללת ארבעה סבבים של הפונקציה הפנימית. FEAL-8 מכיל שמונה סבבים עם אותו מפתח ואילו FEAL-NX מכילה מספר דינאמי של סבבים בהתאם לצורך כך ש- $N\geq 8$ . (המספר המומלץ הוא $N=32$ ) ואילו "X" מתייחס לאופציה של מפתח באורך 128 סיביות שנוספה בגרסה המאוחרת יותר.

ביטחון

מאז שפורסם הפך FEAL ליעד מועדף מצד קריפטונאליסטים מרחבי העולם ופורסמו מחקרים רבים אודות החולשות שלו. כיום ידוע שהצופן אינו בטוח לשימוש כי הוא פגיע במיוחד למספר התקפות קריפטוגרפיות מעשיות ביניהן קריפטואנליזה דיפרנציאלית וקריפטואנליזה ליניארית. למעשה הצופן שימש כ"קטליזטור" במהלך פיתוח התקפות קריפטוגרפיות אילו. הקריפטואנליזה הדיפרנציאלית הומצאה בשביל לפצח את FEAL ובתוך כך התגלתה ככלי יעיל לניתוח צפנים אחרים. כל גרסאות צופן FEAL אינן מומלצות כיום לשימוש כלל והעניין בהן הוא אקדמי בלבד.

בתחילה התגלו בעיות בגרסה הראשונה של הצופן על ידי דן בואר ושון מרפי שגילו התקפות קריפוטאנליטיות הדורשות כמות מועטה של טקסטים גלויים נבחרים כדי לפצח את הצופן בקלות^[2]^[3]. ההתקפות שלהם מכילות אלמנטים דומים להתקפה הדיפרנציאלית שהתגלתה מאוחר יותר. ב-1998 ניסו מפתחי הצופן לפתור את הבעיה על ידי העלאת מספר הסבבים וכך נוצר FEAL-8 הכולל שמונה סבבים במקום ארבעה.

ב-1991 פרסמו אלי ביהם ועדי שמיר את ההתקפה הדיפרנציאלית שלהם על FEAL-8^[4]. אחריהם פורסמו עוד כמה התקפות מסוג זה שמצליחות לפצח את הצופן עם כמות יחסית קטנה של טקסטים גלויים נבחרים. בתגובה פותח FEAL-NX אך הסתבר שההתקפה הדיפרנציאלית של שמיר וביהם הייתה ישימה גם נגד הגרסה הזו שהיא החזקה ביותר שפותחה, ההתקפה שלהם יעילה מכוח גס כל עוד $N\leq 31$ .

ב-1991 גילו טארדי וגילברט התקפה חדשה נגד גרסאות צופן FEAL שמסוגלת לפצח אותו בסיבוכיות טובה מכוח גס^[5]. למשל FEAL-8 ניתן בשיטה זו לשבירה עם $2^{15}$ טקסטים גלויים נבחרים. מאוחר יותר פרסם מיצורו מצואי את ההתקפה הליניארית שמבוססת על רעיון זה המסוגלת לשבור את צופן FEAL-4 בתוך כחמש דקות עם שישה טקסטים גלויים ידועים. ב-1994 פורסמה התקפה ליניארית נגד FEAL-8 עם $2^{12}$ טקסטים גלויים נבחרים^[6]. למעשה בעקבות התקפות אילו נסתם הגולל על FEAL והוא אינו בשימוש כיום כלל. NTT ממליצים להשתמש בקמליה במקומו.

חשיבות הצופן וההתקפות המתוארות היא בעיקר בלקח שאפשר להפיק מהם. זהו הצופן הראשון שפותח על ידי NTT ושימש יסוד ובסיס להתפתחות צפני בלוקים מודרניים חזקים יותר ועמידים יותר נגד קריפטואנליזה דיפרנציאלית וליניארית כמו E2 שהיה מהמועמדים לתקן AES ולא הגיע לגמר וקמליה שנחשב לצופן מודרני חזק.

פירוט מהלכי הצופן

להלן תיאור צופן FEAL-NX כאשר $N\geq 32$ . הוא מקבל מפתח באורך 64 או 128 סיביות לפי בחירת המשתמש ופועל על בלוק גלוי באורך 8 בתים. באופן כללי האלגוריתם מבצע שלושה מהלכים:

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

בשלב ההכנה הנקרא קדם-עיבוד, בלוק הטקסט הגלוי $P$ מחולק לשני חצאים $(R_{0},L_{0})$ באורך 32 סיביות כל אחד. תחילה מבצעים:

(L_{0},R_{0})\leftarrow (L_{0},R_{0})\oplus (K_{N},K_{N+1},K_{N+2},K_{N+3})

כלומר מחברים ב-XOR עם ארבעה תת-מפתחות מתאימים. כל תת-מפתח באורך 16 סיביות לכן כל מחצית מהבלוק מחוברת עם שני תת-מפתחות ואז

(L_{0},R_{0})\leftarrow (L_{0},R_{0})\oplus (\phi ,L_{0})

כאשר הסימן $\phi$ מייצג בלוק המכיל 32 אפסים, הסימן $\oplus$ הוא XOR ו- $K_{i}$ מייצג את תת-המפתחות מתהליך ההכנה המתואר להלן. המשמעות של המהלך הוא שהמחצית הימנית היא תוצאה של XOR עם המחצית השמאלית. לפעולת XOR עם אפסים אין השפעה לכן המחצית השמאלית נותרת ללא שינוי.

בשלב האיטרציה, הקלט $(L_{0},R_{0})$ משלב ההכנה עובר עיבוד עם הפונקציה $f$ בסך הכול $N$ פעמים:

R_{r}\leftarrow L_{r-1}\oplus f(R_{r-1},K_{r-1})

L_{r}=R_{r-1}

כאשר $1\leq r\leq N$ . הפונקציה $f$ מתוארת להלן והפלט הוא התוצאה מהסבב האחרון $(L_{N},R_{N})$ .

בשלב הסיום, מחליפים בין החצאים של הפלט האחרון $(R_{N},L_{N})\leftarrow (L_{N},R_{N})$ ואז מחשבים את:

(R_{N},L_{N})\leftarrow (R_{N},L_{N})\oplus (\phi ,R_{N})

ולסיום מחברים עם חלקים מתאימים מהמפתח:

(R_{N},L_{N})\leftarrow (R_{N},L_{N})\oplus (K_{N+4},K_{N+5},K_{N+6},K_{N+7})

הטקסט המוצפן הוא $C=(R_{N},L_{N})$ .

אלגוריתם הפענוח

תהליך הפענוח דומה, הקלט $(R_{N},L_{N})$ מעובד תחילה על ידי:

(R_{N},L_{N})\leftarrow (R_{N},L_{N})\oplus (K_{N+4},K_{N+5},K_{N+6},K_{N+7})

ואז

(R_{N},L_{N})\leftarrow (R_{N},L_{N})\oplus (\phi ,R_{N})

לאחר מכן מבצעים $N$ פעמים:

L_{r-1}\leftarrow R_{r}\oplus f(L_{r},K_{r-1})

R_{r-1}\leftarrow L_{r}

כדי לקבל את הטקסט המקורי תחילה מבצעים:

(L_{0},R_{0})\leftarrow (L_{0},R_{0})\oplus (\phi ,L_{0})

לסיום מחשבים את:

(L_{0},R_{0})\leftarrow (L_{0},R_{0})\oplus (K_{N},K_{N+1},K_{N+2},K_{N+3})

שימו לב שמחברים ארבעה תת-מפתחות כי תת-מפתח הוא באורך 16 סיביות ולכן נדרשים ארבעה כדי לחבר עם $(L_{0},R_{0})$ שהוא באורך 64 סיביות (8 בתים).

תהליך הכנת המפתח

#define ROTL(x, n)  (byte)(((byte)(x) << (n))  |  ((byte)(x) >> (8-(n))))
#define S0(x, y)   (byte)(ROTL(((byte)((x) + (y)    )), 2))
#define S1(x, y)   (byte)(ROTL(((byte)((x) + (y) + 1)), 2))

void FEAL_Fk(byte *a, byte *b)
{
	a[1] ^= a[0], a[2] ^= a[3];
	byte t;
	t = a[2] ^ b[0], a[1] = S1(a[1], t);
	t = a[1] ^ b[1], a[2] = S0(a[2], t);

	t = a[1] ^ b[2], a[0] = S0(a[0], t);
	t = a[2] ^ b[3], a[3] = S1(a[3], t);
}
void FEAL_F(byte *a, byte *b, byte *e)
{
	a[1] = (b[0] ^ b[1] ^ e[0]);
	a[2] = (b[2] ^ b[3] ^ e[1]);

	a[1] = S1(a[1], a[2]);
	a[2] = S0(a[1], a[2]);

	a[0] = S0(b[0], a[1]);
	a[3] = S1(b[3], a[2]);
}

קוד C++‎ של הפונקציות הפנימיות

f

ו-

f_{k}

מהמפתח הסודי המסופק על ידי המשתמש מכינים $N+8$ תת-מפתחות מסומנים $K_{0},K_{1},K_{2},...,K_{N+7}$ כל אחד באורך 16 סיביות (שני בתים), כאשר $N$ מהם משמשים לצורך הפונקציה הפנימית, מפתח אחד לכל סבב ואילו 8 הנוספים משמשים לפעולת ההלבנה (חיבור ב-XOR), ארבעה מהם לפני האיטרציה של הפונקציה הפנימית וארבעה לאחריה. תחילה המפתח מחולק לשני חצאים $(K_{L},K_{R})$ באורך 64 סיביות כל אחד.

את החצי הימני $K_{R}$ מחלקים לשני חצאים $(K_{R1},K_{R2})$ ומכינים סדרה של משתנים מקומיים בהתאם למספר הסבבים $Q_{r}$ בהם מציבים עבור $i=0,1,2,...$ :

Q_{r}\leftarrow K_{R1}\oplus K_{R2}

כאשר

r=3i+1

,

Q_{r}\leftarrow K_{R1}

כאשר

r=3i+2

,

Q_{r}\leftarrow K_{R2}

כאשר

r=3i+3

$r$ נמוך מ- $(N/2)+4$ ו- $N\geq 32$ כאשר $N$ זוגי.

את החצי השמאלי $K_{L}$ מחלקים לשני חצאים $(A_{0},B_{0})$ ומכינים משתנה מקומי ריק $D_{0}$ . את $K_{i}$ כאשר $i=0$ עד $N+7$ מכינים עם $r=1$ עד $(N/2)+4$ כדלהלן:

D_{r}=A_{r-1},A_{r}=B_{r-1}

,

B_{r}=f_{K}(\alpha ,\beta )=f_{K}(A_{r-1}(B_{r-1}\oplus D_{r-1})\oplus Q-r))

,

K_{2(r-1)}=(B_{r0},B_{r1})

,

K_{2(r-1)+1}=(B_{r2},B_{r3})

$B_{r}$ הוא משתנה מקומי המחולק לארבעה בתים $B_{r0},B_{r1},B_{r2},B_{r3}$ .

פונקציות עזר

הפונקציה $f$ מגיעה בשתי גרסאות אחת עבור פונקציית הסבב הפנימית והשנייה עבור הכנת המפתח. הפונקציה $f(\alpha ,\beta )$ המשמשת לצורך פונקציית הסבב מקבלת שני פרמטרים הראשון באורך 32 סיביות והשני באורך 16 סיביות, כאשר $\alpha$ מחולק לארבעה בתים: $\alpha =(\alpha _{0},\alpha _{1},\alpha _{2},\alpha _{3})$ ו- $\beta$ מחולק לשני בתים $\beta =(\beta _{0},\beta _{1})$ . פלט הפונקציה כמתואר בתרשים משמאל, הוא $f=(f_{0},f_{1},f_{2},f_{3})$ כדלהלן:

f_{1}=\alpha _{1}\oplus \beta _{0},f_{2}=\alpha _{2}\oplus \beta _{1}

f_{1}=f_{1}\oplus \alpha _{0},f_{2}=f_{2}\oplus \alpha _{3}

f_{1}=S_{1}(f_{1},f_{2}),f_{2}=S_{0}(f_{2},f_{1})

f_{0}=S_{0}(\alpha _{0},f_{1}),f_{3}=S_{1}(\alpha _{3},f_{2})

.

הפונקציה $f_{K}(\alpha ,\beta )$ מקבלת שני פרמטרים באורך 32 סיביות כל אחד וכן תת-מפתח באורך 16 סיביות. הפרמטרים $\alpha ,\beta$ מחולקים לבתים כך: $\alpha =(\alpha _{0},\alpha _{1},\alpha _{2},\alpha _{3})$ וכן $\beta =(\beta _{0},\beta _{1},\beta _{2},\beta _{3})$ ואז הפונקציה מחשבת ומחזירה את ארבעת הערכים $(f_{K0},f_{K1},f_{K2},f_{K3})$ , כדלהלן:

f_{K1}=\alpha _{1}\oplus \alpha _{0}

f_{K2}=\alpha _{2}\oplus \alpha _{3}

f_{K1}=S_{1}(f_{K1},(f_{K2}\oplus \beta _{0}))

f_{K2}=S_{0}(f_{K2},(f_{K1}\oplus \beta _{1}))

f_{K0}=S_{0}(\alpha _{0},(f_{K1}\oplus \beta _{2}))

f_{K3}=S_{1}(\alpha _{3},(f_{K2}\oplus \beta _{3}))

הפונקציות $S_{0}$ ו- $S_{1}$ מוגדרות כדלהלן:

S_{0}(X_{1},X_{2})={\text{ROT2}}((X_{1}+X_{2}){\text{ mod }}256)

S_{1}(X_{1},X_{2})={\text{ROT2}}((X_{1}+X_{2}+1){\text{ mod }}256)

כאשר $X_{1}$ ו- $X_{2}$ הם בתים והפונקציה ROT2 היא הזזה מעגלית לשמאל שתי סיביות, לדוגמה בהינתן $X_{1}=00010011$ ו- $X_{2}=11110010$ אז $T=(X_{1}+X_{2}+1){\text{ mod }}256=0000110$ וכן $S_{1}(X_{1},X_{2})=00011000$ בבסיס בינארי.

קוד לדוגמה

void FEAL_keygen(byte *k, byte *e, uint r)
{
	byte a[4], b[4], d[4], kr1[4], kr2[4], t, s[4];

	for (uint i = 0; i < 4; i++) {
		a[i] = k[i], b[i] = k[i + 4];
		kr1[i] = k[i + 8], kr2[i] = k[i + 12];
		d[i] = 0;
	}

	for (uint i = 0; i < r + 8; i += 2) {
		for (uint j = 0; j < 4; j++) {
			s[j] = b[j];
			if ((i / 2) % 3 == 0) {
				s[j] ^= (kr1[j] ^ kr2[j]);
			}
			else if ((i / 2) % 3 == 1) {
				s[j] ^= kr1[j];
			}
			else {
				s[j] ^= kr2[j];
			}
			s[j] ^= d[j];
			d[j] = a[j];  /*  for next steps  */
		}
		FEAL_Fk(a, s);

		for (uint j = 0; j < 4; j++) {
			e[2 * i + j] = a[j];
		}

		for (uint j = 0; j < 4; j++) {
			t = a[j];
			a[j] = b[j], b[j] = t;
		}
	}
}

void FEAL_encrypt(byte *p, uint r, byte *e, byte *c)
{
	byte a[4], b[4], t, s[4];

	for (uint j = 0; j < 4; j++) {
		a[j] = p[j] ^ e[2 * r + j];
		b[j] = p[j + 4] ^ e[2 * r + j + 4] ^ a[j];
	}

	for (uint i = 0; i < r; i++) {
		FEAL_F(s, b, e + 2 * i);

		for (uint j = 0; j < 4; j++) {
			a[j] ^= s[j];
		}

		for (uint j = 0; j < 4; j++) {
			t = a[j];
			a[j] = b[j], b[j] = t;
		}
	}

	for (uint j = 0; j < 4; j++) {
		a[j] ^= b[j];
	}

	for (uint j = 0; j < 4; j++) {
		c[j] = (b[j] ^ e[2 * r + j + 8]);
		c[j + 4] = (a[j] ^ e[2 * r + j + 12]);
	}
}


void FEAL_decrypt(byte *c, uint r, byte *e, byte *p)
{
	byte a[4], b[4], t, s[4];

	for (uint j = 0; j < 4; j++) {
		a[j] = c[j] ^ e[2 * r + j + 8];
		b[j] = c[j + 4] ^ e[2 * r + j + 12] ^ a[j];
	}

	for (uint i = 0; i < r; i++) {
		FEAL_F(s, b, e + 2 * (r - 1 - i));

		for (uint j = 0; j < 4; j++) {
			a[j] ^= s[j];
		}

		for (uint j = 0; j < 4; j++) {
			t = a[j];
			a[j] = b[j], b[j] = t;
		}
	}

	for (uint j = 0; j < 4; j++) {
		a[j] ^= b[j];
	}

	for (uint j = 0; j < 4; j++) {
		p[j] = (b[j] ^ e[2 * r + j]);
		p[j + 4] = (a[j] ^ e[2 * r + j + 4]);
	}
}

קריפטואנליזה דיפרנציאלית של FEAL-4

קריפטואנליזה דיפרנציאלית פועלת לפי מודל התקפת גלוי-נבחר^[7], כלומר המתקיף רשאי לבחור זוגות של טקסטים גלויים וטקסטים מוצפנים המתאימים להם שהוצפנו עם מפתח שאינו ידוע לו ותפקידו הוא לגלות את המפתח הסודי ששימש להצפנתם. המתקיף בוחר את הטקסטים באופן כזה שהדיפרנציאל (ההפרש) שלהם עונה על "מאפיין" מסוים המתאים לצורך ההתקפה. כאן הדיפרנציאל הוא מעל פעולת XOR ולכן הדברים נעשים פשוטים יותר כי בגלל התכונה הידועה שאם מבצעים XOR בין שני טקסטים מוצפנים שהוצפנו עם אותו קטע מהמפתח למעשה מבטלים את השפעת המפתח כאילו לא היה קיים (ראו פנקס חד-פעמי). במקרה של FEAL-4 התגלתה עובדה מעניינת: נתונה הפונקציה הפנימית של הצופן $F$ , עבור כל זוג טקסטים $A_{0}$ ו- $A_{1}$ אם $A_{0}\oplus A_{1}={\text{0x808000000}}$ (בבסיס הקסדצימלי) אז מתקיים $F(A_{0})\oplus F(A_{1})={\text{0x02000000}}$ . למרבה ההפתעה זהו דיפרנציאל בעל הסתברות של 1 שלא קשה לחשב והוא משמש לשבירת הצופן.

FEAL-4 זהה לתיאור FEAL-XN למעט העובדה שהפונקציה הפנימית מבוצעת רק 4 פעמים ותהליך הכנת מפתח שונה. אפשר להציג את הצופן בכמה דרכים, אולם לצורך הקריפטואנליזה הדיפרנציאלית שלו הוא מוצג כאן בדרך קצת שונה מהקודמת (קל להוכיח ששתיהן למעשה שקולות). המפתח מחולק לשישה תת-מפתחות באורך 32 סיביות כל אחד (במקום 12 תת-מפתחות באורך 16 סיביות בתיאור המקורי). אפשר להתעלם מתהליך הכנת המפתח כולו כי ההתקפה מתמקדת בשחזור תת-המפתחות ואם מצליחים לנחש אותם אז אפשר לשחזר את המפתח הסודי בקלות. פונקציית הסבב הפנימית $F$ מקבלת ארבעה בתים $(x_{0},x_{1},x_{2},x_{3})$ ומחזירה ארבעה בתים $(y_{0},y_{1},y_{2},y_{3})$ , היא עושה שימוש בפונקציות $S_{0}$ ו- $S_{1}$ המתוארות לעיל והיא נראית כך:

y_{1}=S_{1}(x_{0}\oplus x_{1},x_{2}\oplus x_{3})

y_{0}=S_{0}(x_{0},y_{1})

y_{2}=S_{0}(y_{1},x_{2}\oplus x_{3})

y_{3}=S_{1}(y_{2},x_{3})

תיאור ההתקפה הדיפרנציאלית על צופן FEAL-4

לצורך ההתקפה המתקיף בוחר טקסט גלוי אקראי $P_{0}$ ומחשב את הטקסט הגלוי $P_{1}$ המקיים $P_{1}=P_{0}\oplus {\text{0x8080000080800000}}$ וכן מניחים (לפי הגדרת מודל ההתקפה) שהמתקיף השיג את הטקסטים המוצפנים המתאימים להם $C_{0}$ ו- $C_{1}$ בהתאמה ואז הוא מחשב את הדיפרנציאלים שלהם $P'=P_{0}\oplus P_{1}$ וכן $C'=C_{0}\oplus C_{1}$ וכן מחשב את הדיפרנציאלים של כל ערכי הביניים של הצופן המתקבלים משני הטקסטים שהוצפנו $P_{0}$ ו- $P_{1}$ ומה שמתקבל מופיע בתרשים משמאל. העובדה שהמפתח לא מופיע בתרשים אינה טעות, כיוון שמדובר על דיפרנציאל של שני טקסטים שהוצפנו עם אותו מפתח לכן אפשר להתעלם ממנו כרגע. הדיפרנציאל האמור יחד עם הטקסטים הידועים עוזר לגלות את המפתח בשלב הבא של ההתקפה. אם מנסים לנוע בכיוון ההפוך בשיטת היפגשות באמצע, כלומר מנסים לחשב את ערכי הביניים מהטקסט המוצפן כלפי מעלה, רואים שיש אפשרות להשיג את הקלט והפלט לפונקציה הפנימית $F$ במהלך האחרון של הצופן. כי $C_{0}$ ו- $C_{1}$ ידועים וכן אפשר לחשב את הדפירנציאלים $C',L',R'$ כך שמתקיים $L'={\text{0x2000000}}\oplus Z'$ וכן $R'=L'\oplus Y'$ מה שמאפשר לחשב את $Y'={\text{0x80800000}}\oplus X'$ . היות שהטקסט המוצפן ידוע מתקבל $Y=L\oplus R$ .

עם כל המידע הזה אפשר לפצח את הצופן תחילה על ידי ניחוש תת-המפתח השלישי $K_{3}$ . מחשבים את $Z'$ ואז מחשבים את $Y_{0}$ ו- $Y_{1}$ (המתאימים ל- $C_{0}$ ו- $C_{1}$ ) אותם אפשר להשיג על ידי חישוב מהסוף להתחלה. היות ש- $K_{3}$ הוא באורך 32 סיביות ישנם למעשה $2^{32}$ ערכים אפשריים. אם נסמן ניחוש אחד ב- ${\tilde {K}}_{3}$ , אז בידיעת $Y_{0}$ אפשר לחשב את ${\tilde {Z}}_{0}$ ובידיעת $Y_{1}$ אפשר לחשב את ${\tilde {Z}}_{1}$ כך שיתקבל $Z'={\tilde {Z}}_{0}\oplus {\tilde {Z}}_{1}$ . אם המשוואה הזו מתקיימת אז הניחוש הצליח ו- ${\tilde {K}}_{3}$ הוא "מועמד" מתאים ושומרים אותו. היות שיכולים להיות מועמדים רבים שמקיימים את התנאי האמור, יש צורך לבדוק נכונות מול זוגות טקסטים נוספים. אם בודקים לפחות עם ארבעה זוגות כאלה הסיכויים הם מאוד גבוהים שאפשר להגיע לניחוש מוצלח והוא יהיה יחיד. אם התנאי האמור לא מתקיים נפטרים מערך זה ומחפשים ערכים אחרים. פקטור העבודה לגילוי תת-מפתח אחד הוא ברמה של $2^{32}$ שזה לא מהיר במיוחד, אבל כאן נעזרים במבנה הפנימי של הפונקציה $F$ כדי להאיץ את החיפוש לכדי פקטור של $2^{17}$ . לצורך כך מגדירים תחילה פונקציה המקבלת ארבעה בתים ומחשבת $M(A)=M(a_{0},a_{1},a_{2},a_{3})=(0,a_{0}\oplus a_{1},a_{2}\oplus a_{3},0)$ . ההתקפה המשופרת לניחוש $K_{3}$ פועלת בשני שלבים. תחילה עבור כל ערך אפשרי של $A=(0,a_{0},a_{1},0)$ מחשבים את:

Q_{0}=F(M(Y_{0})\oplus A),Q_{1}=F(M(Y_{1})\oplus A)

.

אם מתבוננים בהגדרה של $F$ רואים שאם $A=M(K_{3})$ אז מתקיים $\langle Q_{0}\oplus Q_{1}\rangle _{8...23}=\langle Z'\rangle _{8...23}$ כאשר המספרים מייצגים את 16 הסיביות האמצעיות החל מהסיבית השמינית (כאשר הספירה מתחילה מאפס) ועד הסיבית ה-23. אפשר להשתמש בעובדה זו כדי למצוא מועמדים עבור $M(K_{3})$ ובכך למעשה מגלים 16 סיביות של $K_{3}$ . בשלב השני כל מועמד ששרד את שלב אחד נבדק שוב כך שבהינתן מועמד $A=(0,a_{0},a_{1},0)$ , מגרילים תחילה שני בתים $B=b_{0},b_{1}$ ומחשבים את ${\tilde {K}}_{3}=(b_{0},a_{0}\oplus b_{0},a_{1}\oplus b_{1},b_{1})$ ואז מחשבים את ${\tilde {Z}}_{0}$ ו- ${\tilde {Z}}_{1}$ כמו בשלב אחד ובודקים אם מתקיים $Z'={\tilde {Z}}_{0}\oplus {\tilde {Z}}_{1}$ . בדרך זו לאחר בדיקה מקיפה עם מספר זוגות טקסטים ידועים אפשר לשחזר את תת-המפתח $K_{3}$ או לפחות לנחש מספר קטן של מועמדים אפשריים ואז אפשר לעבור לשלב הבא של שחזור תת-המפתח $K_{2}$ וכן $K_{1},K_{4},K_{5}$ עד שמנחשים את כל המפתח. בכל שלב נעזרים בניחוש תת-המפתח מהשלב הקודם כדי לנחש את הקלט והפלט של הפונקציה הפנימית.

ההתקפה המתוארת מצליחה בפקטור של $2^{17}$ בקירוב עם ארבעה טקסטים גלויים ידועים בלבד ואינה אורכת יותר ממספר שניות על מחשב פשוט כך שגרסת FEAL-4 אינה ראויה לשימוש כלל. ההתקפה הדיפרנציאלית הורחבה ויושמה נגד כל גרסאות FEAL ונמצא שבכולן היא מצליחה בפקטור עבודה שהוא נמוך מכוח גס, למעט גרסת FEAL-NX כאשר $N>32$ , אולם בשל העובדה שפגיעות הצופן להתקפה זו מעידה על פגם מהותי בתכנונו, השימוש בכל הגרסאות שלו נזנח עקב כך.

ראו גם

הערות שוליים

^ Introduction to FEAL, NTT 1990
^ Cryptanalysis of F.E.A.L. Bert den Boer, Spnnger-Verlag Berlin Heidelberg 1988
^ THE CRYPTANALYSIS OF FEAL WITH TWENTY CHOSEN PLAINTEXTS, Sean Murphy, January 1990
^ Differential Cryptanalysis of Feal and N-Hash, Eli Biham, Adi Shamir, Spnnger-Verlag Berlin Heidelberg 1991
^ A Known Plaintext Attack of FEAL-4 and FEAL-6, Anne Tardy-Corfdir, Henri Gilbert, May 2001
^ A New Method for Known Plaintext Attack of FEAL Cipher, Mitsuru Matsui, Atsuhiro Yamagishi, May 2001
^ Applied Cryptanalysis: Breaking Ciphers in the Real World, Mark Stamp, Richard M. Low, Apr 2007, Wiley-IEEE Press

[1] Introduction to FEAL, NTT 1990

[2] Cryptanalysis of F.E.A.L. Bert den Boer, Spnnger-Verlag Berlin Heidelberg 1988

[3] THE CRYPTANALYSIS OF FEAL WITH TWENTY CHOSEN PLAINTEXTS, Sean Murphy, January 1990

[4] Differential Cryptanalysis of Feal and N-Hash, Eli Biham, Adi Shamir, Spnnger-Verlag Berlin Heidelberg 1991

[5] A Known Plaintext Attack of FEAL-4 and FEAL-6, Anne Tardy-Corfdir, Henri Gilbert, May 2001

[6] A New Method for Known Plaintext Attack of FEAL Cipher, Mitsuru Matsui, Atsuhiro Yamagishi, May 2001

[7] Applied Cryptanalysis: Breaking Ciphers in the Real World, Mark Stamp, Richard M. Low, Apr 2007, Wiley-IEEE Press

[1]

[2]

[3]

[4]

[5]

[6]

[7]