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

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

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

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

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

תרשים מבנה מרקל דמגרד

תיאור המבנה

נתונה פונקציה ${\displaystyle f}$ שממפה קלט באורך ${\displaystyle r+n}$ סיביות לפלט באורך ${\displaystyle n}$ סיביות. ממנה אפשר לבנות פונקציית גיבוב כדלהלן:

1. מחלקים את הקלט ${\displaystyle M}$ באורך ${\displaystyle b}$ סיביות ל-${\displaystyle t}$ בלוקים ${\displaystyle M_{1},M_{2},...,M_{t}}$ בני ${\displaystyle r}$ סיביות כל אחד.
2. אם הבלוק האחרון קטן מ-${\displaystyle r}$ סיביות, מוסיפים '1' ומרפדים באפסים עד שמתקבל בלוק בגודל ${\displaystyle r}$ סיביות.
3. מוסיפים בלוק ${\displaystyle M_{t+1}}$ שבו מקודדים את אורך המסר בסיביות ומרפדים באפסים.
4. מגדירים וקטור אתחול קבוע שערכו תלוי ביישום ספציפי. מציבים ${\displaystyle H_{0}=IV}$.
5. עבור כל ${\displaystyle i}$ כאשר ${\displaystyle 1\leq i\leq t+1}$ מחשבים ${\displaystyle H_{i}=f(H_{i-1}\ \|\ M_{i})}$ כאשר ל-${\displaystyle H_{i}}$ קוראים ערך-ביניים (chaining value).
6. הפלט הוא ${\displaystyle h(M)=H_{t+1}}$.

הסימון ${\displaystyle \|}$ מייצג שרשור מחרוזות. כדי לחזק את המבנה עוד יותר התוצאה האחרונה היא פלט פונקציה מסיימת (finalisation). הפונקציה האחרונה יכולה לשמש גם לכיווץ נוסף של התוצאה הפנימית לפלט באורך הרצוי כמו גם לחיזוק המבנה.

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

פונקציות הגיבוב הנפוצות מורכבות בדרך כלל מפונקציית דחיסה פנימית איטרטיבית, כשהמטרה היא השגת שלושה מאפיינים עיקריים מהקל אל הכבד: קושי בהיפוך (מקור ראשון), עמידות מפני מציאת מקור שני ועמידות מפני התנגשויות. האיטרציה אפשרית בכמה דרכים כשמבנה מרקל-דמגרד המתואר היה במשך שנים הפופולרי ביותר והוא הבסיס של סדרת פונקציות התמצות MD וכן של SHA. כמו כן ההנחה היא שמציאת מקור ראשון או שני בכוח גס היא מסדר גודל של ${\displaystyle 2^{m}}$ כאשר ${\displaystyle m}$ הוא אורך הפלט בסיביות ומציאת התנגשות היא בסדר גודל ${\displaystyle 2^{m/2}}$ בגלל פרדוקס יום ההולדת. הוכח שמבנה מרקל-דמגר משמר את המאפיין האחרון - עמידות בפני התנגשויות והדעה הרווחת הייתה בעבר שהוא משמר גם את שני המאפיינים האחרים אם כי זה לא הוכח.

בעקבות קריפטואנליזה חדשה הסתבר שההנחה הייתה שגויה. הממצא הראשון היה של ריצ'רד דין שגילה ב-1999 התקפה נגד מבנה מרקל-דמגרד שנקראת התקפת נקודות שבת (להלן), המתמקדת בנקודות השבת של הפונקציה הפנימית ומאפשרת בתנאים מסוימים גילוי מקור שני בסיבוכיות של ${\displaystyle O(m\cdot 2^{m/2})}$ זמן ומקום כאשר ${\displaystyle m}$ הוא אורך התמצית של פונקציית הגיבוב. מאוחר יותר חוקרים שיפרו את ההתקפה בעזרת טכניקה של Joux מ-2004 שנקראת התקפת רב-התנגשויות (multi-collisions attack) המתוארת להלן והראו שעם חישוב מוקדם אפשר להפוך את הפונקציה בסיבוכיות של ${\displaystyle O(2^{m/2})}$ עם מסרים יחסית קצרים.

להלן תקציר קריפטואנליזה של מבנה מרקל-דמגרד.

התקפת נקודת שבת

מבנה מרקל דמגרד מחוזק בדרך כלל על ידי ריפוד המסר והוספת קידוד האורך שלו בסופו. ללא תוספת זו המתקיף יכול לפעול כדלהלן: בהינתן פונקציית גיבוב של מסר ארוך ${\displaystyle M=M_{1},M_{2},M_{3},...,M_{l}}$ והתמצית של המסר ${\displaystyle H(M)}$ שהיא בעצם ערך הביניים או המצב הפנימי האחרון של הפונקציה. המתקיף מעוניין למצוא מסר אחר ${\displaystyle M^{*}}$ כך שיתקיים ${\displaystyle H(M)=H(M^{*})}$. תחילה הוא בוחר אקראית בלוקים שונים ${\displaystyle M'}$ כלשהם עד שנמצא בלוק כזה שהתמצית שלו זהה לאחד מ-${\displaystyle l}$ ערכי הביניים של המסר ${\displaystyle M}$. אם נמצא בלוק ${\displaystyle M_{i}}$ כזה הוא יכול לחבר ל-${\displaystyle M'}$ רק את הבלוקים של ${\displaystyle M}$ מהנקודה ${\displaystyle i}$ שבה נמצאה ההתנגשות, כך יתקבל מסר חדש ${\displaystyle M^{*}}$ שהתמצית שלו זהה למסר המקורי אך באורך שונה. התקפה זו מסוכלת על ידי תוספת אורך המסר.

אפשר לעקוף את שיטת הריפוד של מרקל דמגרד בהתקפה מתוחכמת שנקראת התקפת נקודות-שבת (fixed-points attack)^[1]. אחד הממצאים מהמחקר הוא המאפיין הבא: אפשר להוכיח שאם יהיה קל להפוך את מבנה מרקל דמגרד יהיה אפשר למצוא מקור לפונקציה הפנימית עם התקפת יום הולדת. אך ההפך אינו נכון, כלומר גם אם ניתן להוכיח שהפיכת מבנה מרקל דמגרד היא בסיבוכיות ${\displaystyle 2^{m}}$ פעולות, עדיין פונקציית הגיבוב הפנימית אינה יכולה להציע ביטחון טוב יותר מ-${\displaystyle 2^{m/2}}$.

ריצ'רד דין הראה שאם פונקציית הדחיסה הפנימית של פונקציית הגיבוב היא כזו שקל למצוא בה נקודות שבת, דהיינו קל למצוא מסר ותמצית ${\displaystyle (h,M)}$ כך שמתקיים ${\displaystyle H(h,M)=h}$ אזי קל יותר לשבור את מבנה מרקל דמגרד. קיומן של נקודות שבת היה ידוע למומחים רבים אך לא נחשב בעבר כאיום ממשי כשלעצמו.

דוגמה לפונקציית גיבוב שקל למצוא בה נקודות שבת היא מבנה דוויס-מאייר שהוא מבנה גנרי של פונקציית גיבוב המבוסס על צופן בלוקים. בהינתן צופן בלוקים ${\displaystyle E}$ המקבל מסר ${\displaystyle M}$ באורך ${\displaystyle m}$ סיביות ומפתח באורך ${\displaystyle n}$ סיביות, פונקציית הגיבוב מבצעת: ${\displaystyle h_{i}=H(h_{i-1},M_{i})=E_{M_{i}}(h_{i-1})\oplus h_{i-1}}$.

במקרה כזה נקודת השבת עבור כל ${\displaystyle M}$ היא ${\displaystyle h=E_{M}^{-1}(0)}$ כי מתקיים:

${\displaystyle E_{M}(E_{M}^{-1}(0))\oplus E_{M}^{-1}(0)=0\oplus E_{M}^{-1}(0)=H}$

כלומר עבור כל בלוק מסר קיים בלוק מיוחד המקיים ${\displaystyle f(H,M)=H}$ וקל לחשב אותו. פונקציות התמצות SHA-1 ו-SHA-2 פועלות על עיקרון דומה למבנה דוויס-מאייר עם חיבור שלמים במקום XOR.

התקפת נקודות שבת של ג'ון קלסי וברוס שנייר^[2] לשבירת מבנה מרקל-דמגרד פועלת בשלושה צעדים בסיסיים:

1. מוצאים ${\displaystyle 2^{m/2}}$ נקודות שבת כאלו מסמנים אותם על ידי ${\displaystyle A=(h,M)}$.
2. בוחרים ${\displaystyle 2^{m/2}}$ בלוקים כלשהם ומחשבים את ערך הביניים שלהם. אותם מסמנים על ידי ${\displaystyle B=(H(IV,{\tilde {m}}),{\tilde {m}})}$.
3. מחפשים התנגשויות בין ערכי הביניים ונקודות השבת. כלומר כניסות זהות ב-${\displaystyle A}$ ו-${\displaystyle B}$.

אם נמצא ערך ביניים ${\displaystyle h}$ ונקודת שבת זהים, נניח שהבלוק המתאים ב-${\displaystyle A}$ נקרא ${\displaystyle m}$ כלומר ${\displaystyle (h,m)\in A}$ וכן הבלוק המתאים ל-${\displaystyle h}$ ב-${\displaystyle B}$ הוא ${\displaystyle {\tilde {m}}}$ כלומר ${\displaystyle (h,{\tilde {m}})\in B}$. המתקיף חוזר על התקפה זו כשהוא מתחיל משרשור של שני הבלוקים ${\displaystyle {\tilde {m}}\|m}$ כלומר מנסה להוסיף בלוקים שגורמים לערך ביניים להיות זהה למסר המקורי, בונה שוב רשימות כמו בסעיפים 1 ו-2 ומחפש התאמות ביניהן. אם נמצא מסר כזה שערכי הביניים מתאימים לנקודות השבת אזי למתקיף קל להרחיב את המסר לאורכו המקורי על ידי הוספת נקודות שבת לפי הצורך עד שמגיע לאורך הרצוי. ובכך לקבל תוצאת גיבוב זהה ואם אורך המסר זהה קידוד הארוך בסופו מניב תוצאה זהה ובכך למעשה המתקיף הערים על שיטת הריפוד.

כמובן שההתקפה מניחה שקל למצוא נקודת שבת, אולם שנייר וקלסי הראו שאפשר לבצע את ההתקפה גם אם קשה למצוא נקודות שבת על ידי שימוש בטכניקה של Joux שנקראת רב-התנגשויות. הם צמצמו את סיבוכיות ההתקפה האמורה ל-${\displaystyle 3\cdot 2^{m/2}}$ עם מקום בסדר גודל של ${\displaystyle 2^{m/2}}$. ג'ון פיליפ אמסון שיפר את ההתקפה הזו אף יותר^[3] עד לסיבוכיות של ${\displaystyle 2^{m/2}}$ וללא צריכת זיכרון משמעותית.

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

Joux גילה את העובדה שבפונקציות איטרטיביות מציאת התנגשויות מרובות, כלומר רשימה של מסרים המייצרים תמצית גיבוב זהה קלה כמעט כמו מציאת התנגשות אחת. ההתקפה שלו נקראת התקפת רב-התנגשויות^[4]. הרעיון הוא שאמנם במבנה מרקל-דמגרד קשה למצוא התנגשות עבור כל בלוק בנפרד, אבל בהנחה שמוצאים ${\displaystyle t}$ התנגשויות (כל אחת מתחילה מערך הביניים של ההתנגשות הקודמת) אפשר לבנות ${\displaystyle 2^{t}}$ מסרים עם ערך גיבוב זהה על ידי צירופים של בלוקים מתנגשים. לפני התגלית של Joux מומחים היו סבורים שמציאת ${\displaystyle k}$ התנגשויות בפונקציית גיבוב איטרטיבית עם התקפת יום הולדת היא בסיבוכיות אופטימלית של ${\displaystyle k!^{1/k}\cdot 2^{m(k-1)/k}}$, אולם Joux הוכיח שמציאת התנגשויות מרובות אפשרית ב-${\displaystyle \lceil \log _{2}k\rceil \cdot 2^{n/2}}$ פעולות. המסקנה מההתקפה שלו היא שאם מחברים שתי פונקציות גיבוב זו אחר זו לא מקבלים ביטחון כפול נגד התנגשויות כפי שעשויים לחשוב. החיבור בטוח רק כמו הפונקציה החזקה מבין השתיים.

באופן כללי התקפת רב-התנגשויות פועלת כדלהלן. כדי לחשב ${\displaystyle 2^{k}}$ התנגשויות מתוך ${\displaystyle k}$ התנגשויות בודדות, תחילה מחשבים את הזוג ${\displaystyle (M_{1},M_{1}')}$ כך שמתקיים ${\displaystyle f(H_{0},M_{1})=f(H_{0},M_{1}')=H_{1}}$, כאשר ${\displaystyle H_{0}}$ הוא וקטור האתחול. לאחר מכן מוצאים זוג נוסף ${\displaystyle (M_{2},M_{2}')}$ עם התכונה הבאה: ${\displaystyle f(H_{1},M_{2})=f(H_{1},M_{2}')=H_{2}}$. כך ממשיכים כאשר כל תוצאה מהווה וקטור אתחול לחישוב הבא, עד שמגיעים ל-${\displaystyle (M_{k},M_{k}')}$ כאשר ${\displaystyle H_{k-1}}$ הוא וקטור האתחול. משנמצאו ${\displaystyle k}$ ערכים כאלו ניתן לבנות מהם ${\displaystyle 2^{k}}$ מסרים שונים שלהם תמצית זהה. אם נקרא למסר אחד ${\displaystyle X\in (M,M')}$ אזי לכל אחד מ-${\displaystyle 2^{k}}$ המסרים ${\displaystyle X_{1},...,X_{k}}$ שניתן לבנות יש ערכי ביניים ${\displaystyle H_{1},...,H_{k}}$ מרשימת ההתנגשויות ומהם אפשר ליצור ${\displaystyle 2^{k}}$ מסרים כאלו על ידי צירופים שונים והוספת בלוקים לפי הצורך. העלות של המהלך האמור היא ${\displaystyle k\cdot 2^{m/2}}$ כפול הזמן הדרוש לביצוע פעולת גיבוב אחת ועם צריכת זיכרון נמוכה. לדוגמה אם ${\displaystyle k=2}$ תחילה מוצאים התנגשות ראשונה ${\displaystyle f(H_{0},M_{1})=f(H_{0},M_{1}')=H_{1}}$ ואז התנגשות שנייה ${\displaystyle f(H_{1},M_{2})=f(H_{1},M_{2}')=H_{2}}$ ואז אפשר להכין ${\displaystyle k^{2}=4}$ התנגשויות: ${\displaystyle (M_{1}M_{2}),(M_{1}M_{2}'),(M_{1}',M_{2})}$ ו-${\displaystyle (M_{1}'M_{2}')}$, כולם מכילים תמצית זהה.

התקפת כינוס

ג'ון קלסי וטדיושי קונו פיתחו התקפה נגד מבנה מרקל דמגרד הנקראת "התקפת כינוס" (Herding attack)^[5]. בהתקפה זו בהנחה שהמתקיף מסוגל למצוא התנגשויות מרובות בכוח גס הוא יכול תחילה להציג ערך גיבוב של מסר כלשהו ולאחר מכן "לכנס" כל התחלה של מסר נתון אחר כך שיתקבל ערך הגיבוב שהתחייב לו על ידי בחירת סיומת מתאימה. כלומר המתקיף מראה שהוא מצליח לייצר מסר עם תוספת כלשהי שהגיבוב שלו מתאים לערך הגיבוב הראשוני ובכך הוא הפר למעשה את ההנחה היסודית שלא ניתן למצוא מקור. הרעיון שלהם מסתמך על בחירת ערך גיבוב בצורה כזו שתקל על המתקיף במציאת מקור וההתקפה היא שיפור של הרעיון של Joux על ידי איזון בין זמן וזיכרון. בשלב הראשון המתקיף בוחר ${\displaystyle 2^{t}}$ ערכי ביניים אפשריים ${\displaystyle h_{i}}$ וכן בוחר ${\displaystyle 2^{m/2-t/2}}$ בלוקים בודדים של מסרים כלשהם כאשר ${\displaystyle m}$ הוא אורך הבלוק בסיביות. הוא מחשב את הפלטים של כל אחד מהבלוקים עם כל אחד מערכי הביניים, מתוך הרשימה הגדולה שקיבל הוא צפוי למצוא מספר התנגשויות. הוא שומר את כל הבלוקים שגרמו להתנגשות וחוזר על התהליך מספר פעמים עם ערכי הביניים שנמצאו. לאחר שהוא נשאר עם ערך ביניים אחד הוא משתמש איתו כדי לחשב את ערך הגיבוב שהוא מתחייב אליו. בשלב המקוון המתקיף צריך לבצע ${\displaystyle 2^{m-t}}$ פעולות גיבוב עד שהוא מוצא מסר שערך הביניים שלו תואם אחד כזה שנמצא ברשימה של ${\displaystyle 2^{t}}$ ערכים שהכין קודם. אם הוא נמצא ברשימה הוא יכול לקחת את הבלוק המתאים לו שאמור להוביל לערך הגיבוב שהתחייב. סיבוכיות ההתקפה כולה היא ${\displaystyle 2^{m/2+t/2}}$ פעולות הכנה באוף ליין וכן ${\displaystyle 2^{m-t}}$ פעולות און ליין והיא עשויה להיות פרקטית.

שיפורים

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

• צמצום דרישות הביטחון מהפונקציה הפנימית או הפחתת התלות בהגדרות ביטחון מחמירות.
• שימוש במצב פנימי מורחב (wide pipe).
• שיפור מבנה מרקל דמגרד באופן שישמר טוב יותר את תכונות הפונקציה הפנימית.

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

הרחבת הזיכרון או המצב הפנימי (internal state) של פונקציית הדחיסה מתגבר על החיסרון של המבנה האיטרטיבי של מרקל-דמגרד. במקרה זה מציאת התנגשויות פנימיות בערכי הביניים תהיה קשה כמו הפיכת הפונקציה כולה בהנחה שפונקציית הדחיסה טובה. שיטה זו שולבה באלגוריתם LAKE המהווה בסיס לפונקציית הגיבוב BLAKE.

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

eMD

שיטת eMD שהיא קיצור של enveloped Merkle-Damgard^[7] הוצעה ב-2006 על ידי מיהיר בלייר ואחרים. והיא נועדה לחיזוק מבנה מרקל דמגרד על ידי שימור הפסאודו-אקראיות של הפונקציה הפנימית. eMD מורכב משני מנגנונים שמטרתם לשמר את תכונות הפונקציה הפנימית. הראשון ריפוד המסר הכולל שילוב קידוד אורך המסר בסופו המבטיח עמידות מפני התנגשויות והשני עטיפת הפונקציה הפנימית בפונקציה פנימית נוספת. המבנה פועל כדלהלן:

הפונקציה הפנימית היא מהצורה:

${\displaystyle c:\{0,1\}^{d+n}\rightarrow \{0,1\}^{n}}$ פונקציה כאשר ${\displaystyle d\geq n+64}$.

פונקציית המעטפת היא מהצורה:

${\displaystyle c^{\circ }:\{0,1\}^{2n}\times D^{\circ }\rightarrow \{0,1\}^{n}}$ כאשר ${\displaystyle D^{\circ }=\cup _{i\geq 1}\{0,1\}^{(i+1)d-n}}$.

היא פועלת על ${\displaystyle c}$ כדלהלן:

${\displaystyle c^{\circ }(I_{1},I_{2},M)}$: ${\displaystyle M_{1},...,M_{k}\ \ {\overset {\underset {\mathrm {def} }{}}{\leftarrow }}\ \ \ M}$ ${\displaystyle P\leftarrow M_{1},...,M_{k-1}}$ ${\displaystyle {\text{Return }}c(c^{+}(I_{1},P)\ \|\ M_{k}\ \|\ I_{2})}$

כאשר ${\displaystyle c^{+}}$ היא מבנה מרקל דמגרד הרגיל. בנוסף צריכה להיות פונקציית ריפוד מתאימה:

${\displaystyle {\text{padEMD}}:\{0,1\}^{\leq 2^{64}}\rightarrow D^{\circ }}$.

הפונקציה מקודדת את אורכו של ${\displaystyle M}$ המסומן ${\displaystyle |M|}$ בתוך 64 הסיביות האחרונות של המסר המרופד ${\displaystyle {\text{padEMD}}(M)}$. וכן דרושים שני וקטורי אתחול ${\displaystyle I_{1}}$ ו-${\displaystyle I_{2}}$ שונים וקבועים. כעת מבנה eMD הוא:

${\displaystyle \mathbf {eMD} [c]=c^{\circ }(I_{1},I_{2},{\text{padEMD(M))}}}$.

ROX

ב-2004 פרסמו פיליפ רוגווי ותומס שרימפטון מאמר חשוב^[8] לגבי הגדרות ותכונות של פונקציות גיבוב קריפטוגרפיות וציינו שבע תכונות יסודיות שפונקציית גיבוב כזו צריכה לעמוד בהן שהן וריאציות של עמידות מפני התנגשויות, מציאת מקור ראשון ומציאת מקור שני. על בסיס רעיונות אילו פותח המבנה ROX^[9] קיצור של Random Oracle XOR שמציע ביטחון טוב יותר ממבנה מרקל דמגרד. הרעיון הוא אם נתונה פונקציית דחיסה מהצורה ${\displaystyle F:\{0,1\}^{k}\times \{0,1\}^{b+n}\rightarrow \{0,1\}^{n}}$. כאשר ${\displaystyle 2^{l}}$ הוא מקסימום אורך המסר בסיביות (למשל ${\displaystyle l=64}$ מקובל). ${\displaystyle k}$ קטן כגון ${\displaystyle k=80}$ ו-${\displaystyle n}$ יכול להיות 160. ונתונים שני אורקלים אקראיים ${\displaystyle RO_{1}:\{0,1\}^{k}\times \{0,1\}^{x}\times \{0,1\}^{\lceil \log l\rceil }\rightarrow \{0,1\}^{n}}$ וכן ${\displaystyle RO_{2}:\{0,1\}^{k}\times \{0,1\}^{l}\times \{0,1\}^{\lceil \log b\rceil }\rightarrow \{0,1\}^{2n}}$. אותם אפשר לבנות מצופן בלוקים עם קלט שונה בסיבית אחת. פונקציית הריפוד מקבלת את המסר ${\displaystyle M}$ ומפיקה בלוקים של מסר מרופד כך:

${\displaystyle m_{1}\|...\|m_{l}=M\|RO_{2}(m',\gamma ,1)\|RO_{2}(m',\gamma ,2)\|...,}$

הריפוד מוסיף למסר סיביות המיוצרות על ידי האורקל האקראי ${\displaystyle RO_{2}}$ כך שהבלוק האחרון יכיל לפחות ${\displaystyle 2n}$ סיביות. ייתכן שיתווסף בלוק ריק בסוף המסר המכיל רק ריפוד. נתונה פונקציה ${\displaystyle \nu (i)}$ שמחזירה את השלם הגדול ביותר ${\displaystyle j}$ כך שמתקיים ${\displaystyle 2^{j}}$ מחלק את ${\displaystyle i}$. וכן הסימן ${\displaystyle m'}$ מייצג את ${\displaystyle k}$ הסיביות הראשונות של ${\displaystyle m}$. מבנה ROX מומחש בפסאודו קוד הבא:

${\displaystyle \mathbf {ROX} _{F}^{RO_{1},RO_{2}}(K,M)}$ ${\displaystyle m_{1}\|...\|m_{l}\leftarrow {\text{roxpad}}^{RO_{2}}(M)}$ ${\displaystyle h_{0}=IV.}$ ${\displaystyle {\text{For }}i=0{\text{ to }}\lfloor \log _{2}(l)\rfloor {\text{ do: }}}$ ${\displaystyle \mu \leftarrow RO_{1}(K,{\mathfrak {m}},i)}$ ${\displaystyle {\text{For }}i=1{\text{ to }}l{\text{ do: }}}$ ${\displaystyle g_{i}\leftarrow h_{i-1}\oplus \mu _{\nu (i)},}$ ${\displaystyle h_{i}\leftarrow F(K,m_{i}\|g_{i})}$ ${\displaystyle {\text{Return }}h_{l}}$

מבנה ROX נחשב לבטוח ומשמר את כל התכונות הטובות שצוינו, במסגרת מודל אורקל אקראי.

HAIFA

HAsh Iterative FrAmework בקיצור HAIFA^[10] הוצע ב-2009 על ידי אלי ביהם ואור דונקלמן כשיפור של מבנה מרקל-דמגרד. HAIFA משמר את התכונות הטובות של מבנה מרקל דמגרד תוך הוספה בביטחון וסקלביליות. הוא פשוט וגמיש, משמר את העמידות מפני התנגשויות של פונקציית הדחיסה, משפר את העמידות שלה נגד התקפת מקור שני ומקשה על התקפת נקודת שבת והתקפות מתקדמות אחרות. אפשר לראות ב-HAIFA כמודל פשוט המשלב יחד כמה מהרעיונות שהוצעו כמו eMD, ROX ו-RMC וניצול התכונות הטובות שלהם.

הרעיון הכללי של HAIFA הוא תוספת מונה וגיוון (salt) לתוך פונקציית הדחיסה. המונה מייצג את מספר הסיביות המצטבר שנקלטו עד כה בכל סבב של האיטרציה. וה-${\displaystyle {\text{salt}}}$ הוא ערך אקראי כלשהו לא סודי. בשיטה זו פונקציית הדחיסה תראה כך:

${\displaystyle H:\{0,1\}^{m}\times \{0,1\}^{n}\times \{0,1\}^{b}\times \{0,1\}^{s}\rightarrow \{0,1\}^{m}}$.

ערך הביניים מחושב על ידי:

${\displaystyle h_{i}=H(h_{i-1},M_{i},{\text{nbits}},{\text{salt}})}$.

כאשר ${\displaystyle {\text{nbits}}}$ מייצג את מספר הסיביות שנקלטו עד עכשיו. כדי לגבב את המסר ${\displaystyle M}$ והגיוון ${\displaystyle s}$ יש לבצע את המהלכים הבאים:

1. תחילה מרפדים את ${\displaystyle M}$ לפי שיטת הריפוד להלן.
2. מחשבים את וקטור האתחול ${\displaystyle IV}$ באורך ${\displaystyle m}$ סיביות בשיטה המתוארת להלן.
3. באופן איטרטיבי מעבדים את המסר המרופד בפונקציה ${\displaystyle H}$ עם הערך ההתחלתי ${\displaystyle IV}$ והגיוון ${\displaystyle s}$. במקרה שהבלוק האחרון שנוסף למסר בעקבות הריפוד אינו מכיל סיביות מהמסר עצמו אלא רק את הריפוד הערך ${\displaystyle {\text{nbits}}=0}$.
4. חותכים במידת הצורך ומחזירים את ערך הביניים האחרון.

ריפוד המסר של HAIFA דומה לשיטת הריפוד של מרקל דמגרד.

1. מוסיפים '1' בסוף המסר.
2. מרפדים באפסים לפי הצורך כך שאורך המסר יהיה שקול ל-${\displaystyle n-(t+r)}$ מודולו ${\displaystyle n}$ כאשר ${\displaystyle t}$ הוא מספר הסיביות הדרוש לקידוד אורך המסר ו-${\displaystyle r}$ מספר הסיביות הדרוש לקידוד אורך התמצית.
3. מוסיפים את אורך המסר ב-${\displaystyle t}$ הסיביות הבאות.
4. מוסיפים את אורך התמצית בסיביות ב-${\displaystyle r}$ הסיביות הבאות.

הכנת ה-IV דורשת עבודה נוספת כדי לתמוך בתמצית מסר באורכים שונים כפי שתקן SHA דורש. תחילה יש לעבד את וקטור האתחול. כלומר בהינתן ${\displaystyle IV}$ שנבחר על ידי המשתמש יש לחשב את:

${\displaystyle IV=H(IV,m,0,0)}$

את ${\displaystyle m}$ מקודדים ב-${\displaystyle r}$ הסיביות הראשונות, מוסיפים '1' ולאחר מכן ${\displaystyle n-r-1}$ אפסים. לאחר קריאה זו אפשר להמשיך ליתר הבלוקים של המסר. הקריאה הזו שונה מיתר הקריאות לפונקציה ${\displaystyle H}$ והיא ייחודית בכך שבשיטה זו אפשר לחתוך את פלט פונקציית הגיבוב לכל אורך רצוי. בנוסף במקרים כאשר ידוע מראש שפלט קבוע באורכו אפשר לחשב מראש את הקריאה הזו ולקודד את התוצאה בתוך הפונקציה.

הוספת אורך תמצית המסר נועדה למנוע מצב שבו שני מסרים עם שני וקטורי אתחול שונים יפיקו ערך ביניים זהה. כמו כן שיטת HAIFA מסתמכת על כך שניתן להבחין בבלוק האחרון. זה אפשרי בשיטה זו כיוון שיש מונה. אם ${\displaystyle {\text{nbits}}<n-(t+r){\text{ mod }}n}$ וכן ${\displaystyle {\text{nbits}}>0}$ אז זהו הבלוק האחרון של המסר וכן לא קיים אחריו בלוק ריפוד. אחרת קיימות שתי אפשרויות אם ${\displaystyle {\text{nbits}}\neq 0{\text{ mod }}n}$ אזי המשמעות היא שקיים בלוק נוסף שמכיל ריפוד, אחרת אם ${\displaystyle {\text{nbits}}=0{\text{ mod }}n}$ זהו בלוק הריפוד עצמו שבמקרה אינו מכיל סיביות מהמסר כלל. למשל אם ${\displaystyle m=512}$ ו-${\displaystyle n=1536}$ ונניח ש-${\displaystyle t+r=64}$. היות ש-${\displaystyle n}$ מתחלק ב-512 נוסף בלוק ריפוד באורך 512 ובתחילתו תוספת 1 לאחריו 447 אפסים ובסופו קידוד האורך ב-64 ביט ומתקבל בסך הכול 2048. במקרה זה בבלוק האחרון ${\displaystyle {\text{nbits}}=0}$.

מבנה HAIFA שולב בפונקציית הגיבוב BLAKE שהייתה מועמדת לתחרות פונקציות הגיבוב SHA-3 שהתקיימה ב-2008 ונוהלה על ידי NIST. וכן מהווה בסיס לגרסה המתקדמת BLAKE2.

בדומה למבנה מרקל דמגרד אפשר להוכיח שמבנה HAIFA משמר את עמידות הפונקציה הפנימית מפני התנגשויות. כאשר שיטת הריפוד ותוספת המונה יחד עם ה-${\displaystyle {\text{salt}}}$ מקשים מאוד על מספר התקפות מתקדמות כמו התקפת נקודת שבת, התקפת רב-התנגשויות וכדומה. ה-${\displaystyle {\text{salt}}}$ למעשה מקנה לפונקציה פסאודו-אקראיות. זה מאפשר להגדיר את ביטחון הפונקציה במודלים תאורטיים, זה מעביר את כל ההתקפות שהיו אפשריות במצב אוף ליין למצב און ליין כיוון שה-${\displaystyle {\text{salt}}}$ אינו ידוע למתקיף מראש. ה-${\displaystyle {\text{salt}}}$ אינו סודי והוא יכול להיות למעשה כל דבר תלוי יישום כמו נומרטור, מחרוזת זיהוי, חותם זמן או סתם מחרוזת אקראית. וכן הוא לא חייב להיות כאורך המסר אלא כאורך הבלוק בלבד.

ראו גם

• פונקציית גיבוב קריפטוגרפית
• SHA-2

הערות שוליים

1. Richared D. Dean, Formal Aspects of Mobile Code Security., Ph.D. dissertation, Princeton University, 1999.
2. John Kelsey, Bruce Schneier, Second Preimages on n-Bit Hash Functions for Much Less than 2n, Advances in Cryptology, proceedings of EUROCRYPT 2005, Lecture Notes in Computer Science 3494, pp. 474–490, Springer-Verlag, 2005.
3. Faster Multicollisions
4. Antoine Joux, Multicollisions in Iterated Hash Functions, Advances in Cryptology, proceedings of CRYPTO 2004, Lecture Notes in Computer Science 3152, pp. 306– 316, Springer-Verlag, 2004.
5. John Kelsey, Tadayoshi Kohno, Herding Hash Functions and the Nostradamus Attack, preproceedings of Cryptographic Hash Workshop, held in NIST, Gaithersburg, Maryland, 2005.
6. Shai Halevei, Hugo Krawczyk, Strengthening Digital Signatures via Randomized Hashing, Advances in Cryptology, proceedings of CRYPTO 2006, Lecture Notes in Computer Science 4117, pp. 41–59, Springer-Verlag, 2006.
7. Mihir Bellare, Thomas Ristenpart, Multi-Property-Preserving Hash Domain Extension: The EMD Transform, NIST 2nd hash function workshop, Santa Barbara, August 2006.
8. Phillip Rogaway and Thomas Shrimpton. Cryptographic hash-function basics: Definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. In Bimal K. Roy and Willi Meier, editors, Fast Software Encryption 2004, volume 3017 of Lecture Notes in Computer Science, pages 371–388. Springer-Verlag, Berlin, Germany, 2004.
9. Elena Andreeva, Gregory Neven, Bart Preneel, Thomas Shrimpton, SevenProperties-Preserving Iterated Hashing: ROX, ECRYPT document STVL4KUL15-ROX-2.0, private communications, 2007
10. A Framework for Iterative Hash Functions - HAIFA