פונקציית גיבוב קריפטוגרפית
תכונות בסיסיות > התקפת יום הולדת

פרדוקס יום ההולדת טוען שהסיכויים שיימצאו בחדר אחד שניים מתוך 23 אנשים שלהם יום הולדת זהה, הם בערך 0.507 (מעל 50 אחוז), שזוהי באופן מפתיע תוצאה גבוהה מהאינטואיציה הראשונית (ולכן תוצאה זו בתורת ההסתברות נקראת 'פרדוקס'). היות שלא מדובר על יום הולדת ספציפי אלא כל זוג תואם, מספר הזוגות האפשריים בקבוצה כזו הוא רק  23\times 22/2=253. במילים אחרות כדי שההסתברות ששני משתנים מקריים יהיו זהים מעל מרחב הסתברות  U בהתפלגות אחידה בהסתברות גבוהה מחצי נדרשים לפחות  1.2\cdot |U|^{1/2} מאורעות. במקרה של יום הולדת השורש הריבועי של 365 הוא בערך 19.10 ולכן צריכים להיות לפחות 23 אנשים, אך בכל הקשור לימי הולדת נתון זה אינו מדויק כיוון שהתפלגות הלידות אינה אחידה (למשל באוקטובר נולדים כ-5% יותר תינוקות בממוצע מאשר בחודשים האחרים בשנה).
העובדה שמבחינה סטטיסטית היתכנות של התנגשויות גבוהה יחסית ניתנת לניצול לשבירת פונקציית גיבוב (או כל פונקציה חד-כיוונית). הרעיון הוא שהמתקיף שמקבל לידיו קלט מסוים נניח  m אותו הוא מעוניין לזייף ואת ערך הגיבוב שלו נניח  h(m) המשמש כהוכחה למקוריותו. הוא מכין תחילה  r_{1} וריאציות של  m וכן  r_{2} וריאציות של הקלט המזויף  m' אותו הוא מעוניין להחליף איתו. את כל הערכים הוא מגבב ומאחסן בטבלה ממוינת. לאחר מכן הוא מחפש בטבלה שני קלטים האחד מקורי והשני מזויף שלהם ערך גיבוב זהה. במידה שנמצא זוג תואם כזה נניח  (m_{i},m_{i}') הוא יכול לשייך את ערך הגיבוב של  m_{i} לקלט  m_{i}' ולטעון שהוא מקורי היות שמתקיים  h(m_{i}')=h(m_{i}). ההבדלים בין הקלטים יכולים להיות כל הבדל קל שאינו משנה את משמעות התוכן כמו רווחים כפולים, שורות ריקות וכדומה. מבחינה הסתברותית מספר ההתנגשויות הצפוי הוא  r_{1}\cdot r_{2}/n והסיכוי למצוא התנגשות אחת הוא בסדר גודל  1-\exp(-r_{1}\cdot r_{2}/2^{n}) שהוא בערך 63% עם זיכרון בסדר גודל של  O(r) כאשר  r=r_{1}=r_{2}=2^{n/2}. יש להביא בחשבון גם את מיון הערכים שהוא בסיבוכיות של  O(r\log r) וכן החיפוש שהוא בסיבוכיות  O(\log r) אך פעולות אילו אינן משמעותיות ואפשר להתעלם מהן. את ההתקפה פיתח גידעון יובל ב-1979.
יתרה מזו, אפשר לצמצם את דרישות הזיכרון באופן משמעותי אם ממירים את בעיית חיפוש ההתנגשויות לבעיה אחרת מאוד דומה שנקראת בעיית מציאת מחזוריות של פונקציה אקראית. אם נתונה פונקציה אקראית  x_{0},x_{1}=f(x_{0}),x_{2}=f(x_{1}),..., קיימים אלגוריתמים מהירים למציאת שני ערכים  x_{i},x_{j} כך שמתקיים  f(x_{i})=f(x_{j}) כאשר  i\neq j וזאת ללא צורך בזיכרון כלל. בנוסף אפשר ליישם את אלגוריתם החיפוש באופן מקבילי. לדוגמה בטכנולוגיה של 1994 אפשר היה לבנות בעלות של 10 מיליון דולר, חומרה ייעודית למציאת התנגשויות בפונקציית הגיבוב MD5 כאשר  n=128 בתוך 21 יום. בשנת 2004 במחיר נמוך מזה אפשר היה למצוא התנגשויות בתוך 4 שעות.
להתקפה זו השלכה מהותית על ביטחון כל פונקציית גיבוב. אם פונקציית גיבוב מפיקה פלט של  n סיביות, בהנחה שלא קיימת נגדה התקפה טובה מכוח גס אז אומרים שביטחונה המרבי הוא בפקטור של כמחצית  n ללא תלות באיכותה. למשל ב-SHA-1 פלט הפונקציה המינימלי הוא 160 סיביות ועל כן מציאת התנגשות בכוח גס היא בסיבוכיות של  2^{80}. נכון לשנת 2015 מקובל להשתמש בערכי גיבוב באורך של לפחות 256 סיביות כדי לקבל ביטחון ברמה של  2^{128} שהוא המינימום הנדרש כיום. ליתר דיוק מספיק שהזיכרון הפנימי של האלגוריתם יהיה גדול כדי לסכל התקפה זו ואילו ערך הגיבוב המתקבל ממנו ניתן ל"קיטום" לגודל הרצוי. הוכח שאם פונקציית הגיבוב בטוחה, הרי שאפשר ליטול רק חלק מתוצאת הגיבוב מבלי להסתכן בירידה בביטחון כל עוד אורך הגיבוב שמשתמשים בו מספיק גדול כדי למנוע ניחוש בכוח גס, למעשה זו השיטה הרווחת כיום.