1.5 סקריפטינג של אתגרים פתרון
פתרון - סקריפטינג של אתגרים¶
נעבור תרגיל-תרגיל ונבנה בסוף בוט שלם שסוגר את coin1. כל שלב מוסבר, ובסוף יש גם שרת דמו מקומי שאפשר להתאמן מולו בלי שעון עצר.
פתרון תרגיל 1 - להכיר את הפרוטוקול ביד¶
מתחברים:
השרת פותח בבאנר שמסביר את המשחק (מטבעות אמיתיים שוקלים 10, מזויף שוקל 9), מבקש ללחוץ enter, ואז מתחיל לזרוק סבבים. כל סבב נפתח בשורה בסגנון:
המשמעות: יש 45 מטבעות באינדקסים 0..44, ומותרות 6 שקילות לפני ששולחים תשובה. עכשיו שולחים רשימת אינדקסים, למשל:
והשרת מחזיר את סכום המשקל שלהם, למשל 40. איך זה מסגיר את המזויף? ארבעה מטבעות אמיתיים שוקלים 4 * 10 = 40. קיבלנו בדיוק 40, אז המזויף אינו בין 0 עד 3. אילו היינו מקבלים 39, היינו יודעים שהמזויף חבוי בטווח הזה (מטבע אחד שוקל 9 במקום 10).
הכלל שגילינו: סכום של k מטבעות אמיתיים הוא 10*k. כל סטייה כלפי מטה אומרת "המזויף כאן". זו בדיוק שקילה שמחלקת את מרחב החשד לשניים.
וכשמנסים לשחק ביד, מגלים מהר את הבעיה: אחרי כמה סבבים איטיים השרת סוגר את החיבור כי נגמר הזמן. מסקנה: צריך סקריפט.
פתרון תרגיל 2 - להתחבר ולפרסר את N ו-C¶
מתחברים, בולעים את הבאנר עד המילה ready?, שולחים enter, וקוראים את שורת הסבב הראשון:
#!/usr/bin/env python3
from pwn import *
import re
context.log_level = 'info'
io = remote('pwnable.kr', 9007)
io.recvuntil(b'ready?') # consume the entire banner to the end
io.recvline() # the rest of the prompt line
io.sendline(b'') # press enter
line = io.recvline() # b'N=45 C=6\n'
m = re.search(rb'N=(\d+)\s+C=(\d+)', line)
N, C = int(m.group(1)), int(m.group(2))
print('N =', N, 'C =', C)
הביטוי הרגולרי rb'N=(\d+)\s+C=(\d+)' עמיד לרווחים וטאבים מסביב, ומחזיר את שני המספרים בקבוצות 1 ו-2. אם משהו נתקע כאן, מוסיפים context.log_level = 'debug' ורואים בדיוק מה השרת שולח ומתי הוא מחכה - זה הכלי הכי חשוב לדיבוג סנכרון.
למה זה עבד: הפרדנו את שלב הסנכרון (recvuntil על הבאנר) משלב הפרסור (regex על השורה). ברגע שאנחנו יודעים לחלץ את N ו-C, כל השאר הוא חישוב מקומי.
פתרון תרגיל 3 - חיפוש בינארי לסבב בודד¶
מחזיקים טווח סגור [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
answer = lo # one coin left - that's the answer
io.sendline(str(answer).encode())
ננתח את הצמצום. אם המשקל הוא בדיוק (mid - lo + 1) * 10, כל המטבעות ב-[lo, mid] אמיתיים, אז המזויף בהכרח ב-[mid+1, hi] ולכן lo = mid + 1. אחרת יש בטווח מטבע קל מדי, המזויף ב-[lo, mid] ולכן hi = mid. הלולאה נעצרת כשהטווח מצטמצם למטבע אחד.
מספר השקילות: כל צעד חוצה את גודל הטווח, ולכן דרושים ceil(log2(N)) צעדים במקרה הגרוע. עבור N=45 זה 6 - בדיוק הערך של C. זו לא צירוף מקרים: השרת קבע את C כך שיספיק בול לחיפוש בינארי, לא יותר.
למה זה עבד: כל שקילה נותנת סיביט מידע אחד (המזויף בחצי הזה או בחצי השני), וחיפוש בינארי הוא הדרך האופטימלית לנצל כל סיביט. אי אפשר לרדת מתחת ל-log2(N) שקילות.
פתרון תרגיל 4 - לולאת סבבים ולנצח את השעון¶
עכשיו מחברים הכל. שתי נקודות עדינות: לצרוך בדיוק C שקילות בכל סבב, ולזהות את סוף המשחק.
לגבי C: החיפוש הבינארי לפעמים מצטמצם למטבע אחד עוד לפני שניצלנו את כל C השקילות (קורה כש-N אינו חזקה של 2). אבל השרת מחכה לבדיוק C שקילות לפני שהוא מוכן לקבל תשובה. הפתרון: אם כבר מצאנו את המטבע (lo == hi) אבל נשארו שקילות, שוקלים שוב את אותו מטבע בודד (שקילה חוקית לגמרי) ומתעלמים מהתוצאה, עד שהשלמנו C שקילות.
הנה הבוט המלא:
#!/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 local demo: '127.0.0.1', 9007
io = remote(HOST, PORT)
io.recvuntil(b'ready?') # consume the entire banner
io.recvline() # the rest of the prompt line
io.sendline(b'') # press enter to start
rounds = 0
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))
rounds += 1
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() # 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: # 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
print('\ncleared rounds:', rounds)
מריצים, וכעבור שנייה-שתיים מקבלים את הדגל. שימו לב: לא הנחנו כמה סבבים יש - הלולאה ממשיכה עד שהשרת מפסיק לשלוח שורות N=.. ומתחיל לשלוח את שורת הסיום.
למה זה עבד: הpadding של השקילות שומר על סנכרון מושלם מול שרת שסופר בדיוק C שקילות. הורדת רמת הלוג והימנעות מהדפסות בלולאה החמה מבטיחות שנעמוד בתקציב הזמן בקלות.
איך להכליל: אם תריצו את השרת האמיתי עם context.log_level = 'debug' ותראו שהוא מקבל את התשובה מתי שתרצו (בלי לדרוש C שקילות מלאות), אפשר להסיר את הpadding ולשלוח את התשובה ברגע ש-lo == hi. בכל מקרה, פתיחת כל סבב עם recvuntil(b'N=') מסנכרנת מחדש בתחילת הסבב ומייתרת את הצורך לנחש את המוסכמה המדויקת.
פתרון תרגיל 5 (העמקה) - עמידות והכללה¶
גרסה עמידה יותר שמסנכרנת כל סבב ומטפלת ב-timeout:
while True:
try:
io.recvuntil(b'N=', timeout=5) # anchor: start of a new round
except EOFError:
break
rest = io.recvline().strip() # b'45 C=6'
m = re.search(rb'(\d+)\s+C=(\d+)', rest)
if not m:
continue
N, C = int(m.group(1)), int(m.group(2))
# ... same binary search as before ...
לגבי השאלות בסוף התרגיל:
- אילו המזויף היה כבד יותר (שוקל 11), התנאי היה מתהפך: משקל גבוה מהצפוי מסגיר שהמזויף בטווח. עדיין חיפוש בינארי, רק עם
weight > (mid - lo + 1) * 10. - הכתיב
weight % 10 == 0שקול ל-weight == (mid - lo + 1) * 10כאן, ועמיד יותר אם הפרש המשקל אינו בדיוק 1 (כל עוד הוא לא כפולה של 10). - שני מטבעות מזויפים היו שוברים את החיפוש הבינארי הפשוט, כי שקילה כבר לא מחלקת נקי לשני חצאים - היינו צריכים אסטרטגיה אחרת (למשל שקילות שמבודדות כל מזויף בנפרד).
שרת אימון מקומי - להתאמן בלי הרשת¶
כדי לדבג בנוחות ובלי לבזבז ניסיונות מול השרת האמיתי, הנה שרת דמו שמדמה את החוקים במדויק. מריצים אותו בטרמינל אחד ומכוונים את הבוט ל-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()
מריצים את השרת (python3 coin_server.py), מכוונים את הבוט ל-HOST, PORT = '127.0.0.1', 9007, ומריצים. הבוט עובר את כל 100 הסבבים ומקבל flag{DEMO_all_rounds_cleared} בפחות משנייה. ברגע שזה עובד מקומית, ההעברה לשרת האמיתי היא רק שינוי של HOST ו-PORT בחזרה ל-pwnable.kr, 9007.
למה זה עבד: השרת הדמו והבוט חולקים בדיוק אותה מוסכמה - C שקילות ואז תשובה - אז הסנכרון מושלם. זה מלמד עיקרון כללי במחקר חולשות: כשאפשר, בונים סימולציה מקומית של היעד ומדבגים מולה לפני שיורים על המטרה האמיתית.
סיכום הפתרון¶
- הפרוטוקול: סכום של
kמטבעות אמיתיים הוא10*k; סטייה מסגירה שהמזויף בטווח. - חיפוש בינארי מוצא את המזויף ב-
ceil(log2(N))שקילות, בדיוק תקציבCשל השרת. - ניהול סבב דורש לצרוך את כל
Cהשקילות (עם padding אם סיימנו מוקדם) לפני שליחת התשובה. - עמידה בזמן מושגת עם
log_level='error', מינימום סבבי רשת, ובלי הדפסות בלולאה. - שרת דמו מקומי מאפשר לדבג בלי שעון עצר ובלי לשרוף ניסיונות מול היעד.