כיוון שקריפטואנליזה דיפרנציאלית הייתה ידועה למדעני IBM בעת פיתוח תקן DES הם הקפידו שהתקן יהיה עמיד באופן יחסי בפני מתקפה זו. יתרה מזו, ידוע שללא ערכי תיבות ההחלפה שנבחרו על ידיים, צופן DES היה חלש מאוד. מאידך, צפנים אחרים בני התקופה שלא היו מודעים לשיטה היו רגישים למתקפה זו.
השיטה.
קריפטואנליזה דיפרנציאלית בגרסה הבסיסית מנצלת את ההסתברות הגבוהה של מופעים מסוימים של דיפרנציאלים בין זוגות בלוקים בפלט הצופן (ליתר דיוק בקלט לסבב האחרון של הצופן) בהינתן דיפרנציאלים של בלוקים גלויים מסוימים בקלט הצופן. המושג דיפרנציאל פירושו שאם למשל נתונה פונקציה formula_1 המקבלת קלט formula_2 באורך formula_3 סיביות; formula_4 ומפיקה פלט formula_5. אם נסמן שני קלטים אפשריים לפונקציה ב-formula_6 ו-formula_7 בהתאמה וכן הפלטים המתאימים להם ב-formula_8 ו-formula_9 בהתאמה, כלומר formula_10 וכן formula_11. אז הדיפרנציאל של הקלט (או ההפרש) הוא formula_12 כאשר הסימן formula_13 מייצג חיבור XOR של וקטורים באורך formula_3 סיביות. לכן,
האיברים formula_17 ו-formula_18 מייצגים את הסיביות במיקום ה-formula_19 של formula_6 ו-formula_7 בהתאמה. באופן דומה formula_22 הוא הדיפרנציאל של הפלט ולכן
בצופן אידיאלי המתנהג באופן אקראי לגמרי, ההסתברות שדיפרנציאל פלט מסוים formula_25 יופיע בהינתן דיפרנציאל קלט מסוים formula_26 אמורה להיות formula_27 כאשר formula_3 מייצג את מספר הסיביות של formula_2. אולם במציאות אין זה כך ולכן הקרפיטואנליזה הדיפרנציאלית מחפשת את המקרים בהם דיפרנציאל פלט מסוים מופיע בשכיחות גבוהה יותר בהינתן דיפרנציאל קלט מסוים. אם ההסתברות הדיפרנציאלית של הצופן שמקובל לסמנה ב-formula_30 גבוהה באופן משמעותי מ-formula_27 אפשר יהיה באמצעותה לפצח את הצופן.
בתחילה המתקיף מחפש זוגות קלט/פלט המניבים דיפרנציאל הגבוה ביותר האפשרי. כדי להצליח בכך עליו תחילה לאסוף מידע על הצופן. המושג הראשון שצריך לחשב הוא מאפיין דיפרנציאלי של הצופן. אם נתון צופן בלוקים כלשהו כמו DES הבנוי בסגנון רשת החלפה-תמורה ונניח שהקלט לצופן שהוא בלוק טקסט גלוי מסומן ב-formula_2 והקלט לסבב האחרון של הצופן מסומן ב-formula_33. המטרה היא למצוא טקסט כלשהו או קבוצת טקסטים כאלה שהדיפרנציאל שלהם (formula_34) הוא בהסתברות גבוהה. המאפיין הדיפרנציאלי של הצופן הוא למעשה כפולה של כל ההסתברויות של סדרת הפרשי קלט/פלט הפונקציה הפנימית במעברים של כל סבבי הצופן כך שדיפרנציאל הפלט של סבב אחד מתאים לדיפרנציאל הקלט של הסבב הבא וכן הלאה. מאפיין דיפרנציאלי בעל הסתברות גבוהה מעניק למתקיף את הרמז הדרוש כדי לחשוף חלק מסיביות המפתח מהסבב האחרון. זאת על ידי השוואה בין קלטים אפשריים לסבב האחרון ובדיקת הדיפרנציאל שלהם עבור סיביות מפתח שונות שהוא מנסה לנחש. כאשר מופיע דיפרנציאל גבוה הדבר מעיד כי ניחוש הסיביות הצליח בהסתברות גבוהה.
כדי לבנות מאפיין דיפרנציאלי של צופן שהוא גבוה ככל האפשר, צריך לבחון תחילה את המאפיינים של כל תיבות ההחלפה של הצופן בנפרד ואז לאסוף מספיק נתונים כדי לבנות את הדיפרנציאל של הצופן בכללותו. המתקיף בוחן את דיפרנציאל קלט/פלט של כל תיבת החלפה ומתמקד בעיקר בדיפרנציאלים בעלי הסתברות גבוהה (המופיעים בשכיחות גבוהה יותר מהאחרים באופן משמעותי) ואז משלב יחד את הדיפרנציאלים של תיבות ההחלפה מסבב לסבב כך שדיפרנציאל סיביות פלט שאינן אפס מסבב אחד מתאים לדיפרנציאל סיביות קלט שאינן אפס בסבב הבא. כתוצאה מכך נוצר מצב שסיביות תת-המפתחות המעורבות בהצפנה של זוגות אילו נעלמות מביטויי הדיפרנציאלים. הסיבה לכך נעוצה בפעולת XOR. היות שהמפתח קבוע בכל הזוגות, סיביות המפתחות שמופיעות פעמיים ייעלמו כי XOR של כל ערך בעצמו שווה אפס, למשל אם נתונים formula_35 וכן formula_36 אז אם נבצע XOR בין שניהם יתקבל formula_37 ולא ישאר זכר מ-formula_38 כי
תיבות ההחלפה.
בכל צופן בלוקים במבנה רשת החלפה תמורה כמו DES או AES קיימות תיבות החלפה הקרויות S-box. תיבות ההחלפה הן בעצם אוסף של פונקציות אי-ליניאריות קבועות (אי ליניאריות פירושה שלא ניתן לייצג את פלט הפונקציה כסדרה של פעולות כמו חיבור או כפל על הקלט). ההבדל בין תיבות ההחלפה של DES לעומת AES הוא שבאחרון התיבות הפיכות. בקריפטואנליזה דיפרנציאלית מתמקדים בחלק האי-ליניארי של הצופן, במקרה זה בתיבות ההחלפה. לדוגמה נתונה תיבת ההחלפה הבאה הלקוחה מצופן DES:
טבלה זו מייצגת פונקציה המקבלת קלט באורך 4 סיביות: formula_40 ומחזירה פלט באורך 4 סיביות: formula_41 מתוך formula_42 ערכים אפשריים, לפי הטבלה. לדוגמה אם הקלט הוא formula_43 או בבסיס הקסדצימלי formula_44 הפלט צריך להיות formula_45 או formula_46. אפשר לרשום זאת כסדרה של פונקציות: formula_47 או formula_48 וכן הלאה. אם רושמים את כל הדיפרנציאלים של זוגות אפשריים של קלט/פלט לתיבת ההחלפה הזו ההסתברות של formula_25 בהינתן formula_26 עבור זוג מסוים formula_51 וכן formula_52 מתקבלת על ידי ספירת כל המופעים שלהם חלקי formula_53. היות שהסדר אינו חשוב ויש רק 4 סיביות, במילים אחרות 16 אפשרויות לכן אפשר לרשום את כל 16 הערכים האפשריים של formula_6 ולהגביל את formula_7 שיהיה formula_56. ואז לחשב את ערכי formula_25 עבור כל זוג קלט (formula_58) אפשרי. את כל זה אפשר לסכם בטבלה, את הערכים הבינאריים של הקלט formula_2, הפלט formula_33 וכן ערכי formula_26 ו-formula_25 עבור ערכי formula_51. לדוגמה, הטבלה הבאה מכילה חלק מהנתונים הללו עבור תיבת ההחלפה המתוארת. אפשר לראות שאם formula_64 אז formula_65 מופיע בשמונה מתוך 16 המקרים האפשריים, דהיינו בהסתברות של 8/16. כמו כן אם formula_66 אז formula_67 בהסתברות של 4/16. כמו כן רואים שבמקרה ש- formula_68 אז formula_69 לא מופיע אף פעם (הסתברות אפס). אילו תיבת ההחלפה הייתה אידיאלית אז כל הערכים בטבלה היו אמורים להופיע בהסתברות של formula_70 אולם מסתבר שמצב כזה בלתי אפשרי מבחינה מתמטית, כלומר לא קיימת תיבת החלפה באורך 4 סיביות שהדיפרנציאלים שלה הם formula_71 עבור כל המופעים.
את כל המידע האמור מסכמים בטבלת התפלגות דיפרנציאלית שבה השורות מייצגות את formula_26 והעמודות את formula_25. להמחשה מובאת טבלת ההתפלגות הדיפרנציאלית של תיבת ההחלפה של DES מהדוגמה לעיל. אפשר לראות שלמעט המקרה יוצא הדופן של formula_74 הערך הגבוה ביותר הוא 8 המתאים ל-formula_75 ו-formula_76. לכן ההסתברות של הדיפרנציאל formula_76 בהינתן כל זוג אפשרי של קלט המקיים formula_75 היא 8/16. הערך הנמוך ביותר הוא 0 שמתאים לכל המקרים בהם formula_25 אינו מופיע אף פעם בהינתן formula_26. סכום כל האיברים בכל שורה בטבלה הוא formula_42 וכן בכל העמודות. כמו כן רואים שכל הערכים זוגיים, הסיבה היא היות שהסדר אינו חשוב לכן הדיפרנציאל של formula_82 שווה לדפירנציאל של formula_83. כמו כן הערך בפינה הימנית העליונה הוא תמיד formula_42 וכל הערכים האחרים בשורה זו ובעמודה זו הם 0 כנדרש.
היות שהצופן מכיל בדרך כלל מספר תיבות החלפה שונות וכן מספר סבבים כאשר בכל סבב מופעלות תיבות החלפה אחרות, יש צורך לסכם את הדיפרנציאלים של כל תיבות ההחלפה הפעילות באותה דרך ואז לשלב את הדיפרנצאלים של הזוגות בכולן כדי לקבל את "המאפיין הדיפרנציאלי" של הצופן. כשאומרים תיבת החלפה פעילה מתכוונים לתיבת החלפה שדיפרנציאל הפלט שלה אינו בהסתברות אפס. למרות שמפתח ההצפנה שונה מתיבה לתיבה ומסבב לסבב אפשר להוכיח באופן ישיר שכאשר הדיפרנציאל הוא מעל XOR אין למפתח כל השפעה על דיפרנציאלים של הזוגות, בגלל התכונה המהותית של פעולה זו שהיא הופכית של עצמה ולכן אם ערך מסוים מופיע פעמיים הוא מתבטל. כדי להדגים את חישוב המאפיין הדיפרנציאלי של הצופן נניח למען הפשטות שקיימות 4 תיבות החלפה וישנם ארבעה סבבים בסך הכול וקלט הצופן הוא בלוק באורך 16 סיביות (כל תיבה מקבלת 4 סיביות ממנו). למען הנוחות כל תיבה מסומנת במספר מ-1 עד 4 וכל סבב מסומן בהתאם מ-1 עד 4 לכן התיבה formula_85 פירושה תיבת ההחלפה הראשונה בסבב השלישי של הצופן. נבחן לצורך ההמחשה (כמתואר בתרשים משמאל) את מסלול הדיפרנציאלים של הסיביות במיקומים 5, 7 ו-8 של הקלט במעבר בתיבות המסומנות ב-formula_86 (התיבה השנייה בסבב הראשון, השלישית בסבב השני והתיבות השנייה והשלישית בסבב השלישי) וכן במעבר דרך התמורות הבאות אחריהן. יש לשים לב שהמאפיין הדיפרנציאלי המתקבל כאן הוא של שלושה סבבים בלבד ולא של מלוא ארבעת הסבבים של הצופן. כיוון שאילו תיבות ההחלפה הפעילות היחידות עבור פוזיציות אילו של הקלט, הדיפרנציאל בכל התיבות האחרות יהיה 0. נניח שהדיפרנציאלים של תיבות ההחלפה התקבלו לפי הפירוט הבא:
דיפרנציאל הקלט של הצופן הוא הדיפרנציאל של הקלט בסבב הראשון של הצופן לפני הכניסה לתיבת ההחלפה הראשונה. בהסתמך על ניתוח הדיפרנציאלים של תיבת ההחלפה המתוארת מתקבל: