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