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

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

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

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

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

תחילית נבחרת

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

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

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

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

TCR

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

הערות שוליים

1. Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate
2. Universal One-Way Hash Functions and their Cryptographic Applications