התקפת איזון זמן/זיכרון
Rainbow Table

טבלת ריינבו היא שיטת כוח גס גנרית המבוססת על שיטת הלמן לשבירת פונקציית גיבוב, יעילה בעיקר לניחוש סיסמאות או מספרי כרטיס אשראי וכדומה המכילים מחרוזת אלפנומרית קצרה. הוצעה לראשונה על ידי Philippe Oechslin ב-2003 ומהווה שיפור ניכר של שיטת הלמן המתוארת לעיל. המגבלה העיקרית בשיטת הלמן היא שכאשר שני מסלולים מתנגשים באותה טבלה הם מתמזגים (מאותה נקודה ואילך הנקודות בשני המסלולים תהיינה זהות) מה שמגביל את רמת הכיסוי של הטבלאות ופוגע בסיכויי ההצלחה למצוא סיסמה (או מפתח הצפנה). טבלת ריינבו היא גישה אחרת המאפשרת התנגשות ללא התמזגות אפילו באותה טבלה. כזכור הלמן הציע להשתמש בטבלאות שונות שההבדל ביניהן הוא שהפונקציה  g שמכינה את פלט הפונקציה כמפתח הצפנה לפונקציה הבאה תהיה שונה במעט מטבלה לטבלה. הרעיון שנקרא מסלול ריינבו (rainbow chain) הוא להשתמש בפונקציית הכנה  R_{i} המשתנה לא רק מטבלה לטבלה אלא גם מנקודה לנקודה. אם נתונה הפונקציה החד-כיוונית  f מתחילים מהנקודה  R_{1}(f_{0}(X_{0})) ומחשבים את המסלול:  X_{i+1}=R_{i}(f_{i-1}(X_{i})) עד שמגיעים ל- R_{t},f_{t-1}(X). כל פונקציה שונה מקודמתה באופן מינורי (כמו היפוך מספר מועט של סיביות). בשיטה זו קיימת רק טבלה אחת ואורך המסלולים קבוע. אין צורך בטבלאות מרובות כפי שהציע הלמן וכן אין צורך בנקודות מובחנות כפי שהציע ריבסט. היות שהפונקציות משתנות בתדירות גבוהה, כדי שתהיה התמזגות ההתנגשות חייבת להופיע בדיוק באותה פוזיציה (עמודה). עבור טבלה עם מסלולים באורך  t הסיכויים שיופיע ערך זהה בשתי שורות באותה עמודה הם  1/t. ההסתברות להצלחה בהינתן טבלה בגודל  m\times t  חסומה על ידי:
כאשר  m_{1}=m ו- m_{n+1}=N\left(1-e^{-{\frac {m_{n}}{N}}}\right).
בדומה לטבלאות של הלמן כדי לחפש מפתח, תחילה מחשבים את  R_{n-1} על טקסט המוצפן ומחפשים נקודת סיום תואמת לפלט שהתקבל, אם נמצאה התאמה אפשר לשחזר את המסלול מנקודת ההתחלה של אותה שורה. אם לא נמצאה התאמה, מפעילים את הפונקציות  R_{n-2},f_{n-1} על הפלט ומנסים לראות אם המפתח נמצא בעמודה לפני האחרונה, אם לא נמצאה התאמה ממשיכים עם  R_{n-3},f_{n-2},f_{n-1} וכן הלאה. סך כל הפעולות הן  \textstyle {\frac {t(t-1)}{2}}. זהו שיפור בפקטור של חצי לעומת הטבלאות של הלמן שבהן נדרשים  t^{2} הפעלות של הפונקציה  f כדי לחפש ב- t טבלאות בגודל  m\times t.
בהשוואה לטבלאות של הלמן, עם טבלת ריינבו בגודל  mt\times t, סיכויי ההצלחה בשניהם שווים. בשני המקרים הטבלאות מכסות  mt^{2} מפתחות עם  t פונקציות הכנה שונות. בשניהם עלולה להיווצר התמזגות אם נמצאה התנגשות באותה טבלה או באותה עמודה במקרה של ריינבו, אך הדבר אינו משפיע על התנגשויות בנקודות אחרות. מעבר לעובדה שהושג שיפור בחצי בסיכויי ההצלחה, לטבלת ריינבו מספר יתרונות:
מספר הטבלאות מצטמצם בפקטור של  t.
התמזגות של מסלול ריינבו גורמת לכך שנקודת הסיום תהיה זהה ולכן ניתן להבחין בכך. בדרך זו אפשר לייצר טבלאות נטולות התמזגויות (אך לא נטולות התנגשויות).
טבלת ריינבו נטולת לולאות. לולאה היא מצב שבו הפונקציה  f מייצרת מסלול קצר מ- t שחוזר על עצמו באופן מעגלי. אפשר לאתר לולאות גם בשיטת הלמן אך הדבר דורש פעולות נוספות.
שיטת הנקודות המובחנות של ריבסט יוצרת בעיה בגלל האורך המשתנה של המסלולים. לעובדה זו חשיבות רבה, כי זה עוזר לצמצם את מספר אזעקות השווא כזכור אילו מקרים בהם אף על פי שפלט הפונקציה תואם המפתח שונה.
בניסוי מעשי הראו מפתחי האלגוריתם איך הצליחו לנחש סיסמאות מגובבות של מערכת ההפעלה חלונות, כחלק ממערכת שנקראה LanManager. במערכת זו שעדיין נתמכת בשל תאימות לאחור, השיטה הייתה לחתוך סיסמה באורך מקסימלי של 14 אותיות לשתי מחרוזות באורך 7 בתים כל אחת, אחרי המרת האותיות לאותיות רישיות. כל מחרוזת שימשה כמפתח הצפנה לצופן DES. עם מפתחות אילו מצפינים פעמיים מחרוזת טקסט קבועה (שאינה סודית) ומתקבלים שני פלטים באורך 8 בתים כל אחד, אותם משרשרים יחד למחרוזת אחת באורך 16 בתים המשמשת כגיבוב של הסיסמה.
בגלל התכנון הגרוע, אפשר לתקוף את המערכת בשיטת הפרד ומשול, מנסים לנחש כל חצי של מחרוזת הגיבוב בנפרד. היות שהסיסמה היא לכל היותר 14 אותיות או ספרות למעשה סיבוכיות ההתקפה היא רק  2^{37} פעולות גיבוב של 8 בתים לעומת  2^{83} של 16 בתים. לצורך הדגמה הם השתמשו בטבלת ריינבו אחת בגודל  t=4666,m=38223872. כמו כן השוו ביצועים לעומת 4666 טבלאות הלמן בגודל  4666\times 8192. עם טבלאות אילו הם ניסו לנחש 500 סיסמאות אקראיות על מחשב שולחני מסוג פנטיום 4 1.5GHz עם זיכרון בגודל 500MB. רמת הכיסוי הגיעה ל-75.8% בטבלאות הלמן ו-78.8% בטבלת ריינבו והביצועים שהתקבלו הראו שטבלת ריינבו הייתה מהירה פי שבעה מטבלאות הלמן באותו גודל. עם שטח אחסון שאינו עולה על 1.4GB אפשר היה לפצח 99.9 אחוז מכל הגיבובים של סיסמאות אלפנומריות בטווח  2^{37} בזמן של 13.6 שניות. תוצאה זו היא המהירה ביותר בהשוואה לשיטות אחרות.
הדרך הטובה ביותר לסכל התקפה כזו היא להוסיף גיוון לתהליך גיבוב הסיסמאות. השיטה המומלצת כיום היא פונקציית גזירת מפתח קריפטוגרפית שמשלבת salt (מלח) שהיא מחרוזת אקראית חד-פעמית שאינה סודית. גישה אחרת היא להגביר את כמות העבודה הדרושה בהכנת סיסמה אחת, למשל להפעיל את פונקציית הגיבוב אלף פעמים במקום פעם אחת עבור כל סיסמה. ההאטה בזמן עבור משתמש בודד אינה מורגשת, אך היא מאטה מאוד את הזמן הכולל הדרוש לשלב ההכנה המקודם של התקפת איזון/זמן זיכרון והופכת אותה ללא כדאית.