לדלג לתוכן

8.7 קריפטו ו RSA תרגול

תרגול - קריפטו ו-RSA

בתרגול הזה נתרגל את שני סוגי אתגרי הקריפטו מההרצאה: היפוך של cipher ביתי (בסגנון crypto1), וexploit של מימוש RSA שבור (בסגנון rsa calculator). המטרה שתגיעו לפתרון בעצמכם - הפתרון המלא נמצא בקובץ הנפרד, אבל נסו קודם ותצמדו לכללים.

שני האתגרים נמצאים בקטגוריית Rookiss באתר pwnable.kr. התחברו לפי דף האתגר - לרוב זה בצורת ssh <chal>@pwnable.kr -p2222 עם סיסמה שמופיעה בדף, ואת השירות מסוג "מחשבון" מריצים לפעמים דרך nc. מכיוון שהמימושים המדויקים משתנים מגרסה לגרסה, נעבוד גם על בינארי דמו וסקריפט שירות שתריצו מקומית ושמכילים בדיוק את אותה חולשה. מה שתלמדו כאן עובר ישירות לאתגר עצמו.

הכנת סביבה - setup

התקינו את הכלים ובנו את שני הקבצים למטה במחיצת עבודה:

pip install pycryptodome gmpy2 sympy pwntools

הבינארי הvulnerable ל-cipher (שמרו כ-cipher_demo.c והדרו):

#include <stdio.h>
#include <string.h>
#include <unistd.h>

unsigned char cipher[16] = {
    0x7a, 0x4d, 0x62, 0x01, 0x50, 0x40, 0x0e, 0x4c,
    0x6f, 0x0a, 0x4a, 0x49, 0xb4, 0x0a, 0xb7, 0x44
};

void encode(unsigned char *in, unsigned char *out, int len) {
    for (int i = 0; i < len; i++)
        out[i] = ((in[i] + i) ^ 0x37) & 0xff;
}

int main() {
    unsigned char buf[16] = {0}, enc[16] = {0};
    read(0, buf, 16);
    encode(buf, enc, 16);
    if (memcmp(enc, cipher, 16) == 0)
        system("/bin/cat flag");
    else
        puts("wrong");
    return 0;
}

gcc -o cipher_demo cipher_demo.c
echo 'FLAG{demo_cipher}' > flag

שירות RSA הvulnerable (שמרו כ-rsa_service.py):

from Crypto.Util.number import getPrime, bytes_to_long
FLAG = b"FLAG{demo_rsa_cube_root}"
e = 3
p, q = getPrime(1024), getPrime(1024)
n = p * q
c = pow(bytes_to_long(FLAG), e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

תרגיל 1 - היפוך ה-cipher

הריצו את cipher_demo והבינו מה encode עושה, ואז מצאו את הקלט בן 16 הבתים שיגרום ל-encode(buf) == cipher.

  1. כתבו במילים את הטרנספורמציה שכל בית עובר. מה הפעולות ובאיזה סדר?
  2. מהי הפעולה ההופכית לכל שלב, ובאיזה סדר צריך להפעיל אותן?
  3. חשבו בפייתון את 16 בתי הקלט מתוך המערך cipher.
  4. הזרימו את הבתים ל-./cipher_demo דרך stdin וודאו שהתקבל הדגל.

רמז: הקידוד הוא out = (in + i) ^ 0x37. הופכים בסדר הפוך ובפעולה ההופכית - קודם מבטלים את ה-xor, אחר כך את החיבור.

רמז שני: הבתים אינם בהכרח מודפסים, אז השתמשו ב-sys.stdout.buffer.write או ב-pwntools כדי להזרים אותם בלי לפגוע בהם.

תרגיל 2 - שורש שלישי על RSA

הריצו את rsa_service.py, קחו את n, e, c, ופענחו את הדגל בלי לפרק את n.

  1. שימו לב לערך של e. למה הוא מזמין התקפה?
  2. חשבו בערך את הגודל של המסר (הדגל) כמספר, והשוו אותו לגודל של n. האם m^3 קטן מ-n?
  3. אם כן - חלצו את m בעזרת שורש שלישי שלם, והמירו חזרה לבתים.

רמז: אם m^3 < n אז לא היה צמצום מודולרי כלל, כלומר c = m^3 פשוטו כמשמעו. הפונקציה gmpy2.iroot(c, 3) מחזירה את השורש ודגל שאומר אם הוא מדויק.

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

תרגיל 3 - מודולוס משותף

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

צרו את הקלט:

from Crypto.Util.number import getPrime, bytes_to_long
p, q = getPrime(512), getPrime(512)
n = p * q
m = bytes_to_long(b"common modulus is bad")
e1, e2 = 17, 65537         # gcd(e1, e2) = 1
c1, c2 = pow(m, e1, n), pow(m, e2, n)
print(n, e1, e2, c1, c2)
  1. למה חשוב ש-gcd(e1, e2) = 1? מה זה מאפשר לכם למצוא?
  2. מצאו מקדמים שלמים a, b כך ש-a*e1 + b*e2 = 1.
  3. הרכיבו את m מ-c1, c2 והמקדמים. שימו לב לטיפול במקדם השלילי.

רמז: אלגוריתם אוקלידס המורחב נותן את a, b. אחד מהם יהיה שלילי, ומעריך שלילי מודולו n הוא העלאת ההופכי הכפלי בחזקה החיובית. בפייתון 3.8+ הפונקציה pow(base, -k, n) עושה את זה בשבילכם.

תרגיל 4 - שחזור d על ידי פירוק

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

from Crypto.Util.number import getPrime, bytes_to_long
from sympy import nextprime
p = getPrime(512)
q = nextprime(p + 12345)   # q is very close to p - a classic mistake
n = p * q
e = 65537
c = pow(bytes_to_long(b"close primes leak"), e, n)
print(n, e, c)
  1. למה הקרבה בין p ל-q מסוכנת? איזה אלגוריתם פירוק מנצל אותה?
  2. פרקו את n וקבלו את p, q.
  3. חשבו את phi, אז את d, ואז פענחו את c.

רמז: פירוק Fermat מתחיל מ-a = isqrt(n) + 1 ומעלה את a עד ש-a^2 - n הוא ריבוע מושלם. אז p = a - b, q = a + b.

רמז שני: אחרי שיש לכם phi = (p-1)*(q-1), המעריך הפרטי הוא d = pow(e, -1, phi) והפענוח הוא pow(c, d, n).

תרגיל 5 - אורקל פענוח והסתרה (העמקה)

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

מודל האורקל למשחק מקומי:

def make_oracle(d, n, forbidden_c):
    def oracle(ct):
        if ct == forbidden_c:
            raise ValueError("refused")
        return pow(ct, d, n)     # decrypts everything else
    return oracle
  1. איזו תכונה של RSA מאפשרת "להלביש" את c בגורם אקראי r בלי לשנות את המסר שמאחוריו?
  2. בנו טקסט מוצפן מולבש c' שהאורקל יסכים לפענח, ושונה מ-c.
  3. מהאורקל תקבלו m'. איך מורידים את ההסתרה ומקבלים את m המקורי?

רמז: RSA הומומורפי לכפל - (x*y)^e = x^e * y^e. בחרו r, שלחו c * r^e mod n, וקבלו m * r mod n. אז חלקו ב-r מודולרית עם pow(r, -1, n).

שאלת העמקה - למחשבה

בכל ההתקפות כאן פענחנו בלי לתקוף את המתמטיקה של RSA עצמה - תקפנו בחירה גרועה של פרמטר (מעריך קטן, מודולוס משותף, ראשוניים קרובים, אורקל פתוח). נסו לנסח לעצמכם: מהי הבחירה ה"נכונה" בכל אחד מהמקרים שהייתה סוגרת את החולשה? למשל, למה e = 65537 עם padding OAEP וראשוניים אקראיים באמת בלתי אחידים היה מנטרל את כל ארבע ההתקפות בבת אחת? ההבנה הזו היא בדיוק ההבדל בין "לפתור אתגר" לבין "להבין למה קריפטו נכון לא נשבר".