פונקציית גיבוב קריפטוגרפית

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

התקפת יום הולדת

פרדוקס יום ההולדת אומר שהסיכויים שיימצאו בחדר אחד שניים מתוך 23 אנשים שלהם יום הולדת זהה, הם בערך 0.507 (מעל 50 אחוז), שזה באופן מפתיע גבוה מהאינטואיציה הראשונית (מסיבה זו נקרא 'פרדוקס'). היות שלא מדובר על יום הולדת ספציפי אלא כל זוג תואם, מספר הזוגות האפשריים בקבוצה כזו הוא רק . במילים אחרות כדי שההסתברות ששני משתנים מקריים יהיו זהים מעל מרחב הסתברות  בהתפלגות אחידה בהסתברות גבוהה מחצי נדרשים לפחות  מאורעות. במקרה של יום הולדת השורש הריבועי של 365 הוא בערך 19.10 ולכן צריכים להיות לפחות 23 אנשים, אך בכל הקשור לימי הולדת נתון זה אינו מדויק כיוון שהתפלגות הלידות אינה אחידה (למשל באוקטובר נולדים כ-5% יותר תינוקות בממוצע מאשר בחודשים האחרים בשנה).
העובדה שמבחינה סטטיסטית היתכנות של התנגשויות גבוהה יחסית ניתנת לניצול לשבירת פונקציית גיבוב (או כל פונקציה חד-כיוונית). הרעיון הוא שהמתקיף שמקבל לידיו קלט מסוים נניח  אותו הוא מעוניין לזייף ואת ערך הגיבוב שלו נניח  המשמש כהוכחה למקוריותו. הוא מכין תחילה  וריאציות של  וכן  וריאציות של הקלט המזויף  אותו הוא מעוניין להחליף איתו. את כל הערכים הוא מגבב ומאחסן בטבלה ממוינת. לאחר מכן הוא מחפש בטבלה שני קלטים האחד מקורי והשני מזויף שלהם ערך גיבוב זהה. במידה שנמצא זוג תואם כזה נניח  הוא יכול לשייך את ערך הגיבוב של  לקלט  ולטעון שהוא מקורי היות שמתקיים . ההבדלים בין הקלטים יכולים להיות כל הבדל קל שאינו משנה את משמעות התוכן כמו רווחים כפולים, שורות ריקות וכדומה. מבחינה הסתברותית מספר ההתנגשויות הצפוי הוא  והסיכוי למצוא התנגשות אחת הוא בסדר גודל  שהוא בערך 63% עם זיכרון בסדר גודל של  כאשר . יש להביא בחשבון גם את מיון הערכים שהוא בסיבוכיות של  וכן החיפוש שהוא בסיבוכיות  אך פעולות אילו אינן משמעותיות ואפשר להתעלם מהן. את ההתקפה פיתח גידעון יובל ב-1979.
יתרה מזו, אפשר לצמצם את דרישות הזיכרון באופן משמעותי אם ממירים את בעיית חיפוש ההתנגשויות לבעיה אחרת מאוד דומה שנקראת בעיית מציאת מחזוריות של פונקציה אקראית. אם נתונה פונקציה אקראית , קיימים אלגוריתמים מהירים למציאת שני ערכים  כך שמתקיים  כאשר  וזאת ללא צורך בזיכרון כלל. בנוסף אפשר ליישם את אלגוריתם החיפוש באופן מקבילי. לדוגמה בטכנולוגיה של 1994 אפשר היה לבנות בעלות של 10 מיליון דולר, חומרה ייעודית למציאת התנגשויות בפונקציית הגיבוב MD5 כאשר  בתוך 21 יום. בשנת 2004 במחיר נמוך מזה אפשר היה למצוא התנגשויות בתוך 4 שעות.
להתקפה זו השלכה מהותית על ביטחון כל פונקציית גיבוב. אם פונקציית גיבוב מפיקה פלט של  סיביות, בהנחה שלא קיימת נגדה התקפה טובה מכוח גס אז אומרים שביטחונה המרבי הוא בפקטור של כמחצית  ללא תלות באיכותה. למשל ב-SHA-1 פלט הפונקציה המינימלי הוא 160 סיביות ועל כן מציאת התנגשות בכוח גס היא בסיבוכיות של . נכון לשנת 2015 מקובל להשתמש בערכי גיבוב באורך של לפחות 256 סיביות כדי לקבל ביטחון ברמה של  שהוא המינימום הנדרש כיום. ליתר דיוק מספיק שהזיכרון הפנימי של האלגוריתם יהיה גדול כדי לסכל התקפה זו ואילו ערך הגיבוב המתקבל ממנו ניתן ל"קיטום" לגודל הרצוי. הוכח שאם פונקציית הגיבוב בטוחה, הרי שאפשר ליטול רק חלק מתוצאת הגיבוב מבלי להסתכן בירידה בביטחון כל עוד אורך הגיבוב שמשתמשים בו מספיק גדול כדי למנוע ניחוש בכוח גס, למעשה זו השיטה הרווחת כיום.

התקפת בלוק מתקן

התקפת בלוק מתקן (correcting block) היא התקפה המנצלת את המבנה האלגברי של פונקציית התמצות הפנימית. ההתקפה מתמקדת בחיפוש התנגשויות או מקור נוסף על ידי החלפת בלוק אחד או יותר בסוף, באמצע או בהתחלה של המסר. ההתקפה מתבצעת על ידי חישוב  כאשר  הוא הבלוק המתקן. מבנה אלגברי פגיע במיוחד להתקפה זו משום שאפשר להפוך לפעמים את פונקציית התמצות הפנימית בעזרת מניפולציה אלגברית. דרך נפוצה להתמודד עם התקפה זו היא להוסיף יתירות מכוונת למסר לפני הגיבוב כך שיהיה קשה למצוא בלוק מתקן עם היתירות הדרושה. המחיר כמובן הוא ירידה בביצועים. לדוגמה ב-1984 הציעו דייוויס ופרייס פונקציית גיבוב עם פונקציית תמצות  כדלהלן: . היתירות שהם הוסיפו הייתה 64 אפסים שנוספו לכל בלוק לפנים או בסוף. גיראולט ואחרים הראו כיצד אפשר לתקוף פונקציה כזו ולמצוא מקור נוסף. CCITT X.509 הייתה פונקציית גיבוב שפותחה ב-1988 וניסתה למנוע את ההתקפה המתוארת על ידי הוספת היתירות באופן כזה שכל ניבל (חצי בית) בכל הבתים של המסר יכיל ארבעה אפסים. למרות זאת הראה קופרשמידט שאפשר למצוא התנגשויות במבנה זה באמצעות ההתקפה האמורה.

פונקציית גיבוב אקראית

פונקציית גיבוב אקראית היא פונקציית גיבוב המשלבת בנוסף לקלט הרגיל גיוון אקראי הנקרא מלח (salt). מהיבט תאורטי המטרה של המלח היא לאפשר הסתמכות על פונקציית גיבוב בעלת ביטחון חלש כמו MD5 ו-SHA-1 שבעקבות קרפיטואנליזה חדשה שמצביעה על בעיות בעמידות מפני התנגשויות מומחים המליצו שלא להשתמש בהן. הרעיון הוצע ב-2007 על ידי שי הלוי והוגו קרווציק לחיזוק אלגוריתם חתימה דיגיטלית DSA, המשלב בין היתר פונקציית גיבוב. השאיפה היא שאלגוריתם החתימה יישאר בטוח אפילו אם פונקציית הגיבוב איתה הוא משתמש אינה מספקת עמידות מפני התנגשויות בעקבות קריפטואנליזה חדשה שמצביעה על חולשות במבנה הפנימי שלה, בדיוק כמו שקרה עם MD5 ו-SHA-1. במילים אחרות מנגנון חתימה דיגיטלית שעושה שימוש בפונקציית גיבוב אקראית לא חייב להסתמך על ההנחה שקשה למצוא התנגשויות בפונקציית הגיבוב שהיא הגדרה מחמירה ובדרך כלל קשה יותר להשגה אלא על הגדרה קלה יותר הנקראת "פונקציית גיבוב אוניברסלית".