בשל העובדה שפונקציית התמצות הפנימית formula_1 חייבת לקבל בלוק קלט באורך קבוע ומוגדר מראש (512 או 1024 סיביות), בעוד שהמסר המיועד לגיבוב בדרך כלל גדול משמעותית מאורך הבלוק. הפתרון הישיר הוא לחלק את המסר לבלוקים בגודל קבוע ולעבדם עם הפונקציה הפנימית באופן איטרטיבי. מתחילים עם וקטור אתחול קבוע ידוע מראש, שנקרא גם IV (קיצור של Initialization Vector) ואז בכל סבב פונקציית הכיווץ הפנימית מקבלת כקלט את הבלוק הבא ואת תמצית הבלוק הקודם ומפיקה תמצית חדשה, כך פלט סבב אחד הופך קלט לסבב הבא וכן הלאה עד לעיבוד כל הבלוקים. אם המסר אינו מתחלק יפה בגודל הבלוק, מרפדים את הבלוק האחרון בשיטת הריפוד של תמצית המסרים (בקיצור MD) של רונלד ריבסט שתתואר בהמשך. ההנחה המונחת בבסיס הרעיון היא שאם הפונקציה הפנימית טובה, הפעלתה באופן זה אינו מחליש את ביטחון האלגוריתם בכללותו. הנחה זו אינה אוטומטית ולא תמיד נכונה, כיוון שייתכן שהמתקיף יוכל לנצל פרצות במבנה כדי לשבור את האלגוריתם, מה שלא היה אפשרי כנגד הפונקציה הפנימית באופן נפרד. הרעיון של מרקל ודמגרד אותו הם הוכיחו שאפשר לחזק את המבנה המתואר על ידי הוספת בלוק המייצג את גודל המסר, אותו מעבדים בסוף. באופן זה לא ניתן יהיה לתקוף את האלגוריתם על ידי הוספת בלוקים (מה שקרוי התקפת הרחבה המובאת להלן). ההוכחה שלהם אומרת באופן תמציתי שאם הפונקציה הפנימית עמידה מפני התנגשויות, מבנה מרקל-דמגרד בכללותו גם הוא עמיד מפני התנגשויות.
תיאור המבנה.
נתונה פונקציה formula_1 שממפה קלט באורך formula_3 סיביות לפלט באורך formula_4 סיביות. ממנה אפשר לבנות פונקציית גיבוב כדלהלן:
הסימון formula_19 מייצג שרשור מחרוזות. כדי לחזק את המבנה עוד יותר התוצאה האחרונה היא פלט פונקציה מסיימת (finalisation). הפונקציה האחרונה יכולה לשמש גם לכיווץ נוסף של התוצאה הפנימית לפלט באורך הרצוי כמו גם לחיזוק המבנה.
ביטחון הבנייה.
פונקציות הגיבוב הנפוצות מורכבות בדרך כלל מפונקציית דחיסה פנימית איטרטיבית, כשהמטרה היא השגת שלושה מאפיינים עיקריים מהקל אל הכבד: קושי בהיפוך (מקור ראשון), עמידות מפני מציאת מקור שני ועמידות מפני התנגשויות. האיטרציה אפשרית בכמה דרכים כשמבנה מרקל-דמגרד המתואר היה במשך שנים הפופולרי ביותר והוא הבסיס של סדרת פונקציות התמצות MD וכן של SHA. כמו כן ההנחה היא שמציאת מקור ראשון או שני בכוח גס היא מסדר גודל של formula_20 כאשר formula_21 הוא אורך הפלט בסיביות ומציאת התנגשות היא בסדר גודל formula_22 בגלל פרדוקס יום ההולדת. הוכח שמבנה מרקל-דמגר משמר את המאפיין האחרון - עמידות בפני התנגשויות והדעה הרווחת הייתה בעבר שהוא משמר גם את שני המאפיינים האחרים אם כי זה לא הוכח.
בעקבות קריפטואנליזה חדשה הסתבר שההנחה הייתה שגויה. הממצא הראשון היה של ריצ'רד דין שגילה ב-1999 התקפה נגד מבנה מרקל-דמגרד שנקראת התקפת נקודות שבת (להלן), המתמקדת בנקודות השבת של הפונקציה הפנימית ומאפשרת בתנאים מסוימים גילוי מקור שני בסיבוכיות של formula_23 זמן ומקום כאשר formula_21 הוא אורך התמצית של פונקציית הגיבוב. מאוחר יותר חוקרים שיפרו את ההתקפה בעזרת טכניקה של Joux מ-2004 שנקראת התקפת רב-התנגשויות (multi-collisions attack) המתוארת להלן והראו שעם חישוב מוקדם אפשר להפוך את הפונקציה בסיבוכיות של formula_25 עם מסרים יחסית קצרים.
להלן תקציר קריפטואנליזה של מבנה מרקל-דמגרד.
התקפת נקודת שבת.
מבנה מרקל דמגרד מחוזק בדרך כלל על ידי ריפוד המסר והוספת קידוד האורך שלו בסופו. ללא תוספת זו המתקיף יכול לפעול כדלהלן: בהינתן פונקציית גיבוב של מסר ארוך formula_26 והתמצית של המסר formula_27 שהיא בעצם ערך הביניים או המצב הפנימי האחרון של הפונקציה. המתקיף מעוניין למצוא מסר אחר formula_28 כך שיתקיים formula_29. תחילה הוא בוחר אקראית בלוקים שונים formula_30 כלשהם עד שנמצא בלוק כזה שהתמצית שלו זהה לאחד מ-formula_31 ערכי הביניים של המסר formula_5. אם נמצא בלוק formula_33 כזה הוא יכול לחבר ל-formula_30 רק את הבלוקים של formula_5 מהנקודה formula_14 שבה נמצאה ההתנגשות, כך יתקבל מסר חדש formula_28 שהתמצית שלו זהה למסר המקורי אך באורך שונה. התקפה זו מסוכלת על ידי תוספת אורך המסר.
אפשר לעקוף את שיטת הריפוד של מרקל דמגרד בהתקפה מתוחכמת שנקראת התקפת נקודות-שבת (fixed-points attack). אחד הממצאים מהמחקר הוא המאפיין הבא: אפשר להוכיח שאם יהיה קל להפוך את מבנה מרקל דמגרד יהיה אפשר למצוא מקור לפונקציה הפנימית עם התקפת יום הולדת. אך ההפך אינו נכון, כלומר גם אם ניתן להוכיח שהפיכת מבנה מרקל דמגרד היא בסיבוכיות formula_20 פעולות, עדיין פונקציית הגיבוב הפנימית אינה יכולה להציע ביטחון טוב יותר מ-formula_22.
ריצ'רד דין הראה שאם פונקציית הדחיסה הפנימית של פונקציית הגיבוב היא כזו שקל למצוא בה נקודות שבת, דהיינו קל למצוא מסר ותמצית formula_40 כך שמתקיים formula_41 אזי קל יותר לשבור את מבנה מרקל דמגרד. קיומן של נקודות שבת היה ידוע למומחים רבים אך לא נחשב בעבר כאיום ממשי כשלעצמו.
דוגמה לפונקציית גיבוב שקל למצוא בה נקודות שבת היא מבנה דוויס-מאייר שהוא מבנה גנרי של פונקציית גיבוב המבוסס על צופן בלוקים. בהינתן צופן בלוקים formula_42 המקבל מסר formula_5 באורך formula_21 סיביות ומפתח באורך formula_4 סיביות, פונקציית הגיבוב מבצעת: formula_46.
במקרה כזה נקודת השבת עבור כל formula_5 היא formula_48 כי מתקיים:
כלומר עבור כל בלוק מסר קיים בלוק מיוחד המקיים formula_50 וקל לחשב אותו. פונקציות התמצות SHA-1 ו-SHA-2 פועלות על עיקרון דומה למבנה דוויס-מאייר עם חיבור שלמים במקום XOR.
התקפת נקודות שבת של ג'ון קלסי וברוס שנייר לשבירת מבנה מרקל-דמגרד פועלת בשלושה צעדים בסיסיים:
אם נמצא ערך ביניים formula_57 ונקודת שבת זהים, נניח שהבלוק המתאים ב-formula_55 נקרא formula_21 כלומר formula_60 וכן הבלוק המתאים ל-formula_57 ב-formula_56 הוא formula_63 כלומר formula_64. המתקיף חוזר על התקפה זו כשהוא מתחיל משרשור של שני הבלוקים formula_65 כלומר מנסה להוסיף בלוקים שגורמים לערך ביניים להיות זהה למסר המקורי, בונה שוב רשימות כמו בסעיפים 1 ו-2 ומחפש התאמות ביניהן. אם נמצא מסר כזה שערכי הביניים מתאימים לנקודות השבת אזי למתקיף קל להרחיב את המסר לאורכו המקורי על ידי הוספת נקודות שבת לפי הצורך עד שמגיע לאורך הרצוי. ובכך לקבל תוצאת גיבוב זהה ואם אורך המסר זהה קידוד הארוך בסופו מניב תוצאה זהה ובכך למעשה המתקיף הערים על שיטת הריפוד.
כמובן שההתקפה מניחה שקל למצוא נקודת שבת, אולם שנייר וקלסי הראו שאפשר לבצע את ההתקפה גם אם קשה למצוא נקודות שבת על ידי שימוש בטכניקה של Joux שנקראת רב-התנגשויות. הם צמצמו את סיבוכיות ההתקפה האמורה ל-formula_66 עם מקום בסדר גודל של formula_22. ג'ון פיליפ אמסון שיפר את ההתקפה הזו אף יותר עד לסיבוכיות של formula_22 וללא צריכת זיכרון משמעותית.
רב-התנגשויות.
Joux גילה את העובדה שבפונקציות איטרטיביות מציאת התנגשויות מרובות, כלומר רשימה של מסרים המייצרים תמצית גיבוב זהה קלה כמעט כמו מציאת התנגשות אחת. ההתקפה שלו נקראת התקפת רב-התנגשויות. הרעיון הוא שאמנם במבנה מרקל-דמגרד קשה למצוא התנגשות עבור כל בלוק בנפרד, אבל בהנחה שמוצאים formula_7 התנגשויות (כל אחת מתחילה מערך הביניים של ההתנגשות הקודמת) אפשר לבנות formula_70 מסרים עם ערך גיבוב זהה על ידי צירופים של בלוקים מתנגשים. לפני התגלית של Joux מומחים היו סבורים שמציאת formula_71 התנגשויות בפונקציית גיבוב איטרטיבית עם התקפת יום הולדת היא בסיבוכיות אופטימלית של formula_72, אולם Joux הוכיח שמציאת התנגשויות מרובות אפשרית ב-formula_73 פעולות. המסקנה מההתקפה שלו היא שאם מחברים שתי פונקציות גיבוב זו אחר זו לא מקבלים ביטחון כפול נגד התנגשויות כפי שעשויים לחשוב. החיבור בטוח רק כמו הפונקציה החזקה מבין השתיים.
באופן כללי התקפת רב-התנגשויות פועלת כדלהלן. כדי לחשב formula_74 התנגשויות מתוך formula_71 התנגשויות בודדות, תחילה מחשבים את הזוג formula_76 כך שמתקיים formula_77, כאשר formula_78 הוא וקטור האתחול. לאחר מכן מוצאים זוג נוסף formula_79 עם התכונה הבאה: formula_80. כך ממשיכים כאשר כל תוצאה מהווה וקטור אתחול לחישוב הבא, עד שמגיעים ל-formula_81 כאשר formula_82 הוא וקטור האתחול. משנמצאו formula_71 ערכים כאלו ניתן לבנות מהם formula_74 מסרים שונים שלהם תמצית זהה. אם נקרא למסר אחד formula_85 אזי לכל אחד מ-formula_74 המסרים formula_87 שניתן לבנות יש ערכי ביניים formula_88 מרשימת ההתנגשויות ומהם אפשר ליצור formula_74 מסרים כאלו על ידי צירופים שונים והוספת בלוקים לפי הצורך. העלות של המהלך האמור היא formula_90 כפול הזמן הדרוש לביצוע פעולת גיבוב אחת ועם צריכת זיכרון נמוכה. לדוגמה אם formula_91 תחילה מוצאים התנגשות ראשונה formula_77 ואז התנגשות שנייה formula_80 ואז אפשר להכין formula_94 התנגשויות: formula_95 ו-formula_96, כולם מכילים תמצית זהה.
התקפת כינוס.