לדלג לתוכן

1.4 התנגשות גיבוב ומספרים פתרון

פתרון - התנגשות גיבוב ומספרים

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

פתרון תרגיל 1 - פענוח הדרישה

נסתכל שוב על הקוד הרלוונטי מ-col.c:

unsigned long hashcode = 0x21DD09EC;

unsigned long check_password(const char* p){
    int* ip = (int*)p;
    int i;
    int res=0;
    for(i=0; i<5; i++){
        res += ip[i];
    }
    return res;
}

והתשובות:

  1. אורך הקלט חייב להיות 20 בתים בדיוק, מהבדיקה strlen(argv[1]) != 20 ב-main.
  2. הפונקציה עושה int* ip = (int*)p - כלומר מפרשת מחדש את מצביע ה-char כמצביע ל-int. אחר כך ip[0] עד ip[4] הם חמישה מספרים של 4 בתים כל אחד, ויחד 5 * 4 = 20 בתים. זה בדיוק תואם את אורך הקלט הנדרש.
  3. היעד הוא 0x21DD09EC בהקסה, שהוא 568134124 בעשרוני.
  4. הקלט לא יכול להכיל בית 0x00. הפונקציה strlen סופרת תווים עד בית ה-null הראשון. אם יופיע 0x00 באמצע, האורך הנמדד יהיה קצר מ-20, והבדיקה תיכשל עם ההודעה passcode length should be 20 bytes.

פתרון תרגיל 2 - חשבון ההתנגשות

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

568134124 / 5 = 113626824   remainder 4

אז ניקח ארבעה מספרים של 113626824 ומספר חמישי שסופג את השארית, כלומר 113626824 + 4 = 113626828:

113626824  =  0x06C5CEC8
113626828  =  0x06C5CECC

check:  4 * 0x06C5CEC8 + 0x06C5CECC
     =  454507296 + 113626828
     =  568134124
     =  0x21DD09EC   (exactly the target)

אף אחד מהמספרים לא מכיל בית 0x00: 0x06C5CEC8 בנוי מהבתים 06 C5 CE C8, וכולם שונים מאפס. מצוין, נעבור את בדיקת האורך.

הערה על overflow וסימן: הסכום 0x21DD09EC קטן מ-0x7FFFFFFF, כך שכשהוא מצטבר במשתנה int המסומן הוא נשאר חיובי ולא גולש. לכן כשהוא מוחזר מ-check_password (המוגדרת unsigned long), הרחבת הסימן ממלאת את הבתים העליונים ב-0x00000000, והערך נשאר 0x0000000021DD09EC - בדיוק שווה ל-hashcode. בחירת מספרים קטנים וחיוביים היא זו ששמרה עלינו מהמלכודת הזו.

פתרון תרגיל 3 - סדר הבתים

נמיר כל מספר לבתים בסדר little-endian - הבית הנמוך ראשון:

0x06C5CEC8  ->  C8 CE C5 06
0x06C5CECC  ->  CC CE C5 06

והקלט המלא, 20 בתים:

C8 CE C5 06   C8 CE C5 06   C8 CE C5 06   C8 CE C5 06   CC CE C5 06
\_ number 1 _/ \_ number 2 _/ \_ number 3 _/ \_ number 4 _/ \_ number 5 _/

נאמת בפייתון:

import struct
payload = struct.pack('<I', 0x06C5CEC8) * 4 + struct.pack('<I', 0x06C5CECC)
print(len(payload))          # 20
print(0x00 in payload)       # False
print(payload.hex())         # c8cec506c8cec506c8cec506c8cec506cccec506

עם pwntools הקוד שקול הוא p32(0x06C5CEC8)*4 + p32(0x06C5CECC), שמייצר בדיוק את אותם בתים.

פתרון תרגיל 4 - הזרמת הקלט והרצה

עכשיו מריצים את col עם הקלט. הבתים שלנו לא מודפסים, אז נשתמש ב-command substitution כדי להעביר אותם כארגומנט.

אם על המכונה python הוא פייתון 2 (כפי שנפוץ בגרסה הישנה של pwnable.kr), הדרך הקצרה:

./col `python -c 'print "\xc8\xce\xc5\x06"*4 + "\xcc\xce\xc5\x06"'`

אם python הוא פייתון 3, נשתמש ב-sys.stdout.buffer.write כדי לא לפגוע בבתים:

./col $(python3 -c "import sys; sys.stdout.buffer.write(b'\xc8\xce\xc5\x06'*4 + b'\xcc\xce\xc5\x06')")

הפלט הצפוי הוא תוכן הקובץ flag - כלומר מחרוזת הדגל שמדפיס system("/bin/cat flag").

אם קיבלתם wrong passcode, כמעט תמיד הסיבה היא סדר בתים הפוך: כתבתם 06 C5 CE C8 במקום C8 CE C5 06. אם קיבלתם passcode length should be 20 bytes, כנראה נכנס בית 0x00 שקיצר את המחרוזת, או שהמעטפת פירשה את רצף ה-escape אחרת ממה שציפיתם.

פתרון עמיד יותר עם pwntools

כדי לא להיות תלויים במעטפת ובגרסת הפייתון, אפשר להריץ הכל מתוך סקריפט pwntools יחיד, מקומית או דרך SSH:

from pwn import *

# the target the sum needs to reach
target = 0x21DD09EC

# four equal parts and one that absorbs the remainder
part  = target // 5          # 0x06C5CEC8
rest  = target - part * 4    # 0x06C5CECC
payload = p32(part) * 4 + p32(rest)

assert len(payload) == 20
assert b'\x00' not in payload
assert sum(u32(payload[i:i+4]) for i in range(0, 20, 4)) == target

# run locally
io = process(['./col', payload])
print(io.recvall().decode(errors='replace'))

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

פתרון תרגיל 5 - אימות עם GDB

נריץ תחת GDB כדי לראות בעיניים שהמספרים נקראים כמו שתכננו. נשתמש ב-pwndbg (או pwntools gdb), אבל גם GDB רגיל עובד.

gdb ./col

ובתוך GDB:

break check_password
run $(python3 -c "import sys; sys.stdout.buffer.write(b'\xc8\xce\xc5\x06'*4 + b'\xcc\xce\xc5\x06')")

כשנעצור בכניסה ל-check_password, המצביע לקלט נמצא באוגר הפרמטר הראשון. במוסכמת הקריאה של x86-64 (System V) הפרמטר הראשון עובר ב-rdi. נדפיס חמש מילים של 4 בתים מהכתובת הזו:

x/5xw $rdi

הפלט הצפוי (הכתובת משמאל תשתנה):

0x7fffffffe4a0: 0x06c5cec8  0x06c5cec8  0x06c5cec8  0x06c5cec8
0x7fffffffe4b0: 0x06c5cecc

שימו לב איך GDB כבר מציג את המספרים בסדר הנכון - 0x06c5cec8 - למרות שבזיכרון הבתים שמורים כ-C8 CE C5 06. זה בדיוק ה-little-endian בפעולה: הכלי קורא את הבתים ומרכיב מהם את המספר.

אם נצעד בלולאה (למשל עם next כמה פעמים) ונדפיס את res, נראה אותו מטפס: 0x06c5cec8, ואז 0x0d8b9d90, וכך הלאה עד 0x21dd09ec בסוף. אפשר לוודא את הערך הסופי:

finish

וה-finish יראה את ערך ההחזרה של הפונקציה - שאמור להיות 0x21dd09ec, בדיוק כמו hashcode.

למה זה עבד ואיך להכליל

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

שלוש נקודות שכדאי לקחת הלאה לאתגרים ולמערכות אמיתיות:

  1. סדר בתים תמיד קובע. ברגע שמפרשים בתים גולמיים כמספרים, p32/p64 ו-u32/u64 של pwntools הם החברים הכי טובים שלכם. אל תמירו בתים ידנית אם אפשר להימנע.
  2. מגבלות על הבתים הן חלק מהאתגר. כאן האיסור היה על בית 0x00 בגלל strlen. במקומות אחרים תיתקלו באיסור על תווי רווח, על תווים לא מודפסים, או על בתים מחוץ לטווח ASCII. תמיד בדקו אילו בתים הקורבן יסרב לקבל, ובנו את הפתרון בהתאם.
  3. חשבו על סימן וoverflow מראש. ברגע שהסכום עלול לחרוג מ-0x7FFFFFFF, המשתנה המסומן והרחבת הסימן ל-unsigned long נכנסים לתמונה. אפשר להימנע מהם (מספרים קטנים), או לנצל אותם במכוון - אבל אף פעם לא להתעלם מהם.

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