8.7 קריפטו ו RSA הרצאה

בפרק הזה עסקנו בreverse engineering ככלי לexploit, ועד עכשיו התוצר הסופי שלנו היה כמעט תמיד shell או דגל שמגיע מoverflow, מ-ROP או מבאג לוגי. בהרצאה הזו נעצור על משפחה קצת שונה של אתגרים - אתגרי קריפטו. כאן אין buffer overflow ואין דריסת return address. במקום זה יש בדיקה מתמטית שצריך לעבור: מנגנון הצפנה ביתי שאפשר להפוך, או מימוש RSA עם פרמטרים שבורים. המטרה שלנו כתוקפים היא לא "לשבור קריפטוגרפיה" במובן האקדמי הכבד, אלא לזהות את החולשה הספציפית ולנצל אותה בעזרת מעט מתמטיקה ופייתון.

חשוב להבין את ההבחנה הזו מראש. קריפטוגרפיה חזקה, כשהיא מיושמת נכון, לא נשברת בתרגיל. מה שנשבר בפועל הוא המימוש: מפתח קבוע שנחשף, cipher ביתי שמישהו כתב לבד, מעריך e קטן מדי, מודולוס משותף, או שירות שבטעות משמש כאורקל. שני האתגרים שנפרק כאן - crypto1 ו-rsa calculator מ-pwnable.kr - הם בדיוק זה: לא פריצה של אלגוריתם, אלא exploit של טעות במימוש.

הלך הרוח - reverse the check, don't break the crypto¶

לפני שנצלול, בואו נסגור את הגישה. באתגר קריפטו טיפוסי מקבלים שלושה דברים: קוד מקור (או בינארי לreverse engineering), פלט כלשהו שהשירות מייצר, וקריטריון הצלחה. העבודה שלנו היא שרשרת של שלוש שאלות:

1. what exactly does the check require of me?   (which value needs to be produced)
2. which transformation separates me            (cipher, hash, RSA, xor)
   from that value?
3. is the transformation invertible, and how?   (find the input that produces the output)

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

הצפנה מבוססת xor - the xor cipher¶

הפעולה הכי נפוצה ב-cipher-ים ביתיים היא xor. הסיבה פשוטה: קל לכתוב אותה, היא נראית "מבלבלת", והרבה מתכנתים בטעות חושבים שהיא מספקת אבטחה. היא לא. הנה שלוש התכונות שהופכות את xor למתנה בשביל תוקף:

a ^ a = 0            xor of a value with itself zeroes out
a ^ 0 = a            xor with zero changes nothing
(a ^ k) ^ k = a      xor twice with the same key returns the original

התכונה השלישית היא הלב: xor הוא ההופכי של עצמו. אם הצפנתי c = m ^ k, אז כדי לחלץ את m אני פשוט מבצע c ^ k שוב. אין כאן "פונקציית פענוח" נפרדת - זו אותה פעולה בדיוק. וזה אומר שאם אני יודע שני מתוך שלושה (מקור, מפתח, טקסט מוצפן), אני מחלץ את השלישי מיד.

בואו נראה cipher ביתי טיפוסי בסגנון שמופיע באתגרים. הבינארי שומר טקסט מוצפן קבוע, מקודד את הקלט שלנו, ומשווה:

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

// the ciphertext of the correct password, constant inside the binary
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++) {
        // homemade transformation: add the index then xor with a fixed key
        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;
}

מה encode עושה לכל בית? קודם מוסיפה את האינדקס i, ואז עושה xor עם 0x37. שימו לב לסדר, כי כשנהפוך צריך להפוך אותו הפוך. הבדיקה דורשת ש-encode(buf) == cipher. אנחנו לא יודעים את הסיסמה, אבל אנחנו יודעים את cipher, את המפתח 0x37 ואת הנוסחה - וזה כל מה שצריך.

היפוך הטרנספורמציה - inverting¶

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

encode:  out = (in + i) ^ 0x37
invert:  in  = (out ^ 0x37) - i

זהו. עוברים על 16 הבתים של cipher, מפעילים את הנוסחה ההפוכה, ומקבלים את הקלט שיעבור את הבדיקה:

cipher = bytes([0x7a,0x4d,0x62,0x01,0x50,0x40,0x0e,0x4c,
                0x6f,0x0a,0x4a,0x49,0xb4,0x0a,0xb7,0x44])
plain = bytes(((c ^ 0x37) - i) & 0xff for i, c in enumerate(cipher))
print(plain)   # b'MyS3cr3tP4ssw0rd' - the input that makes encode return exactly cipher

הפעולה & 0xff שם כדי לחקות את החשבון של unsigned char (מודולו 256), בדיוק כמו שהבינארי עושה. שימו לב שאם הטרנספורמציה הייתה כוללת גם ערבוב בין בתים (למשל בית שתלוי בבית הקודם, כמו במצב CBC), היינו צריכים להפוך גם את התלות הזו - אבל העיקרון זהה: פורקים את הצינור ומפעילים כל שלב הפוך.

האתגר crypto1 מ-pwnable.kr¶

האתגר crypto1 (בקטגוריית Rookiss) בנוי בדיוק על התבנית הזו. בדף האתגר מקבלים את קוד המקור וגישה למכונה. הצורה הכללית: התוכנית לוקחת את הקלט שלכם (בדרך כלל מזהה וסיסמה מקודדים ב-hex), מריצה אותם דרך שרשרת של פענוח hex ואז טרנספורמציה סימטרית, ומשווה לערך קבוע ששמור בבינארי. אם ההשוואה מתלכדת - מקבלים את הדגל.

התהליך שלכם זהה למה שעשינו למעלה, רק עם עוד שלב או שניים של קידוד:

your input --> decode hex --> transformation (xor/permutation) --> compare to constant

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

הזכרת RSA - RSA recap¶

עכשיו לחלק השני והכבד יותר: RSA. נזכיר בקצרה איך זה עובד, כי כל התקפה שנראה נשענת על שבירה של הנחה מסוימת בתהליך.

key generation:
  choose two large primes  p, q
  n = p * q                      (the modulus, public)
  phi = (p-1) * (q-1)            (Euler's function, secret)
  choose e such that gcd(e, phi) = 1  (the public exponent, usually 65537)
  d = e^(-1) mod phi             (the private exponent, secret)

encryption:  c = m^e mod n
decryption:  m = c^d mod n

הביטחון של RSA נשען על שתי הנחות: שקשה לפרק את n לגורמים p ו-q, ושהמסר m באמת עובר את הצמצום מודולו n (כלומר m^e באמת גדול מ-n). כל אחת מההתקפות שנראה שוברת את אחת ההנחות האלה. שימו לב לנקודה מרכזית: אם התוקף משיג את phi, הוא מיד מחשב d = e^(-1) mod phi ומפענח הכל. ולהשיג את phi שקול לפרק את n, כי phi = (p-1)(q-1) = n - p - q + 1.

מלכודת ראשונה: מעריך קטן ושורש שלישי - small e cube-root¶

ההתקפה הראשונה, והנפוצה ביותר באתגרים, מנצלת מעריך פומבי קטן. נניח e = 3. ההצפנה היא c = m^3 mod n. מה קורה אם המסר m קטן, כך ש-m^3 עצמו קטן מ-n? אז הצמצום מודולו n פשוט לא קורה, כי m^3 כבר קטן מהמודולוס:

if  m^3 < n   then   c = m^3 mod n = m^3   (no reduction)
so            m = the integer cube root of c

זה הכל. במקום לפרק את n הענק, אנחנו פשוט מוציאים שורש שלישי שלם מ-c. באתגרים זה קורה כל הזמן: מצפינים דגל קצר (עשרות בתים) עם e=3 ומודולוס של 2048 ביט. הדגל כמספר הוא בערך 2^240, אז m^3 הוא בערך 2^720, שקטן בהרבה מ-n שהוא 2^2048. אין צמצום, והשורש השלישי מחזיר את המסר במדויק.

איך מחשבים שורש שלישי שלם של מספר ענק? הכי נקי עם gmpy2:

import gmpy2
from Crypto.Util.number import long_to_bytes

c = 0x....        # the ciphertext the service gave us
m, exact = gmpy2.iroot(c, 3)   # integer cube root + flag if it's exact
assert exact, "m^3 is larger than n, this attack doesn't fit"
print(long_to_bytes(int(m)))

אם אין gmpy2, שורש שלישי שלם בחיפוש בינארי הוא כמה שורות בלבד:

def icbrt(c):
    lo, hi = 0, 1 << ((c.bit_length() // 3) + 2)
    while lo < hi:
        mid = (lo + hi) // 2
        if mid**3 < c:
            lo = mid + 1
        else:
            hi = mid
    return lo

וריאציה: שידור לשלושה נמענים - Hastad broadcast¶

מה אם המסר גדול, אבל אותו m נשלח לשלושה נמענים שונים עם e=3 ושלושה מודולוסים n1, n2, n3? אז יש לנו שלוש משוואות ci = m^3 mod ni. לפי משפט השאריות הסיני - CRT - אפשר לשלב אותן למשוואה אחת מודולו n1*n2*n3, ומכיוון ש-m^3 < n1*n2*n3, השורש השלישי של התוצאה המשולבת מחזיר את m. זו הכללה יפה של אותה מלכודת: מעריך קטן פוגש כמות מספיקה של טקסטים מוצפנים.

מלכודת שנייה: מודולוס משותף - common modulus attack¶

התקפה אלגנטית שמופיעה בשירותי "מחשבון RSA": אותו מסר m מוצפן פעמיים עם אותו מודולוס n אבל שני מעריכים שונים e1, e2 שזרים זה לזה (gcd(e1, e2) = 1). זה קורה כשמשתמשים משתפים מפתח או כשהשירות מאפשר להצפין עם מעריך שהמשתמש בוחר.

יש לנו c1 = m^e1 mod n ו-c2 = m^e2 mod n. מכיוון ש-gcd(e1, e2) = 1, אלגוריתם אוקלידס המורחב נותן מקדמים שלמים a, b כך ש:

a * e1 + b * e2 = 1

עכשיו הקסם:

c1^a * c2^b  =  (m^e1)^a * (m^e2)^b
             =  m^(a*e1 + b*e2)
             =  m^1
             =  m   (mod n)

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

def egcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x, y = egcd(b, a % b)
    return (g, y, x - (a // b) * y)

g, a, b = egcd(e1, e2)
assert g == 1, "the exponents are not coprime, this attack doesn't apply as-is"
m = (pow(c1, a, n) * pow(c2, b, n)) % n

מלכודת שלישית: שחזור d על ידי פירוק n - recovering d¶

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

מספר קטן. אם n קטן מספיק (עד בערך 70-80 ספרות עשרוניות), כלים כמו sympy.factorint או השירות factordb.com מפרקים אותו ישירות. תמיד שווה לנסות קודם את factordb - אם מישהו כבר פירק את n, קיבלתם את הגורמים בחינם.

ראשוניים קרובים - Fermat. אם p ו-q קרובים זה לזה (טעות נפוצה כשמייצרים אותם ברצף), פירוק Fermat מוצא אותם מהר. הרעיון: n = a^2 - b^2 = (a-b)(a+b), אז מתחילים מ-a = ceil(sqrt(n)) ומעלים את a עד ש-a^2 - n הוא ריבוע מושלם:

from gmpy2 import isqrt
def fermat(n):
    a = isqrt(n) + 1
    while True:
        b2 = a*a - n
        b = isqrt(b2)
        if b*b == b2:
            return a - b, a + b   # p, q
        a += 1

ברגע שיש p ו-q, השאר מיידי:

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)          # the inverse of e modulo phi
m = pow(c, d, n)             # full decryption

מעריך פרטי קטן - Wiener. אם דווקא d קטן (בערך d < n^(1/4)), התקפת Wiener משחזרת אותו ישירות מ-e ו-n, בלי לפרק. היא מבוססת על כך ש-e/n קרוב מאוד ל-k/d, ואחד מהמקורבים - convergents של פיתוח שבר משולב של e/n הוא בדיוק k/d. המימוש המלא של Wiener נמצא בפתרון, כי הוא מעט ארוך, אבל העיקרון הזה - "מעריך פרטי קטן דולף דרך שברים משולבים" - שווה לזכור.

מלכודת רביעית: אורקל פענוח והסתרה - decryption oracle and blinding¶

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

הטריק נקרא הסתרה - blinding. מכיוון ש-RSA הומומורפי לכפל ((x*y)^e = x^e * y^e), אנחנו "מלבישים" את c בגורם אקראי, מבקשים לפענח את הגרסה המולבשת, ומורידים את הגורם בסוף:

choose a random r
c' = c * r^e mod n           the blinded ciphertext (different from c, so the service agrees)
m' = (c')^d = m * r mod n    the oracle decrypts it for us
m  = m' * r^(-1) mod n       remove r and get the original message

השירות אף פעם לא ראה את c, ובכל זאת פענחנו אותו. בקוד:

r = random.randrange(2, n)
c_blind = (c * pow(r, e, n)) % n
m_blind = oracle_decrypt(c_blind)          # the service decrypts the blinded version
m = (m_blind * pow(r, -1, n)) % n          # r^(-1) mod n

אותו רעיון בדיוק מאפשר לזייף חתימה: אם השירות חותם (מעלה בחזקת d) על כל הודעה חוץ מזו שאתם רוצים, מלבישים אותה, מבקשים חתימה, ומורידים את ההסתרה. RSA גולמי בלי padding כמו OAEP או padding חתימה נכון תמיד vulnerable להסתרה הזו.

כלים - the toolbox¶

לאתגרי הקריפטו האלה, אלה הכלים שתרצו מותקנים:

pip install pycryptodome gmpy2 sympy
# pycryptodome: bytes_to_long, long_to_bytes, inverse, getPrime
# gmpy2:        iroot (integer root), isqrt, fast operations on huge numbers
# sympy:        factorint, primes, continued fractions

הספרייה pwntools היא מה שמחבר אתכם לשירות רשת ומחלץ את הפרמטרים מהפלט. SageMath היא אלטרנטיבה כבדה שמכילה את הכל (פירוק, אלגברה, שבר משולב) ושווה להכיר, אבל לרוב האתגרים פייתון עם שלוש הספריות למעלה מספיק בהחלט.

הנה שלד pwntools מלא שמתחבר לשירות RSA, מושך את n, e, c, ומריץ את התקפת השורש השלישי. זה בדיוק המבנה שתבנו עליו את הפתרון:

from pwn import *
import gmpy2
from Crypto.Util.number import long_to_bytes

def grab_int(io, prefix):
    # reads a line of the form "name = 12345" and returns the number
    line = io.recvline_startswith(prefix.encode())
    return int(line.split(b'=')[1].strip())

io = remote('localhost', 1337)      # or process(['python3','rsa_service.py'])
n = grab_int(io, 'n')
e = grab_int(io, 'e')
c = grab_int(io, 'c')
log.info(f"e = {e}, n has {n.bit_length()} bits")

assert e == 3, "this attack only fits a small exponent"
m, exact = gmpy2.iroot(c, 3)
assert exact, "no exact cube root - try a different attack"

flag = long_to_bytes(int(m))
log.success(f"flag: {flag.decode(errors='replace')}")
io.close()

שימו לב שהבדיקה assert exact היא רשת ביטחון: היא אומרת לכם מיד אם המסר גדול מדי והשורש השלישי לא ישים, כדי שתעברו להתקפה מתאימה אחרת במקום לרדוף אחרי תוצאה שגויה.

סיכום¶

בהרצאה הזו למדנו איך ניגשים לאתגרי קריפטו בעולם ה-pwn:

הלך הרוח: לא שוברים קריפטו חזק, מזהים את הפרמטר שנבחר רע והופכים את הבדיקה. שלושת השלבים: מה נדרש, איזו טרנספורמציה חוסמת, איך הופכים אותה.
צופן מבוסס xor הפיך בטריוויאליות כי (a ^ k) ^ k = a. מפרקים את הצינור ומפעילים כל שלב בהיפוך, בסדר הפוך. זו הצורה של האתגר crypto1.
הצפנת RSA עם מעריך קטן ו-m^3 < n: אין צמצום מודולרי, ולכן שורש שלישי שלם של c מחזיר את המסר. ההכללה לשלושה נמענים היא Hastad עם CRT.
מודולוס משותף: אותו m עם שני מעריכים זרים מאפשר לחלץ את m דרך אוקלידס המורחב, בלי d ובלי פירוק.
שחזור d: מפרקים את n כשהוא קטן (factordb, sympy), כשהראשוניים קרובים (Fermat), או משחזרים d קטן ישירות (Wiener). ואז d = e^(-1) mod phi.
אורקל פענוח: התכונה ההומומורפית של RSA מאפשרת הסתרה - c' = c * r^e - כדי לפענח או לזייף חתימה על טקסט שהשירות סירב לגעת בו.
הכלים: pycryptodome, gmpy2, sympy, ו-pwntools לחיבור לשירות. תמיד לאמת את התוצאה מול המודל של הקורבן לפני שמכריזים על הצלחה.