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

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

שיטת העבודה מסבירה כיצד לפרק מסר לבלוקים בגודל r, לרפד את הבלוק האחרון ולהוסיף בלוק אחד שמקודד את אורך המסר. בפועל כל סבב מחשב H_i = f(H_{i-1} || M_i), כאשר f היא פונקציית הדחיסה והסימון || הוא שרשור. אם פונקציית הדחיסה היא חד-כיוונית (קשה להפוך את פלטה לכניסה) וחסינת-התנגשויות (קשה למצוא שתי כניסות עם אותו פלט), אזי הבנייה כולה נשארת חזקה, בתנאים מתאימים.

השלבים העיקריים: לחלוק את המסר לבלוקים של r סיביות; לרפד את הבלוק האחרון על ידי הוספת '1' ואז אפסים; להוסיף בלוק שקידוד אורכו של המסר; לקבוע IV ולהריץ את פונקציית הדחיסה על כל בלוק עד לקבלת הפלט h(M)=H_{t+1}. לעיתים מוסיפים שלב סיום (finalisation) שמכווץ או מחזק את הפלט הסופי.

מבנה מרקל-דמגרד שימש בסיס ל-MD5, SHA-1 ו-SHA-2. בעבר הוכח שמבנה זה שומר על חסינות מפני התנגשויות בתנאי שפונקציית הדחיסה עמידה. עם זאת, קריפטואנליזה מודרנית הראתה חולשות: התקפות שונות מנצלות תכונות המבנה האיטרטיבי ויכולות להוריד את המורכבות שמצפים לה למציאת התנגשויות.

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

Joux הראה ששילוב של כמה התנגשויות מקומיֹת יכול ליצור מספר גדול של מסרים שונים בעלי אותה תמצית. אם מוצאים באופן סדרתי t התנגשויות שמתחילות בכל פעם מהתוצאה של זו שלפניה, אפשר לבנות עד 2^t מסרים עם אותה תמצית. זה מקטין את העלות של מציאת כמה התנגשותות ביחס למה שמחשבו בעבר, ולכן פוגע ברעיון שהשילוב של שתי פונקציות גיבוב בהכרח מגביר את הביטחון.

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

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

הצעה בשם eMD (enveloped Merkle, Damgård) משלבת ריפוד תקין עם "עטיפת" פונקציית הדחיסה בפונקציה נוספת. מבנה זה שומר מידע על אורך המסר בתוך 64 סיביות אחרונות ומוסיף שני וקטורי אתחול שונים, במטרה לשמר פסאודו-אקראיות ולחזק את הביטחון.

מבנה ROX (Random Oracle XOR) משתמש באורקלים אקראיים מדומים (RO_1, RO_2) יחד עם פונקציית דחיסה F. הרעיון הוא לערבב ערכים אקראיים לכל בלוק לפני החישוב, ובכך להשיג הגנות נוספות במודל האורקל האקראי.

HAIFA (HAsh Iterative FrAmework) מוסיף למרקל-דמגרד מונה (המספר הכולל של סיביות שמועבדו עד כה) ו-salt (ערך אקראי לא סודי). המונה וה-salt נכנסים לפונקציית הדחיסה וחוסמים התקפות כמו נקודות שבת ורב-התנגשויות. HAIFA שימש כבסיס ל-BLAKE ולשיפורים שהוצעו בתחרות SHA-3.

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

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

המסר נחלק לבלוקים. לכל בלוק משתמשים בפונקציית דחיסה שמקבלת גם את התמצית הקודמת. בסוף מקבלים תמצית סופית קצרה.

מבנה זה שימש באלגוריתמים מוכרים כמו MD5 ו-SHA. חוקרים מצאו דרכי תקיפה שונות שיכולות למצוא "התנגשויות". התנגשות היא שתי כניסות שמייצרות את אותה תוצאה.

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

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

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

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

שיטה שנקראת eMD עוטפת את פונקציית הדחיסה ומקודדת את האורך בתוך 64 סיביות.

ROX מוסיף "אורקלים אקראיים" שעוזרים לערבב את הקלט ולהגן טוב יותר.

HAIFA מוסיף מונה וסולטן (salt). זה עוזר להשיג ביטחון טוב יותר ומשמש בבסיס BLAKE.