כאן formula_102 הוא קבוע (בבסיס הקסדצימלי) וכן את הבלוקים formula_96 בגודל formula_5 סיביות מכינים על ידי שמחלקים תחילה את המסר לבלוקים בגודל formula_105 סיביות ומרחיבים כל בלוק על ידי הוספת יתירות, מחלקים את המידע לחצאי בתים ומציבים '1111' בארבע הסיביות המשמעותיות הנותרות של כל בית. הסימן formula_106 מייצג OR, הסימן formula_107 מייצג XOR והסימן formula_108 אומר שתוצאת ההעלאה בריבוע נחתכת בכל סבב ל-formula_5 סיביות האחרונות. בנוסף התקן מגדיר פונקציה מסיימת מסובכת שנועדה למחוק כל זכר של המבנה האלגברי של הפונקציה. התוצאה האחרונה של פונקציית התמצות formula_110 מחולקת ל-4 תת-בלוקים, איתם מחשבים ברקורסיה עוד שנים-עשר בלוקים בגודל formula_111 סיביות formula_112, מאחדים את כל 16 הבלוקים שנוצרו לשמונה בלוקים בני formula_105 סיביות formula_114, מרחיבים אותם לפי השיטה האמורה לעיל ומבצעים עוד שמונה סבבים של פונקציית התמצות על הבלוקים האחרונים. ולסיום התוצאה הסופית היא מחרוזת סיביות בגודל formula_105 המחושבת על ידי formula_116. ההתקפה הטובה ביותר הידועה כנגד מבנה זה היא בסיבוכיות של formula_117 שהיא לא יותר טובה מכוח גס. MASH-2 היא גרסה שונה במעט שבה ההעלאה בריבוע מוחלפת ב-formula_118.
התקפת בלוק מתקן.
התקפת בלוק מתקן (correcting block) היא התקפה המנצלת את המבנה האלגברי של פונקציית התמצות הפנימית. ההתקפה מתמקדת בחיפוש התנגשויות או מקור נוסף על ידי החלפת בלוק אחד או יותר בסוף, באמצע או בהתחלה של המסר. ההתקפה מתבצעת על ידי חישוב formula_119 כאשר formula_120 הוא הבלוק המתקן. מבנה אלגברי פגיע במיוחד להתקפה זו משום שאפשר להפוך לפעמים את פונקציית התמצות הפנימית בעזרת מניפולציה אלגברית. דרך נפוצה להתמודד עם התקפה זו היא להוסיף יתירות מכוונת למסר לפני הגיבוב כך שיהיה קשה למצוא בלוק מתקן עם היתירות הדרושה. המחיר כמובן הוא ירידה בביצועים. לדוגמה ב-1984 הציעו דייוויס ופרייס פונקציית גיבוב עם פונקציית תמצות formula_121 כדלהלן: formula_122. היתירות שהם הוסיפו הייתה 64 אפסים שנוספו לכל בלוק לפנים או בסוף. גיראולט ואחרים הראו כיצד אפשר לתקוף פונקציה כזו ולמצוא מקור נוסף. CCITT X.509 הייתה פונקציית גיבוב שפותחה ב-1988 וניסתה למנוע את ההתקפה המתוארת על ידי הוספת היתירות באופן כזה שכל ניבל (חצי בית) בכל הבתים של המסר יכיל ארבעה אפסים. למרות זאת הראה קופרשמידט שאפשר למצוא התנגשויות במבנה זה באמצעות ההתקפה האמורה.
מבנה ספוג.
פונקציית ספוג היא כלי קריפטוגרפי ורסטילי שיכול בין היתר לשמש כבסיס להכנת פונקציית גיבוב על ידי מה שקרוי "מבנה ספוג". מבנה ספוג הוא מצב הפעלה של פרמוטציה קבועה, עם כלל ריפוד מתאים, שמקבל כקלט מחרוזת בינארית formula_123 בכל אורך, מכיל זיכרון פנימי רחב ומפיק פלט formula_124 כאשר formula_5 מוגדר על ידי המשתמש. מבנה ספוג הוא הכללה של פונקציית גיבוב באופן שמאפשר קלט קבוע כמו בצופן זרם או פלט קבוע כמו באימות מסרים. הוא מכיל זיכרון, דהיינו הפונקציה הפנימית מופעלת באופן איטרטיבי על המצב הפנימי בשילוב עם הקלט. את ביטחון האלגוריתם מבטאים במונחים של גודל הזיכרון הפנימי. בפונקציית ספוג נעשה שימוש בפועל בכמה אלגוריתמים חדשים, ביניהם SHA-3.
פונקציית גיבוב אקראית.
פונקציית גיבוב אקראית היא פונקציית גיבוב המשלבת בנוסף לקלט הרגיל גיוון אקראי הנקרא מלח (salt). מהיבט תאורטי המטרה של המלח היא לאפשר הסתמכות על פונקציית גיבוב בעלת ביטחון חלש כמו MD5 ו-SHA-1 שבעקבות קרפיטואנליזה חדשה שמצביעה על בעיות בעמידות מפני התנגשויות מומחים המליצו שלא להשתמש בהן. הרעיון הוצע ב-2007 על ידי שי הלוי והוגו קרווציק לחיזוק אלגוריתם חתימה דיגיטלית DSA, המשלב בין היתר פונקציית גיבוב. השאיפה היא שאלגוריתם החתימה יישאר בטוח אפילו אם פונקציית הגיבוב איתה הוא משתמש אינה מספקת עמידות מפני התנגשויות בעקבות קריפטואנליזה חדשה שמצביעה על חולשות במבנה הפנימי שלה, בדיוק כמו שקרה עם MD5 ו-SHA-1. במילים אחרות מנגנון חתימה דיגיטלית שעושה שימוש בפונקציית גיבוב אקראית לא חייב להסתמך על ההנחה שקשה למצוא התנגשויות בפונקציית הגיבוב שהיא הגדרה מחמירה ובדרך כלל קשה יותר להשגה אלא על הגדרה קלה יותר הנקראת "פונקציית גיבוב אוניברסלית".
פונקציית גיבוב אוניברסלית.
פונקציית גיבוב אוניברסלית או בשמה האחר TCR קיצור של Target Collision Resistance היא פונקציית גיבוב אקראית שאינה עמידה מפני התנגשויות באופן מלא. פונקציה זו פותחה בהשראת נאור ויונג שהציעו לראשונה את פונקציית הגיבוב האוניברסלית בקיצור UOWHF ששמה שונה לאחר מכן על ידי בלייר ורוגווי ל-TCR.
בניסוח רשמי, פונקציית גיבוב אוניברסלית היא בעצם משפחה של פונקציות formula_126 עבור קבוצה כלשהי formula_2. היא תקרא אוניברסלית או TCR אם לא קיים אלגוריתם יעיל formula_128 שאיתו אפשר לנצח במשחק הבא למעט בהסתברות זניחה. formula_128 בוחר קלט כלשהו formula_130 ומקבל ערך אקראי formula_131 והוא צריך למצוא קלט אחר formula_132 כך שמתקיים formula_133. כאשר formula_134 היא פונקציית גיבוב כמו MD5 והערך formula_61 הוא מעין מפתח ונקרא גם "מלח". למתקיף אין שליטה על ערך זה, הוא חייב לקבל אותו עבור כל מסר שהוא מנסה לגבב. בדרך זו אפשר להפוך כל פונקציית גיבוב דטרמיניסטית ל-TCR. המלח formula_61 יכול להיות ערך קצר כלשהו אך חייב להיות חד-פעמי עבור כל מסר נתון.
מבנה זה נחשב יעיל ומבטיח קושי רב יותר במציאת התנגשויות כלומר למצוא formula_137 המקיים formula_138 מאשר במודל הסטנדרטי של פונקציות גיבוב. כאן התקפת יום הולדת אינה ישימה כיוון שהיא לא יכולה להיות אוף ליין, כלומר התוקף חייב לקבל בנוסף לתמצית הקלט את formula_61 שמיוצר באופן אקראי עבור כל מסר, לכן אפשר להסתפק בכל פונקציית גיבוב במבנה מרקל דמגרד שהיא בעלת עמידות מפני מציאת מקור נוסף ואינה חסינת התנגשויות (הגדרה 3 לעיל). הגדרה פורמלית של פונקציית גיבוב TCR היא:
פשוט הקלט לפונקציית הגיבוב מחובר עם מחרוזת המלח הקצרה בלוק אחר בלוק ב-XOR לפני שמפעילים את פונקציית הגיבוב. בגלל השימוש במלח האקראי formula_61 לא תמיד הפונקציה ניתנת לשימוש כחלק ממנגנון חתימה דיגיטלית כי יש צורך לחתום גם על המלח ושלוח אותו יחד עם המסר לצד המקבל, מה שמחייב שינויים משמעותיים בקוד המקור של המערכות הקיימות. אפשר לפתור את הבעיה על ידי הכללת formula_61 כחלק מהמסר כך:
כאן בנוסף לחיבור מחרוזת המלח הקצרה עם כל הבלוקים של הקלט, משרשרים את מחרוזת המלח עצמה בראש הקלט ואת הכול ביחד מגבבים עם פונקציית הגיבוב כרגיל. גרסה זו נקראת eTCR והיא מציעה ביטחון רב יותר, יתרונה הוא שאין צורך לחתום על המלח בנפרד וניתן להכניס את השינוי במערכות הקיימות ללא שינויים מרחיקי לכת בקוד המערכת.
תקן פונקציית גיבוב בטוחה (SHA).
במטרה ליצור תקן בין-לאומי אחיד של פונקציות גיבוב קריפטוגרפיות פרסם המכון הלאומי לתקנים וטכנולוגיה האמריקאי את תקן SHA קיצור של secure hash algorithm. בשנת 1993 פורסמה הראשונה מבין הפונקציות במשפחה שנקראה SHA-0 (האפס נוסף מאוחר יותר כדי להבדילה מהגרסאות המתקדמות). הפונקציה הוחלפה ב-1995 בגרסה המחוזקת SHA-1, עקב חולשות שנתגלו בה. SHA-1 דמתה ל-SHA-0 בשינויים קלים. שתי הפונקציות מבוססות על אלגוריתם תמצית מסרים של רונלד ריבסט MD5, פועלות בשיטת מרקל-דמגרד ומפיקות פלט באורך 160 סיביות. ב-2002 פרסם NIST את משפחת הפונקציות SHA-2, המפיקות ארבעה פלטים אפשריים 224, 256, 384 ו-512 סיביות.
משפחת SHA היא סדרת פונקציות גיבוב ייעודיות המבוססות על הידע שנצבר בעקבות סדרת האלגוריתמים MD (תמצית מסרים). פונקציות אלו נבנו תוך שימת דגש על פיזור אחיד של כל סיביות המסר באופן כזה שלכל חלקי המסר תהיה השפעה על הפלט. הפונקציות משתמשות בפעולות פשוטות כמו XOR, Shift ו-Rotate הבנויות כסדרה של פונקציות לוגיות המקבלות שלושה ערכים ומפיקות ערך אחד בגודל קבוע. כאשר ב-SHA1 וכן SHA256 הערכים בגודל מילה (32 סיביות) ואילו ב-SHA384 ו-SHA512 הערכים בגודל מילה כפולה (64 סיביות). ההבדל העיקרי בין הפונקציות השונות במשפחה הוא בכמות סיביות הפלט וערכי האתחול הקבועים.
בנובמבר 2007 הושקה תחרות פתוחה לתקן SHA החדש, בדומה לתחרות שהתקיימה לצפני בלוקים שבה זכה AES. באוקטובר 2012 נסגרה התחרות והוכרז Keccak האלגוריתם הזוכה בתחרות, זה שיחליף בהדרגה את קודמו לתפקיד ונקרא SHA-3. בארגון התקינה ממליצים שלא להשתמש יותר ב-SHA-1 וממליצים לעבור ל-SHA-2 או SHA-3. בארגון התקינה רואים בתקן SHA-2 עדיין בטוח לשימוש נכון לשנת 2013 ולא מתוכנן להחליפו בזמן הקרוב. העובדה ש-SHA-3 שונה מאוד בעיצובו ואופן פעולתו מתקן SHA-2 רק מרחיב את האפשרויות כיוון שלא סביר שתמצא התקפה אחת שתהיה יעילה כנגד שניהם. Keccak הזוכה בתחרות SHA-3 הוא אלגוריתם גיבוב יעיל ובטוח, שפותח על ידי קריפטוגרפים בלגיים ואיטלקיים. הוא מצטיין בגמישות רבה, שולי ביטחון גבוהים, ביצועים כלליים טובים ומימוש יעיל בחומרה. באלגוריתם זה הוכנס לראשונה מבנה הספוג הנחשב למבנה יעיל ובטוח.
פונקציות גיבוב.