Secret Service

• קטגוריה: Cryptography
• 1500 נקודות
• נפתר על ידי קבוצת JCTF

תיאור

פתרון

האתר סיפק שני ממשקים. הראשון נקרא Execute a Command:

הממשק מקבל מספר מקודד ב-Base64 ומחזיר את הערך של המספר, לאחר פענוח, בצורת טקסט. הממשק השני נקרא Create Demo Commands:

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

המטרה היא לשלוח בממשק הראשון את הערך המוצפן של "FLAGPLX". לאתגר הזה נציע שני פתרונות. נתחיל מהפתרון אליו כותב האתגר התכוון ולאחר מכן נעבור לפתרון ה"אלגנטי" יותר.

הפתרון הרצוי:

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

בנוסף שליחת המספר "1" ("==MQ" בבסיס 64) לממשק המפענח תחזיר את המספר "1", כלומר החולשה הראשונה בהצפנת RSA שמצאנו היא שאין padding. מהגודל של הערך המוצפן של "2" (אותו ניתן לקבל באמצעות הממשק השני) ניתן להסיק כי ה-e (ה-public exponent) הוא לא 3, אלא כנראה ערך נפוץ אחר (65537). למעשה זה יכול להיות כל ערך, זהו רק ניחוש מושכל למרות שבשלב זה הנתון הזה לא עוזר לנו במיוחד.

משחק עם הממשק השני ע"י שליחת ערכים אחרים מאשר אלו שהיו ברשימה הנפתחת, מוביל אותנו למסקנה שבחלק מהערכים חוזר ערך אקראי ובחלק חוזר הערך האמיתי מוצפן, לדוגמה: http://secretservice.challenges.bsidestlv.com/index.php?action=demo&value=10 מחזיר ערך אחר בכל פעם ופענוח של הערכים הללו (בממשק הפענוח) מחזיר ג'יבריש, אבל הקישור:
http://secretservice.challenges.bsidestlv.com/index.php?action=demo&value=11 מחזיר בכל פעם את הערך המוצפן של 11.

איך נוכל להשתמש בכל הנתונים הללו כדי לבנות את ההצפנה של "FLAGPLX"?

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

44950212844456690224840967364926980361299115474741976132427291503764555110057)^2 = 2020521634761959213956959964170116468842444132795734683180575187844425880920275118393733286671080411387807242172023597551747229132837716407656271382543249

שליחת הערך הזה (כמובן בבסיס 64) לממשק הפענוח תחזיר את הערך 4 מכיוון שמתקיים פה:

me^e * m^e = m^2e mod n

אבל ערך כזה לא היה אמור להתקבל על ידי ממשק הפענוח מכיוון שהוא נותן לנו את היכולת לזייף הודעות בצורה הבאה: הודעה מוצפנת באלגוריתם RSA לאחר שהופכים את ההודעה למספר (פשוט על ידי הצבה של ערך ה-ASCII של כל תו), ולכן הערך של "FLAGPLX" הוא 0x464c4147504c58 והפקטורים הם:

2 * 2 * 2 * 83 * 179 * 166479535091

ולכן אם נכפיל את הערך המוצפן של כל הערכים האלו נקבל מספר גדול שכאשר נבצע עליו פענוח כ-C^d mod n nבאמצעות ממשק הפענוח נקבל בחזרה את "FLAGPLX". התברר לנו שזאת הייתה מטרתו של ממשק ההדגמה – בנוסף לרשימה הסגורה של הערכים שהוא החזיר, הוא החזיר גם את הערך המוצפן של כל מספר ראשוני שנשלח אליו, ולכן יכולנו לבנות את הערך המוצפן של כל ערך שנרצה באמצעות הכפלה של הערך המוצפן של הגורמים הראשוניים שלו, מבלי שהיה לנו את המפתח פרטי ו/או הציבורי. זה היה הפתרון שכותב האתגר התכוון אליו. בסוף האתגר, הפידבק שלנו לכותב האתגר היה שהוא היה צריך להוציא מרשימת הדוגמאות את כל המספרים הלא ראשוניים. הסיבה הראשונה היא אחידות, אם ברשימת הדוגמאות היו רק מספרים ראשוניים (או מחרוזות שמתורגמות למספרים ראשוניים) היה אפשר לממש את זה באמצעות כלל אחד (שהמספר הוא ראשוני) ולא באמצעות שני כללים (או שמספר הוא ראשוני הוא שהוא מתוך הרשימה), אך היה פה משהו נוסף, סיבה טובה יותר...

הפתרון האלגנטי:

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

(M^e mod n * M^e mod n) mod n = M^2e mod n

אבל המשמעות של x mod n היא x+kn, ולכן:

(M^e mod n * M^e mod n) - (M^2e mod n) = kn

מאחר ורשימת הדוגמאות כללה בתוכה מספרים ראשוניים ומספרים פריקים (4,6,8 ו-9), נוכל לחלץ את kn (כמובן ש-n זהו ה-RSA modulus ו-k זהו מספר שלם גדול מ-0).

למעשה, ניתן היה אפילו למצוא את n ישירות באמצעות חישוב של ערך ה-GCD של שני ערכים כאלו (𝑘1𝑛 ו-𝑘2𝑛). בשלב הזה, RECLASS פשוט חישבו את הגורמים הראשוניים, מצאו את p ואת q, הכפילו ביניהם וקיבלו את n. לאחר מציאת הערך של n ניתן להשתמש בו ישירות על מנת להצפין את ההודעה "FLAGPLX".

בפועל, לא היה הכרחי למצוא את p ואת q (וגם היה בלתי אפשרי אם היה מדובר בהצפנה חזקה יותר, כמו 2048-RSA). על ידי חישוב GCD ובדיקה של ראשוניים קטנים (באמצעות msieve או factordb), היינו נשארים עם מספר פריק באורך המפתח (במקרה שלנו 256~) שהוא עצמו n, כלומר, היה ניתן להשתמש בו ישירות על מנת להצפין את ההודעה.

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

s6 = 43567593582703824135057604147410721491175339927073911761181767862580007889801 #6
s4 = 28704952153372369130078841833343740896457901926335558742680288438605486893172 #4
s3 = 1690090801071764914955097576963309824451388960507654086159474954444109322980 #3
s2 = 44950212844456690224840967364926980361299115474741976132427291503764555110057 #2
kn = (s2*s2)-s4
kn2 = (s2*s3)-s6

n=GCD(kn,kn2)
### CHECK HERE THAT n IS THE COMPOSITE OF BIG NUMBERS. This was the case here :-)
### If not, msieve can be used to find small exponents and divide kn by them.

e = 65537
t = "FLAGPLX"
m = int(t.encode("hex"),16)

sol = str(pow(m,e,n)).encode("base64").replace("\n","")

payload = {'action':'execute','value':sol}
r = requests.get('http://secretservice.challenges.bsidestlv.com/index.php',params=payload)
print r.text

#congrats! :) your flag is BsidesTLV{iloveyou!nohomo(morphic)}