חזרה לבלוג

איך מכינים PNG שמציג את ה-MD5 של עצמו? hashquine מאפס, The Arma Of Efe

איך יוצרים PNG שכותב את ה-MD5 שלו בתוך הפיקסלים שלו בלי תבנית מוכנה? מדריך על MD5, מפתחות התנגשות, שכבות PNG וחיפוש efe23...23efe על RTX 5070.

התמונה שלמעלה אינה לוגו רגיל. על הקשת שמימין, מלמעלה למטה, כתוב efe235ae1b88c53e73d1c11515623efe, וזה ה-MD5 של הקובץ עצמו. מי שיוריד את התמונה ויריץ md5sum יראה את אותן 32 הספרות.

קבצים מסוג זה נקראים hashquine. הדוגמה המפורסמת ברשת היא ה-PNG עם הדרקון של retr0id, ורוב האנשים משתמשים בתבנית המוכנה שלו. אנחנו יצרנו את שלנו מאפס, בלי שום תבנית, עם הלוגו שלנו (The Arma Of Efe), עם קישור הבלוג שלנו, ועם תקציר מותאם אישית שמתחיל ב-efe ומסתיים ב-efe. להלן נסביר את התהליך צעד אחר צעד, כפי שלמדנו תוך כדי ניסוי.

ה-hashquine בפורמט PNG של Retr0id עם הדרקון, שמציג את תקציר ה-MD5 של עצמו

ה-hashquine בפורמט PNG של David “Retr0id” Buchanan, ‏MD5: 1337e2ef42b9bee8de06a4d223a51337. תמונה: Retr0id, דרך corkami/collisions.

מהו hash ולמה הוא משתנה בכל אות?

Hash (תקציר) הוא טביעת אצבע באורך קבוע שנגזרת מתוכן הקובץ. MD5 היא פונקציית תקציר שתוכננה בידי Ronald Rivest ב-1991. בין שהקלט הוא בייט אחד ובין שהוא 50 GB, הפלט תמיד בן 128 ביט, כלומר 32 ספרות מהתווים 0-9 ו-a-f.

התכונה המרכזית של פונקציות תקציר היא אפקט המפולת: השינוי הקטן ביותר בקלט משנה את כל הפלט. נסו להקליד משהו בתיבה למטה:

בעיית הביצה והתרנגולת

בגלל אפקט המפולת, תמונה שנושאת בתוכה את ה-MD5 שלה נראית במבט ראשון בלתי אפשרית:

  1. מציירים את התמונה ומחשבים את ה-MD5 שלה, למשל 4a8c91e0….
  2. כותבים את הקוד הזה על התמונה ושומרים.
  3. מכיוון שהפיקסלים השתנו, ה-MD5 של הקובץ הוא עכשיו משהו אחר, למשל 9f02d71a….
  4. כותבים את הקוד החדש, והתקציר משתנה שוב.

כדי לשבור את המעגל הזה צריך להיכנס פנימה, אל ה-MD5 עצמו.

הרעיון שמשבר את המעגל: מפתחות שאינם משנים את ה-MD5

MD5 אינו מעבד קובץ בפעם אחת. הוא מחלק אותו לבלוקים של 64 בייט ומעבד אותם לפי הסדר: מצב ההתחלה (IV) מתערבב עם הבלוק הראשון ומייצר מצב ביניים (IHV). המצב הזה מתערבב עם הבלוק הבא, וכך הלאה עד סוף הקובץ. המצב הסופי הוא ה-MD5 בן 32 הספרות.

הנקודה המכרעת: אפשר למצוא שני חלקי נתונים שונים (A ו-B), כל אחד באורך 128 בייט ומיושר לגבול של 64 בייט, שמובילים לאותו מצב ביניים. זוהי התנגשות עם קידומת זהה, וכלים כמו FastColl מייצרים אותה בזמן קצר. מכיוון שכל בלוק שבא אחריה רואה את אותו מצב, מתקיים:

  • אם מופיע החלק A, נראה על המסך קטע של קו, ואם מופיע B, הקו נעלם,
  • אבל ה-MD5 בסוף הקובץ אינו משתנה כלל.

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

איך צויר הקו אות אחר אות?

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

מכיוון שלא השתמשנו בתבנית מוכנה, נדרש לעבור בבת אחת את ארבע שכבות האימות של ה-PNG:

  1. יישור ל-64 בייט: כל מפתח בקובץ חייב לשבת בדיוק על הגבול offset % 64 == 0. הוספנו לזרם הדחיסה DEFLATE בלוקים ריקים באורך אפס, וכך יישרנו כל מפתח לגבול הזה.
  2. מסנני Sub ו-Up של PNG: את אינדקסי הפלטה 0..254 הפכנו לשחורים, ורק את האינדקס 255 לבן. שני החלקים של זוג התנגשות נבדלים בביט העליון של כמה בייטים. בשורה עם מסנן Sub ההבדל הזה מזיז את הפיקסלים שאחריו ב-128 ומתקבל קו אופקי, ומסנני Up מעבירים אותו מטה. את הבייטים שאחרי המפתח בחרנו כך שהקו יהיה לבן לגמרי (255) במצב אחד ושחור במצב השני.
  3. איזון Adler-32 של zlib: בזמן פתיחת הנתון המכווץ הוא עובר בדיקת סכום Adler-32, וכל מפתח משנה את הסכום הזה בכמה מאות יחידות. בשורות השחורות הנחנו 160 מפתחות איזון, ואת תת-הקבוצה שמחזירה את הסכום בדיוק בחרנו בעזרת תכנון דינמי וחיפוש בשיטת המפגש באמצע.
  4. אימות CRC-32 של IDAT: בסוף כל צ’אנק IDAT יש CRC-32 בן 32 ביט. מיד אחרי הזרם המכווץ הוספנו 40 בלוקים נוספים, ופתרנו מערכת משוואות לינאריות מעל GF(2) בעזרת אלימינציית גאוס, כך שערך ה-CRC-32 התקבע על 0x1807EFE0.

תקציר מותאם אישית: כל ספרה מכפילה את העבודה ב-16

לא הספיק שהקובץ יציג את ה-MD5 שלו. רצינו שהתקציר יתחיל ב-efe וייגמר ב-efe. לשם כך שינינו את בלוק ה-nonce בן 64 הבייט שבסוף הקובץ וניסינו מיליארדי תקצירים.

כל ספרה יכולה לקבל 16 ערכים שונים, ולכן כל ספרה קבועה חדשה מכפילה את מספר הניסיונות הממוצע פי 16: עבור N ספרות קבועות נדרשים בממוצע 16^N ניסיונות. מעבד 24 הליבות שלנו מריץ לולאת C פשוטה ומחשב 177 מיליון MD5 בשנייה. כשעברנו לבצע את אותו חישוב על כרטיס המסך הניידי RTX 5070 בעזרת OpenCL, הקצב עלה ל-3.54 מיליארד בשנייה, פי 20 בערך. ל-efe23…23efe נדרשים בממוצע 1.1 טריליון ניסיונות; שלנו הופיע אחרי 90 מיליארד ניסיונות, בערך 25 שניות.

הזיזו את המחוון כדי לשנות את מספר הספרות הקבועות. התוצאות שבאמת מצאנו מסומנות בנקודות:

בדקו בעצמכם

הורידו את התמונה והריצו אותה בטרמינל. ב-Windows אפשר להשתמש ב-certutil -hashfile dosya.png MD5, וב-macOS ב-md5 dosya.png.

$ md5sum the-arma-of-efe-23-hashquine.png the-arma-of-efe-hashquine.png
efe235ae1b88c53e73d1c11515623efe  the-arma-of-efe-23-hashquine.png
efe8d2bee9dc7b5815f72581e5c17efe  the-arma-of-efe-hashquine.png

הספרות ה-32 בפלט זהות לקוד שכתוב על הקשת מלמעלה למטה.

הקוד שמייצר את התמונה נמצא כולו ב-GitHub: the-arma-of-owl/the-arma-of-efe-hashquine. מכיוון שגם שלד ההתנגשות נמצא במאגר, אפשר ליצור hashquine חדש עם ערך nonce משלכם.

מקורות: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗