התקפת התנגשויות

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

ההתקפה מחולקת לשתי קטגוריות.

• מציאת התנגשות. בהינתן פונקציית גיבוב $H$ ושני מסרים כלשהם $m_{1}$ ו-$m_{2}$ (למתקיף אין שליטה על תוכנם) כאשר $m_{1}\neq m_{2}$, מציאת התנגשות היא כל מצב שבו $H(m_{1})=H(m_{2})$.
• מציאת התנגשות עם תחילית נבחרת (chosen prefix). בהינתן פונקציית גיבוב $H$, שתי תחיליות כלשהן $p_{1}$ ו-$p_{2}$ שנבחרו על ידי המתקיף ושני מסרים אקראיים $m_{1},m_{2}$ שאין לו שליטה על תוכנם. התנגשות היא כל מצב שבו מתקיים $H(p_{1}\ \|\ m_{1})=H(p_{2}\ \|\ m_{2})$. כאשר הסימן $\|$ מייצג שרשור.

בשל פרדוקס יום הולדת כל פונקציית גיבוב קריפטוגרפית בעלת פלט באורך $n$ סיביות לא משנה כמה היא בטוחה, ניתנת לשבירה בכוח גס - דהיינו מציאת התנגשות, בסיבוכיות של $2^{n/2}$.

תחילית נבחרת

התקפת תחילית נבחרת (chosen prefix) פורסמה לראשונה ביורוקריפט 2007 נגד אלגוריתם MD5 והתקפה מעשית כזו בוצעה ב-2008בה הצליחו חוקרים לזייף תעודת X.509 חתומה שאיתה ניתן היה להתחזות לרשות מאשרת. באופן כללי אלגוריתמים הבנויים בסגנון מבנה מרקל דמגרד (כמו סדרת SHA) חשופים להתקפה זו בשל אופי המבנה עצמו. מסיבה זו כיום נוטים לפתח פונקציות גיבוב חדשות שלהן תכונת אקראיות.

חתימה דיגיטלית

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

1. תחילה המתקיף מכין שני מסמכים שונים A ו-B אשר תמצית הגיבוב שלהם זהה. המטרה שלו היא לשכנע את בוב בטענה שהמסמך B הגיע מאליס.
2. המתקיף שולח לאליס את המסמך A, היא חותמת עליו לאחר שהסכימה עם תוכנו ומחזירה אותו בחזרה למתקיף.
3. המתקיף מצמיד את החתימה של מסמך A למסמך B.
4. המתקיף שולח את המסמך B לבוב יחד עם החתימה מהמסמך A בטענה שהמסמך נחתם על ידי אליס.
5. לבוב אין דרך לדעת שהמסמך שקיבל אינו המסמך המקורי עליו חתמה אליס, כי החתימה עליו נמצאה תקפה, הוא מקבל את טענת המתקיף.

TCR

פונקציית גיבוב $f_{k}()$ כאשר $k$ מגדיר את האורך והוא פרמטר ביטחון, תקרא TCR (קיצור של Target collision resistance או בשם אחר פונקציית גיבוב אוניברסלית) אם כל יריב פולינומי A (המוגבל בזמן ומקום) יכול לנצח במשחק הבא בהסתברות זניחה. תחילה הוא מקבל אתגר כלשהו $m_{1}$ ולאחר מכן הוא מקבל את $k$ ואז הוא מנצח במשחק אם הצליח לייצר ערך נוסף $m_{2}$ כך שמתקיים $f_{k}(m_{1})=f_{k}(m_{2})$. תכונה זו דומה לתכונת עמידות מפני מציאת מקור שני (second pre-image) והיא נחשבת לגרסה חלשה של עמידות מפני התנגשויות ולפעמים היא יותר פרקטית כך שאפשר להסתפק בה לעומת הגרסה החזקה יותר של עמידות מלאה מפני התנגשויות.