پرش به محتویات

چالش brainrot13

Cover

تحلیل اولیه داده‌های چالش

در ابتدا چالش کد زیر همراه را با خروجی آن به ما داده است:

chall.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import bytes_to_long, getPrime
import codecs
import re

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 3

flag = 'UMDCTF{redacted}'
assert re.fullmatch("UMDCTF\\{[a-z]+\\}", flag)
assert len(flag) == 28
rotflag = codecs.encode(flag, 'rot13')

def encrypt(b):
    while (len(b) < 120):
        # Optimal Asymmetric Encryption Padding
        b += b'OAEP'
    pt = bytes_to_long(b)
    return pow(pt, e, n)

print(f"n = {n}")
print(f"ct1 = {encrypt(flag.encode())}")
print(f"ct2 = {encrypt(rotflag.encode())}")

n = 96685821958083526684938680238271304286887980859392922334047044570819254535637534763165507014186569373580269436562287115575895071477094697751185058766474544708343165263644182297048851208627306861544906558700694910255483830223450427540731613986917757415247541102253686241820221043700623282515147528145504812161
ct1 = 31415617614942980419493801728329478459882170524654275330189702271291172239569974917796230082992620119324013322311500280165046115132115888952730272833129650105740565501270236988682510607126061981801996717672566496111413558704046446132351270004211376270714769910968931266620926532143617027921568831958784579911
ct2 = 72563774621694978528581466712845934115989091233025298416607646944054938010207983336599181951465053976617135146411342652500844040957885351294246597514830545442455636203961703603515841401653220929094734409672423770927867923227749902813163411103868690480354808090999202815188200468063383568781761012284874177390

اولین نکته که به چشم می خورد مقدار کوچک e=3 است . سپس میبینیم که مقدار فلگ و مقدار با(rotated) آن یک مقدار ثابت "OAEP" اصطلاحا pad می شود سپس رمز می‌شود. به عنوان مثال برای پرچم فرضی 'UMDCTF{helloooooooooooooooo}' دو پیام زیر قبل از رمز شدن به صورت زیرهستند.

b1=b'UMDCTF{helloooooooooooooooo}OAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEP'
b2=b'HZQPGS{uryybbbbbbbbbbbbbbbb}OAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEPOAEP'

حل چالش

پس مقادیر رمز را به صورت زیر خواهد بود:

ct_1=(flag||P)^3 \mod n \\ ct_2=(rot13(flag)||P)^3 \mod n

که در آن مقدار pad یعنی P برای هردو ثابت و یکسان است.این سوال شبیه به سوال Redundancy است که در آن یک مقدار ثابت به عنوان pad به متن فلگ چسبیده است. به خاطر همین در این سوال بدون در نظر گرفتن ct_2 فلگ رو بدست می آوریم. برای نمایش ریاضی و تبدیل فلگ به مرتبه ای با اندازه pad از مقدارK=256^{92} استفاده می کنیم و

(Flag×K+P)^3≡ct_1 \mod n

نکته

مقدار K براساس طول pad یعنی 92 و تعداد حالات بیت یک کاراکتر 8 بیتی یعنی 256 حالت تعیین می‌شود.

پس رابطه ریاضی آن به شکل زیر است که در آن x مجهول و مقدار فلگ است

(x⋅K+P)^{3}-ct_{1} \equiv 0 \mod n

طبق Coppersmith اگر در رمزنگاری RSA مقدار e=3 و مقدار pad رندم اضافه شده متن کوچک باشد با f نسبت به n به اندازه کافی کوچک باشد، می‌توانیم ریشه صحیح F را از معادله پیدا کنیم. پس براساس معادله درجه سه

f(x)=x^{3}+ax^{2}+bx+c \mod n

در آن

a=3⋅P⋅K^{−1} \mod n\\ b=3⋅(P⋅K^{−1})^{2} \mod n\\ c=(P^3−ct_{1})⋅K^{−3} \mod n\\

حال می توانیم مقدار ریشه معادله که همان فلگ خواهد بود بدست بیاوریم.

solve.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from Crypto.Util.number import *
import codecs

n = 96685821958083526684938680238271304286887980859392922334047044570819254535637534763165507014186569373580269436562287115575895071477094697751185058766474544708343165263644182297048851208627306861544906558700694910255483830223450427540731613986917757415247541102253686241820221043700623282515147528145504812161
ct1 = 31415617614942980419493801728329478459882170524654275330189702271291172239569974917796230082992620119324013322311500280165046115132115888952730272833129650105740565501270236988682510607126061981801996717672566496111413558704046446132351270004211376270714769910968931266620926532143617027921568831958784579911
ct2 = 72563774621694978528581466712845934115989091233025298416607646944054938010207983336599181951465053976617135146411342652500844040957885351294246597514830545442455636203961703603515841401653220929094734409672423770927867923227749902813163411103868690480354808090999202815188200468063383568781761012284874177390
e = 3


padding = b'OAEP' * 23
P = bytes_to_long(padding)
K = 256 ** len(padding)  # 256^92


g = gcd(K^3, n)
if g == 1:
    inv_K3 = inverse(K^3, n)
    R.<x> = PolynomialRing(Zmod(n))
    a = 3 * P * inverse(K, n) % n
    b = 3 * (P * inverse(K, n))^2 % n
    c = (P^3 - ct1) * inv_K3 % n

    f = x^3 + a*x^2 + b*x + c

    bound = 256^28

    roots = f.small_roots(X=bound, beta=0.5, epsilon=0.05)

    if roots:
        F = roots[0]
        flag = long_to_bytes(int(F))
        print("Found flag:", flag.decode())
FLAG 🚩

UMDCTF{shouldverotatedtwice}

نویسنده

HIGHer