קריפטואנליזה ליניארית
תיאור כללי > ניחוש סיביות מפתח

לאחר שהתגלה הקירוב הליניארי הכולל של  R-1 מתוך  R הסבבים של הצופן, עם הטיה הסתברותית משמעותית, עוברים לשלב ניחוש סיביות תת-המפתח האחרון על ידי חישוב לאחור. ביתר פירוט, תחילה מנסים את כל האפשרויות של המפתח האחרון ( K_{5} במקרה זה) ומחברים אותם ב-XOR עם הבלוק המוצפן, ואז מבצעים פענוח חלקי (העברה בתיבות ההחלפה של הסבב האחרון) של הבלוק שהתקבל. פעולה זו מתבצעת עבור כל זוגות הבלוקים גלויים/מוצפנים שנמצאים בידי המתקיף. שומרים מונה שמקודם בכל פעם שהתקבל ערך המקיים את הצירוף הליניארי של התיבות מהסבב האחרון (יש לזכור שהבלוק הגלוי ידוע). כל ניחוש סיביות מפתח שהמונה שלו גבוה או נמוך ממחצית מזוגות הקלט/פלט שבידי המתקיף בשיעור משמעותי הדבר נחשב לניחוש מוצלח. ניחוש לא נכון אמור לתת תוצאה אקראית ולכן המשוואה האמורה תתקיים בהסתברות קרובה לחצי.
בצופן הצעצוע המובא להמחשה, הצירוף הליניארי האחרון משפיע על הפלט לתיבות  S_{42} ו- S_{44} של הסבב האחרון. כיוון שכל תיבה מכילה 4 סיביות בסך הכול 8 זה אומר שעבור כל זוג קלט/פלט מנסים את כל 256 צירופי סיביות של המפתח  K_{5} במקטעים  [K_{5,5}...K_{5,8},K_{5,13}...K_{5,16}] (יתר סיביות המפתח אינן משפיעות כי שתי תיבות אילו היו התיבות הפעילות היחידות בסבב זה). עבור כל ניחוש מפתח חלקי כזה, מקדמים מונה כלשהו אם המשוואה האחרונה התקיימה. הזוגות שלהם המונה הגבוה ביותר (שלילי או חיובי) מרמזות על ניחוש מוצלח בהסתברות גבוהה. המשוואה האחרונה (הצירוף הליניארי של הצופן) משפיעה על התוצאה בהתאם למפתח. אם ערכן של סיביות המפתח בפוזיציות הללו הוא  \textstyle \sum _{K}=0 אז המשואה תתקיים בהסתברות גבוהה מחצי ואילו אם  \textstyle \sum _{K}=1 המשוואה תתקיים בהסתברות נמוכה מחצי. את צופן הצעצוע המתואר אפשר לתקוף עם 10,000 זוגות קלט/פלט ידועים, ולפי תיאור ההתקפה עד כה, התגלה ניחוש מוצלח של סיביות תת-המפתח  [K_{5,5}...K_{5,8}]=[0010] וכן  [K_{5,13}...K_{5,16}]=[0100]. ואכן המונה עבור סיביות אילו  [2,4] בבסיס הקסדצימלי כצפוי היה גבוה משמעותית מ-5,000. הטבלה הבאה מכילה להמחשה, אוסף חלקי מתוך 256 האפשרויות. ערכים אילו מייצגים את שיעור ההטיה לפי החשבון האמור, "הטיה = מונה פחות חצי לחלק למספר הזוגות". כאשר המונה מתייחס לניחוש מסוים של 8 סיביות מהמפתח. אפשר לראות שההטיה הגבוהה ביותר מופיעה כאשר הניחוש הוא 2,4.
| קטע תת-המפתח>  [K_{5,5}...K_{5,8},K_{5,13}...K_{5,16}] | הטיה>  | קטע תת-המפתח>  [K_{5,5}...K_{5,8},K_{5,13}...K_{5,16}] | הטיה>  |
| --- | --- | --- | --- |
| 1C | 0.0031 | 2A | 0.0044 |
| 1D | 0.0078 | 2B | 0.0186 |
| 1E | 0.0071 | 2C | 0.0094 |
| 1F | 0.0170 | 2D | 0.0053 |
| 20 | 0.0025 | 2E | 0.0062 |
| 21 | 0.0220 | 2F | 0.0133 |
| 22 | 0.0211 | 30 | 0.0027 |
| 23 | 0.0064 | 31 | 0.0050 |
| 24 | 0.0336 | 32 | 0.0075 |
| 25 | 0.0106 | 33 | 0.0162 |
| 26 | 0.0096 | 34 | 0.0218 |
| 27 | 0.0074 | 35 | 0.0052 |
| 28 | 0.0224 | 36 | 0.0056 |
| 29 | 0.0054 | 37 | 0.0048 |
הערך  0.0336 בשורה 9 בטבלה שהתגלה במהלך הניסוי, קרוב מאוד לערך הצפוי של  1/32=0.03125. למרות שניחוש נכון תמיד יהיה בעל הטיה גבוהה ביותר, בכל זאת קיימים ערכים של ניחושים לא נכונים שמכילים הטיה גבוהה. מה שמעיד על כך שההשוואה של ניחושים נכונים אינה בדיוק השוואה של נתונים אקראיים מול משוואה ליניארית שאז ההטיה אמורה להיות אפס במצב אידיאלי. העובדה שזה לא קורה נובעת מכמה סיבות ביניהן מאפייני תיבות ההחלפה המשפיעות על הפענוח החלקי, אי דיוקים הנובעים מההנחה השגויה שהצירופים של תיבות ההחלפה בלתי תלויים זה בזה וכן מההשפעה של מה שקרוי "פרישה ליניארית" או "מעטפת ליניארית" ראה קבוצה פורשת.