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

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

הגדרה כללית

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

N מייצג את גודל מרחב החיפוש (למשל מספר המפתחות האפשריים).

P מייצג את הזמן הדרוש לעבודת ההכנה בשלב הלא מקוון.

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

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

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

במקרה של צופן בלוקים $N=2^{n}$ הוא מרחב כל המפתחות האפשריים כאשר $n$ הוא אורך המפתח בסיביות (למשל בצופן AES עם מפתח באורך 128 סיביות $N=2^{128}$ ). למען הפשטות ההנחה היא שגם מרחב המסרים האפשריים הוא $N$ . בדרך כלל לצורך ההתקפה המתקיף רשאי לבחור בלוק מוצפן יחיד והבלוק המקורי שהוצפן. במונח "לבחור" מתכוונים שהמתקיף הצליח להשיג לכל הפחות בלוק טקסט קריא אחד לפי בחירתו ואת תוצאת ההצפנה שלו עם מפתח לא ידוע. מודל זה נקרא התקפת גלוי-נבחר. התקפת איזון זמן/זיכרון שהוצגה לראשונה על ידי מרטין הלמן נחשבת להתקפה הטובה ביותר מסוג זה נגד פונקציה אקראית, היא מאזנת בין הערכים $TM^{2}=N^{2},P=N,D=1$ , הערכים האופטימליים תלויים בעלות היחסית של המשאבים החישוביים שברשות המתקיף. למשל אם $T=M$ , לפי הלמן אפשר להגיע לאיזון של $T=N^{2/3}$ וכן $M=N^{2/3}$ כלומר שיפור בפקטור של שליש לעומת התקפת כוח גס.

רקע

התקפת איזון זמן/זיכרון הועלתה לראשונה ב-1980 על ידי מרטין הלמן^[1]. בעיות חיפוש רבות כמו בעיית תרמיל הגב או בעיית הלוגריתם הבדיד ניתנות לפתרון מהיר יותר מכוח גס באמצעות שימוש מושכל בזמן וזיכרון. כלומר אם קיימים $N$ פתרונות אפשריים לבעיה נתונה, איזון זמן זיכרון מאפשר למצוא את הפתרון הנכון בזמן של $T$ פעולות חישוב עם $M$ מילות זיכרון בתנאי שהמשוואה $TM=N$ מתקיימת. ליתר דיוק האגף הימני של המשוואה צריך להיות $cN\log _{2}N$ אולם אפשר להתעלם מהלוגריתם והקבוע $c$ .

ניחוש מפתח הצפנה שהוא בעצם קריפטואנליזה בסיסית של כל צופן סימטרי, אינו אלא בעיית חיפוש שיש לה שני מקרי קצה. המקרה $T=N,M=1$ שבו לא נעשה שימוש בזיכרון כלל אך מצריך זמן ביצוע מלא, כלומר המתקיף צריך לנסות כמעט את כל $N$ המפתחות האפשריים במקרה הממוצע עד שימצא המפתח הנכון ומהצד השני $T=1,M=N$ שמסתמך על טבלת איחזור ענקית, כך שהזמן הדרוש לאיחזור המפתח הנכון מתקרב ל- $O(1)$ (אם לא מביאים בחשבון את זמן ההכנה). מציאת התאמה בטבלה ממויינת באמצעות חיפוש בינארי וטבלאות גיבוב היא פעולה קלה במונחי מחשוב, אך מאידך המחיר הוא שימוש מופרז בזיכרון. שני מקרי הקצה אינם מעשיים מצד אחד הזמן הדרוש גבוה מדי ומהצד השני כמות הזיכרון בלתי מעשית.

יהיו $t$ ו- $m$ שני פרמטרים שחשיבותם תובהר בהמשך, אם מתעלמים לרגע מזמן הביצוע של ההכנה המוקדמת, חיפוש פתרון של כל פונקציה חד-כיוונית באמצעות טכניקת איזון זמן זיכרון יכול להתבצע בסיבוכיות מקום ממוצעת של $M=tm$ וזמן בסדר גודל של $T=t^{2}$ פעולות בקירוב, בתנאי שמתקיים $mt^{2}=N$ . אם $m=t=N^{1/3}$ מתקבל $M=T=N^{2/3}$ שזהו שיפור משמעותי לעומת חיפוש ממצה של כל הפתרונות האפשריים בשיטה הישירה וזאת עם זיכרון בגודל $tm$ . אם סיבוכיות החיפוש נמדדת במונחים של $M+T$ (זמן פלוס זיכרון) אף על פי שזיכרון וזמן אינם מושגים זהים אפשר להתעלם מפרט זה, בכללות מושג שיפור בפקטור של שליש בסיבוכיות. ההשלכה היא שחיפוש מפתח DES באורך 56 סיביות מתקצר לחיפוש בסדר גודל של 38 סיביות. יתרה מזו, בבעיות מסוימות כמו פרמוטציה פסאודו אקראית או בעיית הלוגריתם הבדיד, אפשר להשיג שיפור גדול יותר עד פקטור של חצי, קרי $M=T=N^{1/2}$ על חשבון עליה קלה בסיבוכיות עבודת ההכנה.

חיפוש ממצה

ערך מורחב – כוח גס

חיפוש ממצה של מפתח ההצפנה או התקפת כוח גס ישירה נגד צופן סימטרי יכולה להתבצע לפי מודל התקפת גלוי-ידוע כך שברשות המתקיף לפחות בלוק טקסט גלוי אחד ובלוק מוצפן שמתאים לו (כלומר שהוצפן עם מפתח סודי כלשהו אותו המתקיף מעוניין לחשוף), אותו הוא השיג בדרך כלשהי אך אין לו שליטה על התוכן. ואילו התקפה שעושה שימוש בטבלת חיפוש דורשת מודל התקפת גלוי-נבחר, כלומר המתקיף שהכין את הטבלה מראש עם בלוק נתון (למשל בלוק המכיל רק אפסים), צריך שתהיה לו היכולת לבחור בזמן ריצה לפחות בלוק גלוי אחד המכיל את הנתונים שהוא מעוניין והבלוק המוצפן המתאים לפני שהוא מתחיל בהתקפה. זה אפשרי בעולם האמיתי, אפשר למשל לחשוב על מקרה שבו המתקיף יודע שהוצפן בלוק המכיל נתונים קבועים הידועים לכל. הרעיון של התקפת כוח גס ישירה פשוט, אם נתון בלוק טקסט מוצפן $C_{0}$ שהוצפן עם המפתח $K$ וההנחה היא שהמתקיף יודע בדרך כלשהי מהו הבלוק שהוצפן $P_{0}$ והוא מעוניין לגלות את $K$ , בניסוח פורמלי:

C_{0}=F_{K}(P_{0})

כאשר $F$ היא פונקציית הצפנה כמו DES והנעלם היחיד במשוואה האמורה הוא $K$ . המתקיף תחילה בונה טבלה שמכילה $N$ הצפנות של $P_{0}$ עם מפתחות הצפנה שונים כאשר $N$ מתייחס למרחב כל המפתחות האפשריים של הצופן (לדוגמה ב-DES $N=2^{56}$ ), בכל שורה בטבלה הוא מאחסן מפתח אחר וטקסט מוצפן מתאים, ממיין את הטבלה לפי הטקסט המוצפן ואז מחפש התאמה עם $C_{0}$ , היות שהטבלה ממוינת אפשר למצוא התאמה אם קיימת באמצעות חיפוש בינארי בזמן של $\log _{2}N$ , אם מאיצים את החיפוש עם טבלאות גיבוב אפשר להתעלם מהלוגריתם לצורך הדיון ולהחשיב את פעולת החיפוש כקרובה ל- $O(1)$ .

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

תיאור כללי של שיטת הלמן

בהינתן פונקציה אקראית $f$ הממפה את המפתח $x$ לבלוק טקסט מוצפן $y$ עבור טקסט קריא קבוע כלשהו. אפשר לראות שקל לחשב את $f$ אבל קשה להפוך אותה, כי חישוב הפונקציה ההופכית $x=f^{-1}(y)$ היא בדיוק הבעיה הקריפטואנליטית של חילוץ מפתח ההצפנה $x$ בהינתן טקסט מוצפן $y$ . כדי לבצע את הפעולה ההפוכה מהר יותר מכוח גס הציע הלמן לנצל את פרדוקס יום ההולדת על ידי הוספת שלב "קדם עיבוד" שמנסה "לכסות" במידה רבה ככל האפשר את $N$ הנקודות של מרחב המפתח. כלומר להגביר ככל האפשר את הסיכויים שהמפתח אותו מחפשים יפול במקרה באחת מנקודות הכיסוי. הוא הציע להשתמש במטריצה מסדר $m\times t$ שהשורות בה הם "מסלולים" באורך $t$ הנוצרים מהפעלה רקורסיבית של הפונקציה $f$ על $m$ נקודות התחלה אקראיות שונות. היות שכל נקודה ניתנת לחישוב על ידי הנקודה הקודמת לה במסלול, אפשר למעשה לאחסן בזיכרון רק את נקודת ההתחלה ונקודת הסיום של כל מסלול כזה. תוצאת שלב ההכנה היא הטבלה המכילה אוסף ערכים המייצגים נקודות התחלה ונקודות סיום של המסלולים, הממוינים לפי נקודת הסיום. בשלב ההתקפה המקוונת המתקיף מנסה לגלות אם $x$ מכוסה על ידי אחת הנקודות בטבלה. האלגוריתם מחשב את $f$ על $y$ באופן איטרטיבי, סורק את עמודוצת הטבלה ומנסה למצוא התאמה של התוצאה שבידו עם נקודת סיום כלשהי. אם נמצאה התאמה הוא יודע שהפתרון $x$ נמצא בשורה זו ולכן כל שעליו לעשות הוא לקפוץ לנקודת ההתחלה של אותה שורה ולחשב את $f$ על $y$ במספר הפעמים הדרוש עד שהוא מגיע ל- $x$ והערך שבו ביקר צעד אחד לפניו הוא הפתרון הנכון בסבירות גבוהה.

התמזגות

מטריצה אחת לא יכולה לכסות את כל הנקודות כי ככל שמוסיפים שורות, לפי פרדוקס יום ההולדת כל עוד $t\cdot mt\leq N$ בהכרח שייוצרו התנגשויות. התנגשות פירושה שהתקבל ערך זהה בשתי נקודות בשורות שונות לא בהכרח באותה עמודה. הבעיה היא שכל התנגשות גורמת להתמזגות, אם נקודה מסוימת הופיעה שוב בשורה אחרת מנקודה זו ואילך עד סוף המסלול הנקודות בשתי השורות הללו תהיינה זהות. התמזגויות קשות להבחנה כיוון שאם ההתנגשות חלה בעמודות שונות נקודת הסיום לא תהיה זהה. מבחינה סטטיסטית התמזגויות פוגעות באופן משמעותי ברמת הכיסוי ולכן בסיכויים לנחש מפתח, זאת למרות עבודת ההכנה הזהה. החסם העליון לכיסוי מקסימלי עבור טבלה אחת הוא במקרה שהפרמטרים מקיימים $mt^{2}=N$ . במקרה כזה הטבלה מכסה רק שטח של $1/t$ מהמרחב לכן יש צורך ב- $t$ טבלאות בלתי תלויות כאלו כדי לכסות את המרחב כולו. אולם הלמן הבחין בעובדה מעניינת שאם משנים מעט את הפונקציה $f$ עבור כל טבלה, למשל $f_{i}(x)=h_{i}(f(x))$ כאשר $h_{i}$ היא פונקציה פשוטה של הפלט כמו סידור מחדש של סיביות, אפשר למנוע התנגשויות ולשפר את רמת הכיסוי מאוד. התכונות של הפונקציות המותאמות הן:

כל זוג נקודות $f_{i}$ ו- $f_{j}$ כאשר $i\neq j$ בעיקרון בלתי תלויות. גם אם תימצא נקודה זהה אין זה מעיד בהכרח על התמזגות, כלומר הנקודות שלאחריה לא תהיינה בהכרח זהות. כתוצאה מכך האיחוד של $t$ המטריצות (כשכל אחת מכסה $mt$ נקודות) מכסה חלק קבוע פחות או יותר של טווח הכיסוי המלא.
הבעיה של חישוב $x$ מתוך $y=f(x)$ ניתנת לפתרון על ידי היפוך כל אחת מהווריאציות $f_{i}$ של הפונקציה $f$ מעל הנקודה המתאימה $y_{i}=f_{i}(x)=h_{i}(f(x))$ .
הערך $y_{i}=f_{i}(x)$ ניתן לחישוב אפילו אם $x$ לא ידוע על ידי חישוב $h_{i}$ לערך כלשהו $y=f(x)$ .

שלב ההכנה דורש רק $P\approx N$ פעולות, כל מטריצה מכסה $mt$ נקודות אך דורשת רק $m$ מילים בזיכרון, כל פעולת חיפוש בטבלה דורשת $t$ ניסיונות שכל אחד מהם דורש $t$ הפעלות של פונקציה $f_{i}$ כלשהי של אחת הטבלאות, זמן ההתקפה הכולל הוא $T=t^{2}$ , כדי למצוא את עקומת האיזון בין $T$ ל- $M$ שמביאה לביצועים אופטימליים משתמשים בחסם האמור $mt^{2}=N$ ומקבלים $TM^{2}=t^{2}\cdot m^{2}t^{2}=N^{2}$ . בעוד שהזמן $T$ יכול להיות כל ערך בטווח $1\leq T\leq N$ , המקום $M$ מוגבל ל- $N^{1/2}\leq M\leq N$ שאם לא כן יוצא ש- $T>N$ ואז ההתקפה תהיה איטית מכוח גס.

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

יהי $E_{K}(X):2^{n}\times 2^{k}\rightarrow 2^{n}$ פונקציה המייצגת הצפנה של בלוק $n$ -סיביות טקסט קריא $X$ עם מפתח סודי $K$ בגודל $k$ סיביות. כחלק מההתקפה בלוק טקסט מוצפן בגודל $n$ משמש בעצמו כמפתח הצפנה בגודל $k$ כך שיש צורך בפונקציה כלשהי שממירה בלוק מוצפן של $n$ סיביות למפתח הצפנה $g:2^{n}\rightarrow 2^{k}$ . במקרה של DES המפתח קטן מהבלוק, לכן הציע הלמן למשל פונקציית כיווץ פשוטה שחותכת את התוצאה לגודל הרצוי ומתעלמת משמונה הסיביות האחרונות. במקרה ש- $n<k$ – מצב אפשרי בצופן AES עם מפתח הגדול מ-128, הפונקציה יכולה להוסיף מספר סיביות קבועות (למשל אפסים) כדי להרחיב את הבלוק $n$ לגודל המתאים כמפתח.

לסיכום לצורך ההתקפה מגדירים פונקציה $f$ שהיא תוצאת הצפנה של הבלוק $P$ לאחר המרה למפתח הצפנה עם הפונקציה $g$ (הפונקציה $g$ אינה הכרחית אם הבלוק המוצפן יכול לשמש ישירות כמפתח הצפנה):

f(K)=g(E_{K}(P))

.

חישוב $f(K)$ הוא פעולה קלה כפעולת הצפנה. לעומת זאת חישוב $K$ מתוך $f(K)$ שקול לקריפטואנליזה של הצופן. התקפת איזון זמן/זיכרון מורכבת משני שלבים, שלב הכנה שמתבצע אוף ליין ושלב ההתקפה און ליין המתוארים להלן.

שלב ההכנה הלא מקוון

תחילה $N=2^{n}$ הוא מרחב המפתחות האפשריים. התוקף בוחר מתוך המרחב $N$ , $m$ נקודות התחלה start point אקראיות שונות שיהיו מפתחות הצפנה, אותן מסמנים: ${\text{SP}}_{1},{\text{SP}}_{2},...,{\text{SP}}_{m}$ . ואז עבור כל נקודת התחלה מחשב את 'שרשרת ההצפנה' כדלהלן: (א) מציב בכניסה הראשונה בשורה $i$ את נקודת ההתחלה $X_{i,0}={\text{SP}}_{i}$ ואז (ב) כל כניסה הבאה אחריה מכילה את $X_{i,j+1}=f(X_{i,j})$ עבור $1\leq j\leq t$ , כלומר כל כניסה היא הצפנה של $P$ עם מפתח שהוא תוצאת ההצפנה של כניסה קודמת. הטקסט המוצפן עצמו משמש כמפתח הצפנה לאחר שעבר המרה מתאימה עם הפונקציה $g$ . למעשה שורה אחת היא שרשרת של $t$ הצפנות חוזרות של $P$ על ידי $f$ , עם סדרה של מפתחות שהאחד נוצר מהשני, עד שמגיעים לנקודת הסיום $X_{i,t}={\text{EP}}_{i}$ . לסיכום הטבלה היא:

{\text{SP}}_{1}=X_{1,0}\ \ \ {\xrightarrow {f}}\ \ \ X_{1,1}\ \ \ {\xrightarrow {f}}\ \ \ X_{1,2}\ \ \ {\xrightarrow {f}}\ \ \ \cdots \cdots \ \ \ {\xrightarrow {f}}\ \ \ X_{1,t}={\text{EP}}_{1}

{\text{SP}}_{2}=X_{2,0}\ \ \ {\xrightarrow {f}}\ \ \ X_{2,1}\ \ \ {\xrightarrow {f}}\ \ \ X_{2,2}\ \ \ {\xrightarrow {f}}\ \ \ \cdots \cdots \ \ \ {\xrightarrow {f}}\ \ \ X_{2,t}={\text{EP}}_{2}

{\text{SP}}_{3}=X_{3,0}\ \ \ {\xrightarrow {f}}\ \ \ X_{3,1}\ \ \ {\xrightarrow {f}}\ \ \ X_{3,2}\ \ \ {\xrightarrow {f}}\ \ \ \cdots \cdots \ \ \ {\xrightarrow {f}}\ \ \ X_{3,t}={\text{EP}}_{3}

\vdots

{\text{SP}}_{m}=X_{m,0}\;\;\;{\xrightarrow {f}}\;\;\ X_{m,1}\;\;{\xrightarrow {f}}\;\;\ X_{m,2}\;\;\;{\xrightarrow {f}}\;\;\;\cdots \cdots \;\;\;{\xrightarrow {f}}\;\;\ X_{m,t}={\text{EP}}_{m}

כדי לצמצם דרישות זיכרון לא מאחסנים את ערכי הביניים אלא את נקודות ההתחלה והסיום ${\text{SP}}_{i},{\text{EP}}_{i}$ בלבד וממיינים אותן בסדר נומרי לפי נקודות הסיום ${\text{EP}}_{i}$ .

שלב ההתקפה המקוונת

לצורך הפשטות (כאמור לעיל) משתמש מסוים בחר במפתח סודי $K$ כלשהו, הצפין את הבלוק הקריא $P$ (שידוע לתוקף, למשל הבלוק יכול להיות מחרוזת אפסים או כל טקסט קבוע ומוסכם) ובדרך מסוימת התוצאה $C=E_{K}(P)$ נפלה לידי התוקף ועליו לגלות את $K$ . התוקף מיישם את הפונקציה $g$ כדי לקבל את $Y_{1}=g(C)=f(K)$ ואז מבצע את המהלכים הבאים:

בודק בטבלה אם $Y_{1}={\text{EP}}_{i}$ , עבור כל $i$ מ- $1$ עד $m$ . במקרה שכן, התוקף יודע שהמפתח הנכון הוא הערך האחד לפני אחרון בשורה $i$ כי כאמור הערך האחרון הוא תוצאה של הצפנת המקור עם מפתח אחד לפניו. היות שתוצאות הביניים לא שמורות, עליו לחשב את כל השורה מנקודת ההתחלה לפי הסדר עד הגיעו לנקודה הרצויה במקרה זה $X_{i,t-1}$ וזהו בדיוק המפתח אותו הוא מחפש. כעת עליו רק לוודא שפענוח $C$ אכן מוביל ל- $P$ וההתקפה הסתיימה בהצלחה. ייתכן מצב שבו ל- ${\text{EP}}_{i}$ יש יותר ממקור אחד ואז השוויון האחרון אינו נכון, כלומר אף על פי שקיימת התאמה עם ${\text{EP}}_{i}$ , בפענוח $C$ התגלה שהתוצאה אינה תואמת את $P$ . זהו מצב אפשרי והוא מכונה כאן 'אזעקת שווא'. מתייחסים אליו כאילו לא הייתה התאמה. הוכח שמספר אזעקות השווא הצפוי חסום על ידי $mt(t+1)/2N$ .
אם $Y_{1}\neq {\text{EP}}_{i}$ . כלומר אף אחת מנקודות הסיום אינה מתאימה, או שהייתה אזעקת שווא מסעיף 1, התוקף מחשב את $Y_{2}=f(Y_{1})$ וחוזר לשלב 1. בשלב זה הבדיקה תוכיח אם המפתח הוא בעמודה השנייה מימין ( $X_{i,t-2}$ ), בסבב השלישי ייבדק אם המפתח הוא אחד מ- $X_{i,t-3}$ וכן הלאה עד לבדיקת כל הערכים בטבלה, שאז במידה שלא נמצאה התאמה ההתקפה נכשלה.

יש לשים לב שהתוקף צריך לגשת לטבלה בכל פעם שמחושב $Y$ חדש. אם כל $m\times t$ האלמנטים שבטבלה שונים, ההסתברות להצלחה היא $\textstyle P(S)={\frac {m\times t}{2^{k}}}$ . בפועל סיכויי ההצלחה נמוכים יותר כי הם תלויים באופן שבו השרשראות מתפרסות על פני מרחב המפתח. קיימת גם אפשרות ששרשרת הצפנה שהתחילה עם מפתח אחד תתנגש ותתמזג עם שרשרת אחרת שהתחילה עם מפתח אחר (מנקודה זו ועד לנקודת הסיום כל החוליות בשתי השרשראות תהיינה זהות). ככל שהטבלה גדולה יותר כך גדלים הסיכויים להתנגשות. כל התמזגות מצמצמת למעשה את מספר האפשרויות שהטבלה מכסה. אם $f$ היא פונקציה ראנדומלית, ההסתברות להצלחה חסומה ב:

P(S)\geq {\frac {1}{N}}\sum _{i=1}^{m}\sum _{j=0}^{t-1}\left({\frac {N-it}{N}}\right)^{j+1}

מהמשוואה עולה כי הערכים האופטימליים של $t$ ו- $m$ הם כאלו שמקיימים $mt^{2}=N$ שאז הסיכויים הם בערך $1/0.80=1.25$ . שזהו לא שיפור משמעותי כפי שהיינו מצפים. כדי לקבל סיכויי הצלחה גבוהים יותר משתמשים בטבלאות מרובות, כל אחת עם פונקציה $f$ שונה, בכך מבטיחים פריסה טובה יותר של אלמנטים והימנעות מהתמזגויות ובכך מגבירים את הסיכויים בפקטור שהוא ביחס לכמות הטבלאות (או סך כל האלמנטים). אי אפשר למנוע התנגשות לגמרי אך גם אם ערך כלשהו מתנגש בנקודה כלשהי היות שהפונקציה שונה לא תתרחש התמזגות. בכללות עבור $r$ טבלאות הסיכויים הם:

P(S)_{\text{total}}\geq 1-(1-P(S)_{\text{table}})^{r}

כאשר $P(S)_{\text{table}}$ מתייחס לסיכויים עם טבלה אחת. אם מציבים $m=t=N^{1/3}$ ההסתברות לטבלה אחת היא בערך $P(S)=N^{1/3}$ , לכן עם $N^{1/3}$ טבלאות אפשר להשיג סיכויים של $N^{2/3}$ . כמות הזיכרון תהיה במקרה זה $M=N^{2/3}$ מילים וסך כל הפעולות הוא $T=N^{2/3}$ . החיפוש בטבלאות יכול להתבצע באופן סדרתי או מקבילי להאצה נוספת וכמובן שאפשר להשתמש ביותר טבלאות לפי הצורך כדי להגביר סיכויים.

נקודות מובחנות

חיסרון מעשי אחד בשיטת הלמן הוא מספר הקריאות בדיסק הקשיח. באופן כללי גישה לדיסק צורכת כשמונה מילישניות לעומת פעולה בתוך זיכרון המעבד שהיא בערך שתי ננושניות. בגלל ההבדל העצום במהירות הגישה מומלץ לצמצם את מספר הקריאות בדיסק ככל האפשר. רון ריבסט הציע רעיון במקום לקבוע את אורך המסלולים בכל שורה בטבלה לאורך קבוע, המסלול יכול להמשיך עד שמגיעים לנקודה כלשהי שיש לה מאפיין מיוחד כלשהו כמו ערך המכיל רצף מסוים של אפסים. נקודה כזו נקראת "נקודה מובחנת" (באנגלית Distinguished point). במהלך שלב ההכנה מתחילים מנקודות התחלה מובחנות אקראיות ומחשבים את המסלולים באותה דרך, אך עוצרים רק כאשר מגיעים לנקודה מובחנת נוספת. כך נוצרים מסלולים באורכים שונים המכילים נקודות מובחנות בלבד. אם $k=\log(t)$ האורך הצפוי של כל מסלול יהיה בערך $t$ . קבוצת כל נקודות הסיום בכל $t$ הטבלאות בסך הכול $t^{2}m$ נקודות מכסה כמות ניכרת של בערך $N/t$ מהנקודות המובחנות האפשריות. נקודות מובחנות קלות להכנה וקלות לזיהוי.

היתרון העיקרי של גישה זו הוא שבמהלך ההתקפה יש צורך לבצע רק קריאה אחת בדיסק הקשיח עבור כל מסלול (כאשר ניתקלים לראשונה בנקודה מובחנת), מספר ההפעלות של הפונקציה $f_{i}$ נשאר $t^{2}$ אבל מספר הקריאות בדיסק יורד מ- $t^{2}$ ל- $t$ שזה יתרון משמעותי.

Rainbow Table

טבלת ריינבו^[2] היא שיטת כוח גס גנרית המבוססת על שיטת הלמן לשבירת פונקציית גיבוב, יעילה בעיקר לניחוש סיסמאות או מספרי כרטיס אשראי וכדומה המכילים מחרוזת אלפנומרית קצרה. הוצעה לראשונה על ידי 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$ חסומה על ידי:

P_{table}=1-\prod _{i-1}^{t}\left(1-{\frac {m_{i}}{N}}\right)

.

כאשר $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 (מלח) שהיא מחרוזת אקראית חד-פעמית שאינה סודית. גישה אחרת היא להגביר את כמות העבודה הדרושה בהכנת סיסמה אחת, למשל להפעיל את פונקציית הגיבוב אלף פעמים במקום פעם אחת עבור כל סיסמה. ההאטה בזמן עבור משתמש בודד אינה מורגשת, אך היא מאטה מאוד את הזמן הכולל הדרוש לשלב ההכנה המקודם של התקפת איזון/זמן זיכרון והופכת אותה ללא כדאית.

התקפת איזון זמן/זיכרון/דטה

בשל ההתנהגות השונה של צופן זרם לעומת צופן בלוקים, התקפת איזון זמן/זיכרון נגד צופן זרם שונה בהתאם. היא נקראת התקפת איזון זמן/זיכרון/דטה (time/memory/data tradeoff), כי נוסף אלמנט שלא קיים בהתקפה הבסיסית המתייחס לכמות המידע המושג און ליין הדרוש לצורך ההתקפה. בצופן זרם, המרחב $N$ מייצג את מספר המצבים הפנימיים של המחולל שיכול להיות שונה ממרחב המפתחות. "מצב פנימי" של המחולל הפסאודו אקראי המובנה בצופן זרם הוא בעצם תכולת הזיכרון הפנימי ברגע נתון בזמן הפעלת הצופן. כזכור צופן זרם הוא סוג של מכונת מצבים שמכילה זיכרון. הנתונים שהמתקיף מקבל בזמן ההתקפה הם $D$ הסיביות הראשונות של פלט המחולל שהן בעצם תחילתו של זרם המפתח איתו הוצפן הטקסט הקריא. ההנחה היא שהמתקיף הצליח להשיג אותן למשל על ידי XOR עם קטע טקסט קריא ידוע כמו כותר (במקרה זה אין הבדל בין מודל התקפת גלוי-ידוע לבין גלוי-נבחר). מטרת המתקיף או הקריפטואנליסט היא לגלות לפחות אחד מהמצבים הפנימיים של המחולל. משום שברגע שנמצא מצב פנימי אחד, ניתן לשחזר את כל הסיביות שהופקו מנקודת זמן זו ואילך על ידי הפעלת המחולל קדימה במספר הפעימות הדרוש עד לפענוח כל הטקסט המוצפן. כמובן שהמתקיף יכול להפעיל את המחולל לאחור ובכך להגיע למצב הפנימי הראשון או במילים אחרות לגלות את מפתח ההצפנה, אבל בצופן זרם פעולה זו לא נחוצה כלל כי בידי המתקיף מספיק מידע לפענח את כל הטקסט המוצפן מנקודה זו.

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

התקפת איזון זמן זיכרון על צופן זרם תוארה לראשונה על ידי Steve Babbage^[3] ו-Jovan Dj. Golić^[4]. בהתקפה זו ממפים את $N$ המצבים הפנימיים האפשריים ל- $\log(N)$ הסיביות הראשונות שנוצרו על ידי המחולל. במילים אחרות המיפוי $f(x)=y$ מהמצב הפנימי $x$ לפלט המחולל $y$ נחשב כפונקציה אקראית חד-כיוונית מעל $N$ נקודות שקל לחשב בכיוון אחד אך קשה להפוך. אם המתקיף מצליח להפוך את הפונקציה עבור מצב פנימי אחד כלומר למצוא את מצב פנימי כלשהו לפי פלט המחולל הרי שהוא הצליח לשבור את הצופן. שלב ההכנה המקודמת של ההתקפה מתחיל ב- $M$ מצבים פנימיים אקראיים כלשהם וחישוב פלט המחולל לפי מצבים אילו עד טווח מסוים, אחסונם בטבלה ענקית לפי סדר עולה של הפלט. שורות הטבלה מכילות $(x_{i},y_{i})$ כאשר $x_{i}$ הוא מצב פנימי כלשהו ו- $y_{i}$ הוא פלט המחולל. בשלב ההתקפה המקוונת ניתנים למתקיף $D+\log(N)-1$ סיביות מהם המתקיף מכין את כל החלונות (או רצפים) האפשריים $y_{1},y_{2},...,y_{D}$ של $\log(N)$ סיביות עוקבות (עם חפיפות). היות שהטבלה ממויינת אפשר למצוא בזמן לוגריתמי שורה בטבלה המכילה מצב פנימי ופלט שמתאימים לרצף הקיים $D$ אם קיימת. בשל פרדוקס יום ההולדת אפשר להעריך את האיזון בין זמן וזיכרון ולהגיע לסיבוכיות אופטימלית. כיוון שידוע שהתנגשות (התאמה) בין שתי תת-קבוצות מתוך $N$ נקודות תקרה בהסתברות גבוהה אם המכפלה שלהן גבוהה מ- $N$ . אם מתעלמים מהלוגריתם מתקבל $DM=N$ כאשר זמן ההכנה הוא $P=M$ וזמן ההתקפה הוא $T=D$ . אפשר לצמצם את $T$ מ- $D$ ל-1 ולהכליל את האיזון ל- $TM=N$ כמו האיזון של הלמן לתמורה אקראית בניגוד לאיזון $TM^{2}=N^{2}$ לפונקציה אקראית (לכן כאשר $T=M$ מתקבל $T=M=N^{1/2}$ שזה פקטור של חצי במקום שליש). אף על פי שבאמת ההשוואה אינה מדויקת בגלל שצופן זרם מתנהג אחרת.

אלכס ביריוקוב ועדי שמיר הרחיבו ושיפרו את ההתקפה בסגנון איזון זמן/זיכרון/דאטה^[5] באופן כזה שניצול $D$ משפר את סיבוכיות ההתקפה על ידי שילוב שני הסוגים המתוארים. כלומר $P=N/D$ וכן $TM^{2}D^{2}=N^{2}$ עבור כל $D^{2}\leq T\leq N$ . עם זה אפשר להשיג איזון של זמן עיבוד מוקדם $P=N^{2/3}$ וכן זמן התקפה $T=N^{2/3}$ וזיכרון $M=N^{1/3}$ עם דטה זמינה און ליין בסדר גודל $D=N^{1/3}$ . למשל עבור $N=2^{100}$ הפרמטרים $P=T=2^{66}$ וכן $M=D=2^{33}$ הם כמעט פרקטיים.