תקיפת היפגשות באמצע

בקריפטואנליזה, תקיפת היפגשות באמצע או תקיפת נפגשים באמצע (באנגלית: meet-in-the-middle attack) בקיצור MITM, היא התקפת כוח גס גנרית בשיטת איזון זמן/זיכרון נגד סכמות הצפנה מרובה. התקפה זו היא הסיבה מדוע הצפנת DES כפול עם שני מפתחות שונים אינה משיגה ביטחון כפול כמצופה ולכן משתמשים בגרסת DES משולש כדי להשיג ביטחון כפול. התקפה זו ישימה גם נגד הצפנה יחידה אם מתייחסים לחלקים שונים של הצופן כאילו היו הצפנה מרובה.

היסטוריה

בגלל המפתח הקצר של DES שהוא רק 56 סיביות, במקום לפתח צופן חדש, אחת ההצעות לחזק את ביטחון הצופן במחיר מועט הייתה להצפין את המידע פעמיים עם שני מפתחות שונים. לכאורה אם משתמשים בשני מפתחות באורך 56 סיביות אמורים לקבל ביטחון כפול, 112 סיביות. כדי לשבור את הצופן בכוח גס בשיטה הישירה נדרשים לנסות בערך $2^{112}$ מפתחות שזה לא מעשי כלל. ב-1977 הוכיחו ויטפילד דיפי ומרטין הלמן^[1] שהביטחון המושג אינו כפול כפי שנדמה בגלל שבתוספת זיכרון יש דרך לשבור את הצופן במאמץ כמעט זהה למאמץ הדרוש לשבירת הצופן עם מפתח אחד. הם הוכיחו שאפשר לפצח את DES כפול בסיבוכיות של $2^{57}$ עם סיבוכיות מקום בסדר גודל של $2^{56}$ . אף על פי שכמות זיכרון כזו אינה מעשית בכל אופן ניתנה הוכחה תאורטית שמראה בבירור שהתוספת בביטחון הצופן בעקבות הוספת מפתח זניחה. בנוסף, קיימות דרכים לצמצום דרישות הזיכרון של ההתקפה כמתואר בהמשך ולכן אפשר למעשה לשלול לגמרי את התועלת שבהצפנה כפולה. ההתקפה שלהם למעשה ישימה נגד כל צופן בלוקים שמשתמשים בו בתצורה של הצפנה כפולה סדרתית וכן אפשר להרחיבה נגד וריאציות של הצפנה מרובה עם שלושה מפתחות הצפנה ויותר. גרסה מתקדמת שלה נקראת התקפת היפגשות באמצע רב-ממדית שהיא קריפטואנליזה חדשה יחסית שנוסתה נגד צפנים כמו KATAN, Hammingbird ו-GOST.

תיאור כללי

התקפת היפגשות באמצע היא התקפת כוח גס גנרית שאינה מסתמכת על המבנה הפנימי של הצופן המותקף והיא מאתגרת את ההנחה שאם מצפינים פעמיים משיגים ביטחון כפול. היא פועלת לפי מודל התקפת גלוי-ידוע, ההנחה היא שהמתקיף הצליח להשיג בדרך כלשהי בלוק טקסט גלוי $p$ ובלוק טקסט מוצפן $c$ המתאים לו, דהיינו שהוצפן עם שני מפתחות סודיים באמצעות האלגוריתם אותו הוא מעוניין לשבור ותפקידו לנחש את המפתחות. הרעיון הוא פשוט, תחילה מכינים שתי טבלאות. בראשונה מאחסנים את תוצאות הצפנה של הבלוק הגלוי $p$ עם כל המפתחות האפשריים וממיינים אותה לפי הטקסט המוצפן. בשנייה מאחסנים את תוצאות פענוח הבלוק המוצפן $c$ עם כל המפתחות האפשריים וממיינים לפי הפלט ואז משווים בין שתי הטבלאות ומנסים למצוא התאמה. אם נמצאה התאמה יש סיכוי שהמפתחות המאוחסנים באותן כניסות שבהן קיימת ההתאמה הם המפתחות הסודיים שאיתם השתמש המצפין. צריך לזכור שיכול להיות מצב שבו אף על פי שיש התאמה המפתחות אינם אילו שהשתמש בהם המצפין (כי קיימים מפתחות רבים שאם מצפינים איתם את הבלוק האמור מתקבל פלט זהה). אם משווים את התוצאה עם זוגות נוספים של קלט/פלט רוב הסיכויים שהמפתחות שיתאימו בכולם יהיו המפתחות בהם השתמש המצפין. המאמץ הדרוש בשלב השני לניחוש המפתחות אינו עולה על המאמץ הדרוש לנחש מפתח אחד כי החיפוש בטבלה הממויינת עם טלבאות גיבוב רגילות אינו דורש מאמץ משמעותי ואפשר להתייחס אליו כאילו היה בסיבוכיות $O(1)$ . אך זאת במחיר כמובן של תוספת טבלה המכילה את כל ההצפנות האפשריות של הבלוק הגלוי $p$ . עבור בלוק באורך $n$ הזיכרון הדרוש הוא $2^{n}$ .

התקפת היפגשות באמצע מנסה למצוא את המפתחות משני הצדדים, מהצד של הטקסט הגלוי ומהצד של הטקסט המוצפן והפתרון נמצא אי שם באמצע (ומכאן שמה). כלומר מנסים לנחש תוצאה של הרכבה של מספר פונקציות אקראיות על ידי מיפוי לפנים ומיפוי לאחור ומנסים למצוא ערך אמצעי שמקיים את שני המיפויים או שני האגפים. כי אם $f_{1}$ ו- $f_{2}$ הן שתי פונקציות פסאודו-אקראיות הפיכות כלשהן, בהינתן $y=f_{1}(f_{2}(x))$ חייבים להיות ערכים המקיימים $f_{1}(x)=M=f_{2}^{-1}(y)$ .

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

תיאור האלגוריתם

הצפנה כפולה היא תצורה שבה מצפינים את הקלט פעמיים עם מפתחות שונים בזה אחר זה. כלומר בהינתן הבלוק $p$ מצפינים על ידי:

c=E_{k_{2}}(E_{k_{1}}(p))

ולפענוח מבצעים:

p=E_{k_{1}}^{-1}(E_{k_{2}}^{-1}(c))

כאן צופן הבלוקים במצב הצפנה מסומן ב- $E$ ובמצב פענוח ב- $E^{-1}$ עם המפתחות $k_{1},k_{2}$ כאשר $k_{1}\neq k_{2}$ . המתקיף מנסה לצמצם את טווח החיפוש בטכניקת היפגשות באמצע בדרך הבאה:

עבור כל מפתח $k_{1}\in \{0,1\}^{n}$ מחשב את $z=E_{k_{1}}(p)$ ומאחסן בטבלה $L_{1}$ את כל הזוגות $(z,k_{1})$ .
עבור כל מפתח $k_{2}\in \{0,1\}^{n}$ מחשב את $z=E_{k_{2}}^{-1}(c)$ ומאחסן את הזוגות $(z,k_{2})$ בטבלה $L_{2}$ .
ממיין את כניסות הטבלאות $L_{1}$ ו- $L_{2}$ לפי הערך הראשון $z$ .
מכין רשימה $S$ המכילה את כל ההתאמות בין שתי הטבלאות. אם נתונה כניסה כלשהי בטבלה $L_{1}$ עם הערכים $z_{1},k_{1}'$ וכניסה אחרת בטבלה $L_{2}$ עם הערכים $z_{2},k_{2}'$ , אז התאמה היא מצב בו מתקיים $z_{1}=z_{2}$ .
מחזיר את הרשימה $S$ .

הרשימה $S$ מכילה למעשה את כל זוגות המפתחות $(k_{1},k_{2})$ האפשריים המקיימים $c=E_{k_{2}}(E_{k_{1}}(p))$ . זה נכון משום שהערכים ברשימה $S$ מקיימים:

E_{k_{1}}(p)=E_{k_{2}}^{-1}(c)

.

והשוויון האמור מתקיים רק אם $c=E_{k_{2}}(E_{k_{1}}(p))$ . אם אורך הבלוק של הצופן המותקף הוא באורך זהה. למשל אם המפתח והבלוק באורך $n$ אז הסיכויים לנחש את המפתחות הם $2^{-n}$ , כך שמספר האלמנטים ברשימה $S$ צפוי להיות בערך $2^{2n}/2^{n}=2^{n}$ . אמנם התוצאה הזו גבוהה, אך בהינתן זוג נוסף של קלט/פלט כלומר $p',c'$ אחרים המקיימים את המשוואה של ההצפנה הכפולה עם אותם מפתחות, אז אם מנסים את כל האלמנטים ברשימה אפשר למצוא את זוג המפתחות הנכונים בהסתברות מאוד גבוהה. ככל שמנסים יותר זוגות ההסתברות עולה.

סיבוכיות ההתקפה המתוארת היא $O(2^{n})$ . הכנה ומיון של שתי הטבלאות $L_{1}$ ו- $L_{2}$ מתבצעת בזמן של בערך $2^{n}$ . אם הטבלאות ממויינות כל ההתאמות ביניהן ניתנות לאיתור בזמן של $O(|S|+|L_{1}|+|L_{2}|)=O(2^{n})$ . ניחוש המפתחות אם משתמשים בשני זוגות קלט/פלט מתבצעת בזמן של $O(|S|)=2^{n}$ , כך שסיבוכיות הזמן של ההתקפה האמורה היא $O(2^{n})$ .

שיפורים

אבן וגלודרייך הציעו שיפור של האלגוריתם^[2]. אפשר להגביל את דרישות הזיכרון ל- $w$ , מחלקים את הטווח $L_{1}$ לתת-קבוצות בגודל $w$ . עבור כל תת-קבוצה מחשבים ומאחסנים את הזוג $(E_{k_{1}}(p),k_{1})$ ועבור כל $k_{2}$ מחשבים את $E_{k_{2}}^{-1}(c)$ ומחפשים בטבלה $L_{1}$ התאמה. זמן הריצה הצפוי במקרה זה הוא $\textstyle {\frac {1}{2}}({\frac {n_{1}}{w}})(w+n_{2})\approx {\frac {n_{1}n_{2}}{2w}}$ פעולות הצפנה.

מייקל ויינר ופול ואן-אורשוט הציעו שיפור נוסף על ידי שימוש באלגוריתם חיפוש התנגשויות מקבילי^[3] וצמצום דרישות הזיכרון באופן ניכר. לפי הרעיון שלהם התקפה נגד DES בשיטת היפגשות באמצע נחשבת מעשית מבחינת היקף המשאבים הדרושים לה.

התקפת היפגשות באמצע רב-ממדית

אפשר להרחיב את ההתקפה הקלאסית של דיפי והלמן לממדים נוספים^[4]. בהינתן מספר זוגות תואמים של בלוק גלוי $p$ ובלוק מוצפן $c$ כך שמתקיים $c=E_{k}(p)$ ונניח שהצופן $E$ ניתן לפירוק לשני צפנים עוקבים $E_{f}(k_{f},\cdot )$ ו- $E_{b}(k_{b},\cdot )$ כך שמתקיים $c=E_{b}(k_{b},E_{f}(k_{f},p))$ . מתייחסים למנגנון הפנימי של הצופן כאילו היה הצפנה מרובה ומנסים לנחש את ערכי הביניים באמצעות שתי התקפות היפגשות באמצע. המפתחות $k_{f}$ ו- $k_{b}$ הם תת-מפתחות של $E_{f}$ ו- $E_{b}$ בהתאמה. (כאן $f$ ו- $b$ הם קיצור של קדימה ואחורה). לצורך הפשטות ההתקפה המתוארת כאן אינה יעילה אלא נועדה לצורך ההסבר.

התקפת היפגשות באמצע דו-ממדית

נניח שמנסים לנחש תחילה מצב ביניים פנימי של הצופן המסומן ב- $g$ באמצעות שתי התקפות MITM על תת-הצפנים שאורך הבלוק שלהם מתחלק ב- $g$ . היא נקראת התקפת נפגש באמצע דו-ממדית המסומנת בקיצור 2D-MITM. מניחים שהצופן מורכב משני שלבים, בשלב הראשון הבלוק מוצפן עם זוג תת-המפתחות $k_{f_{1}},k_{f_{2}}$ הנגזרים מהמפתח הראשי ובשלב השני הבלוק מוצפן שוב עם תת-המפתחות $k_{b_{1}},k_{b_{2}}$ שגם הם נגזרים מהמפתח הראשי. למען הפשטות נניח שתת-המפתחות האמורים אינם חופפים. כלומר אינם משתפים ביניהם סיביות זהות של מפתח המאסטר $k$ . ההתקפה מתנהלת כדלהלן.

מחשבים את $v_{1}=E_{f_{1}}(k_{f_{1}},p)$ עבור כל מפתח אפשרי $k_{f_{1}}$ ומאחסנים בטבלה $T_{1}$ הממויינת לפי $v_{1}$ .
מחשבים את $v_{2}'=E_{b_{2}}^{-1}(k_{b_{2}},c)$ עבור כל מפתח אפשרי $k_{b_{2}}$ ומאחסנים בטבלה $T_{2}'$ הממויינת לפי $v_{2}'$ .
עבור כל ניחוש אפשרי של ערך הביניים $g$ $g$ מבצעים:
1. (א) $v_{1}'=E_{b_{1}}^{-1}(k_{b_{1}},g)$ עבור כל מפתח אפשרי $k_{b_{1}}$ ומאחסנים בטבלה $T_{1}'$ הממויינת לפי $v_{1}'$ .
2. (ב) מחשבים את $v_{2}=E_{f_{2}}(k_{f_{2}},g)$ עבור כל $k_{f_{2}}$ אפשרי ומאחסנים בטבלה $T_{2}$ הממויינת לפי $v_{2}$ .
3. (ג) כל הזוגות התואמים $(k_{f_{1}},k_{b_{1}})$ עבור $v_{1}=v_{1}'$ יחד עם כל הזוגות התואמים $(k_{f_{2}},k_{b_{2}})$ עבור $v_{2}=v_{2}'$ מהווים יחדיו מועמדים למפתח ששימש להצפנה הכוללת. כדי להגביר את הסיכויים למצוא את המפתחות הנכונים מתוך הרשימה בודקים זוגות נוספים של טקסט גלוי/טקסט מוצפן בכוח גס ישיר על הרשימה. אם מפתח אחד עבר את כל הבדיקות זהו המפתח הנכון בהסתברות גבוהה.

היות שאין צורך לחשב מחדש את $E_{f_{1}}$ ו- $E_{b_{2}}^{-1}$ עבור מצבים פנימיים שונים $g$ סיבוכיות הזמן הכוללת של ההתקפה היא:

2^{|k_{f_{1}}|}+2^{|k_{b_{2}}|}+2^{|g|}\cdot (2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|})

עבור כל מצב ביניים $g$ שמנחשים, שלב התקפת MITM הראשונה במעבר מ- $p$ ל- $g$ מצמצם את טווח המפתח ל- $2^{|k|-|v_{1}|}$ ושלב ההתקפה MITM השנייה במעבר מ- $g$ ל- $c$ מצמצם עוד את טווח החיפוש של המפתח ל- $2^{|k|-|v_{1}|-v_{2}|}$ לכן בסך הכול מספר סיביות טווח החיפוש מצטמצם ל- $2^{|g|}\cdot (2^{|k|-|v_{1}|-|v_{2}|})=2^{|k|+|g|-|v_{1}|-|v_{2}|}$ . בהנחה ש- $g$ שווה באורכו ל- $n$ מתקבלת סיבוכיות של $2^{|k|-n}$ . הסיבוכיות הכוללת של שלב הכוח גס קרובה לזו. סיבוכיות הזיכרון של ההתקפה היא $2^{|k_{f_{1}}|}+2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}+2^{|k_{b_{2}}|}$ כי צריך לאחסן את כל ארבע הטבלאות בזיכרון. במקרה הכללי תת-המפתחות אינם נפרדים לגמרי אלא בדרך כלל חולקים ביניהם סיביות זהות ממפתח המאסטר כך שההתקפה המתוארת אינה ישימה ישירות. יש כמה דרכים לפתור את הבעיה, אפשר להתייחס לכל סיבית של תת-מפתח כאל משתנה נפרד או לבצע טרנספורמציה ליניארית לפני שמחפשים התאמה בין תת-מפתחות.

התקפת נפגש באמצע רב-ממדית

אפשר לנסות לנחש מצבי ביניים נוספים של הצופן ולחלק את הצופן למקטעים קטנים יותר. התקפת היפגשות באמצע רב ממדית הנקראת MD-MITM או $(i+1){\text{D-MITM}}$ היא הכללה של הטכניקה המתוארת. הצעדים הדרושים באופן כללי להתקפה הכללית הם:

בונים טבלה $T_{1}$ עבור המפתחות $k_{f_{1}}$ על ידי חישוב $v_{1}=E_{f_{1}}(k_{f_{1}},p)$ .
בונים טבלה $T_{i+1}'$ עבור $k_{b_{i+1}}$ על ידי חישוב $v_{i+1}'=E_{b_{i+1}}^{-1}(k_{b_{i+1}},c)$ .
עבור כל ניחוש של $g_{1}$ $g_{1}$ מבצעים:
1. בונים טבלה $T_{1}'$ על ידי $v_{1}'=E_{b_{1}}^{-1}(k_{b_{1}},g_{1})$ שבה מחפשים התאמות עם $T_{1}$ .
2. בונים טבלה $T_{2}$ על ידי $v_{2}=E_{f_{2}}(k_{f_{2}},g_{1})$ .
3. עבור כל ניחוש של $g_{2}$ $g_{2}$ מבצעים:
  1. בונים טבלה $T_{2}'$ המכילה את $v_{2}'=E_{b_{2}}^{-1}(k_{b_{2}},g_{2})$ להתאמה עם הטבלה $T_{2}$ .
  2. עבור כל $g_{i}$ $g_{i}$ מבצעים:
    1. בונים טבלה $T_{i}'$ המכילה את $v_{i}'=E_{b_{i}}^{-1}(k_{b_{i}},g_{i})$ להתאמה עם $T_{i}$ .
    2. מחשבים את $v_{i+1}=E_{f_{i+1}}(k_{f_{i+1}},g_{i})$ ובונים טבלה $T_{i+1}$ להתאמה עם הטבלה $T_{i+1}'$ .
    3. מבצעים בדיקה בכוח גס על כל שילוב אפשרי של הזוגות $(T_{1},T_{1}'),(T_{2},T_{2}'),\cdots ,(T_{i+1},T_{i+1}')$ ומחזירים את כל המקרים שבהם מתקיימת התאמה כניחושים אפשריים של המפתח הסודי.