שיטת מרקל-דמגרד

בקריפטוגרפיה, בניית מרקל-דמגרד (Merkle-Damgård Construction) היא שיטה לבניית פונקציית גיבוב קריפטוגרפית חסינת-התנגשויות באמצעות פונקציית תמצות חד-כיוונית, שהוצעה לראשונה על ידי רלף מרקל ואיוון דמגרד ב-1979 והוכחה על ידם כבטוחה. דהיינו אם משתמשים בסכמת ריפוד מתאימה ופונקציית הכיווץ הפנימית היא חד-כיוונית וחסינת התנגשויות אזי הבנייה כולה איתנה. בנייה זו נוצלה במספר אלגוריתמים פופולריים כמו MD5,‏ SHA-1 ו-SHA-2.

עקרונות השיטה

בשל העובדה שפונקציית התמצות הפנימית  חייבת לקבל בלוק קלט באורך קבוע ומוגדר מראש  (512 או 1024 סיביות), בעוד שהמסר המיועד לגיבוב בדרך כלל גדול משמעותית מאורך הבלוק. הפתרון הישיר הוא לחלק את המסר לבלוקים בגודל קבוע ולעבדם עם הפונקציה הפנימית באופן איטרטיבי. מתחילים עם וקטור אתחול קבוע ידוע מראש, שנקרא גם IV (קיצור של Initialization Vector) ואז בכל סבב פונקציית הכיווץ הפנימית מקבלת כקלט את הבלוק הבא ואת תמצית הבלוק הקודם ומפיקה תמצית חדשה, כך פלט סבב אחד הופך קלט לסבב הבא וכן הלאה עד לעיבוד כל הבלוקים. אם המסר אינו מתחלק יפה בגודל הבלוק, מרפדים את הבלוק האחרון בשיטת הריפוד של תמצית המסרים (בקיצור MD) של רונלד ריבסט שתתואר בהמשך. ההנחה המונחת בבסיס הרעיון היא שאם הפונקציה הפנימית טובה, הפעלתה באופן זה אינו מחליש את ביטחון האלגוריתם בכללותו. הנחה זו אינה אוטומטית ולא תמיד נכונה, כיוון שייתכן שהמתקיף יוכל לנצל פרצות במבנה כדי לשבור את האלגוריתם, מה שלא היה אפשרי כנגד הפונקציה הפנימית באופן נפרד. הרעיון של מרקל ודמגרד אותו הם הוכיחו שאפשר לחזק את המבנה המתואר על ידי הוספת בלוק המייצג את גודל המסר, אותו מעבדים בסוף. באופן זה לא ניתן יהיה לתקוף את האלגוריתם על ידי הוספת בלוקים (מה שקרוי התקפת הרחבה המובאת להלן). ההוכחה שלהם אומרת באופן תמציתי שאם הפונקציה הפנימית עמידה מפני התנגשויות, מבנה מרקל-דמגרד בכללותו גם הוא עמיד מפני התנגשויות.

ביטחון הבנייה

פונקציות הגיבוב הנפוצות מורכבות בדרך כלל מפונקציית דחיסה פנימית איטרטיבית, כשהמטרה היא השגת שלושה מאפיינים עיקריים מהקל אל הכבד: קושי בהיפוך (מקור ראשון), עמידות מפני מציאת מקור שני ועמידות מפני התנגשויות. האיטרציה אפשרית בכמה דרכים כשמבנה מרקל-דמגרד המתואר היה במשך שנים הפופולרי ביותר והוא הבסיס של סדרת פונקציות התמצות MD וכן של SHA. כמו כן ההנחה היא שמציאת מקור ראשון או שני בכוח גס היא מסדר גודל של  כאשר  הוא אורך הפלט בסיביות ומציאת התנגשות היא בסדר גודל  בגלל פרדוקס יום ההולדת. הוכח שמבנה מרקל-דמגר משמר את המאפיין האחרון - עמידות בפני התנגשויות והדעה הרווחת הייתה בעבר שהוא משמר גם את שני המאפיינים האחרים אם כי זה לא הוכח.
בעקבות קריפטואנליזה חדשה הסתבר שההנחה הייתה שגויה. הממצא הראשון היה של ריצ'רד דין שגילה ב-1999 התקפה נגד מבנה מרקל-דמגרד שנקראת התקפת נקודות שבת (להלן), המתמקדת בנקודות השבת של הפונקציה הפנימית ומאפשרת בתנאים מסוימים גילוי מקור שני בסיבוכיות של  זמן ומקום כאשר  הוא אורך התמצית של פונקציית הגיבוב. מאוחר יותר חוקרים שיפרו את ההתקפה בעזרת טכניקה של Joux מ-2004 שנקראת התקפת רב-התנגשויות (multi-collisions attack) המתוארת להלן והראו שעם חישוב מוקדם אפשר להפוך את הפונקציה בסיבוכיות של  עם מסרים יחסית קצרים.
להלן תקציר קריפטואנליזה של מבנה מרקל-דמגרד.

רב-התנגשויות

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

התקפת כינוס

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