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

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

הבנה טובה של המתמטיקה הזו היא לא רק תרגיל אקדמי. הoverflow מספר שלם היא לעיתים קרובות הצעד הראשון בchain exploit: היא זו שמייצרת את גודל ההקצאה השגוי, את בדיקת הגבולות שנכשלת, או את האינדקס השלילי שמוביל לbuffer overflow. מי שמבין מספרים לעומק רואה את הבאגים האלה עוד לפני שהם הופכים לoverflow זיכרון.

---

איך מספרים שלמים מיוצגים - integer representation

בואו נתחיל מהבסיס. מספר שלם במחשב הוא רצף סופי של ביטים - בדרך כלל 8, 16, 32 או 64. לרוחב הזה יש משמעות עצומה, כי הוא קובע כמה ערכים אפשר בכלל להביע. משתנה מסוג int ברוב המערכות הוא 32 ביט, כלומר יש לו בדיוק 2^32 ערכים אפשריים - לא יותר.

השאלה הראשונה היא אם המספר מסומן או לא מסומן:

• מספר לא מסומן - unsigned - משתמש בכל הביטים בשביל הגודל. טווח של 32 ביט: מ-0 עד 4294967295 (כלומר 0xFFFFFFFF).
• מספר מסומן - signed - הביט העליון הוא ביט הסימן. הייצוג הוא משלים לשתיים - two's complement. טווח של 32 ביט: מ--2147483648 עד 2147483647.

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

bit pattern   as unsigned   as signed
0000 0000      0                0
0000 0001      1                1
0111 1111      127              127
1000 0000      128              -128
1111 1110      254              -2
1111 1111      255              -1

שימו לב לנקודה החשובה ביותר: אותו דפוס ביטים בדיוק יכול להתפרש כמספר חיובי גדול או כמספר שלילי, תלוי אך ורק באיך שהקוד מסתכל עליו. הבתים FF FF FF FF בזיכרון הם 4294967295 אם קוראים אותם כ-unsigned int, אבל -1 אם קוראים אותם כ-int. אף אחד מהם לא "נכון" יותר מהשני - זה עניין של פרשנות, ובדיוק בפער הפרשנות הזה נולדים באגים.

---

גלישת מספר שלם - integer overflow

מכיוון שלמשתנה יש מספר סופי של ביטים, יש לו גם ערך מקסימלי. מה קורה כשמוסיפים 1 לערך המקסימלי? הוא גולש וחוזר להתחלה. זה בדיוק כמו מד קילומטראז' מכני שמגיע ל-999999 ואז מתאפס ל-000000.

#include <stdio.h>

int main() {
    unsigned char x = 255;   // the maximum value for an unsigned 8-bit
    x = x + 1;               // overflow!
    printf("%u\n", x);       // prints 0, not 256

    unsigned int y = 0xFFFFFFFF;
    y = y + 1;
    printf("%u\n", y);       // prints 0 again

    return 0;
}

עבור מספרים לא מסומנים, ההתנהגות הזו מוגדרת היטב בתקן C: החישוב נעשה מודולו 2^n. כלומר 0xFFFFFFFF + 1 שווה בדיוק 0. אין כאן "שגיאה" מבחינת השפה - התוכנית ממשיכה כרגיל עם הערך הגלוש.

עבור מספרים מסומנים המצב שונה ומסוכן יותר: הoverflow של signed int היא התנהגות לא מוגדרת - undefined behavior. הקומפיילר רשאי להניח שהיא לעולם לא קורית, ולכן אופטימיזציות עלולות למחוק בדיקות שלמות שכתבתם. בפועל, על רוב המעבדים הoverflow תתנהג כמו wrap-around של משלים לשתיים - 2147483647 + 1 יהפוך ל--2147483648 - אבל אסור להסתמך על זה בקוד אמיתי.

למה זה חשוב לנו כתוקפים - the security angle

הנה תבנית קלאסית של באג שמופיע שוב ושוב בקוד אמיתי:

void copy_data(char *src, unsigned int len) {
    char buf[256];
    if (len > 256) {              // naive bounds check
        return;
    }
    memcpy(buf, src, len);        // safe? not necessarily
}

נראה תקין, אבל דמיינו ש-len מגיע מחיסור: len = end - start. אם end קטן מ-start בגלל טעות לוגית, החיסור בין שני מספרים לא מסומנים ייתן ערך ענק (למשל 0xFFFFFFF0), הבדיקה len > 256 תעבור, וה-memcpy יעתיק ארבעה מיליארד בתים לתוך buffer של 256. הנה buffer overflow שנולדה כולה מoverflow מספר.

תבנית מסוכנת נוספת היא חישוב גודל הקצאה:

char *buf = malloc(count * size);   // what if count * size overflows?

אם count ו-size נשלטים על ידי התוקף, המכפלה שלהם עלולה לגלוש למספר קטן. malloc יקצה buffer קטנטן, אבל הקוד ימשיך לכתוב אליו כאילו הוא ענק. זו הסיבה ש-calloc בודקת overflow במכפלה בעצמה, ולמה ראיתם המון CVE שמתחילים במילים "integer overflow leading to heap overflow".

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

---

סימניות והמרות - signedness and casting

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

השוואה בין מסומן ללא מסומן

int len = get_length();      // returns -1 on error
char buf[100];
if (len < 100) {             // looks like it guards against a buffer that's too large
    memcpy(buf, src, len);   // but len is an int, and memcpy expects an unsigned size_t
}

אם len הוא -1, אז len < 100 הוא אמת (כי -1 < 100), הבדיקה עוברת, אבל memcpy מקבל את len בפרמטר מסוג size_t שהוא לא מסומן. הערך -1 מומר ל-0xFFFFFFFFFFFFFFFF, ו-memcpy מנסה להעתיק כמות אסטרונומית של בתים. שוב - קריסה או גלישה.

הרחבת סימן - sign extension

כשמעתיקים ערך מסומן קטן לרוחב גדול יותר, המעבד מבצע הרחבת סימן: הוא מעתיק את ביט הסימן שמאלה. char בערך 0xFF (שהוא -1 כ-signed char) שהופך ל-int יהפוך ל-0xFFFFFFFF, ולא ל-0x000000FF כמו שאולי ציפיתם.

signed char  0xFF   =  -1
       |  sign extension to int
       v
int          0xFFFFFFFF  =  -1  (not 255)

לעומת זאת, unsigned char בערך 0xFF יהפוך ל-0x000000FF (הרחבה באפסים). ההבדל הזה - האם מרחיבים באפסים או בסימן - הוא מקור נפוץ מאוד לבאגים כשמפרשים בתים גולמיים כמספרים, וזה בדיוק מה שהולך לקרות לנו באתגר collision.

---

פונקציות גיבוב והתנגשויות - hash functions and collisions

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

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

בפונקציית גיבוב חזקה (כמו SHA-256), למצוא התנגשות דורש כמות בלתי מעשית של חישוב. אבל הרבה תוכנות משתמשות ב"גיבוב" ביתי, פשטני, שנועד למהירות ולא לאבטחה. ואז מציאת התנגשות הופכת מקשה לטריוויאלית.

גיבוב חלש - a weak hash

הנה דוגמה לגיבוב חלש קלאסי:

unsigned int weak_hash(const char *p) {
    unsigned int *ip = (unsigned int *)p;
    unsigned int res = 0;
    for (int i = 0; i < 5; i++) {
        res += ip[i];        // simply add five numbers
    }
    return res;
}

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

---

פירוק בתים למספרים לפי סדר הבתים - little-endian layout

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

בואו נראה בדיוק מה קורה כשלוקחים את הבתים C8 CE C5 06 בזיכרון וקוראים אותם כ-unsigned int של 4 בתים:

address:    +0    +1    +2    +3
bytes:      0xC8  0xCE  0xC5  0x06
             |     |     |     |
             v     v     v     v
the number =  0x06 C5 CE C8   (the byte from the highest address is the most significant)
           =  0x06C5CEC8

זו נקודה קריטית שמבלבלת הרבה אנשים: הבית הראשון בזיכרון הופך לבית הימני (הנמוך) של המספר. אם נכתוב את הבתים בסדר C8 CE C5 06, המספר שיתקבל הוא 0x06C5CEC8, ולא 0xC8CEC506. כשנבנה את הקלט לאתגר, נצטרך "להפוך" כל מספר שאנחנו רוצים לבתים בסדר little-endian.

בפייתון זה טריוויאלי עם המודול struct:

import struct
n = 0x06C5CEC8
data = struct.pack('<I', n)   # '<' = little-endian, 'I' = 4-byte unsigned int
print(data.hex())             # c8cec506

בעזרת pwntools זה עוד יותר קצר - הפונקציה p32(0x06C5CEC8) מחזירה בדיוק את אותם ארבעה בתים.

---

המקרה collision מ-pwnable.kr

עכשיו יש לנו את כל החלקים כדי לתקוף אתגר אמיתי. האתגר collision באתר pwnable.kr נותן לנו בינארי בערך כזה:

#include <stdio.h>
#include <string.h>

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;
}

int main(int argc, char* argv[]){
    if(argc<2){
        printf("usage : %s [passcode]\n", argv[0]);
        return 0;
    }
    if(strlen(argv[1]) != 20){
        printf("passcode length should be 20 bytes\n");
        return 0;
    }
    if(hashcode == check_password( argv[1] )){
        system("/bin/cat flag");
        return 0;
    }
    else
        printf("wrong passcode\n");
    return 0;
}

בואו נפרק את מה שהתוכנית דורשת מאיתנו:

1. הקלט מגיע כ-argv[1] - כלומר כארגומנט משורת הפקודה.
2. חייבים בדיוק 20 בתים: הבדיקה strlen(argv[1]) != 20. שימו לב ש-strlen סופרת עד בית ה-null הראשון, ולכן הקלט שלנו לא יכול להכיל אף בית 0x00, אחרת האורך יימדד קצר יותר.
3. הפונקציה check_password לוקחת את 20 הבתים, מסתכלת עליהם כחמישה int (כל אחד 4 בתים), ומחברת אותם ל-res.
4. הסכום צריך להיות שווה ל-hashcode, שהוא 0x21DD09EC.

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

בניית הקלט - constructing the payload

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

target:      0x21DD09EC  =  568134124 (decimal)
divide by 5: 568134124 / 5 = 113626824  (remainder 4)

four numbers:  113626824  =  0x06C5CEC8
fifth number:  113626828  =  0x06C5CECC   (added the remainder 4)

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

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

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

full input (20 bytes):
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 _/

שימו לב ששום בית כאן אינו 0x00, אז נעבור את בדיקת ה-strlen. מצוין.

רגע - הסימניות והoverflow שמאחורי הקלעים

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

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

שנית, אפשר היה גם לנצל את הoverflow במקום להימנע ממנה. לדוגמה, אפשר לבחור ארבעה מספרים אקראיים גדולים ולתת למספר החמישי להשלים את ההפרש, גם אם הדרך לשם עוברת דרך wrap-around. כל עוד הסכום הסופי, מודולו 2^32, שווה ל-0x21DD09EC ונשאר חיובי - הפתרון עובד. אבל בשביל אתגר אחד, הפתרון הפשוט של "לחלק בחמש" הוא הכי נקי.

הרצה - delivering via argv

באתר pwnable.kr מתחברים לאתגר כך:

ssh col@pwnable.kr -p2222
# the password is guest

בתוך המכונה נמצא הבינארי col ובעליו הוא המשתמש שיכול לקרוא את flag. הבינארי רץ עם הרשאות מוגברות (setuid), ולכן כשנצליח, ה-system("/bin/cat flag") ידפיס את הדגל בשבילנו.

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

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

אם הכל תקין, הפלט יהיה תוכן הקובץ flag. את הפירוט המלא של ההרצה, כולל אימות באמצעות GDB שכל מספר נקרא כמו שציפינו, נעשה בתרגול ובפתרון.

---

סיכום

בהרצאה הזו למדנו:

• מספרים שלמים במחשב הם בעלי רוחב סופי, ומיוצגים במשלים לשתיים כשהם מסומנים. אותו דפוס ביטים יכול להתפרש כחיובי גדול או כשלילי.
• גלישת מספר שלם - integer overflow גורמת לערך לחזור סביב 2^n. עבור לא מסומן זו התנהגות מוגדרת (מודולו), עבור מסומן זו התנהגות לא מוגדרת. הoverflow היא לעיתים קרובות הצעד הראשון לbuffer overflow או הקצאה שגויה.
• בלבול סימניות בהשוואות ובהמרות (ובמיוחד הרחבת סימן) הוא מקור עשיר לבאגים כשמפרשים בתים כמספרים.
• פונקציית גיבוב ממפה קלט לחתימה קצרה. גיבוב חלש, כמו סכום פשוט, מאפשר לזייף התנגשות - collision בקלות.
• מעבדי x86 הם little-endian: הבית הראשון בזיכרון הוא הבית הנמוך של המספר. הפונקציות p32/p64 ו-struct.pack('<I', ...) מבצעות את ההמרה בשבילנו.
• באתגר collision פירקנו את היעד 0x21DD09EC לחמישה מספרים (ארבעה של 0x06C5CEC8 ואחד של 0x06C5CECC), הפכנו אותם לבתים little-endian, והזרמנו אותם דרך argv בלי אף בית null.