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

קריפטואנליזה דיפרנציאלית פועלת לפי מודל התקפת גלוי-נבחר, כלומר המתקיף רשאי לבחור זוגות של טקסטים גלויים וטקסטים מוצפנים המתאימים להם שהוצפנו עם מפתח שאינו ידוע לו ותפקידו הוא לגלות את המפתח הסודי ששימש להצפנתם. המתקיף בוחר את הטקסטים באופן כזה שהדיפרנציאל (ההפרש) שלהם עונה על "מאפיין" מסוים המתאים לצורך ההתקפה. כאן הדיפרנציאל הוא מעל פעולת 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} המתוארות לעיל והיא נראית כך:
לצורך ההתקפה המתקיף בוחר טקסט גלוי אקראי  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) מחשבים את:
אם מתבוננים בהגדרה של  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, אולם בשל העובדה שפגיעות הצופן להתקפה זו מעידה על פגם מהותי בתכנונו, השימוש בכל הגרסאות שלו נזנח עקב כך.