לדלג לתוכן

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

תרגול - סקריפטינג של אתגרים

בתרגול הזה נבנה בוט שמנצח את coin1 מ-pwnable.kr. זהו אתגר מקטגוריית Toddler's Bottle, ולא צריך בשבילו התחברות ב-SSH - הוא אתגר רשת טהור. מתחברים אליו ישירות:

nc pwnable.kr 9007

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

מטרת התרגול: לעבור מהבנה ידנית של הפרוטוקול ועד בוט אוטומטי שלם ב-pwntools שסוגר את כל הסבבים. עבדו בשלבים - כל תרגיל בונה על הקודם.

תרגיל 1 - להכיר את הפרוטוקול ביד

לפני שכותבים שורת קוד, מתחברים ומבינים מה בדיוק השרת מדבר.

  1. התחברו עם nc pwnable.kr 9007 וקראו את הבאנר. לחצו enter כדי להתחיל.
  2. מהי השורה שמכריזה על סבב חדש? אילו שני מספרים מופיעים בה ומה המשמעות של כל אחד?
  3. שלחו ידנית רשימת אינדקסים, למשל 0 1 2 3, וראו איזה מספר חוזר. מה הוא אומר לכם?
  4. נסו לשקול טווח שאתם יודעים שהמזויף לא בו לעומת טווח שהוא בו. איך אתם מזהים מהסכום אם המזויף בפנים?
  5. נסו לשחק סבב או שניים לגמרי ביד. שימו לב כמה מהר נגמר לכם הזמן.

רמז: הסכום של k מטבעות אמיתיים הוא בדיוק 10*k. כל סטייה כלפי מטה מסגירה שהמזויף בטווח.

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

תרגיל 2 - להתחבר ולפרסר את N ו-C

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

  1. השתמשו ב-remote('pwnable.kr', 9007).
  2. בלעו את הבאנר עד לנקודה שאחריה מתחיל המשחק (חשבו איזה עוגן טקסט מתאים ל-recvuntil).
  3. שלחו את ה-enter שהשרת מחכה לו.
  4. קראו את שורת הסבב וחלצו ממנה שני מספרים שלמים.
  5. הדפיסו אותם וודאו שהם הגיוניים.

רמז: re.search(rb'N=(\d+)\s+C=(\d+)', line) מחזיר את שני המספרים בקבוצות 1 ו-2. אל תשכחו שהכל בבתים, ושצריך strip לפני int אם אתם מפרסרים ידנית.

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

תרגיל 3 - חיפוש בינארי לסבב בודד

הלב של האתגר. ממשו את החיפוש הבינארי שמוצא את המטבע המזויף בסבב אחד.

  1. החזיקו טווח חשד [lo, hi] שמתחיל ב-[0, N-1].
  2. בכל צעד, שקלו את החצי התחתון של הטווח ושלחו לשרת את האינדקסים.
  3. קראו את הסכום, והשוו אותו למשקל הצפוי אם כל המטבעות אמיתיים.
  4. צמצמו את הטווח בהתאם: אם הכל אמיתי, המזויף בחצי העליון; אחרת בחצי התחתון.
  5. עצרו כשנשאר מטבע אחד - זו התשובה.

רמז: מספר המטבעות בטווח [lo, mid] הוא mid - lo + 1, והמשקל הצפוי אם כולם אמיתיים הוא (mid - lo + 1) * 10.

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

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

תרגיל 4 - לולאת סבבים ולנצח את השעון

עכשיו עוטפים הכל בלולאה שסוגרת את כל הסבבים ומקבלת את הדגל.

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

רמז: אם lo == hi אבל נשארו שקילות, שקלו שוב את אותו מטבע בודד ובלעו את התשובה. כך צורכים שקילה בלי לקלקל את המצב.

רמז שני: context.log_level = 'error' חוסך זמן יקר. הריצו ומדדו - הבוט אמור לסיים הרבה מתחת לתקציב הזמן.

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

תרגיל 5 (העמקה) - עמידות והכללה

כדי שהבוט יהיה איתן ולא רק "עובד פעם אחת":

  1. פתחו כל סבב בעוגן ברור, למשל recvuntil(b'N='), כדי להסתנכרן מחדש גם אם נשארו בתים מהסבב הקודם.
  2. הוסיפו timeout לקריאות כדי שהבוט לא ייתקע לנצח אם משהו משתבש.
  3. חשבו: מה משתנה אם המזויף היה כבד יותר במקום קל יותר? מה אם היו שני מטבעות מזויפים? נסחו איך הייתם מתאימים את הלוגיקה.

רמז: את התנאי weight == (mid - lo + 1) * 10 אפשר לכתוב גם כ-weight % 10 == 0, וזה עמיד יותר להפרשי משקל שאינם בדיוק 1.

בפתרון תמצאו בוט שלם ובדוק, שרת דמו מקומי, והסבר של כל שלב.