8.4 יישור זיכרון ו SSE פתרון

פתרון - alignment זיכרון ו-SSE

נפתור את אתגר memcpy מקצה לקצה. הרעיון המרכזי חוזר על עצמו לאורך כל התרגילים: לולאת ה-SSE ב-fast_memcpy משתמשת ב-movdqa ו-movntdq שדורשות alignment ל-16 בתים, אבל dest מגיע מ-malloc במערכת 32 ביט ולכן איננו מיושר ל-16. הפתרון הוא לבחור גדלים שלעולם לא מכניסים אותנו ללולאה המסוכנת הזו, כך שכל הסיבובים עוברים והדגל מודפס.

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

// memcpy_demo.c  ->  gcc -m32 -O0 -o memcpy_demo memcpy_demo.c -lm
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/mman.h>

char* slow_memcpy(char* dest, const char* src, size_t len) {
    for (size_t i = 0; i < len; i++) dest[i] = src[i];
    return dest;
}

char* fast_memcpy(char* dest, const char* src, size_t len) {
    if (len >= 64) {
        size_t i = len & ~(size_t)63;
        __asm__ volatile (
            "1:\n\t"
            "sub $0x40, %%ecx\n\t"
            "movdqa 0x00(%%esi,%%ecx,1), %%xmm0\n\t"
            "movdqa 0x10(%%esi,%%ecx,1), %%xmm1\n\t"
            "movdqa 0x20(%%esi,%%ecx,1), %%xmm2\n\t"
            "movdqa 0x30(%%esi,%%ecx,1), %%xmm3\n\t"
            "movntdq %%xmm0, 0x00(%%edi,%%ecx,1)\n\t"
            "movntdq %%xmm1, 0x10(%%edi,%%ecx,1)\n\t"
            "movntdq %%xmm2, 0x20(%%edi,%%ecx,1)\n\t"
            "movntdq %%xmm3, 0x30(%%edi,%%ecx,1)\n\t"
            "jne 1b\n\t"
            :: "S"(src), "D"(dest), "c"(i)
            : "xmm0","xmm1","xmm2","xmm3","memory");
        dest += i; src += i; len &= 63;
    }
    return slow_memcpy(dest, src, len);
}

int main() {
    setvbuf(stdout, 0, 2, 0);
    int order = 2;
    while (order != 22) {
        int alloc_size = (int)pow(2, order);
        char *dest = malloc(alloc_size);
        char *src  = mmap(0, 0x1000, PROT_READ|PROT_WRITE,
                          MAP_ANONYMOUS|MAP_PRIVATE, -1, 0);
        size_t sizes;
        printf("Order %d! : ", order);
        if (scanf("%zu", &sizes) != 1) return 1;
        fast_memcpy(dest, src, sizes);
        order++;
    }
    printf("Well done! you are ready to code the assignment :)\n");
    system("/bin/echo THIS_IS_THE_FLAG{alignment_matters}");  // simulates cat flag
    return 0;
}

---

פתרון תרגיל 1 - לשחזר את הקריסה התמימה

נזין את alloc_size עצמו בכל סיבוב. הסיבובים הראשונים עוברים כי הגדלים קטנים מ-64:

Order 2! : 4      order=2 -> alloc_size=4,  len=4  < 64  -> slow_memcpy, OK
Order 3! : 8      order=3 -> 8   < 64 -> OK
Order 4! : 16     order=4 -> 16  < 64 -> OK
Order 5! : 32     order=5 -> 32  < 64 -> OK
Order 6! : 64     order=6 -> 64  >= 64 -> SSE loop -> crash!

הקריסה קורה בדיוק ב-order == 6, כי שם alloc_size מגיע ל-64 והתנאי len >= 64 מתקיים בפעם הראשונה. נאשר תחת pwndbg:

pwndbg> run
Order 2! : 4
...
Order 6! : 64
Program received signal SIGSEGV, Segmentation fault.
=> 0x...  movntdq xmmword ptr [edi+ecx*1], xmm0
pwndbg> p/x $edi & 0xf
$1 = 0x8

ההוראה שגרמה לחריגה היא movntdq (הכתיבה), והכתובת ב-edi (שהוא dest) היא 8 מודולו 16. movntdq דורשת alignment ל-16, dest מיושר רק ל-8, ולכן SIGSEGV.

למה זה עבד: זיהינו את ההוראה המדויקת ואת הסיבה. זו לא overflow ולא מצביע פגום - זו הוראת SSE שדורשת alignment שקיבלה כתובת לא מיושרת. תמיד כשנופלים על movdqa/movaps/movntdq, הדבר הראשון לבדוק הוא reg & 0xf.

---

פתרון תרגיל 2 - למדוד את הalignment של dest

נוסיף את הדפסת הבדיקה ונריץ:

order=2 dest=0x...a8 dest%16=8
order=3 dest=0x...b8 dest%16=8
order=4 dest=0x...c8 dest%16=8
order=5 dest=0x...e8 dest%16=8
order=6 dest=0x...18 dest%16=8
...

השארית היא תמיד 8. ההסבר: במערכת 32 ביט MALLOC_ALIGNMENT שווה 2 * SIZE_SZ = 2 * 4 = 8. המצביע שאנחנו מקבלים מ-malloc יושב 8 בתים אחרי בסיס הנתח (אחרי prev_size ו-size), והנתחים עצמם מיושרים ל-16 - לכן המצביע יוצא 8 מודולו 16, שוב ושוב. לעולם לא נקבל מ-malloc הרגילה כתובת מיושרת ל-16 כאן, ולכן movdqa/movntdq על הbuffer הזה תמיד יקרסו.

לעומת זאת src מגיע מ-mmap, שמחזיר כתובת מיושרת לדף שלם (4096 בתים). דף שלם מיושר גם ל-16, ולכן src תמיד תקין. כלומר הצד הקורא בסדר, והצד הכותב (dest) הוא הבעיה.

למה זה עבד: הוכחנו שהalignment הבעייתי הוא מבני ולא מקרי - הוא נובע ישירות מ-MALLOC_ALIGNMENT של 8 בתים ב-32 ביט. מכאן ברור שאין דרך לגרום ל-movdqa לעבוד על buffer malloc רגיל, ולכן נצטרך פשוט להימנע ממנו.

---

פתרון תרגיל 3 - למצוא גדלים בטוחים

התנאי שמפעיל את הלולאה המסוכנת הוא len >= 64. אם נשלח בכל סיבוב גודל קטן מ-64, נדלג על כל בלוק ה-SSE ונרד ישר ל-slow_memcpy שמעתיקה בית-בית בלי שום דרישת alignment. אין בקוד שום free, ואין בדיקה שהגודל תואם ל-alloc_size, ולכן גם אם נעתיק כמה בתים מעבר לbuffer קטן - אין קריסה, כי אין מבנה heap שמשתחרר או נבדק אחר כך.

הנוסחה הבטוחה: בכל סיבוב שולחים את המינימום בין alloc_size לבין ערך קבוע שקטן מ-64. נבחר את המינימום עם 63:

size(order) = min(2^order, 63)

order 2 -> 4     order 3 -> 8     order 4 -> 16    order 5 -> 32
order 6 -> 63    order 7 -> 63    ...    order 21 -> 63

לגדלים הקטנים (order 2 עד 5) הגודל תמיד קטן מ-64 בלאו הכי, ולגדלים הגדולים אנחנו חוסמים ב-63. בשום סיבוב לא נכנסים ללולאת ה-SSE, אף movdqa/movntdq לא מורצת, ולכן הalignment של dest כבר לא מעניין אף אחד. כל 20 הסיבובים עוברים, order מגיע ל-22, והדגל מודפס.

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

---

פתרון תרגיל 4 - כתיבת פותרן אוטומטי

הנה פותרן מלא ב-pwntools. הוא רץ על שני המסלולים - דמו מקומי או חיבור מרוחק - ומדפיס את הדגל בסוף.

#!/usr/bin/env python3
from pwn import *

context.log_level = 'info'

# during development: local demo. During the real run: connect per the challenge page.
LOCAL = True
if LOCAL:
    io = process(['./memcpy_demo'])
else:
    io = remote('pwnable.kr', 9022)   # replace per the connection line on the challenge page

def safe_size(order):
    return min(2 ** order, 63)        # always below the threshold of 64

for order in range(2, 22):            # order from 2 to 21, exactly 20 rounds
    io.recvuntil(b': ')               # the prompt "Order N! : "
    size = safe_size(order)
    io.sendline(str(size).encode())
    log.info('order %2d -> size %d' % (order, size))

io.recvuntil(b'Well done')
print(io.recvall(timeout=3).decode(errors='replace'))

הרצה:

$ python3 solve.py
[+] Starting local process './memcpy_demo': pid ...
[*] order  2 -> size 4
[*] order  3 -> size 8
...
[*] order 21 -> size 63
 you are ready to code the assignment :)
THIS_IS_THE_FLAG{alignment_matters}

בשרת האמיתי, במקום השורה המדומה, system("/bin/cat flag") ידפיס את הדגל האמיתי. שימו לב שהפותרן לא תלוי בכתובות, ב-ASLR או בהגנות אחרות - זו לא חולשת זיכרון קלאסית אלא אתגר הבנה של alignment ו-SSE, ולכן אין כאן leaks או ROP. כל מה שצריך הוא לבחור נכון את הגדלים.

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

---

פתרון תרגיל 5 (העשרה) - הדרך ה"נכונה" להריץ movdqa

בתרגילים הקודמים ברחנו מ-SSE. עכשיו נגרום לו לעבוד. יש שתי דרכים, וכל אחת מלמדת משהו.

הדרך הראשונה, לתקן את הalignment של dest. מחליפים במקור את malloc בהקצאה מיושרת:

// instead of: char *dest = malloc(alloc_size);
char *dest;
posix_memalign((void**)&dest, 16, alloc_size);   // guaranteed aligned to 16

עכשיו dest מיושר ל-16 בתים בדיוק כמו src, ולכן אפשר להזין גם גדלים גדולים מ-64 ולולאת ה-SSE תרוץ בלי לקרוס. אפשר לוודא שהשארית מודולו 16 היא 0.

הדרך השנייה, להוריד את דרישת הalignment מההוראה. משאירים את malloc ומחליפים בלולאה:

movdqa  ->  movdqu     (unaligned read)
movntdq ->  movdqu     (unaligned write - there is no non-temporal version without alignment)

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

למה זה עבד: שתי הדרכים מיישבות את אותה סתירה - הוראה שדורשת alignment מול buffer שלא מיושר. או שמיישרים את הbuffer (posix_memalign) או שמרפים מדרישת הalignment (movdqu). זו בדיוק ההבחנה מההרצאה בין הקצאה רגילה להקצאה מיושרת, ובין ההוראות המיושרות ללא-מיושרות.