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

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

רקע

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

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

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

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

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

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

בשל ההתנהגות השונה של צופן זרם לעומת צופן בלוקים, התקפת איזון זמן/זיכרון נגד צופן זרם שונה בהתאם. היא נקראת התקפת איזון זמן/זיכרון/דטה (time/memory/data tradeoff), כי נוסף אלמנט שלא קיים בהתקפה הבסיסית המתייחס לכמות המידע המושג און ליין הדרוש לצורך ההתקפה. בצופן זרם, המרחב  מייצג את מספר המצבים הפנימיים של המחולל שיכול להיות שונה ממרחב המפתחות. "מצב פנימי" של המחולל הפסאודו אקראי המובנה בצופן זרם הוא בעצם תכולת הזיכרון הפנימי ברגע נתון בזמן הפעלת הצופן. כזכור צופן זרם הוא סוג של מכונת מצבים שמכילה זיכרון. הנתונים שהמתקיף מקבל בזמן ההתקפה הם  הסיביות הראשונות של פלט המחולל שהן בעצם תחילתו של זרם המפתח איתו הוצפן הטקסט הקריא. ההנחה היא שהמתקיף הצליח להשיג אותן למשל על ידי XOR עם קטע טקסט קריא ידוע כמו כותר (במקרה זה אין הבדל בין מודל התקפת גלוי-ידוע לבין גלוי-נבחר). מטרת המתקיף או הקריפטואנליסט היא לגלות לפחות אחד מהמצבים הפנימיים של המחולל. משום שברגע שנמצא מצב פנימי אחד, ניתן לשחזר את כל הסיביות שהופקו מנקודת זמן זו ואילך על ידי הפעלת המחולל קדימה במספר הפעימות הדרוש עד לפענוח כל הטקסט המוצפן. כמובן שהמתקיף יכול להפעיל את המחולל לאחור ובכך להגיע למצב הפנימי הראשון או במילים אחרות לגלות את מפתח ההצפנה, אבל בצופן זרם פעולה זו לא נחוצה כלל כי בידי המתקיף מספיק מידע לפענח את כל הטקסט המוצפן מנקודה זו.
כדי להבין את ההבדל בין צופן זרם לצופן בלוקים בהקשר זה. אפשר לראות שבצופן בלוקים קיים בידי המתקיף בלוק אחד שאיתו הוא מבצע את ההתקפה, כלומר ישנם שני קלטים (מפתח ובלוק קריא) ופלט אחד (בלוק מוצפן). לא ניתן להפיק תועלת ממספר מרובה של בלוקים ידועים כי בלוקים שונים מצריכים טבלאות שונות. לעומת זאת בצופן זרם קיים רק קלט אחד (מצב פנימי) ופלט אחד (קטע מזרם המחולל), כאשר מנסים להפוך את הפונקציה במקרה זה אפשר לעשות שימוש באותן טבלאות כדי להפוך מספר פלטים שונים. למעשה בצופן בלוקים לא ברור איך אפשר בשיטת הלמן לשפר את ההתקפה אם בידי המתקיף יותר מבלוק אחד, לעומת זאת בצופן זרם מספר רב של סיביות פלט יכול לשפר את הסיכויים משמעותית.
התקפת איזון זמן זיכרון על צופן זרם תוארה לראשונה על ידי Steve Babbage ו-Jovan Dj. Golić. בהתקפה זו ממפים את  המצבים הפנימיים האפשריים ל- הסיביות הראשונות שנוצרו על ידי המחולל. במילים אחרות המיפוי  מהמצב הפנימי  לפלט המחולל  נחשב כפונקציה אקראית חד-כיוונית מעל  נקודות שקל לחשב בכיוון אחד אך קשה להפוך. אם המתקיף מצליח להפוך את הפונקציה עבור מצב פנימי אחד כלומר למצוא את מצב פנימי כלשהו לפי פלט המחולל הרי שהוא הצליח לשבור את הצופן. שלב ההכנה המקודמת של ההתקפה מתחיל ב- מצבים פנימיים אקראיים כלשהם וחישוב פלט המחולל לפי מצבים אילו עד טווח מסוים, אחסונם בטבלה ענקית לפי סדר עולה של הפלט. שורות הטבלה מכילות  כאשר  הוא מצב פנימי כלשהו ו- הוא פלט המחולל. בשלב ההתקפה המקוונת ניתנים למתקיף  סיביות מהם המתקיף מכין את כל החלונות (או רצפים) האפשריים  של  סיביות עוקבות (עם חפיפות). היות שהטבלה ממויינת אפשר למצוא בזמן לוגריתמי שורה בטבלה המכילה מצב פנימי ופלט שמתאימים לרצף הקיים  אם קיימת. בשל פרדוקס יום ההולדת אפשר להעריך את האיזון בין זמן וזיכרון ולהגיע לסיבוכיות אופטימלית. כיוון שידוע שהתנגשות (התאמה) בין שתי תת-קבוצות מתוך  נקודות תקרה בהסתברות גבוהה אם המכפלה שלהן גבוהה מ-. אם מתעלמים מהלוגריתם מתקבל  כאשר זמן ההכנה הוא  וזמן ההתקפה הוא . אפשר לצמצם את  מ- ל-1 ולהכליל את האיזון ל- כמו האיזון של הלמן לתמורה אקראית בניגוד לאיזון  לפונקציה אקראית (לכן כאשר  מתקבל  שזה פקטור של חצי במקום שליש). אף על פי שבאמת ההשוואה אינה מדויקת בגלל שצופן זרם מתנהג אחרת.
אלכס ביריוקוב ועדי שמיר הרחיבו ושיפרו את ההתקפה בסגנון איזון זמן/זיכרון/דאטה באופן כזה שניצול  משפר את סיבוכיות ההתקפה על ידי שילוב שני הסוגים המתוארים. כלומר  וכן  עבור כל. עם זה אפשר להשיג איזון של זמן עיבוד מוקדם  וכן זמן התקפה  וזיכרון  עם  דטה זמינה און ליין בסדר גודל . למשל עבור  הפרמטרים  וכן  הם כמעט פרקטיים.