יהי formula_99 פונקציה המייצגת הצפנה של בלוק formula_2-סיביות טקסט קריא formula_101 עם מפתח סודי formula_30 בגודל formula_103 סיביות. כחלק מההתקפה בלוק טקסט מוצפן בגודל formula_2 משמש בעצמו כמפתח הצפנה בגודל formula_103 כך שיש צורך בפונקציה כלשהי שממירה בלוק מוצפן של formula_2 סיביות למפתח הצפנה formula_107. במקרה של DES המפתח קטן מהבלוק, לכן הציע הלמן למשל פונקציית כיווץ פשוטה שחותכת את התוצאה לגודל הרצוי ומתעלמת משמונה הסיביות האחרונות. במקרה ש-formula_108 – מצב אפשרי בצופן AES עם מפתח הגדול מ-128, הפונקציה יכולה להוסיף מספר סיביות קבועות (למשל אפסים) כדי להרחיב את הבלוק formula_2 לגודל המתאים כמפתח.
לסיכום לצורך ההתקפה מגדירים פונקציה formula_43 שהיא תוצאת הצפנה של הבלוק formula_111 לאחר המרה למפתח הצפנה עם הפונקציה formula_112 (הפונקציה formula_112 אינה הכרחית אם הבלוק המוצפן יכול לשמש ישירות כמפתח הצפנה):
חישוב formula_115 הוא פעולה קלה כפעולת הצפנה. לעומת זאת חישוב formula_30 מתוך formula_115 שקול לקריפטואנליזה של הצופן. התקפת איזון זמן/זיכרון מורכבת משני שלבים, שלב הכנה שמתבצע אוף ליין ושלב ההתקפה און ליין המתוארים להלן.
שלב ההכנה הלא מקוון.
תחילה formula_1 הוא מרחב המפתחות האפשריים. התוקף בוחר מתוך המרחב formula_4, formula_20 נקודות התחלה start point אקראיות שונות שיהיו מפתחות הצפנה, אותן מסמנים: formula_121. ואז עבור כל נקודת התחלה מחשב את 'שרשרת ההצפנה' כדלהלן: (א) מציב בכניסה הראשונה בשורה formula_122 את נקודת ההתחלה formula_123 ואז (ב) כל כניסה הבאה אחריה מכילה את formula_124 עבור formula_125, כלומר כל כניסה היא הצפנה של formula_111 עם מפתח שהוא תוצאת ההצפנה של כניסה קודמת. הטקסט המוצפן עצמו משמש כמפתח הצפנה לאחר שעבר המרה מתאימה עם הפונקציה formula_112. למעשה שורה אחת היא שרשרת של formula_19 הצפנות חוזרות של formula_111 על ידי formula_43, עם סדרה של מפתחות שהאחד נוצר מהשני, עד שמגיעים לנקודת הסיום formula_131. לסיכום הטבלה היא:
כדי לצמצם דרישות זיכרון לא מאחסנים את ערכי הביניים אלא את נקודות ההתחלה והסיום formula_137 בלבד וממיינים אותן בסדר נומרי לפי נקודות הסיום formula_138.
שלב ההתקפה המקוונת.
לצורך הפשטות (כאמור לעיל) משתמש מסוים בחר במפתח סודי formula_30 כלשהו, הצפין את הבלוק הקריא formula_111 (שידוע לתוקף, למשל הבלוק יכול להיות מחרוזת אפסים או כל טקסט קבוע ומוסכם) ובדרך מסוימת התוצאה formula_141 נפלה לידי התוקף ועליו לגלות את formula_30. התוקף מיישם את הפונקציה formula_112 כדי לקבל את formula_144 ואז מבצע את המהלכים הבאים:
יש לשים לב שהתוקף צריך לגשת לטבלה בכל פעם שמחושב formula_162 חדש. אם כל formula_163 האלמנטים שבטבלה שונים, ההסתברות להצלחה היא formula_164. בפועל סיכויי ההצלחה נמוכים יותר כי הם תלויים באופן שבו השרשראות מתפרסות על פני מרחב המפתח. קיימת גם אפשרות ששרשרת הצפנה שהתחילה עם מפתח אחד תתנגש ותתמזג עם שרשרת אחרת שהתחילה עם מפתח אחר (מנקודה זו ועד לנקודת הסיום כל החוליות בשתי השרשראות תהיינה זהות). ככל שהטבלה גדולה יותר כך גדלים הסיכויים להתנגשות. כל התמזגות מצמצמת למעשה את מספר האפשרויות שהטבלה מכסה. אם formula_43 היא פונקציה ראנדומלית, ההסתברות להצלחה חסומה ב:
מהמשוואה עולה כי הערכים האופטימליים של formula_19 ו-formula_20 הם כאלו שמקיימים formula_23 שאז הסיכויים הם בערך formula_170. שזהו לא שיפור משמעותי כפי שהיינו מצפים. כדי לקבל סיכויי הצלחה גבוהים יותר משתמשים בטבלאות מרובות, כל אחת עם פונקציה formula_43 שונה, בכך מבטיחים פריסה טובה יותר של אלמנטים והימנעות מהתמזגויות ובכך מגבירים את הסיכויים בפקטור שהוא ביחס לכמות הטבלאות (או סך כל האלמנטים). אי אפשר למנוע התנגשות לגמרי אך גם אם ערך כלשהו מתנגש בנקודה כלשהי היות שהפונקציה שונה לא תתרחש התמזגות. בכללות עבור formula_172 טבלאות הסיכויים הם:
כאשר formula_174 מתייחס לסיכויים עם טבלה אחת. אם מציבים formula_24 ההסתברות לטבלה אחת היא בערך formula_176, לכן עם formula_177 טבלאות אפשר להשיג סיכויים של formula_178. כמות הזיכרון תהיה במקרה זה formula_8 מילים וסך כל הפעולות הוא formula_7. החיפוש בטבלאות יכול להתבצע באופן סדרתי או מקבילי להאצה נוספת וכמובן שאפשר להשתמש ביותר טבלאות לפי הצורך כדי להגביר סיכויים.
נקודות מובחנות.
חיסרון מעשי אחד בשיטת הלמן הוא מספר הקריאות בדיסק הקשיח. באופן כללי גישה לדיסק צורכת כשמונה מילישניות לעומת פעולה בתוך זיכרון המעבד שהיא בערך שתי ננושניות. בגלל ההבדל העצום במהירות הגישה מומלץ לצמצם את מספר הקריאות בדיסק ככל האפשר. רון ריבסט הציע רעיון במקום לקבוע את אורך המסלולים בכל שורה בטבלה לאורך קבוע, המסלול יכול להמשיך עד שמגיעים לנקודה כלשהי שיש לה מאפיין מיוחד כלשהו כמו ערך המכיל רצף מסוים של אפסים. נקודה כזו נקראת "נקודה מובחנת" (באנגלית Distinguished point). במהלך שלב ההכנה מתחילים מנקודות התחלה מובחנות אקראיות ומחשבים את המסלולים באותה דרך, אך עוצרים רק כאשר מגיעים לנקודה מובחנת נוספת. כך נוצרים מסלולים באורכים שונים המכילים נקודות מובחנות בלבד. אם formula_181 האורך הצפוי של כל מסלול יהיה בערך formula_19. קבוצת כל נקודות הסיום בכל formula_19 הטבלאות בסך הכול formula_184 נקודות מכסה כמות ניכרת של בערך formula_185 מהנקודות המובחנות האפשריות. נקודות מובחנות קלות להכנה וקלות לזיהוי.
היתרון העיקרי של גישה זו הוא שבמהלך ההתקפה יש צורך לבצע רק קריאה אחת בדיסק הקשיח עבור כל מסלול (כאשר ניתקלים לראשונה בנקודה מובחנת), מספר ההפעלות של הפונקציה formula_69 נשאר formula_187 אבל מספר הקריאות בדיסק יורד מ-formula_187 ל-formula_19 שזה יתרון משמעותי.
Rainbow Table.
טבלת ריינבו היא שיטת כוח גס גנרית המבוססת על שיטת הלמן לשבירת פונקציית גיבוב, יעילה בעיקר לניחוש סיסמאות או מספרי כרטיס אשראי וכדומה המכילים מחרוזת אלפנומרית קצרה. הוצעה לראשונה על ידי Philippe Oechslin ב-2003 ומהווה שיפור ניכר של שיטת הלמן המתוארת לעיל. המגבלה העיקרית בשיטת הלמן היא שכאשר שני מסלולים מתנגשים באותה טבלה הם מתמזגים (מאותה נקודה ואילך הנקודות בשני המסלולים תהיינה זהות) מה שמגביל את רמת הכיסוי של הטבלאות ופוגע בסיכויי ההצלחה למצוא סיסמה (או מפתח הצפנה). טבלת ריינבו היא גישה אחרת המאפשרת התנגשות ללא התמזגות אפילו באותה טבלה. כזכור הלמן הציע להשתמש בטבלאות שונות שההבדל ביניהן הוא שהפונקציה formula_112 שמכינה את פלט הפונקציה כמפתח הצפנה לפונקציה הבאה תהיה שונה במעט מטבלה לטבלה. הרעיון שנקרא מסלול ריינבו (rainbow chain) הוא להשתמש בפונקציית הכנה formula_191 המשתנה לא רק מטבלה לטבלה אלא גם מנקודה לנקודה. אם נתונה הפונקציה החד-כיוונית formula_43 מתחילים מהנקודה formula_193 ומחשבים את המסלול: formula_194 עד שמגיעים ל-formula_195. כל פונקציה שונה מקודמתה באופן מינורי (כמו היפוך מספר מועט של סיביות). בשיטה זו קיימת רק טבלה אחת ואורך המסלולים קבוע. אין צורך בטבלאות מרובות כפי שהציע הלמן וכן אין צורך בנקודות מובחנות כפי שהציע ריבסט. היות שהפונקציות משתנות בתדירות גבוהה, כדי שתהיה התמזגות ההתנגשות חייבת להופיע בדיוק באותה פוזיציה (עמודה). עבור טבלה עם מסלולים באורך formula_19 הסיכויים שיופיע ערך זהה בשתי שורות באותה עמודה הם formula_64. ההסתברות להצלחה בהינתן טבלה בגודל formula_163 חסומה על ידי:
כאשר formula_200 ו-formula_201.
בדומה לטבלאות של הלמן כדי לחפש מפתח, תחילה מחשבים את formula_202 על טקסט המוצפן ומחפשים נקודת סיום תואמת לפלט שהתקבל, אם נמצאה התאמה אפשר לשחזר את המסלול מנקודת ההתחלה של אותה שורה. אם לא נמצאה התאמה, מפעילים את הפונקציות formula_203 על הפלט ומנסים לראות אם המפתח נמצא בעמודה לפני האחרונה, אם לא נמצאה התאמה ממשיכים עם formula_204 וכן הלאה. סך כל הפעולות הן formula_205. זהו שיפור בפקטור של חצי לעומת הטבלאות של הלמן שבהן נדרשים formula_187 הפעלות של הפונקציה formula_43 כדי לחפש ב-formula_19 טבלאות בגודל formula_163.
בהשוואה לטבלאות של הלמן, עם טבלת ריינבו בגודל formula_210, סיכויי ההצלחה בשניהם שווים. בשני המקרים הטבלאות מכסות formula_211 מפתחות עם formula_19 פונקציות הכנה שונות. בשניהם עלולה להיווצר התמזגות אם נמצאה התנגשות באותה טבלה או באותה עמודה במקרה של ריינבו, אך הדבר אינו משפיע על התנגשויות בנקודות אחרות. מעבר לעובדה שהושג שיפור בחצי בסיכויי ההצלחה, לטבלת ריינבו מספר יתרונות:
בניסוי מעשי הראו מפתחי האלגוריתם איך הצליחו לנחש סיסמאות מגובבות של מערכת ההפעלה חלונות, כחלק ממערכת שנקראה LanManager. במערכת זו שעדיין נתמכת בשל תאימות לאחור, השיטה הייתה לחתוך סיסמה באורך מקסימלי של 14 אותיות לשתי מחרוזות באורך 7 בתים כל אחת, אחרי המרת האותיות לאותיות רישיות. כל מחרוזת שימשה כמפתח הצפנה לצופן DES. עם מפתחות אילו מצפינים פעמיים מחרוזת טקסט קבועה (שאינה סודית) ומתקבלים שני פלטים באורך 8 בתים כל אחד, אותם משרשרים יחד למחרוזת אחת באורך 16 בתים המשמשת כגיבוב של הסיסמה.