התנגשויות גיבוב, כששני קבצים שונים "נראים" זהים¶
פונקציית גיבוב (hash function) לוקחת קלט בכל גודל, ומחזירה פלט קבוע וקצר - "טביעת אצבע" של הקלט. הרעיון הוא שאם משהו בקלט משתנה, אפילו בייט אחד, הפלט אמור להשתנות לגמרי ובאופן בלתי צפוי. אבל בגלל שהקלט האפשרי אינסופי והפלט תמיד קבוע באורכו, מבחינה מתמטית טהורה, חייבים להתקיים מקרים שבהם שני קלטים שונים מייצרים בדיוק אותו hash. זו התנגשות גיבוב - hash collision.
למה זה בלתי נמנע מתמטית¶
תארו לעצמכם hash שאורכו 256 סיביות. יש 2 בחזקת 256 ערכי פלט אפשריים - מספר עצום, אבל סופי. הקלטים האפשריים, לעומת זאת, אינסופיים - מחרוזות בכל אורך אפשרי. כשיש יותר קלטים אפשריים מפלטים אפשריים, לפי עיקרון פשוט שנקרא "עקרון שובך היונים", מוכרח להיות זוג קלטים לפחות שמתנגשים באותו פלט. השאלה האמיתית היא לא "האם יש התנגשויות", אלא "כמה קשה למצוא אחת בפועל".
אבטחה טובה אומרת "קשה למצוא, לא בלתי אפשרי"¶
פונקציית גיבוב קריפטוגרפית טובה לא מבטיחה שאין התנגשויות, היא מבטיחה שקשה מאוד, מבחינה חישובית, למצוא אחת בכוונה. יש שני סוגי התקפה שכדאי להבחין ביניהם:
- התנגשות רגילה. למצוא שני קלטים שרירותיים כלשהם שמתנגשים באותו hash, בלי דרישה שיהיו קשורים לשום דבר ספציפי.
- התקפת preimage. בהינתן hash ספציפי, למצוא קלט כלשהו שמייצר בדיוק אותו hash, מה שקשה בהרבה מהתנגשות רגילה.
מה שמפתיע רבים בפעם הראשונה הוא "פרדוקס יום ההולדת" - מתברר שהסיכוי למצוא התנגשות בין קבוצת קלטים גדל מהר בהרבה ממה שהאינטואיציה מציעה, בדיוק כמו שבחדר עם עשרים ושלושה אנשים בלבד, הסיכוי ששניים חולקים יום הולדת עובר את חמישים אחוז, למרות שיש שלוש מאות שישים וחמישה ימים אפשריים.
מה קורה כשאלגוריתם גיבוב נשבר בפועל¶
לאורך השנים, כמה אלגוריתמי גיבוב שנחשבו פעם בטוחים הוכחו כפגיעים, כשחוקרים מצאו שיטות למצוא התנגשויות מהר בהרבה ממה שהיה אמור להיות אפשרי. הדוגמה המוכרת ביותר היא MD5, שעבורו כבר קיימות שיטות למצוא התנגשויות במהירות גבוהה, וגם SHA-1, שהוכח כפגיע להתנגשויות מעשיות. זו הסיבה שהתקנים המודרניים ממליצים על משפחת SHA-2 ומעלה לשימוש קריפטוגרפי רציני.
למה זה מסוכן בפועל, לא רק בתאוריה¶
התנגשות גיבוב מנוצלת בהקשרים שונים - חתימה דיגיטלית שמאמתת מסמך על סמך ה-hash שלו יכולה להתחזות, אם תוקף מוצא שני מסמכים שונים בתוכן (אחד תמים, אחד זדוני) עם אותו hash - חותמים על הראשון, והחתימה נשארת תקפה גם על השני. מערכות שבודקות שלמות קובץ (למשל להשוואת קבצים כפולים או וידוא שקובץ לא שונה) גם הן פגיעות אם אלגוריתם הגיבוב שהן משתמשות בו חלש.
איך זה מופיע באתגרי CTF¶
אתגרים בקטגוריית Crypto לפעמים מבקשים למצוא ישירות שני קלטים עם אותו hash תחת אלגוריתם חלש שנבחר במכוון, או לנצל התנגשות כדי לעקוף בדיקת שלמות שהמערכת סומכת עליה. זו דרך מצוינת להבין בפועל, ולא רק בתאוריה, למה בוחרים אלגוריתם גיבוב אחד על פני אחר.
איך זה מתחבר לשאר עולם האבטחה¶
הבנת התנגשויות גיבוב מלמדת שיעור רחב יותר - שום פונקציית אבטחה לא "בטוחה" בוואקום, היא בטוחה ביחס למה שידוע כרגע לגבי החולשות שלה. אלגוריתם שנחשב חזק היום עשוי להיחשב חלש בעוד כמה שנים, ככל שמחקר מתקדם.
בקורס מחקר חולשות אנחנו מסבירים למה בוחרים אלגוריתמי גיבוב מסוימים על פני אחרים, ואיך זיהוי אלגוריתם חלש הוא לרוב הצעד הראשון בפתרון אתגר קריפטוגרפי.
מתעניינים איך בפועל בונים או מנצלים התנגשות גיבוב? בדיסקורד שלנו יש דיונים מעניינים בדיוק על זה.
לסיכום¶
התנגשויות גיבוב הן תופעה מתמטית בלתי נמנעת, אבל אבטחה טובה נשענת על כך שקשה מאוד למצוא אותן בכוונה. כשאלגוריתם גיבוב נשבר, וזה קורה שוב ושוב לאורך ההיסטוריה, כל מערכת שסמכה עליו לצורכי אבטחה צריכה לעבור, ומהר, לאלגוריתם חזק יותר.