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

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

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

---

אקראיות אמיתית לעומת פסאודו - PRNG vs TRNG

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

אקראיות אמיתית - True Random. מקורות פיזיים כמו רעש תרמי, זמני הגעה של פרוטוני קרינה, או ג'יטר בין קריאות חומרה. הפלט באמת בלתי צפוי כי הוא נובע מתופעה פיזיקלית. במחשב מודרני הkernel אוסף "אנטרופיה" ממקורות כאלה ומגיש אותה דרך /dev/urandom ו-getrandom().

אקראיות פסאודו - Pseudo Random. מחולל PRNG הוא פונקציה מתמטית טהורה. יש לו מצב פנימי - state - והוא מייצר את המספר הבא מתוך המצב הנוכחי, ואז מעדכן את המצב. אין כאן שום דבר פיזי. זו נוסחה, וכמו כל נוסחה, בהינתן אותה כניסה היא נותנת אותה יציאה.

PRNG generator - deterministic state machine

  seed
    |
    v
[ state_0 ] --f--> [ state_1 ] --f--> [ state_2 ] --f--> ...
    |                  |                  |
    v                  v                  v
  out_0              out_1              out_2

same seed  ==  same sequence out_0, out_1, out_2, ...  exactly, every time

הפונקציה rand() מספריית C היא PRNG קלאסי. היא לא נועדה לאבטחה בכלל - היא נועדה למשחקים, סימולציות, ובחירת מספר "אקראי" לתצוגה. מי שמשתמש בה כדי לייצר סוד או מפתח - טועה, וזו בדיוק הטעות שנתקוף.

הזרעה - seeding

המצב הפנימי הראשוני של המחולל נקרא seed (זרע). כל הסדרה נגזרת ממנו. שינוי ה-seed משנה את כל הסדרה. אותו seed מחזיר אותה סדרה.

בשפת C זה נראה כך:

#include <stdio.h>
#include <stdlib.h>

int main() {
    srand(1234);          // set the seed
    printf("%d\n", rand()); // the first number in the sequence for seed 1234
    printf("%d\n", rand()); // the second number
    return 0;
}

הפונקציה srand(seed) קובעת את המצב ההתחלתי, ו-rand() שולפת את המספר הבא בסדרה ומקדמת את המצב. תריצו את זה פעמיים - תקבלו בדיוק את אותם שני מספרים. זו לא תקלה, זו ההגדרה.

עכשיו הנה הנקודה הקריטית: מה קורה אם קוראים ל-rand() בלי לקרוא ל-srand() קודם?

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

srand() called?   |   what happens
-------------------+-------------------------------------------
yes, srand(t)      |  the sequence depends on t. If t changes, the sequence changes
not called at all  |  equivalent to srand(1). Fixed sequence, always the same

הקבוע המפורסם של glibc - the first rand() value

בגלל שהזרע הדיפולטי הוא 1, המספר הראשון ש-rand() מחזיר ב-glibc הוא תמיד אותו ערך. הערך הזה מפורסם עד כדי כך שכל מי שעוסק ב-pwn מכיר אותו בעל פה:

first rand() with the default seed (glibc):

  decimal:  1804289383
  hex:      0x6b8b4567

מאיפה זה בא? ה-rand() של glibc משתמש במחולל additive feedback מסוג TYPE_3. המצב הראשוני של הזרע 1 מוליד את הסדרה 1804289383, 846930886, 1681692777 וכן הלאה. אנחנו לא צריכים להבין את הפנימיות - מספיק לנו לדעת שהמספר הראשון קבוע וידוע.

שימו לב שהערך קטן מ-0x7fffffff - וזה הגיוני, כי RAND_MAX ב-glibc הוא 0x7fffffff, כלומר rand() מחזיר תמיד מספר 31 ביט (הביט העליון תמיד אפס). זו עובדה שנצטרך אותה עוד מעט.

איך מוודאים את הקבוע בעצמנו, בלי לסמוך על הזיכרון? שתי דרכים.

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

#include <stdio.h>
#include <stdlib.h>

int main() {
    printf("%u\n", rand());   // without srand at all
    return 0;
}

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

דרך שנייה, בלי לקמפל בכלל, ישר מהמעטפת:

$ python3 -c "print(1804289383, hex(1804289383))"
1804289383 0x6b8b4567

ואם אנחנו רוצים לראות את זה קורה בתוך בינארי אמיתי, נעצור ב-GDB אחרי הקריאה ל-rand ונקרא את הערך המוחזר מ-eax:

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

אתגר random ב-pwnable.kr

עכשיו יש לנו את כל מה שצריך כדי לשבור אתגר אמיתי. המקור של האתגר random נראה כך:

#include <stdio.h>

int main() {
    unsigned int random;
    random = rand();   // "random" value

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

התוכנית מזמינה אותנו לנחש. היא לוקחת מספר "אקראי", מבצעת XOR בינו לבין הקלט שלנו, ומצפה לקבל 0xdeadbeef. ההודעה במקרה כישלון אפילו לועגת לנו: "אולי כדאי לנסות 2 בחזקת 32 מקרים". כלומר, אם random באמת היה אקראי, היינו צריכים לעבור על כל ארבעה מיליארד הערכים האפשריים.

אבל שימו לב מה חסר בקוד: אין שום קריאה ל-srand(). וזה אומר ש-random הוא לא באמת אקראי - הוא הקבוע שאנחנו כבר מכירים:

random = rand() = 0x6b8b4567    (always, because there's no srand)

עכשיו זו כבר לא בעיית ניחוש, זו משוואה של כיתה ז'. אנחנו רוצים למצוא key כך ש:

key XOR 0x6b8b4567 == 0xdeadbeef

התכונה היפה של XOR היא שהוא הופכי לעצמו. אם a XOR b == c, אז a == c XOR b. לכן:

key = 0xdeadbeef XOR 0x6b8b4567

בואו נחשב את זה בית-בית:

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

הקלט שאנחנו צריכים לשלוח הוא 3039230856. זהו. אין ברוט-פורס, אין ניחוש - חישוב אחד.

שימו לב לפרט של scanf

התוכנית קוראת עם scanf("%d", &key), כלומר קריאה של מספר מסומן. אבל הערך שלנו, 0xb526fb88, הוא בעל ביט 31 דלוק, כלומר כמספר מסומן הוא שלילי (בערך מינוס 1.25 מיליארד). למה זה עדיין עובד? כי מה שחשוב הוא תבנית הביטים שנשמרת במשתנה key בן ארבעת הבתים. scanf מאכלס את ארבעת הבתים בערך 0xb526fb88, וה-XOR פועל על הביטים, לא על הפרשנות המספרית. לכן שליחת המספר העשרוני 3039230856 מייצרת בדיוק את תבנית הביטים הרצויה, וה-XOR מחזיר 0xdeadbeef.

בפועל אפשר לפתור את האתגר בשורה אחת:

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

או בעזרת הספרייה pwntools, שנשתמש בה לאורך כל הקורס:

from pwn import *

# random is solved over SSH: connect and run the binary on the server
s = ssh(host='pwnable.kr', port=2222, user='random', password='guest')
p = s.process('./random')

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

הזרעה מבוססת זמן - time-based seed

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

srand(time(NULL));
int secret = rand() % 1000000;

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

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

seed space:

  true randomness:   2^32 possibilities   (~4.3 billion)
  srand(time(0)):    ~window of 5 seconds   (5 possibilities!)

  the difference is between "impossible" and "instant".

הנה תבנית ברוט-פורס ב-Python שקוראת ישירות ל-rand של libc דרך ctypes, כדי שהחיזוי יהיה זהה בית-בית להתנהגות התוכנית ב-C:

import ctypes, time

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

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

now = int(time.time())
for seed in range(now - 2, now + 3):   # small window around now
    guess = predict(seed)
    print(f"seed={seed} -> guess={guess}")
    # here you'd send guess to the program and check if it was accepted

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

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

הדרך הנכונה - CSPRNG

אם צריך אקראיות לצורך אבטחה - מפתח, אסימון, nonce, סיסמה - חייבים מחולל קריפטוגרפי, מסוג CSPRNG (Cryptographically Secure PRNG). ההבדל: גם מי שראה חלק מהפלט לא יכול לחזות את ההמשך או לשחזר את המצב הפנימי, והמחולל מוזרע מאנטרופיה אמיתית של הkernel.

not for security   |  for security
-------------------+---------------------------------
rand() / random()  |  getrandom(2)
srand(time(0))     |  read from /dev/urandom
plain mt19937      |  arc4random() (on BSD/macOS)
                   |  RAND_bytes() (OpenSSL)

#include <sys/random.h>

unsigned char key[32];
getrandom(key, sizeof(key), 0);   // 32 truly random bytes

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

סיכום

• מחולל PRNG כמו rand() הוא נוסחה דטרמיניסטית: אותו זרע נותן תמיד אותה סדרה.
• קריאה ל-rand() בלי srand() שקולה ל-srand(1) - זרע דיפולטי קבוע, ולכן סדרה קבועה זהה בכל הרצה.
• ה-rand() הראשון ב-glibc בזרע דיפולטי הוא תמיד 0x6b8b4567 (עשרוני 1804289383). מוודאים בתוכנית C בת שורה, או ב-GDB דרך eax.
• אתגר random ב-pwnable.kr מבצע key XOR rand() == 0xdeadbeef בלי srand, ולכן הקלט הנכון הוא 0xdeadbeef XOR 0x6b8b4567 = 0xb526fb88 = 3039230856.
• הזרעה עם srand(time(NULL)) נשברת בברוט-פורס של חלון זמן קטן, כי הזמן הנוכחי אינו סוד.
• לאבטחה משתמשים ב-CSPRNG בלבד: getrandom(), /dev/urandom, arc4random(), RAND_bytes().