קריפטואנליזה דיפרנציאלית
השיטה > תיבות ההחלפה

בכל צופן בלוקים במבנה רשת החלפה תמורה כמו DES או AES קיימות תיבות החלפה הקרויות S-box. תיבות ההחלפה הן בעצם אוסף של פונקציות אי-ליניאריות קבועות (אי ליניאריות פירושה שלא ניתן לייצג את פלט הפונקציה כסדרה של פעולות כמו חיבור או כפל על הקלט). ההבדל בין תיבות ההחלפה של DES לעומת AES הוא שבאחרון התיבות הפיכות. בקריפטואנליזה דיפרנציאלית מתמקדים בחלק האי-ליניארי של הצופן, במקרה זה בתיבות ההחלפה. לדוגמה נתונה תיבת ההחלפה הבאה הלקוחה מצופן DES:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| קלט | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
| פלט | E | 4 | D | 1 | 2 | F | B | 8 | 3 | A | 6 | C | 5 | 9 | 0 | 7 |
טבלה זו מייצגת פונקציה המקבלת קלט באורך 4 סיביות:  X=[X_{1}X_{2}X_{3}X_{4}] ומחזירה פלט באורך 4 סיביות:  Y=[Y_{1}Y_{2}Y_{3}Y_{4}] מתוך  2^{n}=16 ערכים אפשריים, לפי הטבלה. לדוגמה אם הקלט הוא  1100 או בבסיס הקסדצימלי  {\text{0xC}} הפלט צריך להיות  0101 או  {\text{0x5}}. אפשר לרשום זאת כסדרה של פונקציות:  F({\text{0xC}})={\text{0x5}} או  F({\text{0x2}})={\text{0xD}} וכן הלאה. אם רושמים את כל הדיפרנציאלים של זוגות אפשריים של קלט/פלט לתיבת ההחלפה הזו ההסתברות של  \Delta Y בהינתן  \Delta X עבור זוג מסוים  X',X'' וכן  Y',Y'' מתקבלת על ידי ספירת כל המופעים שלהם חלקי  2^{n}. היות שהסדר אינו חשוב ויש רק 4 סיביות, במילים אחרות 16 אפשרויות לכן אפשר לרשום את כל 16 הערכים האפשריים של  X' ולהגביל את  X'' שיהיה  X''=X'\oplus \Delta X. ואז לחשב את ערכי  \Delta Y עבור כל זוג קלט ( X',X''=X'\oplus \Delta X) אפשרי. את כל זה אפשר לסכם בטבלה, את הערכים הבינאריים של הקלט  X, הפלט  Y וכן ערכי  \Delta X ו- \Delta Y עבור ערכי  X',X''. לדוגמה, הטבלה הבאה מכילה חלק מהנתונים הללו עבור תיבת ההחלפה המתוארת. אפשר לראות שאם  \Delta X=1011 אז  \Delta Y=0010 מופיע בשמונה מתוך 16 המקרים האפשריים, דהיינו בהסתברות של 8/16. כמו כן אם  \Delta X=1000 אז  \Delta Y=1011 בהסתברות של 4/16. כמו כן רואים שבמקרה ש-  \Delta X=0100 אז  \Delta Y=1010 לא מופיע אף פעם (הסתברות אפס). אילו תיבת ההחלפה הייתה אידיאלית אז כל הערכים בטבלה היו אמורים להופיע בהסתברות של  1/2^{n}=1/16 אולם מסתבר שמצב כזה בלתי אפשרי מבחינה מתמטית, כלומר לא קיימת תיבת החלפה באורך 4 סיביות שהדיפרנציאלים שלה הם  1/16 עבור כל המופעים.
| X | Y |  \Delta Y>  \Delta X=1011 |  \Delta Y>  \Delta X=1000 |  \Delta Y>  \Delta X=0100 |
| --- | --- | --- | --- | --- |
| 0000 | 1110 | 0010 | 1101 | 1100 |
| 0001 | 0100 | 0010 | 1110 | 1011 |
| 0010 | 1101 | 0111 | 0101 | 0110 |
| 0011 | 0001 | 0010 | 1011 | 1001 |
| 0100 | 0010 | 0101 | 0111 | 1100 |
| 0101 | 1111 | 1111 | 0110 | 1011 |
| 0110 | 1011 | 0010 | 1011 | 0110 |
| 0111 | 1000 | 1101 | 1111 | 1001 |
| 1000 | 0011 | 0010 | 1101 | 0110 |
| 1001 | 1010 | 0111 | 1110 | 0011 |
| 1010 | 0110 | 0010 | 0101 | 0110 |
| 1011 | 1100 | 0010 | 1011 | 1011 |
| 1100 | 0101 | 1101 | 0111 | 0110 |
| 1101 | 1001 | 0010 | 0110 | 0011 |
| 1110 | 0000 | 1111 | 1011 | 0110 |
| 1111 | 0111 | 0101 | 1111 | 1011 |
את כל המידע האמור מסכמים בטבלת התפלגות דיפרנציאלית שבה השורות מייצגות את  \Delta X והעמודות את  \Delta Y. להמחשה מובאת טבלת ההתפלגות הדיפרנציאלית של תיבת ההחלפה של DES מהדוגמה לעיל. אפשר לראות שלמעט המקרה יוצא הדופן של  \Delta X=0,\Delta Y=0 הערך הגבוה ביותר הוא 8 המתאים ל- \Delta X=B ו- \Delta Y=2. לכן ההסתברות של הדיפרנציאל  \Delta Y=2 בהינתן כל זוג אפשרי של קלט המקיים  \Delta X=B היא 8/16. הערך הנמוך ביותר הוא 0 שמתאים לכל המקרים בהם  \Delta Y אינו מופיע אף פעם בהינתן  \Delta X. סכום כל האיברים בכל שורה בטבלה הוא  2^{n}=16 וכן בכל העמודות. כמו כן רואים שכל הערכים זוגיים, הסיבה היא היות שהסדר אינו חשוב לכן הדיפרנציאל של  (X',X'') שווה לדפירנציאל של  (X'',X'). כמו כן הערך בפינה הימנית העליונה הוא תמיד  2^{n}=16 וכל הערכים האחרים בשורה זו ובעמודה זו הם 0 כנדרש.
|  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 16 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 2 | 0 | 2 | 4 | 0 | 4 | 2 | 0 | 0 |
| 2 | 0 | 0 | 0 | 2 | 0 | 6 | 2 | 2 | 0 | 2 | 0 | 0 | 0 | 0 | 2 | 0 |
| 3 | 0 | 0 | 2 | 0 | 2 | 0 | 0 | 0 | 0 | 4 | 2 | 0 | 2 | 0 | 0 | 4 |
| 4 | 0 | 0 | 0 | 2 | 0 | 0 | 6 | 0 | 0 | 2 | 0 | 4 | 2 | 0 | 0 | 0 |
| 5 | 0 | 4 | 0 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 4 | 0 | 2 | 0 | 0 | 2 |
| 6 | 0 | 0 | 0 | 4 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 2 | 2 | 2 |
| 7 | 0 | 0 | 2 | 2 | 2 | 0 | 2 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 0 | 4 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 2 | 0 | 0 | 0 | 4 | 0 | 4 | 2 | 2 |
| 9 | 0 | 2 | 0 | 0 | 2 | 0 | 0 | 4 | 2 | 0 | 2 | 2 | 2 | 0 | 0 | 0 |
| A | 0 | 2 | 2 | 0 | 0 | 0 | 0 | 0 | 6 | 0 | 0 | 2 | 0 | 0 | 4 | 0 |
| B | 0 | 0 | 8 | 0 | 0 | 2 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 2 | 0 | 2 |
| C | 0 | 2 | 0 | 0 | 2 | 2 | 2 | 0 | 0 | 0 | 0 | 2 | 0 | 6 | 0 | 0 |
| D | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 4 | 2 | 0 | 2 | 0 | 2 | 0 | 2 | 0 |
| E | 0 | 0 | 2 | 4 | 2 | 0 | 0 | 0 | 6 | 0 | 0 | 0 | 0 | 0 | 2 | 0 |
| F | 0 | 2 | 0 | 0 | 6 | 0 | 0 | 0 | 0 | 4 | 0 | 2 | 0 | 0 | 2 | 0 |
היות שהצופן מכיל בדרך כלל מספר תיבות החלפה שונות וכן מספר סבבים כאשר בכל סבב מופעלות תיבות החלפה אחרות, יש צורך לסכם את הדיפרנציאלים של כל תיבות ההחלפה הפעילות באותה דרך ואז לשלב את הדיפרנצאלים של הזוגות בכולן כדי לקבל את "המאפיין הדיפרנציאלי" של הצופן. כשאומרים תיבת החלפה פעילה מתכוונים לתיבת החלפה שדיפרנציאל הפלט שלה אינו בהסתברות אפס. למרות שמפתח ההצפנה שונה מתיבה לתיבה ומסבב לסבב אפשר להוכיח באופן ישיר שכאשר הדיפרנציאל הוא מעל XOR אין למפתח כל השפעה על דיפרנציאלים של הזוגות, בגלל התכונה המהותית של פעולה זו שהיא הופכית של עצמה ולכן אם ערך מסוים מופיע פעמיים הוא מתבטל. כדי להדגים את חישוב המאפיין הדיפרנציאלי של הצופן נניח למען הפשטות שקיימות 4 תיבות החלפה וישנם ארבעה סבבים בסך הכול וקלט הצופן הוא בלוק באורך 16 סיביות (כל תיבה מקבלת 4 סיביות ממנו). למען הנוחות כל תיבה מסומנת במספר מ-1 עד 4 וכל סבב מסומן בהתאם מ-1 עד 4 לכן התיבה  S_{31} פירושה תיבת ההחלפה הראשונה בסבב השלישי של הצופן. נבחן לצורך ההמחשה (כמתואר בתרשים משמאל) את מסלול הדיפרנציאלים של הסיביות במיקומים 5, 7 ו-8 של הקלט במעבר בתיבות המסומנות ב- S_{12},S_{23},S_{32},S_{33} (התיבה השנייה בסבב הראשון, השלישית בסבב השני והתיבות השנייה והשלישית בסבב השלישי) וכן במעבר דרך התמורות הבאות אחריהן. יש לשים לב שהמאפיין הדיפרנציאלי המתקבל כאן הוא של שלושה סבבים בלבד ולא של מלוא ארבעת הסבבים של הצופן. כיוון שאילו תיבות ההחלפה הפעילות היחידות עבור פוזיציות אילו של הקלט, הדיפרנציאל בכל התיבות האחרות יהיה 0. נניח שהדיפרנציאלים של תיבות ההחלפה התקבלו לפי הפירוט הבא:
דיפרנציאל הקלט של הצופן הוא הדיפרנציאל של הקלט בסבב הראשון של הצופן לפני הכניסה לתיבת ההחלפה הראשונה. בהסתמך על ניתוח הדיפרנציאלים של תיבת ההחלפה המתוארת מתקבל:
שהוא הדיפרנציאל הכי שכיח.  U_{i} מייצג את הקלט של תיבות ההחלפה בסבב ה- i. כמו כן  V_{i} מייצג את הפלט של תיבות ההחלפה בסבב ה- i בהתאמה. לכן  \Delta U_{i} ו- \Delta V_{i} מייצגים את הדיפרנציאלים שלהם בהתאמה. כתוצאה מכך  \Delta V_{1}=[0000\ 0010\ 0000\ 0000]. אם ממשיכים בסגנון זה בונים את הדיפרנציאלים של כל סבב וסבב כך ש- \Delta V_{i}=\Delta U_{i-1}. כמובן שיש להביא בחשבון גם את התמורה המבוצעת בכל סבב של רשת ההחלפה תמורה (היות שהתמורה ליניארית היא משפיעה רק על מיקום הסיביות המושפעות). אם בודקים את הדיפרנציאל עבור התיבה  S_{12} והתמורה שאחריה מגיעים ל:
בהסתברות של  8/16 או  1/2 בהינתן  \Delta P. בסבב השני הדיפרנציאל עבור התיבה  S_{23} הוא
ואחרי התמורה של הסבב השני מתקבל:
בהסתברות של  6/16 בהינתן  \Delta U_{2} או בהסתברות של  1/2\times 6/16=3/16 בהינתן  \Delta P. שוב, בהנחה שהדיפרנציאלים בלתי תלוים. באותה דרך אפשר לחשב את הדיפרנציאל עבור הסבב השלישי בתיבות ההחלפה  S_{32} ו- S_{33} ולאחר התמורה השלישית ומתקבל:
וכן
בהסתברות של  (6/16)^{2} בהינתן  \Delta U_{3}. אם מכפילים את כל ההסתברויות מתקבל המאפיין הדיפרנציאלי של הצופן עד נקודה זו, במקרה זה  8/16\times 6/16\times (6/16)^{2}=27/1024 (בהינתן  \Delta P). וזהו המאפיין הדיפרנציאלי של הצופן לאחר  R-1 מתוך  R סבבים (בדוגמה זו  R=4). כשההנחה בכל הדרך היא שהדיפרנציאלים של כל תיבות ההחלפה בכל הסבבים הם בלתי תלויים זה בזה. בשלב זה של ההתקפה על הצופן מצפינים בלוקים רבים שלהם הדיפרנציאל  \Delta P=[0000\ 1011\ 0000\ 0000] ואז בהסתברות גבוהה, במקרה זה  27/1024 המאפיין הדיפרנציאלי יופיע. כל זוג שאיתו מתקבל  \Delta P נקרא זוג נכון וכל זוג אחר שבו המאפיין האמור אינו מתקבל נקרא זוג לא נכון.
בשלב הבא של ההתקפה מנסים לנחש את המפתח ששימש להצפנת הנתונים בסבב האחרון של הצופן. הרעיון הוא שבמקום לנסות לנחש את כל סיביות המפתח שזה לא מעשי מנסים לנחש רק את הסיביות שהושפעו מהדיפרנציאלים של פלט תיבות ההחלפה הפעילות של הסבב האחרון הנקראות בקיצור TPS (מפתח יעד חלקי). מפענחים חלקית (רק סבב אחד של הצופן) את זוגות הטקסטים המוצפנים המתאימים לזוגות הגלויים שהוצפנו (עם הדיפרנציאל  \Delta P) עבור כל סיביות היעד (TPS) האפשריות ומנהלים מונה עבור כל זוג כזה שמקודם כאשר הדיפרנציאל של הקלט לסבב האחרון קרוב לערך הצפוי (שהוא המאפיין הדיפרנציאלי של הצופן). סיביות היעד של המפתח האחרון אשר מניבות דיפרנציאל גבוה הן בסבירות גבוהה חלק מהמפתח הסודי. היות שההנחה היא שהסיביות הנכונות אמורות להניב דיפרנציאל (של הקלט לסבב האחרון) קרוב מאוד לערך הצפוי. היות שהמאפיין הדיפרנציאלי הוא בעל הסתברות גבוהה, כל זוג ערכים שאינו נכון אמור להניב תוצאה אקראית פחות או יותר ולכן הדיפרנציאל שלה אמור להיות נמוך מאוד. המאפיין הדיפרנציאלי נקרא גם מבחין, כי בעזרתו ניתן להבחין אם נבחר זוג נכון או לא ובכך מתאפשר להבחין אם ניחוש סיביות המפתח הצליח. כי בניחוש נכון יתקבל דיפרנציאל בעל הסתברות גבוהה שהיא קרובה מאוד למאפיין הדיפרנציאלי של הצופן עד נקודה זו ואילו אם הניחוש אינו נכון יתקבל דיפרנציאל בעל הסתברות מאוד נמוכה.
בנוסף אפשר לייעל את ההתקפה אם לא כל תיבות ההחלפה משפיעות על הקלט. למשל בדוגמה המובאת רק שתי תיבות משפיעות על הנתונים של הצופן בסבב השלישי, לכן, היות שהדיפרנציאל של הקלט לסבב האחרון עבור זוג נכון הוא אפס בשתי התיבות האחרות (הלא פעילות), אפשר לפשוט להתעלם מכל הזוגות שבהן לא מופיעים אפסים בדיפרנציאל המתאים לפוזיציות בתיבות אילו. בדוגמה המובאת אפשר לפצח את הצופן בעזרת התהליך המתואר על ידי 5000 זוגות של קלט/פלט נבחרים, דהיינו 10000 הצפנות עם זוגות קלט שהדיפרנציאל שלהם הוא  \Delta P=[0000\ 1011\ 0000\ 0000]. וסיביות היעד הנכונות הן במקרה זה  [K_{5,5}...K_{5,8},K_{5,13}...K_{5,16}]=[0010,0100]=[{\text{0x2}},{\text{0x4}}]. בדוגמה זו המאפיין הדיפרנציאלי של הצופן הוא  27/1024=0.0264 ובניסוי ותהיה התגלה שסיביות היעד הנכונות הניבו תוצאה של  0.0244 שזה די קרוב.