1.3 אקראיות צפויה פתרון

פתרון - אקראיות צפויה

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

פתרון תרגיל 1 - למה זה שביר

המקור של האתגר:

#include <stdio.h>

int main() {
    unsigned int random;
    random = rand();

    unsigned int key = 0;
    scanf("%d", &key);

    if ((key ^ random) == 0xdeadbeef) {
        printf("Good!\n");
        system("/bin/cat flag");
        return 0;
    }

    printf("Wrong, maybe you should try 2^32 cases.\n");
    return 0;
}

תשובות:

1. משווים את key ^ random ל-0xdeadbeef. הערך random מגיע מ-rand().
2. אין שום קריאה ל-srand בקוד. זה הבאג.
3. בגלל שאין srand, ההתנהגות זהה ל-srand(1): זרע דיפולטי קבוע. לכן random מקבל את אותו ערך בכל הרצה, ובכל הרצה עתידית - זה לא באמת אקראי. ההודעה הלועגת "try 2^32 cases" מניחה ש-random אקראי, אבל הוא לא, אז אין צורך בשום ברוט-פורס.

פתרון תרגיל 2 - הקבוע

דרך ראשונה, תוכנית C:

#include <stdio.h>
#include <stdlib.h>
int main() { printf("%u\n", rand()); return 0; }

$ gcc -o r r.c && ./r
1804289383

דרך שנייה, בתוך הבינארי random עם GDB. קודם מאתרים את ההוראה שאחרי call rand:

pwndbg> disassemble main
   ...
   0x08048649 <+...>:  call   0x8048420 <rand@plt>
   0x0804864e <+...>:  mov    DWORD PTR [ebp-0x8], eax   <-- here eax holds rand()
   ...

עוצרים על ההוראה שאחרי הקריאה וקוראים את הערך המוחזר:

pwndbg> break *main+<offset of the mov after call rand>
pwndbg> run
pwndbg> print/x $eax
$1 = 0x6b8b4567

התוצאה, בשתי הדרכים:

decimal:  1804289383
hex:      0x6b8b4567

הערה: אם האתגר מהודר ל-32 ביט, ערך ההחזרה ב-eax. אם מדובר בבינארי 64 ביט, קוראים $rax (או $eax לחצי התחתון). בשני המקרים הקבוע זהה, כי הוא נקבע על ידי glibc ולא על ידי הארכיטקטורה.

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

הפעולה XOR הופכית לעצמה, אז מהמשוואה key ^ random == 0xdeadbeef נובע:

key = 0xdeadbeef XOR 0x6b8b4567

חישוב בית-בית:

  0xde ^ 0x6b = 0xb5
  0xad ^ 0x8b = 0x26
  0xbe ^ 0x45 = 0xfb
  0xef ^ 0x67 = 0x88
  -----------------------
  key = 0xb526fb88 = 3039230856

דרך 1 - שורת פקודה אחת:

$ python3 -c "print(0xdeadbeef ^ 0x6b8b4567)" | ./random
Good!
FLAG{...}

דרך 2 - pwntools מקומית:

from pwn import *

p = process('./random')
key = 0xdeadbeef ^ 0x6b8b4567     # 3039230856
p.sendline(str(key).encode())
print(p.recvall().decode())

דרך 3 - pwntools מול השרת דרך SSH (כך פותרים את random בשרת האמיתי):

from pwn import *

s = ssh(host='pwnable.kr', port=2222, user='random', password='guest')
p = s.process('./random')
key = 0xdeadbeef ^ 0x6b8b4567
p.sendline(str(key).encode())
print(p.recvall().decode())

בכל הדרכים מקבלים Good! ואז את תוכן הדגל.

למה זה עבד: אין srand, לכן random הוא הקבוע 0x6b8b4567. פתרנו משוואת XOR יחידה במקום לעבור על 2^32 מקרים. לגבי scanf("%d") והערך שגדול מ-INT_MAX: מה שמעניין אותנו זו תבנית הביטים ב-key בת ארבעת הבתים. scanf מאכלס את הבתים בערך 0xb526fb88, וה-XOR פועל על הביטים - לכן שליחת העשרוני 3039230856 נותנת בדיוק את התוצאה 0xdeadbeef.

איך להכליל: בכל פעם שאתם רואים rand() בלי srand(), הפלט ידוע מראש. אותה גישה עובדת גם אם התוכנית קוראת ל-rand() כמה פעמים - פשוט מחשבים את הסדרה המלאה של הזרע הדיפולטי (1804289383, 846930886, 1681692777, ...) ומתאימים לכל שימוש.

פתרון תרגיל 4 - שבירת הזרע לפי זמן

1. מרחב הזרעים. הזרע הוא time(NULL), מספר השניות מאז 1970. התוקף יודע את הזמן הנוכחי, אז מבחינתו מרחב האפשרויות אינו 2^32 אלא חלון קטנטן של כמה שניות סביב רגע ההרצה - בפועל אפשרות אחת עד חמש. זה ההבדל בין בלתי אפשרי למיידי.

2. הסקריפט. אנחנו קוראים ל-srand/rand של libc עצמה דרך ctypes, כדי לקבל בדיוק את אותם מספרים שהתוכנית ב-C תקבל. מחשבים את הזרע לפי הזמן הנוכחי, מנחשים, ואם צריך מרחיבים לחלון קטן:

from pwn import *
import ctypes, time

libc = ctypes.CDLL("libc.so.6")

def predict(seed, mod=1000000):
    libc.srand(seed)
    return libc.rand() % mod

def solve_once():
    p = process('./timelock')
    p.recvuntil(b'Guess my number:')

    # the window: the current second, and one-two seconds each direction to cover delays
    now = int(time.time())
    for seed in (now, now - 1, now + 1, now - 2, now + 2):
        guess = predict(seed)
        log.info(f"trying seed={seed} guess={guess}")
        p.sendline(str(guess).encode())
        out = p.recvall(timeout=1).decode(errors='ignore')
        if 'Correct' in out:
            log.success(out.strip())
            return True
        # if we missed, the process already ended - open a new one for the next attempt
        p = process('./timelock')
        p.recvuntil(b'Guess my number:')
    return False

solve_once()

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

[+] Correct! flag{predictable_time_seed}

1. גרסה מינימלית, כשההרצה מיידית ואין השהיה, הזרע הוא פשוט עכשיו:

import ctypes, time, subprocess

libc = ctypes.CDLL("libc.so.6")
libc.srand(int(time.time()))
guess = libc.rand() % 1000000
print(subprocess.run(['./timelock'], input=f"{guess}\n".encode(),
                     capture_output=True).stdout.decode())

למה זה עבד: time(NULL) הוא לא סוד. שחזרנו את הזרע מהשעון שלנו, ומכיוון ש-rand דטרמיניסטי, שחזרנו איתו את secret בדיוק. החלון הקטן נועד רק לספוג השהיה בין הרגע שהתוכנית הזריעה לרגע שאנחנו חישבנו.

איך להכליל ולהרחיב:

• srand(time(NULL) ^ getpid()). מוסיף אנטרופיה של מזהה תהליך, אבל ב-PID יש בפועל טווח מוגבל (לרוב עד כמה עשרות אלפים). מרחב החיפוש גדל לחלון הזמן כפול טווח ה-PID - עדיין בר-ברוט-פורס, פשוט מוסיפים לולאה פנימית על ה-PID.
• קריאות rand() מרובות לפני בחירת הסוד. לא משנה - מריצים אצלנו את אותה כמות קריאות אחרי srand ומגיעים לאותו מצב פנימי, ואז שולפים את הערך הרלוונטי.
• החלפה ל-getrandom() או קריאה מ-/dev/urandom. כאן הברוט-פורס מת: אין זרע צפוי לשחזר, האנטרופיה מגיעה מהkernel ואינה נגזרת מהשעון. זו הסיבה שלכל שימוש רגיש באבטחה חייבים CSPRNG, לא rand().