קריפטואנליזה ליניארית

בקריפטואנליזה, קריפטואנליזה לִינֵאָרִית (באנגלית: Linear cryptanalysis) היא צורה כללית של קרפיטואנליזה המבוססת על ניתוח קירובים ליניאריים ואפיניים הכוללים שילוב סיביות מקלט פונקציית הצפנה סימטרית, מהפלט שלה וממפתח ההצפנה.

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

היסטוריה

הקריפטואנליזה הליניארית מיוחסת למיצורו מצואי, שפרסם אותה לראשונה ב-1992 יחד עם ימאגישי לפיצוח הצופן FEAL^[1] וכן נוסתה נגד צופן DES^[2] והייתה להתקפה הפומבית הראשונה על הצופן, אך היא דורשת מספר עצום של בלוקים ידועים ( $2^{43}$ זוגות במקרה של DES). קריפטואנליזה ליניארית מתאימה במיוחד נגד צופן בלוקים ואף נגד צופן זרם. ההתקפה הליניארית יחד עם הדיפרנציאלית הן שתי ההתקפות הקריפטוגרפיות המפורסמות והמוצלחות ביותר נגד צפני בלוקים מודרניים והביאו לשבירתם המוחלטת של לא מעט צפנים. כיום ההתקפה הליניארית משמשת כאבן בוחן וכלי שימושי לבדיקת ביטחון כל צופן בלוקים מודרני. כיום מצפים מכל צופן שיוכיח עמידות נגד התקפה זו אפילו אם היא תאורטית ביסודה אם היא יעילה מכוח גס באופן ניכר. למרות האמור, למרבה ההפתעה אפילו לאחר שנים של קריפטואנליזה, ההתקפה הליניארית נגד צופן DES התגלתה כלא יעילה במיוחד באופן מעשי. ועד היום DES שרד את שתי ההתקפות המתוארות, הליניארית והדיפרנציאלית כאחד.

וריאציות

במשך השנים פותחו מספר וריאציות של הקריפטואנליזה הליניארית ביניהן:

קריפטואנליזת קירובים ליניאריים מרובים^[3].
קריפטואנליזת מתאם אפס^[4].
קריפטואנליזת חציצה (Partitioning)^[5].

תיאור כללי

הקריפטואנליזה הליניארית מנסה לנצל קיום מופעים בהסתברות גבוהה של משוואות ליניאריות המערבות סיביות מבלוק הקלט, בלוק הפלט (ליתר דיוק מפלט הסבב האחד לפני אחרון של הצופן) ומפתח ההצפנה. הרעיון הבסיסי הוא לבצע קירוב של חלק מפעולת הצופן עם משוואה ליניארית מעל חיבור XOR (חיבור מודולו 2). משוואה ליניארית כזו יכולה להיות למשל:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{X_{i_1}\oplus X_{i_2}\oplus ...\oplus X_{i_u}\oplus Y_{j_1}\oplus Y_{j_2}\oplus ...\oplus Y_{j_v} = 0}}

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i} מייצג את הסיבית במיקום ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} של בלוק הקלט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X=[X_1,X_2,...,X_n]} המכיל $n$ סיביות וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y_j } מייצג את הסיבית במיקום ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} של בלוק הפלט הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y=[Y_1,Y_2,...,Y_n]} . המשוואה המתוארת מחברת תת-קבוצה באורך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} סיביות של $X$ עם תת-קבוצה באורך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} סיביות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y} . המטרה היא למצוא סיביות קלט/פלט שמקיימות את המשוואה האמורה בהסתברות גבוהה באופן משמעותי או בהסתברות נמוכה באופן משמעותי. באופן כללי אסור שלינאריות כזו תתרחש בצופן, אחרת הוא יהיה חלש מאד כי היא הוכחה לכך שהצופן מכיל אקראיות ירודה. באופן אידיאלי אם ננסה להזין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle v+u} סיביות קלט/פלט שונות במשוואה המתוארת ההסתברות שהמשוואה תתקיים צריכה להיות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/2} . ככל שהסטייה או הנטאי בתוצאות גדולה מחצי כך קל יותר למנתח הצופן לשבור אותו. ההטייה בהקשר זה נקראת הטייה ליניארית הסתברותית אותה מסמנים ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_L} . ככל ששיעור ההטייה ההסתברותית הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle |p_{L}-1/2|} גדלה משמעותית כך קל יותר ליישם את ההתקפה הליניארית על הצופן.

ישנן מגוון דרכים לביצוע הקריפטואנליזה הלניארית. לצורך התיאור כאן נתייחס למה שמיצורו מצואי מכנה במאמר שלו אלגוריתם 1. למרות שבמשוואה הלניארית לעיל לא מופיעות סיביות ממפתח ההצפנה המותקף, האגף הימני במשוואה "0" כולל באופן עקיף סיביות מהמפתח שמיקומן ידוע אך לא ערכן. אם סכום הסיביות מהמפתח המשתתפות במשוואה הוא אפס, ההטייה תהיה עם סימן (פלוס או מינוס) זהה אילו המשוואה כללה סיביות מהמפתח (אם ההסתברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_L} התקבלה). אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_L=1} פירושו של דבר שהמשוואה המתוארת מייצגת את התנהגות הצופן בשלמות ולכן הצופן כנראה מכיל פגם חמור. אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_L=0} פירושו של דבר שהמשוואה המתוארת מייצגת פונקציה אפינית של הצופן, שגם זו אינדיקציה לתקלה חמורה. במקרה של XOR פונקציה אפינית היא בעצם המשלים של הפונקציה הליניארית, כך שבשני המקרים הצופן יהיה חשוף להתקפה ליניארית.

דוגמה לקריפטואנליזה ליניארית

לצורך המחשת הקריפטואנליזה הליניארית^[6], נניח שנתון צופן בלוקים פשוט המורכב מרשת החלפה-תמורה. הוא מקבל בלוק קלט באורך 16 סיבות (שני בתים), מעבד את הבלוק על ידי חזרה ארבע פעמים על פונקציה פנימית הכוללת בדומה ל-AES, שלוש שכבות; החלפה, תמורה וערבוב מפתח, כמתואר בתרשים משמאל. למרות שהצופן פשוט והוא מובא כאן להמחשה בלבד, ההתקפה הליניארית על צופן זה מספקת תובנה די טובה לגבי פעולתה נגד צפנים מודרניים מורכבים יותר.

לצורך הדיון נניח ששלב ההחלפה בצופן הצעצוע האמור כולל ארבע תיבות החלפה המקבלות 4 סיביות ומחזירות 4 סיביות. כל תיבת החלפה אפשר ליישם באמצעות טבלה פשוטה המכילה 16 ערכים באורך 4 סיביות כל אחד. הערך המוחזר הוא בעצם תוכן הכניסה שהקלט מייצג את מספרה. ברוב הצפנים קיימות מספר טבלאות, לצורך הפשטות נניח שקיימת רק תיבה אחת כזו שבה משתמשים ארבע פעמים בכל סבב. להלן הטבלה הלקוחה מצופן DES בייצוג הקסדצימלי:

קלט	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

לצורך שלב הטרנספוזיציה (תמורה) נתונה הטבלה הבאה. פעולת הטרנספוזיציה ניתנת לתיאור באופן הבא: הפלט בפוזיציה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} של תיבת ההחלפה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} מנותב לכניסה ה- $j$ של תיבת ההחלפה ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} (בסבב הבא). ראוי לציין שאין טעם בטרנספוזיציה בסבב האחרון של הצופן כי היא ניתנת להפיכה בקלות.

קלט	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
פלט	0	4	8	C	1	5	9	C	2	6	A	D	3	7	B	F

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

קובץ:Linear analysis example-01.png

עיקרון הערמה

מציאת משוואה ליניארית של הצופן מסתמכת על צירוף משוואות ליניאריות של חלקים שונים של הצופן למשוואה ליניארית אחת. החלק הקשה הוא למצוא ולצרף משוואות ליניאריות מתאימות. לצורך ההדגמה נתייחס לצופן הצעצוע המתואר לעיל. אם נתונים שני משתנים מקריים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_2} , אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1\oplus X_2=0} הוא ביטוי ליניארי השקול ל-הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle X_{1}=X_{2}} . אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1\oplus X_2=1} זהו ביטוי אפיני השקול ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1\ne X_2} . נניח שההתפלגות הסטטיסטית נתונה על ידי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_1=i]= \begin{cases} p_1, & i=0 \\ 1-p_1, & i=1 \end{cases}}

וכן

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_2=i]= \begin{cases} p_2, & i=0 \\ 1-p_2, & i=1 \end{cases}}

אם שני המשתנים המקריים בלתי תלויים אפשר לשלב את שניהם ביחד:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_1=i,X_2=j]= \begin{cases} p_1p_2, & i=0,j=0 \\ p_1(1-p_2), & i=0,j=1 \\ (1-p_1)p_2, & i=1,j=0 \\ (1-p_1)(1-p_2), & i=1,j=1 \end{cases}}

וכן אפשר להוכיח ש-

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_1\oplus X_2=0]\ =\Pr[X_1=X_2]}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \, \, \, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\Pr[X_1=0,X_2=0]+\Pr[X_1=1,X_2=1]}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \, \, \, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =p_1p_2+(1-p_1)(1-p_2)} .

דרך אחרת להציג זאת, יהיו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_1=1/2+\varepsilon_1} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_2=1/2+\varepsilon_2} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon_1} ו- $\varepsilon _{2}$ הן שיעור ההטייה ההסתברותיות מחצי כך שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/2\le\varepsilon_1} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon_2\le +1/2} . מזה נובע ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_1\oplus X_2=0]=1/2+2\varepsilon_1\varepsilon_2} . ההטייה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1\oplus X_2=0} היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon_{1,2}=2\varepsilon_1\varepsilon_2} . אפשר להרחיב את האמור ליותר משתנים מקריים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1} עד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_n} עם ההסתברויות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_1=1/2+\varepsilon_1} עד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_n=1/2+\varepsilon_n} . ההסתברות ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1\oplus X_2\oplus ...\oplus X_n=0} תתקיים ניתנת לחישוב באמצעות למת הערמה (Piling-Up Lemma) של מיצורו מצואי, בהנחה שכל המשתנים בלתי תלויים:

נתונים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} משתנים מקריים בלתי תלויים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1,X_2,...,X_n} מתקיים

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_1\oplus X_2\oplus ...\oplus X_n=0]=1/2+2^{n-1}\prod_{i=1}^n\varepsilon_i} .

או לחלופין

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon_{1,2,...,n}=2^{n-1}\prod_{i=1}^n\varepsilon_i}

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon_{1,2,...,n}} מייצג את ההטייה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1\oplus X_2\oplus ...\oplus X_n=0} . יש לשים לב שאם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i=0} או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i=1} אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_1\oplus X_2\oplus ...\oplus X_n=0]=0} או 1 בהתאם. אם רק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i} אחד שווה חצי אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_1\oplus X_2\oplus ...\oplus X_n=0]=1/2} .

כאשר מרכיבים משוואה ליניארית של הצופן המשתנים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_i} הם בעצם קירוב ליניארי של תיבות ההחלפה. למשל, אם נתונים ארבעה משתנים מקריים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1,X_2,X_3} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_4} ויהיו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_1\oplus X_2=0]-1/2+\varepsilon_{1,2}} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_2\oplus X_3=0]=1/2+\varepsilon_{2,3}} , הסכום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1\oplus X_3} המתקבל על ידי חיבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1\oplus X_2} עם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_2\oplus X_3} אז מתקיים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_1\oplus X_3=0]=\Pr[(X_1\oplus X_2)\oplus (X_2\oplus X_3)=0]} .

בדרך זו אפשר לשלב משוואות ליניאריות כדי לקבל משוואה ליניארית חדשה, ואם מניחים שהמשתנים בלתי תלויים אז אפשר להשתמש בלמת הערמה באופן הזה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Pr[X_1\oplus X_3=0]=1/2+2\varepsilon_{1,2}\varepsilon_{2,3}}

כתוצאה מכך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon_{1,3}=2\varepsilon_{1,2}\varepsilon_{2,3}} . אפשר לראות שהביטויים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1\oplus X_2=0} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_2\oplus X_3=0} מקבילים לקירובים הליניאריים של שתי תיבות ההחלפה בהתאמה ואילו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1\oplus X_3=0} מקביל לקירוב הליניארי של שתיהן יחד. כמובן שבניתוח אמיתי של הצופן מעורבים יותר תיבות החלפה ויותר משתנים מקריים בהתאם.

תיבות ההחלפה

במרבית הצפנים כמו DES ו-AES, כל הפעולות למעט תיבות ההחלפה הן פעולות ליניאריות ולכן מספיק לייצג את פעולות תיבות ההחלפה כמשוואה ליניארית כדי לפצח את הצופן. בהינתן תיבת החלפה כמו בדוגמה לעיל, המקבלת 4 סיביות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X=[X_1X_2X_3X_4]} ומחזירה ארבע סיביות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y=[Y_1Y_2Y_3Y_4]} . קל יותר לגלות קירובים ליניאריים על ידי חישוב ההטייה של כל תיבה בנפרד. למשל אם לוקחים את הביטוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_2\oplus X_3\oplus Y_1\oplus Y_3\oplus Y_4=0} או לחלופין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_2\oplus X_3=Y_1\oplus Y_3\oplus Y_4} , מנסים את כל 16 האפשרויות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} ובודקים את התוצאות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y} המתקבלות מתיבת ההחלפה, מגלים שב-12 מתוך 16 המקרים המשוואה האמורה מתקיימת, כלומר בהסתברות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 12/16-1/2=1/4} . דוגמה אחרת, עם הביטוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_1\oplus X_4=Y_2} מתקבלת הטיה של אפס וכן עם המשוואה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_3\oplus X_4=Y_1\oplus Y_4} ההסתברות היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2/16-1/2=-3/8} שזהו קירוב אפיני (בגלל סימן המינוס). היות שההתקפה הליניארית מסתמכת על שיעור ההטייה אין חשיבות לסימן וההתקפה תצליח במידה שווה במקרה של קירוב ליניארי או אפיני (מלמעלה או מלמטה). את כל 16 האפשרויות של הצירופים הליניאריים של כל המשוואות האפשריות, אפשר לסכם בטבלה. על בסיס טבלה הזו מגלים את כל הקירובים הליניאריים/אפיניים של תיבת ההחלפה ומסכמים אותם בטבלה אחרת הנקראת טבלת קירוב ליניארי, לדוגמה כך נראית הטבלה עבור תיבת ההחלפה שנבחרה לצורך הדוגמה:

	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	+8	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	-2	-2	0	0	-2	+6	+2	+2	0	0	+2	+2	0	0
2	0	0	-2	-2	0	0	-2	-2	0	0	+2	+2	0	0	-6	+2
3	0	0	0	0	0	0	0	0	+2	-6	-2	-2	+2	+2	-2	-2
4	0	+2	0	-2	-2	-4	-2	0	0	-2	0	+2	+2	-4	+2	0
5	0	-2	-2	0	-2	0	+4	+2	-2	0	-4	+2	0	-2	-2	0
6	0	+2	-2	+4	+2	0	0	+2	0	-2	+2	+4	-2	0	0	-2
7	0	-2	0	+2	+2	-4	+2	0	-2	0	+2	0	+4	+2	0	+2
8	0	0	0	0	0	0	0	0	-2	+2	+2	-2	+2	-2	-2	-6
9	0	0	-2	-2	0	0	-2	-2	-4	0	-2	+2	0	+4	+2	-2
A	0	+4	-2	+2	-4	0	+2	-2	+2	+2	0	0	+2	+2	0	0
B	0	+4	0	-4	+4	0	+4	0	0	0	0	0	0	0	0	0
C	0	-2	+4	-2	-2	0	+2	0	+2	0	+2	+4	0	+2	0	-2
D	0	+2	+2	0	-2	+4	0	+2	-4	-2	+2	0	+2	0	0	+2
E	0	+2	+2	0	-2	-4	0	+2	-2	0	0	-2	-4	+2	-2	0
F	0	-2	-4	-2	-2	0	+2	0	0	-2	+4	-2	-2	0	+2	0

כל כניסה בטבלה מייצגת בבסיס הקסדצימלי, את מספר הפעמים שנמצאה התאמה בין המשוואה הליניארית של קלט תיבת ההחלפה לבין סכום סיביות הפלט שלה פחות 8. לכן אם מחלקים את הערך בכניסה כלשהי ב-16 מתקבלת ההטיה ההסתברותית של הצירוף הליניארי המתאים. הערך של אינדקס כל כניסה מגדיר את המשתנים המקריים הנכללים במשוואה בצורה של צירוף ליניארי מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1\cdot X_1\oplus a_2\cdot X_2\oplus a_3\cdot X_3\oplus a_4\cdot X_4} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_i\in\{0,1\}} והסימן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cdot} מייצגת פעולת AND. לכן הערך בבסיס הקסדצילמי הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1a_2a_3a_4} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1} הוא הסיבית המשמעותית ביותר. מזה אפשר לראות שההטייה של המשוואה הליניארית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X_3\oplus X_4=Y_1\oplus Y_4} (בשורה הרביעית בעמודה העשירית) היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -6/16=-3/8} וההסתברות שהמשוואה הליניארית תתקיים היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/2-3/8=1/8} . מהתבוננות בטבלה אפשר לשים לב שההסתברות שכל סכום של סיביות פלט שווה לערך שאין בו סיביות מהקלט הוא בדיוק חצי, זאת בגלל שתיבת ההחלפה היא פונקציה חד ערכית ועל וכל צירוף ליניארי מחייב שיהיה מספר שווה של סיביות אפס ואחד. באותה מידה ההסתברות של כל צירוף ליניארי שאין בו סיביות פלט היא בדיוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle +1/2 } (בטבלה היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle +8} ), לכן השורה העליונה בטבלה כולה מאופסת למעט בכניסה השמאלית ביותר וכן לגבי העמודה הראשונה.

קירוב ליניארי של כל הצופן

בהינתן הקירובים הלנאריים של כל תיבות ההחלפה של הצופן, קיים מספיק מידע כדי לחשב את הקירוב הליניארי של הצופן בשלמותו. את זה אפשר לבצע על ידי צירוף מספר קירובים מתאימים מתיבות ההחלפה. עם מידע זה אפשר לחלץ סיביות מהמפתח הסודי ששימש בסבב האחרון של הצופן. לדוגמה, בתרשים משמאל מתואר קירוב לנארי של צופן הצעצוע להמחשה בתיבות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_{12}, S_{22}, S_{32}} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_{34}} כאשר הספרה הראשונה באינדקס התיבה מציינת את מספר הסבב ואילו השנייה את מספר התיבה (שזה התיבה השנייה בסבב הראשון, השנייה בסבב השני והתיבות השנייה והרביעית בסבב השלישי). יש לשים לב שהקירוב האמור אינו כולל את כל הצופן אלא רק שלושה סבבים ממנו, זה כל מה שדרוש להתקפה. לאחר בחינה של התרשים וטבלת הקירובים, מתקבלים הקירובים הבאים:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_{12}: X_1\oplus X_3\oplus X_4 = Y_2} בהסתברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 12/16} והטייה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle +1/4}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_{22}: X_2 = Y_2\oplus Y_4} בהסתברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4/16} והטייה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -1/4}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_{32}: X_2 = Y_2\oplus Y_4} בהסתברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4/16} והטייה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -1/4}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle :S_{34}: X_2 = Y_2\oplus Y_4} בהסתברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4/16} והטייה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -1/4}

יהיו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_i} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_i} בלוק הקלט ובלוק הפלט בהתאמה של תיבות ההחלפה של הצופן בסבב ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} . וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{ij}} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{ij}} הסיבית ה- $j$ של בלוק הקלט או הפלט בהתאמה, בסבב ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} . באותו אופן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_i} מייצג את המפתח המחובר ב-XOR עם בלוק הנתונים בסבב ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_5} הוא המפתח שמחובר לאחר הסבב הרביעי וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{ij}} מתייחס לסיבית במיקום ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} של המפתח ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} . לכן בשלב הראשון של הצופן מתקבל: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_1=P\oplus K_1} . כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} הוא בלוק הקלט הגלוי או המסר המיועד להצפנה, באורך 16 סיביות. על בסיס הקירוב הליניארי של הסבב הראשון של הצופן, המשוואה הליניארית הבאה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{1,6}\ =\ U_{1,5} \oplus U_{1,7} \oplus U_{1,8}}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \ \ \ \ \ \ = (P_5 \oplus K_{1,5}) \oplus (P_7 \oplus K_{1,7}) \oplus (P_8 \oplus K_{1,8})}

מתקיימת בהסתברות $3/4$ . וכן עבור הסבב השני, הצירוף הבא

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{2,6} \oplus V_{2,8} = U_{2,6}}

מתקיים בהסתברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/4} . היות שפלט הסבב הראשון הוא בעצם קלט הסבב השני המחובר עם המפתח המתאים, מתקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{2,6}=V_{1,6}\oplus K_{2,6}} לכן אפשר לקבל קירוב ליניארי מהצורה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{2,6} \oplus V_{2,8} = V_{1,6} \oplus K_{2,6}}

בהסתברות 1/4. לפי למת הערמה של מצואי, אם משלבים יחד את הצירופים משני הסבבים הראשונים מתקבלת המשוואה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{2,6} \oplus V_{2,8} \oplus P_5 \oplus P_7 \oplus P_8 \oplus K_{1,5} \oplus K_{1,7} \oplus K_{1,8} \oplus K_{2,6} = 0}

שמתקיימת בהסתברות ש/ל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/2+2(3/4-1/2)(1/4-1/2)=3/8} עם הטיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -1/8} . למרות שהיא מתבססת על ההנחה שהקירובים הליניאריים של כל סבב בלתי תלויים שהיא הנחה לא מדויקת, בפועל היא עובדת היטב. עבור הסבב השלישי אפשר להבחין ש:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{3,6} \oplus V_{3,8} = U_{3,6}} בהתסברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/4} וכן

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{3,14} \oplus V_{3,16} = U_{3,14}} בהתסברות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/4} .

היות שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{3,6} = V_{2,6} \oplus K_{3,6}} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{3,14} = V_{2,8} \oplus K_{3,14}} מתקבלת המשוואה הבאה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{3,6} \oplus V_{3,8} \oplus V_{3,14} \oplus V_{3,16} \oplus V_{2,6} \oplus K_{3,6} \oplus V_{2,8} \oplus K_{3,14} = 0}

בהתסברות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/2+2(1/4-1/2)^2=5/8} (עם הטיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -1/8} ). כעת אפשר לשלב את הצירופים מכל הסבבים (לפי עקרון הערמה) ולקבל את:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_{3,6} \oplus V_{3,8} \oplus V_{3,14} \oplus V_{3,16} \oplus P_5 \oplus P_7 \oplus P_8 \oplus K_{1,5} \oplus K_{1,7} \oplus K_{1,8} \oplus K_{2,6} \oplus K_{3,6} \oplus K_{3,14} = 0} .

אפשר לפשט את המשוואה. היות שבעצם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{4,6} = V_{3,6} \oplus K_{4,6}, U_{4,8} = V_{3,14} \oplus K_{4,8}, U_{4,14} = V_{3,8} \oplus K_{4,14}} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{4,16} = V_{3,16} \oplus K_{4,16}} , אפשר לשכתב את המשוואה האמורה כך:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle U_{4,6} \oplus U_{4,8} \oplus U_{4,14} \oplus U_{4,16} \oplus P_5 \oplus P_7 \oplus P_8 \oplus \sum_K = 0} .

כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \sum_K} כולל את כל סיביות המפתח המשתתפות (שמיקומן ידוע):

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \sum_K = K_{1,5} \oplus K_{1,7} \oplus K_{1,8} \oplus K_{2,6} \oplus K_{3,6} \oplus K_{3,14} \oplus K_{4,6} \oplus K_{4,8} \oplus K_{4,14} \oplus K_{4,16}}

ההסתברות שהמשוואה האחרונה תתקיים היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/2+2^3(3/4-1/2)(1/4-1/2)^3=15/32} עם הטיה -הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/32} והיא הקירוב הליניארי של הצופן. היות ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \sum_K} קבוע בהתאם למפתח הסודי המשוואה הבאה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{4,6} \oplus U_{4,8} \oplus U_{4,14} \oplus U_{4,16} \oplus P_5 \oplus P_7 \oplus P_8 = 0}

חייבת להתקיים בהסתברות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 15/32} או הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1-15/32)=17/32} שתלוי בערכו של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \sum_K} (אפס או אחד בהתאמה). כעת בידינו הקירוב הליניארי הכולל של שלושת הסבבים הראשונים של הצופן בהסתברות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/32} .

ניחוש סיביות מפתח

לאחר שהתגלה הקירוב הליניארי הכולל של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R-1} מתוך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} הסבבים של הצופן, עם הטיה הסתברותית משמעותית, עוברים לשלב ניחוש סיביות תת-המפתח האחרון על ידי חישוב לאחור. ביתר פירוט, תחילה מנסים את כל האפשרויות של המפתח האחרון (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_5} במקרה זה) ומחברים אותם ב-XOR עם הבלוק המוצפן, ואז מבצעים פענוח חלקי (העברה בתיבות ההחלפה של הסבב האחרון) של הבלוק שהתקבל. פעולה זו מתבצעת עבור כל זוגות הבלוקים גלויים/מוצפנים שנמצאים בידי המתקיף. שומרים מונה שמקודם בכל פעם שהתקבל ערך המקיים את הצירוף הליניארי של התיבות מהסבב האחרון (יש לזכור שהבלוק הגלוי ידוע). כל ניחוש סיביות מפתח שהמונה שלו גבוה או נמוך ממחצית מזוגות הקלט/פלט שבידי המתקיף בשיעור משמעותי הדבר נחשב לניחוש מוצלח. ניחוש לא נכון אמור לתת תוצאה אקראית ולכן המשוואה האמורה תתקיים בהסבתרות קרובה לחצי.

בצופן הצעצוע המובא להמחשה, הצירוף הליניארי האחרון משפיע על הפלט לתיבות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_{42}} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_{44}} של הסבב האחרון. כיוון שכל תיבה מכילה 4 סיביות בסך הכול 8 זה אומר שעבור כל זוג קלט/פלט מנסים את כל 256 צירופי סיביות של המפתח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_5} במקטעים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle [K_{5,5}...K_{5,8},K_{5,13}...K_{5,16}]} (יתר סיביות המפתח אינן משפיעות כי שתי תיבות אילו היו התיבות הפעילות היחידות בסבב זה). עבור כל ניחוש מפתח חלקי כזה, מקדמים מונה כלשהו אם המשוואה האחרונה התקיימה. הזוגות שלהם המונה הגבוה ביותר (שלילי או חיובי) מרמזות על ניחוש מוצלח בהסתברות גבוהה. המשוואה האחרונה (הצירוף הליניארי של הצופן) משפיעה על התוצאה בהתאם למפתח. אם ערכן של סיביות המפתח בפוזיציות הללו הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle\sum_K=0} אז המשואה תתקיים בהסתברות גבוהה מחצי ואילו אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle\sum_K=1} המשוואה תתקיים בהסתברות נמוכה מחצי. את צופן הצעצוע המתואר אפשר לתקוף עם 10,000 זוגות קלט/פלט ידועים, ולפי תיאור ההתקפה עד כה, התגלה ניחוש מוצלח של סיביות תת-המפתח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle [K_{5,5}...K_{5,8}]=[0010]} וכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle [K_{5,13}...K_{5,16}]=[0100]} . ואכן המונה עבור סיביות אילו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle [2,4]} בבסיס הקסדצימלי כצפוי היה גבוה משמעותית מ-5,000. הטבלה הבאה מכילה להמחשה, אוסף חלקי מתוך 256 האפשרויות. ערכים אילו מייצגים את שיעור ההטייה לפי החשבון האמור, "הטייה = מונה פחות חצי לחלק למספר הזוגות". כאשר המונה מתייחס לניחוש מסוים של 8 סיביות מהמפתח. אפשר לראות שההטייה הגבוהה ביותר מופיעה כאשר הניחוש הוא 2,4.

קטע תת-המפתח	הטיה	קטע תת-המפתח	הטיה
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle [K_{5,5}...K_{5,8}, K_{5,13}...K_{5,16}]}		הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle [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

הערך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0.0336} בשורה 9 בטבלה שהתגלה במהלך הניסוי, קרוב מאד לערך הצפוי של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/32=0.03125} . למרות שניחוש נכון תמיד יהיה בעל הטיה גבוהה ביותר, בכל זאת קיימים ערכים של ניחושים לא נכונים שמכילים הטיה גבוהה. מה שמעיד על כך שההשוואה של ניחושים נכונים אינה בדיוק השוואה של נתונים אקראיים מול משוואה ליניארית שאז ההטיה אמורה להיות אפס במצב אידיאלי. העובדה שזה לא קורה נובעת מכמה סיבות ביניהן מאפייני תיבות ההחלפה המשפיעות על הפענוח החלקי, אי דיוקים הנובעים מההנחה השגויה שהצירופים של תיבות ההחלפה בלתי תלויים זה בזה וכן מההשפעה של מה שקרוי "פרישה ליניארית" או "מעטפת ליניארית" ראה קבוצה פורשת.

סיבוכיות ההתקפה

ההסתברות שמשוואה ליניארית תתקיים תלויה בהטייה ההסתברותית של תיבות ההחלפה הפעילות ובמספרן (התיבות הפעילות הן אילו שהקו עובר דרכן בתרשים). באופן כללי ככל שההטייה גבוהה יותר בתיבות ההחלפה כך היא תהיה גבוהה יותר בצופן כולו. כמו כן ככל שפחות תיבות החלפה פעילות כך שיעור ההטייה יהיה גבוה יותר. יהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon} ההטייה מחצי של ההסתברות שמשוואה ליניארית עבור כל הצופן תתקיים. מיצורו מצואי הראה שמספר זוגות הקלט/פלט הנדרש לצורך הקרפיטואנליזה הליניארית פרופורציונלי ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon^{-2}} ואם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_L} מייצג את מספר הבלוקים הקריאים הדרוש אז אפשר להעריכו על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_L\approx 1/\varepsilon^{2}} .

למרות שסיבוכיות ההתקפה נמדדת גם בזמן וגם בזיכרון, בקריפטואנליזה ליניארית מתייחסים בעיקר לכמות הזיכרון. כלומר מניחים שאם יש באפשרותנו להשיג הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N_L} טקסטים אז ההתקפה ברת ביצוע. לאור האמור הדרכים להתגונן מפני הקריפטואנליזה הליניארית הן מיטוב תיבות ההחלפה, כלומר צמצום ההטייה הליניארית שלהם וכן בניית הצופן באופן שיהיו יותר תיבות החלפה פעילות. צופן AES הוא דוגמה מצוינת לגישה זו. אמנם צריך לשים לב שההוכחה כביכול שצופן עמיד מפני קריפטואנליזה ליניארית מסתמכת על אי קיומם של קירובים ליניאריים בהסתברות גבוהה, חישוב ההסתברות של משוואות ליניאריות מתבסס על ההנחה שהתיבות בלתי תלויות וההטייה שלהם בלתי תלויה כך שאפשרי ליישם את עיקרון הערמה של מצואי וכן על ההנחה שקירוב ליניארי יחיד מספיק כדי לחשב את הביטוי הליניארי הטוב ביותר בין סיביות הקלט וסיביות הפלט. במציאות הקירובים הליניאריים של תיבות ההחלפה אינם בלתי תלויים מה שעלול להשפיע על חישוב ההסתברות של ההטייה הכללית של הצופן. וכן מופעים של קירובים ליניאריים עם אותן סיביות קלט ופלט אך עם תיבות החלפה פעילות אחרות ניתנים לצירוף כך שתתקבל הסתברות ליניארית גבוהה יותר מהצפוי עם סט אחד של תיבות החלפה פעילות. תופעה זו נקראת מעטפת ליניארית או פרישה ליניארית. והיא משליכה על כך שגם אם נראה כאילו הצופן אינו מכיל הטיה הסתברותית גבוהה שילוב של מספר מופעים של קירובים ליניאריים יכול להוביל להטייה גבוהה. בכל אופן הגישה הבסיסית המתוארת כאן נוטה לעבוד היטב נגד מספר צפנים מודרניים, זאת משום שההשערה שהקירובים הליניאריים של תיבות ההחלפה בלתי תלויים סבירה למדי וכן אם מופעים של קירובים ליניאריים של קבוצת תיבות החלפה פעילות מניבים הטיה הסתברותית גבוהה הם נוטים להעלים את המעטפת הליניארית.

ראו גם

הערות שוליים

^ Matsui, M. & Yamagishi, A. "A new method for known plaintext attack of FEAL cipher". Advances in Cryptology - EUROCRYPT 1992
^ Matsui, M. "Linear Cryptanalysis Method for DES Cipher" (PDF). Advances in Cryptology - EUROCRYPT 1993.
^ Alex Biryukov, Christophe De Canni'ere, and Michal Quisquater. On Multiple Linear Approximations. In Matt Franklin, editor, Advances in Cryptology – CRYPTO ’04, 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15–19, 2004. Proceedings, volume 3152 of Lecture Notes in Computer Science, pages 1–22, Berlin/Heidelberg, 2004. Springer.
^ Zero-Correlation Linear Cryptanalysis of Block Ciphers
^ Carlo Harpes, Gerard G. Kramer, James L. Massey (May 1995). A Generalization of Linear Cryptanalysis and the Applicability of Matsui's Piling-up Lemma (PDF/PostScript). Advances in Cryptology — Eurocrypt '95. Saint-Malo: Springer-Verlag. pp. 24–38. Retrieved 9 September 2007
^ A Tutorial on Linear and Differential Cryptanalysis, Howard M. Heys

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

24924006

[1] Matsui, M. & Yamagishi, A. "A new method for known plaintext attack of FEAL cipher". Advances in Cryptology - EUROCRYPT 1992

[2] Matsui, M. "Linear Cryptanalysis Method for DES Cipher" (PDF). Advances in Cryptology - EUROCRYPT 1993.

[3] Alex Biryukov, Christophe De Canni'ere, and Michal Quisquater. On Multiple Linear Approximations. In Matt Franklin, editor, Advances in Cryptology – CRYPTO ’04, 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15–19, 2004. Proceedings, volume 3152 of Lecture Notes in Computer Science, pages 1–22, Berlin/Heidelberg, 2004. Springer.

[4] Zero-Correlation Linear Cryptanalysis of Block Ciphers

[5] Carlo Harpes, Gerard G. Kramer, James L. Massey (May 1995). A Generalization of Linear Cryptanalysis and the Applicability of Matsui's Piling-up Lemma (PDF/PostScript). Advances in Cryptology — Eurocrypt '95. Saint-Malo: Springer-Verlag. pp. 24–38. Retrieved 9 September 2007

[6] A Tutorial on Linear and Differential Cryptanalysis, Howard M. Heys

[1]

[2]

[3]

[4]

[5]

[6]