searchable_text.txt

######################################################################################
# This is a textual version of the writeup, in order to make the text searchable.    #
# For a readable version which includes images, please refer to the PDF.             #
######################################################################################

סדרת אתגרי Matrix Defense CTF - 2020
מאת Dvd848 ,YaakovCohen88

כחלק מקמפיין גיוס של חברת Matrix, נפתח CTF עם שבעה אתגרים מתחומים שונים: Web, Pwn, Crypto, Reversing ו-Forensics. במאמר זה נציג את הפתרון שלנו לאתגרים. האתגרים היו פתוחים החל מחודש פברואר 2020 ולמשך מספר חודשים.

אתגר #1: Behind Blue Eyes (20 נקודות)
 
פתרון:
זהו אתגר חימום. לאתגר צורפו תריסר תמונות זהות (לכאורה) שבמרכזן עין כחולה:
 
אם קיבלנו תריסר עותקים סימן שכנראה יש ביניהם הבדל כלשהו למרות הכל. דרך אחת להשוות בין שתי תמונות היא באמצעות תוכנת Beyond Compare - תוכנה להשוואה בין קבצים שתומכת במגוון פורמטים (התוכנה לא חינמית אבל היא שווה כל שקל). נשווה בין שני הקבצים הראשונים ונקבל את התוצאה הבאה:
 
החלק העליון של המסך מראה את שתי התמונות המקוריות ביניהן אנחנו משווים. החלק התחתון מראה את האיחוד של שתי התמונות. אם היה הבדל בתמונה עצמה, הוא היה מוגדש באמצעות סימון צבעוני בתמונה התחתונה. אולם, כפי שניתן לראות, התמונה התחתונה אפורה לחלוטין ולא כוללת הדגשה של הבדל כלשהו. מה כן שונה? ניתן לראות הבדל בפינה הימנית-עליונה של המסך:
 
חלק זה מתאר את ה-metadata של התמונה - שכבת נתונים נוספת שניתן לשמור בקובץ התמונה בנוסף לייצוג הויזואלי של התמונה עצמה. למשל, כך ניתן לשמור היכן התמונה צולמה, באיזה תאריך, ומי צילם אותה. בעבר התפרסמו מספר מקרים בהם רשויות החוק איתרו מבוקשים באמצעות מידע שחולץ מה-metadata של תמונות שפורסמו על ידי המבוקשים עצמם.
כאן אנו רואים הבדל בשדה ה-Make של התמונות: התמונה הראשונה מכילה את האות F, בעוד השנייה מכילה את האות L. 
דרך נוחה לצפות במטא-מידע של תמונה כלשהו היא באמצעות תוכנת exiftool:
 
גם כאן אנחנו רואים את ההבדל בשדה Make. כעת נקרא ונאחד את שדה Make של כל התמונות באמצעות הפקודה:
 
הדגל: FLAG_THE_WHO.
אתגר #2: Message From The Dolphins (70 נקודות)
 
פתרון:
לאתגר צורף קובץ ארכיון: 42.gz. ננסה לפרוס אותו:
 
תוכנת 7Zip, שתומכת פחות או יותר בכל פורמט כיווץ שנמצא בשימוש בפועל, לא מצליחה להסתדר עם הקובץ. נראה שיש בו בעיה כלשהי. האם זו סיבה להתייאש, או לחלופין לנסות לנתח את הבעיה ולתקן אותה? ממש לא, פשוט נמצא תוכנה אחרת שמצליחה להתעלם מהבעיה:
 
מה קיבלנו?
 
קיבלנו קובץ תמונה.
נפתח את התמונה ונקבל:
 

גם הפעם הצצה ב-metadata של התמונה תעניק לנו רמז:
 
שימו לב ל-User Comment - הוא מכיל את הערך “Steganography” שמשמעותו האמנות של הסתרת מסרים סמויים בקבצים תמימים. למשל, הסתרת טקסט על ידי קידודו באמצעות שינוי הערך של הביט התחתון של כל פיקסל (מה שנקרא LSB encoding).
נשתמש בתוכנת zsteg שמחפשת דפוסי steganography נפוצים על מנת לחלץ את הדגל:
 
אתגר #3: Gotta catch em all (80 נקודות)
 
נכנס לקישור המצורף:
 
מדובר באתר פשוט המוקדש לפוקימונים. הדפים "אודות" ו"תמונות" מכילים תוכן סטטי, בעוד הדפים "כניסה" ו"צרו קשר" נראים הרבה יותר מעניינים מכיוון שהם מכילים טפסים.
דף הכניסה:
 
דף יצירת הקשר:
 
מסתבר שאם שולחים קלט ארוך מדי באחד הטפסים, מקבלים חריגה (Exception):
 
החריגה מדליפה חלק מהמימוש של טופס הכניסה:
 
אנחנו לומדים מקטע הקוד הזה מספר דברים:
	האורך המקסימלי של שם משתמש או סיסמא הוא 20 תווים
	מסד הנתונים של שמות המשתמש והסיסמאות מנוהל בקובץ טקסט
	הנתיב היחסי של קובץ הטקסט בתיקיית הבית הוא private/accounts.txt
	כל זוג של שם משתמש וסיסמא נשמר בשורה נפרדת ומופרד על ידי נקודתיים
אם נחזור על הפעולה בטופס יצירת הקשר, נקבל הדלפה של קטע קוד נוסף:
 
קטע קוד זה מגלה לנו שהטופס לוקח את הכותרת שהגיעה מהמשתמש (title) ומייצרת קובץ טקסט בשם זה תחת תיקיית messages. לתוך הקובץ נשמר תוכן הטופס שהגיע מהמשתמש.
החולשה פה היא שהקוד לא מוודא ששדה הכותרת מכיל רק תווים חוקיים, ולכן הוא עשוי להכיל תווים שיש להם משמעות ביצירת נתיב. כלומר, נוכל להכניס כותרת שתאפשר לנו לדרוס את הקובץ accounts.txt שראינו קודם:
 
הכותרת הזו תגרום לכך שהקוד ידרוס את התוכן של הקובץ:
HOME + ‘messages/../private/accounts.txt’
כעת נוכל להתחבר עם שם המשתמש והסיסמא שדרסנו ולקבל את הדגל:
 
 
אתגר #4: Fly Me To The Moon (85 נקודות)
 
פתרון:
אנו מקבלים קובץ בינארי לא מוכר:
 
חלק מהקובץ מכיל מחרוזות base64 אך בדיקה מדגמית של המחרוזות לא מעלה כיוון כלשהו.
אם מנסים אורכי תצוגת שורה שונים ב-Hex Editor מגיעים לבסוף לתבנית שנראית קבועה (התבנית מתקבלת עבור אורך שורה של 68 תווים):
 
(התווים 25-43 נחתכו לשם הנוחות). מבחינת ייצוג טקסטואלי התוכן נראה כך:
 
אז מה יש לנו פה בעצם?
	נראה שכל רשומה מתחילה עם מספר קסם: 0x12131415
	לאחר מכן מגיע אינדקס רץ באורך ארבעה בתים
	לאחר מכן מגיעים ארבעה בתים עם שונות גבוהה - אולי סוג של checksum?
	לאחר מכן, עוד בית אחד שבדרך כלל מכיל את הערך 0
	לבסוף, שדה נתונים שמכיל מחרוזת base64 (כנראה)
אם נרצה לייצג זאת בתור מבנה ב-C, נקבל:
typedef struct
{
   uint32_t magic;    // Equal to 0x12131415
   uint32_t id;       // Running index
   uint32_t checksum; // Maybe a checksum of an unknown format
   uint8_t  bool_val; // Unknown
   uint8_t  msg[37];  // Message
} my_struct;
עיון מדוקדק יותר בערך של הבית הבודד מגלה שיש אך ורק רשומה אחת שבו הוא שווה ל-1:
 
אם נקח את מחרוזת ה-base64 המצורפת ונתרגם אותה, נקבל את הדגל:
 
 
אתגר #5: Somewhat SecureBoot (150 נקודות)
 
נתחבר לשרת המצורף:
 
מה שאנחנו רואים פה זה ניסיון לטעון את Boot Loader 3. הבעיה היא שה-hash שלו מחושב בתור ערך שונה מהמצופה. הערך אמור להיות aaa…aaa אבל בפועל מתקבל ערך אחר. לכן, ה-shell שביקשנו לא נפתח.
נטען את קובץ ההרצה שקיבלנו באמצעות Ghidra ונבדוק את הפלט של ה-Decompiler. שם, ניתן לראות שרוב התוכן ממומש בתוך פונקציית main.

תחילה, מוגדרים מספר משתנים מקומיים:
  char bootloader3_str [21];
  char user_input [32];
  char expected_hash [65];
לאחר מכן, המשתנה expected_hash מאותחל עם aaa…aaa:
  expected_hash._0_8_ = 0x6161616161616161;
  expected_hash._8_8_ = 0x6161616161616161;
  expected_hash._16_8_ = 0x6161616161616161;
  expected_hash._24_8_ = 0x6161616161616161;
  expected_hash._32_8_ = 0x6161616161616161;
  expected_hash._40_8_ = 0x6161616161616161;
  expected_hash._48_8_ = 0x6161616161616161;
  expected_hash._56_8_ = 0x6161616161616161;
  expected_hash[64] = '\0';
לאחר מספר הדפסות, התוכנה מבקשת קלט מהמשתמש:
  puts("Please enter the desired shell to execute upon startup (press \'a\' for /bin/sh)\n");
  fflush(stdout);
  __isoc99_scanf("%s",user_input);
  iVar2 = strcmp(user_input,"a");
  if (iVar2 == 0) {
    user_input._0_8_ = 29400045130965551;
  }
ניתן לראות שהתוכנה קוראת קלט לתוך משתנה user_input באמצעות הפונקציה scanf. כמו כן, ניתן לראות שאין בקריאה לפונקציה שום רמז אודות אורך המשתנה שאליו יוכנס הקלט, מה שאומר ש-scanf תפסיק לקרוא קלט מהמשתמש רק כאשר היא תיתקל בתו whitespace. כלומר, ניתן להשתמש בקריאה זו על מנת לבצע buffer overflow ולדרוס משתנה אחר.
למזלנו, המשתנה שאותו ניתן לדרוס הוא expected_hash, מה שאומר שנוכל להשפיע על הבדיקה שמגיעה אחר כך:
ppcVar3 = read_firmaware(bootloader3_str);
  printf("Attempting to load the bootloader %s with hash %s\n",*ppcVar3,ppcVar3[1]);
  fflush(stdout);
  iVar2 = strcmp(ppcVar3[1],expected_hash);
  if (iVar2 == 0) {
    puts("Bootloader integrity verified successfully.");
    fflush(stdout);
    load(ppcVar3);
  }
  else {
    printf("Bootloader integrity compromised... Expected receiving hash: %s\nExiting...\n",expected_hash);
    fflush(stdout);
    destroy_bootloader(ppcVar3);
  }
 
אנחנו יודעים מהו ה-hash בפועל של ה-bootloader. נשתמש בערך זה על מנת לדרוס את ה-expected_hash ונוכל לעבור את ההשוואה:
 
 
אתגר #6: CamelCase (175 נקודות)
 
פתרון:
אנחנו מקבלים קובץ ארכיון עם מספר קבצי טקסט:
 
הקובץ details.txt מכיל את התוכן הבא:
 
כל אחד משאר הקבצים מכיל צמד מספרים, לדוגמא:
 
הנתונים האלו, יחד עם שם האתגר, מצביעים על כך שמדובר בצופן אל-גמאל:
הצפנת אל גמאל (ElGamal encryption) היא שיטת הצפנה אסימטרית אקראית שהומצאה ב-1984 על ידי טאהר אל-גמאל, קריפטוגרף אמריקאי ממוצא מצרי. בדומה לפרוטוקול דיפי-הלמן, ביטחונה מסתמך על הקושי המשוער שבבעיית הלוגריתם הבדיד ובעיית דיפי-הלמן. היא יכולה לשמש הן להצפנה והן לחתימה דיגיטלית.

שיטת הצפנה זו מתבצעת מעל חבורה ציקלית סופית. במקרה שלנו, נראה שמדובר בחבורה הכפלית Z_q^* של השלמים החיוביים מודולו q, כאשר q הינו מספר ראשוני בטוח, כלומר מתקיים של-( q-1) ישנו לפחות גורם ראשוני אחד גדול.
לכל חבורה כזו ישנה מספר שנקרא יוצר ומסומן ב- g. המספר הזה הוא מספר שבאמצעותו ניתן לייצר כל מספר בחבורה:
Z_q^*={g^0,g^1,g^2,…,g^(q-1)}
למשל, אם ניקח את Z_5^*, נגלה ש-2 משמש בתור היוצר של חבורה זו:
 
כעת, כדי לייצר את המפתח הפרטי, בוחרים מספר אקראי x (מודולו q) ומפרסמים את השלישייה:
(q,g,h= g^x)
בקובץ הטקסט שקיבלנו, g נקרא generator ו- h נקרא public key.
את המספר x שומרים בסוד בתור המפתח הפרטי. 
למרות שאנחנו יודעים מהו g ומהו g^x, מציאת x עצמו נחשבת קשה.
על מנת להצפין הודעה m, מגרילים מספר אקראי k (מודולו q) ומפרסמים את:
(c_1=g^k,c_2=m∙h^k)
בבעיה שלנו, נתון לנו שכל זוג קבצים מקבילים מתוך enc1 ו-enc2 הצפינו את אותו ה- m, כאשר המספר האקראי השני הוא תוצר לינארי של המספר האקראי הראשון. כלומר, כל זוג ניתן לייצוג בתור:
(c_1=g^k,c_2=m∙h^k ),(c_1^'=g^(ak+b),c_2^'=m∙h^(ak+b) )
המספר האקראי עצמו (k) מוגרל מחדש עבור כל הודעה ב-enc1, אך המספרים a ו- bשמהם נגזר המספר האקראי של enc2 נשארים קבועים לאורך כל ההודעות.
בהנתן הנחות אלו, עלינו לפצח את ההצפנה.
במהלך החישוב, אנחנו נשתמש בנגזרת מהמשפט הקטן של פרמה לפיו לכל מספר ראשוני p ולכל מספר שלם a מתקיים ש- a^(p-1)≡1 (mod p).
נתון לנו q (שהינו ראשוני), לכן אנחנו יכולים לחשב את q-1. את q-1 אנחנו יכולים לפרק למחלקים. נניח שמצאנו ש- d כלשהו הוא מחלק כלשהו של q-1.
כעת נתבונן ב-g^k. את k, כמו כל מספר שלם אחר, אפשר לבטא בתור k=d ⋅t+r , וזאת כאשר מתקיים r∈{0…d-1}. לכן:
g^k=g^(dt+r)
נעלה את המספר בחזקת (q-1)/d (שהוא מספר שלם כי d הוא מחלק של q-1).
〖〖(g〗^k)〗^(((q-1)/d))=〖(g^((dt+r) ))〗^(((q-1)/d))=g^((dt+r)⋅((q-1)/d))=g^((dt)⋅((q-1)/d)  + r((q-1)/d)  )=g^((dt)⋅((q-1)/d)   )⋅g^r((q-1)/d) =g^((t)⋅((q-1)/1)   )⋅g^r((q-1)/d) =(g^t )^((q-1) )⋅g^r((q-1)/d) =(1 (mod q))⋅g^r((q-1)/d) =g^r((q-1)/d) =(g^(((q-1)/d) ) )^r mod q
כמובן שכל החישובים הם mod q. כעת, מכיוון שידועים לנו כל המשתנים במשוואה הזו מלבד r , ו- rעצמו נמצא בתחום ידוע (r∈{0…d-1}), אנחנו יכולים להציב כל r אפשרי ולחשב את כל התוצאות האפשריות של 〖(g^(((q-1)/d)))〗^r. ומצד שני, אנחנו יכולים לחשב גם את 〖(g^k)〗^(((q-1)/d)) שהוא בעצם 〖(c_1)〗^(((q-1)/d)).
מכאן אנחנו יכולים להסיק משהו על k:
Then …	If … 
〖(c_1)〗^(((q-1)/d) )=〖(g^(((q-1)/d)))〗^0=1	k mod d=0
〖(c_1)〗^(((q-1)/d) )=〖(g^(((q-1)/d)))〗^1	k mod d=1
〖(c_1)〗^(((q-1)/d) )=〖(g^(((q-1)/d)))〗^2	k mod d=2
…	…
〖(c_1)〗^(((q-1)/d) )=〖(g^(((q-1)/d)))〗^(d-1)	k mod d=d-1

רק אחת מהמשוואות הללו תתקיים, וכך נדע מה השארית של k מחלוקה ב- d(k mod d).
את אותו תהליך אפשר להפעיל גם כדי להסיק מסקנה דומה על ak+b. 
בהנתן מספיק מסקנות כאלו, נוכל גם להסיק דברים על a ו- bעצמם.
עד כאן המתמטיקה היבשה. בפועל, על מנת למנוע התקפה ידועה של גילוי ביט בחזקה של g באמצעות אנליזה דומה לזו שעשינו זה עתה, נהוג להשתמש בערך של היוצר בריבוע ולא בערך של היוצר עצמו. 
כלומר, אם נגדיר 〖Γ=g〗^2, בפועל המספר שאנחנו מקבלים באתגר הינו c_1=Γ^k=〖〖(g〗^2)〗^k=g^2k ולא c_1=g^k, לכן אנחנו נחשב את Γ^(((q-1)/2d)) ולא את g^(((q-1)/d)) (מכיוון ש- Γ^(((q-1)/2d))= 〖〖(g〗^2)〗^(((q-1)/2d))= g^(2((q-1)/2d))=g^(((q-1)/d) ))
נתחיל עם דוגמא. כדי לקרוא בנוחות את קבצי הקלט של התרגיל, נממש תחילה מודול קצר שיקרא אותם:
import os, glob
from pathlib import Path
from collections import namedtuple

ElGamalPair = namedtuple('ElGamalPair', ['c1', 'c2'])

def read_data(base_path: str) -> dict:
    res = {}
    
    with open(os.path.join(base_path, "details.txt")) as f:
        res["q"] = int(f.readline().split(":")[1])
        res["g"] = int(f.readline().split(":")[1])
        res["h"] = int(f.readline().split(":")[1])

    for enc in ["enc1", "enc2"]:
        res[enc] = {}
        for infile in glob.glob(os.path.join(base_path, enc, '*.txt')):
            with open(infile) as f:
                line = f.readline().strip("\n()")
                res[enc][int(Path(infile).stem)] = ElGamalPair._make([int(s) for s in line.split(", ")])
    return res
המודול הזה מאפשר לנו לקבל את הפרמטרים של התרגיל כמילון.
את q קיבלנו כנתון, נחשב את q-1:
 
כעת נחפש את המחלקים של המספר הזה (למשל, באמצעות האתר הזה). התוצאה היא:
2, 2, 2, 3, 3, 5, 8357651, <a very large number…>
נתמקד במחלקים הקטנים משיקולי כוח-חישובי. בדוגמא שלנו, נשתמש ב-3.
כזכור, אנחנו הולכים לחשב את:
Then …	If … 
〖(c_1)〗^(((q-1)/d) )=〖(Γ^(((q-1)/2d)))〗^0=1	k mod d=0
〖(c_1)〗^(((q-1)/d) )=〖(Γ^(((q-1)/2d)))〗^1	k mod d=1
〖(c_1)〗^(((q-1)/d) )=〖(Γ^(((q-1)/2d)))〗^2	k mod d=2

נעשה זאת באמצעות הפונקציה:
def get_mod(params: dict, c1: int, num: int) -> int:
    assert(params["q-1"] % num == 0)
    t = pow(c1, params["q-1"] // num, params["q"]) 
    for i in range(num):
        if t == pow(params["g"], (params["q-1"] // (num * 2)) * i, params["q"]):
            return i
    raise RuntimeError(f"Can't find result for {num}")

נריץ לדוגמא על ההודעה השנייה שניתנה לנו:
 
קיבלנו שעבור הודעה מספר 2, מתקיים:
k mod 3=1
וגם:
(ak+b) mod 3=2
 
אנחנו יכולים להמשיך לעשות אותו דבר עבור כל שילוב של מחלקים, ולקבל עוד נתונים:
 
עכשיו שימו לב לתופעה מעניינת: כאשר השאריות שונות מאפס, הסכום שלהן הוא המספר שאנחנו בודקים. התוצאה הזו חוזרת בכל הדגימות. כבר מפה אפשר לנחש מהם a ו-b, אבל אנחנו נמשיך עוד צעד ונדחוף הכל לתוך z3 בשביל הכיף.
הנה הסקריפט:
import data_reader
import functools, operator, argparse, sys, random
from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))

def get_mod(params: dict, c1: int, num: int) -> int:
    assert(params["q-1"] % num == 0)
    t = pow(c1, params["q-1"] // num, params["q"]) 
    for i in range(num):
        if t == pow(params["g"], (params["q-1"] // (num * 2)) * i, params["q"]):
            return i
    raise RuntimeError(f"Can't find result for {num}")

def find_small_factors(n):
    small_factors = []
    t = n
    for i in range(2, 10):
        while (t % i == 0):
            small_factors.append(i)
            t = t // i
    return small_factors

def analyze(params: dict, solve_ctx: dict):
    verbose = True
    if solve_ctx is not None:
        try:
            import z3
        except:
            raise RuntimeError("Error: Z3 module needed")
        verbose = solve_ctx.get("verbose", False)
    

    params["q-1"] = params["q"] - 1
    small_factors = find_small_factors(params["q-1"])
    if verbose: print(f"Small factors: {small_factors}\n")

    assert(len(params["enc1"]) == len(params["enc2"]))
    
    samples = list(range(len(params["enc1"])))
    if solve_ctx is not None:
        solver = z3.Solver()
        a = z3.Int('a')
        b = z3.Int('b')
        samples = random.sample(samples, k=solve_ctx.get("num_samples", 3))
        k = {i: z3.Int('k{}'.format(i)) for i in samples}
        
    for i in samples:
        if solve_ctx is not None:
            solver.add(k[i] >= 0)
            solver.add(k[i] < params["q"])
        for combination in set(powerset(small_factors)):
            factor = functools.reduce(operator.mul, combination)
            try:
                m = get_mod(params, params["enc1"][i].c1, factor)
                if verbose: print (f"   k[{i}]      % {factor}\t== {m}")
                if solve_ctx is not None: solver.add(k[i] % factor == m)

                m = get_mod(params, params["enc2"][i].c1, factor)
                if verbose: print (f"(a*k[{i}] + b) % {factor}\t== {m}\n")
                if solve_ctx is not None: solver.add((a * k[i] + b) % factor == m)
            except RuntimeError:
                pass

    if solve_ctx is not None:
        print(f"Trying to solve with {len(samples)} samples {samples}: ", end = '', flush = True)
        if solver.check() == z3.sat:
            m = solver.model()
            #print(m)
            print("a = {}, b = {}".format(m[a], m[b]))
        else:
            print("Can't find solution")

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument('-s', '--solve', action='store', type=int, default=0, metavar=('NUM_SAMPLES'), help='Try to solve constraints using up to <NUM_SAMPLES> samples')
    parser.add_argument('--path', default="Camel", type=str, help='Path to data folder')
    args = parser.parse_args()

    try:
        params = data_reader.read_data(args.path)
        if args.solve:
            solve_ctx = {"num_samples": args.solve}
        else:
            solve_ctx = None
        analyze(params, solve_ctx)
    except RuntimeError as e:
        print (str(e))
        sys.exit(1)

את הסקריפט ניתן להריץ בשני אופנים. הרצה ללא פרמטרים תדפיס את השאריות עבור כל ההודעות כפי שראינו קודם. אולם, אם נריץ את הסקריפט עם פרמטר של מספר דגימות, הוא ינסה לפתור את המשוואה עבור מספר זה של דגימות אקראיות באמצעות z3 (אנחנו מגבילים את מספר הדגימות משיקולי כוח חישוב).
 
אנחנו רואים פה מספר הרצות עם 3 דגימות - מספר הדגימות הגבוה ביותר שמאפשר פתרון בזמן סביר. 
כפי שניתן לראות - בהרבה מאוד מקרים התוצאה היא: a=-1,b=0. זה גם מסתדר עם התופעה שראינו קודם, שבה סכום השאריות שווה למספר שאותו אנו בודקים (למעשה עברנו לחבורה ציקלית חדשה שיש בה d איברים מתוך Z_q^*, ומכיוון שזוהי חבורה ציקלית, תכונת המודולו עדיין נשמרת מתוך איברי החבורה: k mod d□(→┴yields )-k mod d= d-k).

כעת, כשמצאנו מועמדים טובים עבור a ו- b, ננסה לפצח את ההצפנה.
אנחנו יודעים ש:
c_2=m∙h^k  mod q
c_2^'=m∙h^(ak+b)= m∙h^(-k)  mod q
נכפיל אותם אחד בשני ונקבל:
c_2⋅ c_2^'=(m∙h^k )⋅(m∙h^(-k) )=m⋅m⋅h^k⋅ h^(-k)= m^2⋅h^(k+(-k) )=m^2⋅ h^0=m^2  mod q
ניחשנו שכל הודעה מכילה תו אחד בלבד מהדגל ואכן לפי התוצאות שקיבלנו ניתן לראות ש-m^2 לא גדול מ-q ולכן מספיק להוציא שורש ולקבל את m.
הסקריפט הבא עושה זאת:
import data_reader
import math

if __name__ == "__main__":
    params = data_reader.read_data("Camel")
    res = ""

    assert(len(params["enc1"]) == len(params["enc2"]))

    for i in range(len(params["enc1"])):
        m = math.isqrt(params["enc1"][i].c2 * params["enc2"][i].c2 % params["q"])
        res += chr(m)

    print(res)
התוצאה:
 
 
אתגר #7: Save Israel (200 נקודות)
 
פתרון:
נריץ את הקובץ המצורף:
 
הפלט היחיד הוא 80eaf9c. זה נראה כמו מספר בייצוג הקסאדסימלי. אך מה משמעותו?
אם נפתח את הקובץ בדיסאסמבלר, נגלה שהוא קשה מאוד לקריאה. בנוסף, הקובץ הוא stripped, כלומר כזה שהוסר ממנו מידע שמסייע לדיבוג. אפשר לפתוח את הקובץ עם דיבאגר ולעבור פקודה אחרי פקודה, אבל זה לא פחות קשה. במקום זאת, ננסה לקבל סיכום ממבט עילי (יחסית) של הפקודות שהתוכנה מריצה.
תחילה, נריץ את התוכנה באמצעות strace - כלי עזר שמפרט את ה-system calls שהתוכנה משתמשת בהם בזמן ריצה:
 
אפשר לראות שהתוכנה קוראת ל-mmap ול-mprotect על טווח שמכיל את הערך המסתורי שלנו. בואו ננסה לשים שם breakpoint:
 
זה לא עובד, לא ניתן לגשת לזיכרון בכתובת זו.
נמשיך לנסות לקבל מושג טוב יותר מה התוכנה עושה. לשם כך, נריץ באמצעות gdb את הסקריפט הבא:
set style enabled off
set pagination off
set logging on
set disassembly-flavor intel
set disassemble-next-line on
starti
define nstep
set $limit = $arg0
while ($limit--)
 ni
 end
end
nstep 40000
בגדול, הסקריפט הזה מגדיר פונקציה שנקראת nstep אשר מבצעת את הפקודה ni (כלומר next instruction) מספר מוגדר של פעמים, ומדפיסה את ה-instruction לקובץ. אנחנו קוראים לפונקציה זו בבקשה להריץ 40,000 פקודות.
 
את התוצאה נוכל לראות בקובץ gdb.txt. הקובץ המתקבל בעל כ-60,000 שורות. כך הוא מתחיל:
 
וכך הוא מסתיים:
 
אפשר לראות שהתוכנה מתחילה מריצה במרחב 0x00cXXXXX ומסתיימת בריצה במרחב 0x08XXXXX. אם כך אולי הכתובת המסתורית הופכת להיות זמינה רק מאוחר יותר? זה מסתדר עם הקריאה ל-mmap שראינו קודם. נחפש את הכתובת המסתורית בתוך הלוג שלנו:
 
אין מזל. אולי ניתן לתוכנה לרוץ קצת, ורק אז ננסה לשים breakpoint?
 
זה עבד! וקיבלנו את הדגל! רגע, מה? איך ריצה עם breakpoint פתאום הדפיסה לנו את הדגל?
כדי לענות על השאלה הזאת, ננסה לנתח בכל זאת את התוכנה עם דיסאסמבלר. ממה שראינו עד עכשיו, התוכנה מתנהגת באופן שמזכיר מאוד packer - תוכנה שמסתירה בתוכה תוכנה נוספת, כאשר היא פורסת ומריצה אותה בזמן ריצה. כלומר, הקוד שאנחנו רואים כשפותחים את התוכנה בדיסאסמבלר הוא קוד שנועד לפרוס ולהריץ תוכנה אחרת שמסתתרת אי שם בבינארי. אותנו לא מעניינת התוכנה החיצונית, לכן אנחנו צריכים להגיע אל התוכנה הפנימית שהיא העיקר.
 
ישנם packer-ים רבים אך המפורסם שבהם הוא UPX, לכן קודם ננסה לפרוס את התוכנה באמצעות UPX:
 
זה לא עבד. אם כך, ננסה להשתמש בכלי-עזר שאמור לזהות את ה-packer שבו נעשה שימוש, אם הוא מוכר:
 
מעניין, Detect it Easy דווקא טוען בתוקף שכן מדובר ב-UPX. אז מי צודק?
מחקר קצר גילה שקל מאוד לגרום ל-UPX להכשל בפריסת קובץ שהוא עצמו יצר, כל מה שצריך זה מספר שינויים קלים בבינארי. הקובץ עצמו ירוץ כשורה, אך לא יהיה אפשר לחלץ ממנו את קובץ ההרצה הפנימי.
איך אפשר להתגבר על בעיה זו? UPX הוא כלי קוד-פתוח. אפשר להוריד את הקוד שלו, להוסיף הדפסות בכל מקום שבו הוא יוצא עם כישלון, ולהבין מה בדיוק מפריע לו בבינארי שלנו. אם נעשה זאת, נקבל שהיה צריך לשנות את המקומות הבאים:
 
 
ננסה לחלץ:
 
הקובץ חולץ בהצלחה! כעת ניתן לפתוח אותו עם Ghidra. 
כעת מסתבר שהכתובת המסתורית שלנו היא משתנה גלובלי:
 
 
נעקוב אחרי השימוש שלה ונקבל:
 
כלומר, התוכנה מדפיסה את הכתובת של המשתנה, ומיד לאחר מכן בודקת אם הוא שווה ל-0. מכיוון שהצבת breakpoint בכתובת כלשהי משנה זמנית את התוכן של הזיכרון שלו ל-0xCC, רק כאשר הצבנו breakpoint ראינו את ההדפסה. התעלומה נפתרה!
 
סיכום
ה-CTF הזה כלל שבעה אתגרים ממספר תחומים מגוונים. על אף שהוא נבנה ברמת קושי עולה, רוב השאלות בסדרת האתגרים הזו נחשבות יחסית קלות ביחס ל-CTF-ים אחרים.
הקושי העיקרי ב-CTF היה בשאלת ה-Crypto, שהצריכה אנליזה מתמטית לא-טריוויאלית. משיטוט בקבוצות ה-CTF הייעודיות, נראה היה שזהו האתגר שרוב המשתמשים חיפשו בו רמז או הכוונה, והוא בעצם היווה את הטריגר העיקרי לכתיבת הפתרון כולו. מהחיפוש שעשינו, לא מצאנו writeup אחר אודות הדרך לתקוף הצפנה חוזרת של הודעה בסכמת ElGamal תוך שימוש ב-LCG עבור בחירת המשתנה האקראי כאשר a ו- bלא ידועים. 
 
תודה רבה למארגנים על הכנת ה-CTF ועל השארתו פתוח למשך תקופה ארוכה ביותר, מה שאיפשר את העבודה עליו בצורה נוחה ואת הכנת פתרון זה.

תודה גם ל- zVaz ול-DHG על תרומתם במהלך פתרון ה-CTF.