השאלה האם קיימת פונקציה חד-כיוונית מוכחת מבחינה מתמטית, נובעת מהשאלה הפתוחה האם P=NP. לאור זאת לא ידוע אם ניתן ליצור פונקציית גיבוב קריפטוגרפית חד-כיוונית 'אמיתית'. עם זאת, קיימות פונקציות הנחשבות כחד-כיווניות לכל צורך מעשי שביטחונן מתואר במונחים של כח המחשוב הדרוש כדי להפוך אותן. מסיבה זו ככל שכח המחשוב עולה, נדרש להחליפן מעת לעת בפונקציות חזקות יותר. פונקציית גיבוב תקרא קריפטוגרפית אם היא מקיימת שלוש תכונות בסיסיות (לפחות את שתי הראשונות), מהקל אל הכבד:
מלבד זאת, פונקציית גיבוב קריפטוגרפית מקיימת את התכונות הבסיסיות של פונקציית גיבוב בכלל. קרי, כיווץ וקלות ביצוע. פונקציית גיבוב אמורה להפיק פלט שהוא קטן יותר מהקלט וכן זמן ביצועה צריך להיות יעיל במונחי מחשוב.
פונקציה חד-כיוונית העמידה בפני התנגשויות (הגדרה 3) היא החזקה ביותר והיא אינה הכרחית בכל המקרים. המודל המקובל להגדרת קושי מבחינה חישובית הוא במונחים של סיבוכיות זמן. כלומר אם נתונה הפונקציה formula_20, זמן הריצה האידיאלי למציאת מקור (הפיכת הפונקציה) צריך להיות מסדר גודל של formula_21. לעומת זאת זמן הריצה במקרה הגרוע למציאת התנגשות מתקצר משמעותית, רק formula_22. זאת בגלל התקפת יום הולדת שמבוססת על פרדוקס יום ההולדת.
התקפת יום הולדת.
פרדוקס יום ההולדת אומר שהסיכויים שיימצאו בחדר אחד שניים מתוך 23 אנשים שלהם יום הולדת זהה, הם בערך 0.507 (מעל 50 אחוז), שזה באופן מפתיע גבוה מהאינטואיציה הראשונית (מסיבה זו נקרא 'פרדוקס'). היות שלא מדובר על יום הולדת ספציפי אלא כל זוג תואם, מספר הזוגות האפשריים בקבוצה כזו הוא רק formula_23. במילים אחרות כדי שההסתברות ששני משתנים מקריים יהיו זהים מעל מרחב הסתברות formula_24 בהתפלגות אחידה בהסתברות גבוהה מחצי נדרשים לפחות formula_25 מאורעות. במקרה של יום הולדת השורש הריבועי של 365 הוא בערך 19.10 ולכן צריכים להיות לפחות 23 אנשים, אך בכל הקשור לימי הולדת נתון זה אינו מדויק כיוון שהתפלגות הלידות אינה אחידה (למשל באוקטובר נולדים כ-5% יותר תינוקות בממוצע מאשר בחודשים האחרים בשנה).
העובדה שמבחינה סטטיסטית היתכנות של התנגשויות גבוהה יחסית ניתנת לניצול לשבירת פונקציית גיבוב (או כל פונקציה חד-כיוונית). הרעיון הוא שהמתקיף שמקבל לידיו קלט מסוים נניח formula_26 אותו הוא מעוניין לזייף ואת ערך הגיבוב שלו נניח formula_27 המשמש כהוכחה למקוריותו. הוא מכין תחילה formula_28 וריאציות של formula_26 וכן formula_30 וריאציות של הקלט המזויף formula_31 אותו הוא מעוניין להחליף איתו. את כל הערכים הוא מגבב ומאחסן בטבלה ממוינת. לאחר מכן הוא מחפש בטבלה שני קלטים האחד מקורי והשני מזויף שלהם ערך גיבוב זהה. במידה שנמצא זוג תואם כזה נניח formula_32 הוא יכול לשייך את ערך הגיבוב של formula_33 לקלט formula_34 ולטעון שהוא מקורי היות שמתקיים formula_35. ההבדלים בין הקלטים יכולים להיות כל הבדל קל שאינו משנה את משמעות התוכן כמו רווחים כפולים, שורות ריקות וכדומה. מבחינה הסתברותית מספר ההתנגשויות הצפוי הוא formula_36 והסיכוי למצוא התנגשות אחת הוא בסדר גודל formula_37 שהוא בערך 63% עם זיכרון בסדר גודל של formula_38 כאשר formula_39. יש להביא בחשבון גם את מיון הערכים שהוא בסיבוכיות של formula_40 וכן החיפוש שהוא בסיבוכיות formula_41 אך פעולות אילו אינן משמעותיות ואפשר להתעלם מהן. את ההתקפה פיתח גידעון יובל ב-1979.
יתרה מזו, אפשר לצמצם את דרישות הזיכרון באופן משמעותי אם ממירים את בעיית חיפוש ההתנגשויות לבעיה אחרת מאוד דומה שנקראת בעיית מציאת מחזוריות של פונקציה אקראית. אם נתונה פונקציה אקראית formula_42, קיימים אלגוריתמים מהירים למציאת שני ערכים formula_43 כך שמתקיים formula_44 כאשר formula_45 וזאת ללא צורך בזיכרון כלל. בנוסף אפשר ליישם את אלגוריתם החיפוש באופן מקבילי. לדוגמה בטכנולוגיה של 1994 אפשר היה לבנות בעלות של 10 מיליון דולר, חומרה ייעודית למציאת התנגשויות בפונקציית הגיבוב MD5 כאשר formula_46 בתוך 21 יום. בשנת 2004 במחיר נמוך מזה אפשר היה למצוא התנגשויות בתוך 4 שעות.
להתקפה זו השלכה מהותית על ביטחון כל פונקציית גיבוב. אם פונקציית גיבוב מפיקה פלט של formula_5 סיביות, בהנחה שלא קיימת נגדה התקפה טובה מכוח גס אז אומרים שביטחונה המרבי הוא בפקטור של כמחצית formula_5 ללא תלות באיכותה. למשל ב-SHA-1 פלט הפונקציה המינימלי הוא 160 סיביות ועל כן מציאת התנגשות בכוח גס היא בסיבוכיות של formula_49. נכון לשנת 2015 מקובל להשתמש בערכי גיבוב באורך של לפחות 256 סיביות כדי לקבל ביטחון ברמה של formula_50 שהוא המינימום הנדרש כיום. ליתר דיוק מספיק שהזיכרון הפנימי של האלגוריתם יהיה גדול כדי לסכל התקפה זו ואילו ערך הגיבוב המתקבל ממנו ניתן ל"קיטום" לגודל הרצוי. הוכח שאם פונקציית הגיבוב בטוחה, הרי שאפשר ליטול רק חלק מתוצאת הגיבוב מבלי להסתכן בירידה בביטחון כל עוד אורך הגיבוב שמשתמשים בו מספיק גדול כדי למנוע ניחוש בכוח גס, למעשה זו השיטה הרווחת כיום.
סוגי פונקציות.
פונקציות גיבוב קריפטוגרפיות מתחלקות לשתי משפחות עיקריות:
מבנה מרקל-דמגרד.
מבנה טיפוסי של פונקציית גיבוב קריפטוגרפית מורכב משלושה שלבים עיקריים; שלב הכנה, הליבה שנקראת 'פונקציית תמצות' ושלב סיום אופציונלי. היות שבדרך כלל המסר גדול במידה נכרת מהקלט אותו מקבלת פונקציית התמצות הפנימית יש צורך ליישם שיטה כלשהי לחלוקה לבלוקים בגודל קבוע וריפוד הבלוק האחרון כאשר אורך המסר אינו מתחלק היטב. השיטה הנפוצה שנקראת MD strengthening הומצאה על ידי רונלד ריבסט והיא מיישמת את מבנה מרקל ודמגרד. בשיטה זו מחלקים את הקלט לבלוקים בגודל קבוע מוסיפים '1' בסוף המסר ומרפדים באפסים ואז מוסיפים בלוק אחד המייצג את גודל המסר בסיביות ומבצעים את פעולת הפונקציה על כל הבלוקים בזה אחר זה. מרקל ודמגרד הוכיחו שאם נתונה פונקציית כיווץ (compression function) חסינת התנגשויות (בקיצור CRHF) למשל פונקציה מהצורה formula_55 כאשר formula_56, אפשר להכין ממנה פונקציית גיבוב בטוחה לגיבוב מסר בכל אורך רצוי, שגם היא חסינת התנגשויות. כלומר ביטחון המבנה האמור אינו חלש מביטחונה של הפונקציה הפנימית עצמה.
פונקציית התמצות formula_9 מקבלת מחרוזת סיביות formula_10 באורך קבוע וערך נוסף (בדרך כלל תוצאת הפונקציה מסבב קודם הנקרא chaining value) ומחזירה פלט באורך קבוע באמצעות חישוב אלגברי כלשהו או בהסתמך על פונקציית הצפנה, לפונקציה זו תכונה חשובה שנקראת אפקט כדור השלג, הכוונה היא שכל שינוי קל בקלט אפילו בסיבית אחת יגרום לשינוי גדול בפלט, כך בתוך מספר סבבים מיטשטש הקשר בין הקלט המקורי לפלט.
כמתואר בתרשים השיטה באופן כללי פועלת כדלהלן:
לסיכום האלגוריתם נראה כך:
פונקציית תמצות.
פונקציית התמצות שנקראת גם פונקציית כיווץ (compression function) היא הליבה של פונקציית הגיבוב. אפשר להכין פונקציית תמצות חד-כיוונית וחסינת התנגשויות בשלושה אופנים עיקריים;
פונקציית גיבוב מבוססת אריתמטיקה מודולרית.
איוון דמגרד הציע סכמה כזו המבוססת על צופן אל-גמאל וגיבסון ובלייר הציעו מבנים דומים המבוססים על בעיית לוגריתם דיסקרטי שפועלים מעל חבורה formula_88 מסדר ראשוני formula_89. הרעיון הוא להכפיל את formula_4 הבלוקים של המסר עם formula_4 אלמנטים אקראיים formula_92 מתוך formula_88. ערך הגיבוב יהיה תוצאה של:
כאשר formula_96 הוא הבלוק formula_97 של המסר לאחר שרופד ב-'1' כדי למנוע מצב שהבלוק יהיה כולו מאופס. בכל אופן מרבית הסכמות המבוססות על אריתמטיקה מודולרית כמו זו הן סכמות שפותחו בשיטות אד הוק, לא הוכחו כבטוחות וחלקן הגדול אף נפרצו בקלות. במיוחד ראוי לציון תקן איזו 4–10118 (MASH) שנפרץ פעם אחר פעם באופן מביך, לאחר שתוקן ובכל פעם התגלו בו שוב חולשות. המבנה הכללי הטוב ביותר היודע הוא מהצורה:
כאשר formula_76 הוא ערך הביניים ו-formula_97 הם הבלוקים של המסר עם יתירות מוספת. חשוב מאוד להוסיף יתירות מכוונת למסר לפני הגיבוב כדי למנוע את 'התקפת בלוק מתקן' (להלן). הגרסה העדכנית של תקן איזו 4–10118 נכון לשנת 1998 (ISO/IEC 10118-4) נקראת MASH קיצור של modular arithmetic secure hash והיא מופיעה בשתי גרסאות MASH-1 ו-MASH-2. פונקציית התמצות הפנימית של MASH היא מהצורה: