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

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

היסטוריה

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

תיאור כללי

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

שיפורים

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

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

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