1.5 סקריפטינג של אתגרים הרצאה

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

למה בכלל צריך אוטומציה - השעון מתקתק

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

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

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

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

מודל האינטראקציה מול שרת - pwntools remote

כשמתחברים לשרת רשת, יש שני זרמי בתים: מה שהשרת שולח אלינו, ומה שאנחנו שולחים אליו. הכלי המרכזי הוא remote:

from pwn import *

io = remote('pwnable.kr', 9007)   # opens a TCP connection to host:port

האובייקט io הוא מה ש-pwntools קוראת לו tube - צינור דו-כיווני. הנה הפעולות שנשתמש בהן כל הזמן:

io.recvline()            # reads bytes up to the next newline (inclusive), and returns them
io.recvuntil(b'N=')      # reads bytes until the requested sequence appears (inclusive)
io.recv(1024)            # reads up to 1024 bytes from what has already arrived
io.sendline(b'0 1 2')    # sends the bytes and appends a newline at the end
io.send(b'hi')           # sends without a newline
io.interactive()         # hands control to you - good for getting a shell or seeing the flag

שימו לב לנקודה שמבלבלת מתחילים: כל מה שנכנס ויוצא הוא בתים (bytes), לא מחרוזות. לכן כותבים b'...' ולא '...'. אם תשלחו מחרוזת רגילה, גרסאות מסוימות של pwntools יתלוננו. כשצריך להמיר מספר לפלט, עושים str(x).encode().

מבחינה ויזואלית, הריקוד בינינו לשרת נראה כך:

        us (the script)                     the server
   +------------------------+        +------------------------+
   | recvuntil(b'ready?')   | <----- | ...banner... ready?    |
   | sendline(b'')          | -----> | (waiting for enter)    |
   | recvline()  -> "N=45"  | <----- | N=45 C=6               |
   | sendline(b'0 1 2 ...') | -----> | (weighing the coins)   |
   | recvline()  -> "39"    | <----- | 39                     |
   |        ... weighings ...|        |                        |
   | sendline(b'12')        | -----> | (checking the answer)  |
   +------------------------+        +------------------------+

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

פרסור פלט של שרת - recvuntil ו-parsing

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

נניח שהשרת שלח שורה כזו:

N=45 C=6

איך נחלץ מתוכה את שני המספרים? יש כמה דרכים, וכולן לגיטימיות:

line = io.recvline()                  # b'N=45 C=6\n'

# way 1: split by spaces and by equals sign
parts = line.split()                  # [b'N=45', b'C=6']
N = int(parts[0].split(b'=')[1])      # 45
C = int(parts[1].split(b'=')[1])      # 6

# way 2: regular expression - more resilient to surrounding noise
import re
m = re.search(rb'N=(\d+)\s+C=(\d+)', line)
N, C = int(m.group(1)), int(m.group(2))

הביטוי הרגולרי עדיף כשלא בטוחים בדיוק איך נראית השורה, כי הוא מדלג על רווחים, טאבים ותווים מסביב. שימו לב ל-rb'...': זה גם raw string (בשביל ה-backslash של \d) וגם bytes (כי אנחנו עובדים על בתים).

כמה מוקשים שכדאי להכיר:

• הפונקציה int(b' 12 \n') תיכשל אם נשאיר רעש. תמיד .strip() לפני int, או תנו ל-regex לתפוס רק את הספרות.
• הפונקציה recvline מחזירה גם את ה-newline בסוף. int() יודע להתעלם מרווחים בקצוות אחרי strip, אבל אל תסמכו על זה בלי לבדוק.
• אם השרת שולח מספר בלי newline בסוף (למשל עם prompt כמו >), recvline ייתקע ויחכה לנצח. במקרה כזה recvuntil(b'> ') הוא הפתרון.

הכלל: כשמשהו נתקע, הדבר הראשון לבדוק הוא מה בדיוק השרת שולח. מפעילים context.log_level = 'debug' וה-pwntools תדפיס כל בית שנכנס ויוצא, בצבע. זה מציל שעות.

חיפוש בינארי על מטבעות - binary search

עכשיו ללב של coin1. יש N מטבעות באינדקסים 0..N-1. מטבע אמיתי שוקל 10, המזויף שוקל 9. אנחנו יכולים לבחור טווח של מטבעות, לשלוח לשרת את האינדקסים, והוא יחזיר לנו את סכום המשקל של הטווח. איך זה עוזר?

הנה התובנה: אם שקלנו k מטבעות והסכום הוא בדיוק 10*k, כל המטבעות בטווח אמיתיים - המזויף בחוץ. אם הסכום הוא 10*k - 1, המזויף חבוי איפשהו בתוך הטווח. כלומר שקילה אחת מחלקת את המרחב לשניים: "המזויף כאן" או "המזויף לא כאן". זה בדיוק חיפוש בינארי.

אם נשקול כל פעם את החצי התחתון של טווח החשד, נחתוך את מספר המועמדים בחצי בכל שקילה. לכן מספר השקילות הדרוש הוא רק ceil(log2(N)). עבור 400 מטבעות זה 9 שקילות בלבד. הנה ההצטמצמות בתמונה, לדוגמה עם N=8 והמזויף באינדקס 5:

suspect range         weigh           result
[0..7]  ????????      {0,1,2,3}       sum=40 (all real) -> fake in the upper half
[4..7]  ....????      {4,5}           sum=19 (short by 1) -> fake in the lower half
[4..5]  ....??..      {4}             sum=10 (real) -> fake in the other half
[5..5]  .....!..      -               one coin left -> answer: 5

בקוד, נחזיק טווח סגור [lo, hi] ונצמצם אותו:

lo, hi = 0, N - 1
while lo < hi:
    mid = (lo + hi) // 2
    coins = ' '.join(str(i) for i in range(lo, mid + 1))   # weigh lo..mid
    io.sendline(coins.encode())
    weight = int(io.recvline().strip())
    if weight == (mid - lo + 1) * 10:      # all real -> fake is above mid
        lo = mid + 1
    else:                                  # there's a fake in the range we weighed
        hi = mid
# at the end of the loop lo == hi, and that's the fake index
answer = lo

שווה לעצור על ההשוואה weight == (mid - lo + 1) * 10. מספר המטבעות בטווח [lo, mid] הוא mid - lo + 1. אם כולם אמיתיים המשקל הצפוי הוא בדיוק פי 10 מזה. כל סטייה כלפי מטה מסגירה שהמזויף בפנים. לא צריך לדעת בכמה בדיוק - עצם זה שהמשקל אינו כפולה מלאה של 10 מספיק (weight % 10 != 0), וזו דרך חלופית וקצת עמידה יותר לכתוב את התנאי.

מבנה של סבב ולולאת סבבים

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

יש כאן פרט חשוב שקל לפספס: כמה שקילות מותר בסבב. השרת נותן לכם C הזדמנויות שקילה, ואז מצפה לתשובה (אינדקס בודד). C נבחר בדיוק כך שיספיק לחיפוש בינארי, כלומר C = ceil(log2(N)). חיפוש בינארי תקין ישתמש בדיוק במספר הזה של שקילות במקרה הגרוע - אבל לפעמים הטווח מצטמצם למטבע אחד עוד לפני שניצלנו את כל C השקילות (קורה כש-N אינו חזקה של 2). אם זה קורה, השרת עדיין מחכה לעוד שקילות לפני שיקבל תשובה, ואנחנו חייבים "לצרוך" אותן.

הפתרון פשוט: אם כבר מצאנו את המטבע (lo == hi) אבל נשארו שקילות בתקציב, שוקלים את אותו מטבע בודד עוד פעם (שקילה חוקית לגמרי) ומתעלמים מהתשובה, עד שהשלמנו את כל C השקילות. רק אז שולחים את התשובה:

lo, hi = 0, N - 1
for _ in range(C):
    if lo == hi:                        # already know - waste a valid weighing
        io.sendline(str(lo).encode())
        io.recvline()                   # consume the weight and ignore it
        continue
    mid = (lo + hi) // 2
    coins = ' '.join(str(i) for i in range(lo, mid + 1))
    io.sendline(coins.encode())
    weight = int(io.recvline().strip())
    if weight == (mid - lo + 1) * 10:
        lo = mid + 1
    else:
        hi = mid
io.sendline(str(lo).encode())           # the answer: the fake index

השילוב הזה - בדיוק C שקילות ואז תשובה אחת - שומר על סנכרון מושלם מול שרת שסופר שקילות. אם תריצו את השרת האמיתי ותראו שהוא דווקא מקבל את התשובה מתי שבא לכם, תוכלו לוותר על הpadding ולשלוח את התשובה ברגע ש-lo == hi. בגלל שלא תמיד יודעים מראש איזו מוסכמה השרת נוקט, הדרך הבטוחה היא לפתוח כל סבב בעוגן ברור, למשל recvuntil(b'N='), כדי להסתנכרן מחדש בתחילת כל סבב גם אם נשארו בתים תלויים מהסבב הקודם.

מרוץ מול השעון - לעמוד בזמן

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

• הורידו את רמת הלוג. ברירת המחדל של pwntools מדפיסה הרבה, וההדפסה איטית. הגדירו context.log_level = 'error' כדי לחתוך רעש וזמן.
• מזעור סבבי הלוך-ושוב. כל שקילה היא הלוך ושוב לשרת, ולטנצ'י הרשת מצטבר. חיפוש בינארי כבר עושה את המינימום ההכרחי (log2(N)), אז אל תוסיפו שקילות מיותרות. אל תשקלו טווח אחד מטבע-מטבע כשאפשר לשקול אותו בבת אחת.
• אל תדפיסו בכל איטרציה. הדפסה לטרמינל בתוך לולאה חמה מאטה. אם בא לכם מד התקדמות, הדפיסו פעם ב-10 סבבים.
• timeout מפורש בקריאות. אם משהו משתבש, אתם לא רוצים שהסקריפט ייתקע לנצח. אפשר לקרוא עם io.recvline(timeout=2) ולטפל במקרה שאין תשובה.
• חשבו מקומית, דברו מעט. כל החישוב (בינארי, פרסור) הוא זול. מה שיקר זו הרשת. תכננו את הקוד כך שכל בית שנשלח הוא הכרחי.

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

שלד בוט מלא - pwntools

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

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

context.log_level = 'error'          # less noise, less wasted time

HOST, PORT = 'pwnable.kr', 9007      # for the real coin1; for the local demo: '127.0.0.1', 9007
io = remote(HOST, PORT)

io.recvuntil(b'ready?')              # consume the entire banner to the end
io.recvline()                        # the rest of the prompt line
io.sendline(b'')                     # press enter to start

while True:
    line = io.recvline()
    m = re.search(rb'N=(\d+)\s+C=(\d+)', line)
    if not m:                        # a line that isn't "N=.. C=.." - probably the end of the game
        text = line.decode(errors='ignore')
        print(text, end='')
        if 'flag' in text or 'Congr' in text or 'Wrong' in text:
            break
        continue

    N, C = int(m.group(1)), int(m.group(2))
    lo, hi = 0, N - 1
    for _ in range(C):
        if lo == hi:                          # already found - a valid weighing to consume C
            io.sendline(str(lo).encode())
            io.recvline()
            continue
        mid = (lo + hi) // 2
        coins = ' '.join(str(i) for i in range(lo, mid + 1))
        io.sendline(coins.encode())
        weight = int(io.recvline().strip())
        if weight == (mid - lo + 1) * 10:     # all real -> fake is in the upper half
            lo = mid + 1
        else:                                 # fake is in the range we weighed
            hi = mid
    io.sendline(str(lo).encode())             # send the answer

הבוט הזה ממצה את כל מה שלמדנו: recvuntil לסנכרון על הבאנר, regex לפרסור N ו-C, חיפוש בינארי עם padding לצריכת השקילות, ולולאה שממשיכה עד שמופיע הדגל. שימו לב שאנחנו לא מניחים כמה סבבים יש - אנחנו ממשיכים עד שהשרת מפסיק לשלוח שורות N=...

שרת אימון מקומי - להתאמן בלי הרשת

לפני שיורים על השרת האמיתי, כדאי מאוד להתאמן מקומית. גם כדי לא לבזבז ניסיונות, וגם כי דיבוג מול שרת מרוחק עם שעון עצר זה סיוט. הנה שרת דמו קצר שמדמה את החוקים של coin1 בדיוק (מטבע אמיתי 10, מזויף 9, שוקלים טווחים, C שקילות ואז תשובה). מריצים אותו בטרמינל אחד, ומכוונים את הבוט ל-127.0.0.1 בטרמינל שני:

#!/usr/bin/env python3
# coin_server.py - local training server that simulates coin1
import socket, random, math

HOST, PORT = '127.0.0.1', 9007
ROUNDS = 100

def recv_line(conn, state):
    while b'\n' not in state['buf']:
        chunk = conn.recv(4096)
        if not chunk:
            raise ConnectionError('client closed')
        state['buf'] += chunk
    line, _, state['buf'] = state['buf'].partition(b'\n')
    return line

def play(conn):
    state = {'buf': b''}
    conn.sendall(b"--- Shall we play a game? ---\n")
    conn.sendall(b"Real coins weigh 10, the single fake coin weighs 9.\n")
    conn.sendall(b"Are you ready? hit enter!\n")
    recv_line(conn, state)                        # the enter from the client
    for _ in range(ROUNDS):
        N = random.randint(16, 400)
        C = math.ceil(math.log2(N))
        fake = random.randrange(N)
        conn.sendall(f"N={N} C={C}\n".encode())
        for _ in range(C):                        # exactly C weighings
            line = recv_line(conn, state).strip()
            idxs = [int(x) for x in line.split()]
            weight = sum(9 if i == fake else 10 for i in idxs)
            conn.sendall(f"{weight}\n".encode())
        answer = int(recv_line(conn, state).strip())
        if answer != fake:
            conn.sendall(b"Wrong! Game over.\n")
            return
    conn.sendall(b"Congrats! flag{DEMO_all_rounds_cleared}\n")

def main():
    srv = socket.socket()
    srv.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    srv.bind((HOST, PORT))
    srv.listen(4)
    print(f"[*] demo coin server on {HOST}:{PORT}")
    while True:
        conn, _ = srv.accept()
        try:
            play(conn)
        except Exception as exc:
            print('[!]', exc)
        finally:
            conn.close()

if __name__ == '__main__':
    main()

מול השרת הזה הבוט שלמעלה עובר את כל 100 הסבבים ומקבל flag{DEMO_all_rounds_cleared} בפחות משנייה. ברגע שזה עובד מקומית, ההעברה לשרת האמיתי היא רק שינוי של HOST ו-PORT.

סיכום

• אתגרי סבבים תחת שעון לא ניתנים לפתרון ביד - צריך סקריפט שמדבר עם השרת בשבילנו.
• המודל הוא צינור דו-כיווני: remote(host, port), ואז recvline / recvuntil לקריאה ו-sendline לכתיבה. הכל בבתים.
• פרסור נעשה עם split פשוט או עם regex על bytes (rb'N=(\d+)\s+C=(\d+)'), תמיד עם strip לפני int.
• חיפוש בינארי מוצא את המטבע המזויף ב-ceil(log2(N)) שקילות: כל שקילה מחלקת את מרחב החשד לשניים לפי הסכום הצפוי 10*k.
• ניהול סבב דורש לצרוך בדיוק C שקילות לפני שליחת התשובה - מרפדים בשקילה חוקית אם סיימנו מוקדם, ומסנכרנים כל סבב עם עוגן כמו recvuntil(b'N=').
• מרוץ הזמן נמדד: log_level='error', מינימום סבבי רשת, בלי הדפסות בלולאה החמה.
• מתאמנים מקומית מול שרת דמו לפני שיורים על היעד האמיתי.

בתרגול נחבר את הכל ונפתור את coin1 מקצה לקצה.