במקרה של צופן בלוקים formula_1 הוא מרחב כל המפתחות האפשריים כאשר formula_2 הוא אורך המפתח בסיביות (למשל בצופן AES עם מפתח באורך 128 סיביות formula_3). למען הפשטות ההנחה היא שגם מרחב המסרים האפשריים הוא formula_4. בדרך כלל לצורך ההתקפה המתקיף רשאי לבחור בלוק מוצפן יחיד והבלוק המקורי שהוצפן. במונח "לבחור" מתכוונים שהמתקיף הצליח להשיג לכל הפחות בלוק טקסט קריא אחד לפי בחירתו ואת תוצאת ההצפנה שלו עם מפתח לא ידוע. מודל זה נקרא התקפת גלוי-נבחר. התקפת איזון זמן/זיכרון שהוצגה לראשונה על ידי מרטין הלמן נחשבת להתקפה הטובה ביותר מסוג זה נגד פונקציה אקראית, היא מאזנת בין הערכים formula_5, הערכים האופטימליים תלויים בעלות היחסית של המשאבים החישוביים שברשות המתקיף. למשל אם formula_6, לפי הלמן אפשר להגיע לאיזון של formula_7 וכן formula_8 כלומר שיפור בפקטור של שליש לעומת התקפת כוח גס.
רקע.
התקפת איזון זמן/זיכרון הועלתה לראשונה ב-1980 על ידי מרטין הלמן.
בעיות חיפוש רבות כמו בעיית תרמיל הגב או בעיית הלוגריתם הבדיד ניתנות לפתרון מהיר יותר מכוח גס באמצעות שימוש מושכל בזמן וזיכרון. כלומר אם קיימים formula_4 פתרונות אפשריים לבעיה נתונה, איזון זמן זיכרון מאפשר למצוא את הפתרון הנכון בזמן של formula_10 פעולות חישוב עם formula_11 מילות זיכרון בתנאי שהמשוואה formula_12 מתקיימת. ליתר דיוק האגף הימני של המשוואה צריך להיות formula_13 אולם אפשר להתעלם מהלוגריתם והקבוע formula_14.
ניחוש מפתח הצפנה שהוא בעצם קריפטואנליזה בסיסית של כל צופן סימטרי, אינו אלא בעיית חיפוש שיש לה שני מקרי קצה. המקרה formula_15 שבו לא נעשה שימוש בזיכרון כלל אך מצריך זמן ביצוע מלא, כלומר המתקיף צריך לנסות כמעט את כל formula_4 המפתחות האפשריים במקרה הממוצע עד שימצא המפתח הנכון ומהצד השני formula_17 שמסתמך על טבלת איחזור ענקית, כך שהזמן הדרוש לאיחזור המפתח הנכון מתקרב ל-formula_18 (אם לא מביאים בחשבון את זמן ההכנה). מציאת התאמה בטבלה ממויינת באמצעות חיפוש בינארי וטבלאות גיבוב היא פעולה קלה במונחי מחשוב, אך מאידך המחיר הוא שימוש מופרז בזיכרון. שני מקרי הקצה אינם מעשיים מצד אחד הזמן הדרוש גבוה מדי ומהצד השני כמות הזיכרון בלתי מעשית.
יהיו formula_19 ו-formula_20 שני פרמטרים שחשיבותם תובהר בהמשך, אם מתעלמים לרגע מזמן הביצוע של ההכנה המוקדמת, חיפוש פתרון של כל פונקציה חד-כיוונית באמצעות טכניקת איזון זמן זיכרון יכול להתבצע בסיבוכיות מקום ממוצעת של formula_21 וזמן בסדר גודל של formula_22 פעולות בקירוב, בתנאי שמתקיים formula_23. אם formula_24 מתקבל formula_25 שזהו שיפור משמעותי לעומת חיפוש ממצה של כל הפתרונות האפשריים בשיטה הישירה וזאת עם זיכרון בגודל formula_26. אם סיבוכיות החיפוש נמדדת במונחים של formula_27 (זמן פלוס זיכרון) אף על פי שזיכרון וזמן אינם מושגים זהים אפשר להתעלם מפרט זה, בכללות מושג שיפור בפקטור של שליש בסיבוכיות. ההשלכה היא שחיפוש מפתח DES באורך 56 סיביות מתקצר לחיפוש בסדר גודל של 38 סיביות. יתרה מזו, בבעיות מסוימות כמו פרמוטציה פסאודו אקראית או בעיית הלוגריתם הבדיד, אפשר להשיג שיפור גדול יותר עד פקטור של חצי, קרי formula_28 על חשבון עליה קלה בסיבוכיות עבודת ההכנה.
חיפוש ממצה.
חיפוש ממצה של מפתח ההצפנה או התקפת כוח גס ישירה נגד צופן סימטרי יכולה להתבצע לפי מודל התקפת גלוי-ידוע כך שברשות המתקיף לפחות בלוק טקסט גלוי אחד ובלוק מוצפן שמתאים לו (כלומר שהוצפן עם מפתח סודי כלשהו אותו המתקיף מעוניין לחשוף), אותו הוא השיג בדרך כלשהי אך אין לו שליטה על התוכן. ואילו התקפה שעושה שימוש בטבלת חיפוש דורשת מודל התקפת גלוי-נבחר, כלומר המתקיף שהכין את הטבלה מראש עם בלוק נתון (למשל בלוק המכיל רק אפסים), צריך שתהיה לו היכולת לבחור בזמן ריצה לפחות בלוק גלוי אחד המכיל את הנתונים שהוא מעוניין והבלוק המוצפן המתאים לפני שהוא מתחיל בהתקפה. זה אפשרי בעולם האמיתי, אפשר למשל לחשוב על מקרה שבו המתקיף יודע שהוצפן בלוק המכיל נתונים קבועים הידועים לכל. הרעיון של התקפת כוח גס ישירה פשוט, אם נתון בלוק טקסט מוצפן formula_29 שהוצפן עם המפתח formula_30 וההנחה היא שהמתקיף יודע בדרך כלשהי מהו הבלוק שהוצפן formula_31 והוא מעוניין לגלות את formula_30, בניסוח פורמלי:
כאשר formula_34 היא פונקציית הצפנה כמו DES והנעלם היחיד במשוואה האמורה הוא formula_30. המתקיף תחילה בונה טבלה שמכילה formula_4 הצפנות של formula_31 עם מפתחות הצפנה שונים כאשר formula_4 מתייחס למרחב כל המפתחות האפשריים של הצופן (לדוגמה ב-DES formula_39), בכל שורה בטבלה הוא מאחסן מפתח אחר וטקסט מוצפן מתאים, ממיין את הטבלה לפי הטקסט המוצפן ואז מחפש התאמה עם formula_29, היות שהטבלה ממוינת אפשר למצוא התאמה אם קיימת באמצעות חיפוש בינארי בזמן של formula_41, אם מאיצים את החיפוש עם טבלאות גיבוב אפשר להתעלם מהלוגריתם לצורך הדיון ולהחשיב את פעולת החיפוש כקרובה ל-formula_18.
בטכניקת איזון זמן/זיכרון מתעלמים מפעולת ההכנה המוקדמת כי היא אינה משפיעה ישירות על סיבוכיות ההתקפה משני טעמים. ראשית, פעולת ההכנה יכולה להתבצע באופן לא מקוון בזמנו החופשי של המתקיף ושנית במקרים מסוימים פעולת ההכנה יכולה להיות שימושית לכמה התקפות ולכן אפשר להניח לצורך הדיון שהיא כבר נעשתה.
תיאור כללי של שיטת הלמן.
בהינתן פונקציה אקראית formula_43 הממפה את המפתח formula_44 לבלוק טקסט מוצפן formula_45 עבור טקסט קריא קבוע כלשהו. אפשר לראות שקל לחשב את formula_43 אבל קשה להפוך אותה, כי חישוב הפונקציה ההופכית formula_47 היא בדיוק הבעיה הקריפטואנליטית של חילוץ מפתח ההצפנה formula_44 בהינתן טקסט מוצפן formula_45. כדי לבצע את הפעולה ההפוכה מהר יותר מכוח גס הציע הלמן לנצל את פרדוקס יום ההולדת על ידי הוספת שלב "קדם עיבוד" שמנסה "לכסות" במידה רבה ככל האפשר את formula_4 הנקודות של מרחב המפתח. כלומר להגביר ככל האפשר את הסיכויים שהמפתח אותו מחפשים יפול במקרה באחת מנקודות הכיסוי. הוא הציע להשתמש במטריצה מסדר formula_51 שהשורות בה הם "מסלולים" באורך formula_19 הנוצרים מהפעלה רקורסיבית של הפונקציה formula_43 על formula_20 נקודות התחלה אקראיות שונות. היות שכל נקודה ניתנת לחישוב על ידי הנקודה הקודמת לה במסלול, אפשר למעשה לאחסן בזיכרון רק את נקודת ההתחלה ונקודת הסיום של כל מסלול כזה. תוצאת שלב ההכנה היא הטבלה המכילה אוסף ערכים המייצגים נקודות התחלה ונקודות סיום של המסלולים, הממוינים לפי נקודת הסיום. בשלב ההתקפה המקוונת המתקיף מנסה לגלות אם formula_44 מכוסה על ידי אחת הנקודות בטבלה. האלגוריתם מחשב את formula_43 על formula_45 באופן איטרטיבי, סורק את עמודוצת הטבלה ומנסה למצוא התאמה של התוצאה שבידו עם נקודת סיום כלשהי. אם נמצאה התאמה הוא יודע שהפתרון formula_44 נמצא בשורה זו ולכן כל שעליו לעשות הוא לקפוץ לנקודת ההתחלה של אותה שורה ולחשב את formula_43 על formula_45 במספר הפעמים הדרוש עד שהוא מגיע ל-formula_44 והערך שבו ביקר צעד אחד לפניו הוא הפתרון הנכון בסבירות גבוהה.
התמזגות.
מטריצה אחת לא יכולה לכסות את כל הנקודות כי ככל שמוסיפים שורות, לפי פרדוקס יום ההולדת כל עוד formula_62 בהכרח שייוצרו התנגשויות. התנגשות פירושה שהתקבל ערך זהה בשתי נקודות בשורות שונות לא בהכרח באותה עמודה. הבעיה היא שכל התנגשות גורמת להתמזגות, אם נקודה מסוימת הופיעה שוב בשורה אחרת מנקודה זו ואילך עד סוף המסלול הנקודות בשתי השורות הללו תהיינה זהות. התמזגויות קשות להבחנה כיוון שאם ההתנגשות חלה בעמודות שונות נקודת הסיום לא תהיה זהה. מבחינה סטטיסטית התמזגויות פוגעות באופן משמעותי ברמת הכיסוי ולכן בסיכויים לנחש מפתח, זאת למרות עבודת ההכנה הזהה. החסם העליון לכיסוי מקסימלי עבור טבלה אחת הוא במקרה שהפרמטרים מקיימים formula_23. במקרה כזה הטבלה מכסה רק שטח של formula_64 מהמרחב לכן יש צורך ב-formula_19 טבלאות בלתי תלויות כאלו כדי לכסות את המרחב כולו. אולם הלמן הבחין בעובדה מעניינת שאם משנים מעט את הפונקציה formula_43 עבור כל טבלה, למשל formula_67 כאשר formula_68 היא פונקציה פשוטה של הפלט כמו סידור מחדש של סיביות, אפשר למנוע התנגשויות ולשפר את רמת הכיסוי מאוד. התכונות של הפונקציות המותאמות הן:
שלב ההכנה דורש רק formula_83 פעולות, כל מטריצה מכסה formula_73 נקודות אך דורשת רק formula_20 מילים בזיכרון, כל פעולת חיפוש בטבלה דורשת formula_19 ניסיונות שכל אחד מהם דורש formula_19 הפעלות של פונקציה formula_69 כלשהי של אחת הטבלאות, זמן ההתקפה הכולל הוא formula_22, כדי למצוא את עקומת האיזון בין formula_10 ל-formula_11 שמביאה לביצועים אופטימליים משתמשים בחסם האמור formula_23 ומקבלים formula_93. בעוד שהזמן formula_10 יכול להיות כל ערך בטווח formula_95, המקום formula_11 מוגבל ל-formula_97 שאם לא כן יוצא ש-formula_98 ואז ההתקפה תהיה איטית מכוח גס.
פירוט האלגוריתם.