AlpacaHack Round 12 (Crypto)

RSARSARSARSARSARSA

Source code của bài:

from math import gcd
import os
from Crypto.Util.number import getPrime, bytes_to_long

e = 19
while True:
    p = getPrime(2048)
    q = getPrime(2048)
    if gcd((p - 1) * (q - 1), e) == 1:
        break
n = p * q

flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}")
assert len(flag) == 26 and flag.startswith("Alpaca{") and flag.endswith("}")

m = bytes_to_long((flag * 1337).encode())
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
'''
n = 434245275129793896913302623186216967500119715299127153234221039838158526818290666891561167619572507897277032319251523352710966722158326513857889678449160348496647427753832233179173745189495799707833020232209447520485615893168704144655033371807912826948460011240258726843346618328839282439390863464375320181495406806870462330735361196286553150480225927729088313551861682406252457739974850015509783430978939475350707211461876140420181118923743456062581297038004651412953310377554877499792225388059857865550418697212704277742826280689987165702071346542831836616149138379224837551040036947064990027047482745931141458056028719767845142490618375017582275824317241572815337810658684051187938258804346960781372035972758516593800419459342799854863845667715099378564373594732798224797622583907677749880918106223965727445907355069025939554400938193579295415911074889648122298896605189398591684277376327938718166279159875826993866460251900514487349848332991005775574378131897581182876147580659857596204121970624162722935263271888969020482566142620134100258216288390250174699829806817678453601913377347867137739622906815272561714188564065071077762169177825466514512198167566882661748389120146622447920498988341055543170346944366105037929197965527
e = 19
c = 78338816976998323261765735600063671710448529902850366859501110834174319629348492230679353792803618614020892663940158627385470036549819116375194598599193512981265682997072278631964394686243958989105159463105190885437258093111178664394786430767942639437287236999171486583513816766766869843448941665224796216610702708658300011987744401747551989248270799179750556330952646223694000679475842632497149402602469848595868051660228892506097962300820851000134370939783634534516434054009303981106884637932006844265722691022870174977860945699441650254771777451995160642261482879537396171107016491225773397809485749640163676209732235156461483660111845782227127763086286553520914359194795617080980736767821995556156173267185240945707717461037831992544868933876015548419376861213017988005848033349136839971120363078490938026883354839573512645985195570831018461470031329716026531550172207332072481279548470657090575709419245114386419567236219816237412255505882075283974654569995321334498673793010812162088796252555619242463561750801895032793870706949913548310632113206159695535952422316840587214237406730422405058644629458566515378607614900910335034732797410592671297941526063690060922625005949094383664832255082556088451940780657576420871470920836
'''

Có hai điểm đáng chú ý ở bài này: Đầu tiên số mũ lập mã $\displaystyle e$ khá nhỏ so với modulo và flag được lặp cấu trúc lại nhiều lần.

Đầu tiên với $\displaystyle b$ bất kì thì hàm bytes_to_long sẽ chuyển đổi giá trị từ bytes sang số nguyên như sau

\[\begin{equation*} bytes-to-long(b)=\sum_{i=0}^{len( b) -1} b[ i] \times 256^{len( b) -1-i} \end{equation*}\]

Mà flag được lặp lại 1337 lần cho nên

\[\begin{equation*} m=\underbrace{f\| f\| ...\| f}_{1337} \end{equation*}\]

Cho nên

\[\begin{gather*} m=f\times 256^{26( 1337-1)} +f\times 256^{26( 1337-2)} +...+f\times 256^{0}\\ \Longrightarrow m=f\times \sum_{i=0}^{k-1} B^{li} \end{gather*}\]

trong đó $\displaystyle l=26$ là độ dài của flag và $\displaystyle k=1337,B=256$. Ta sẽ tính small roots ở bước kế tiếp. Cụ thể

\[\begin{equation*} c=m^{e} =( f\times S)^{e}\bmod n \end{equation*}\]

trong đó $\displaystyle S=\sum _{i=0}^{1336} 256^{26i}$. Suy ra $\displaystyle f^{e} =c\times S^{-e}\bmod n$. Đa thức mà ta khởi tạo sẽ là $\displaystyle f( x) =x^{e} -c’\bmod n$ với $\displaystyle c’=c\times S^{-e}$

Solve script:

from sage.all import *
from Crypto.Util.number import *
n = 434245275129793896913302623186216967500119715299127153234221039838158526818290666891561167619572507897277032319251523352710966722158326513857889678449160348496647427753832233179173745189495799707833020232209447520485615893168704144655033371807912826948460011240258726843346618328839282439390863464375320181495406806870462330735361196286553150480225927729088313551861682406252457739974850015509783430978939475350707211461876140420181118923743456062581297038004651412953310377554877499792225388059857865550418697212704277742826280689987165702071346542831836616149138379224837551040036947064990027047482745931141458056028719767845142490618375017582275824317241572815337810658684051187938258804346960781372035972758516593800419459342799854863845667715099378564373594732798224797622583907677749880918106223965727445907355069025939554400938193579295415911074889648122298896605189398591684277376327938718166279159875826993866460251900514487349848332991005775574378131897581182876147580659857596204121970624162722935263271888969020482566142620134100258216288390250174699829806817678453601913377347867137739622906815272561714188564065071077762169177825466514512198167566882661748389120146622447920498988341055543170346944366105037929197965527
e = 19
c = 78338816976998323261765735600063671710448529902850366859501110834174319629348492230679353792803618614020892663940158627385470036549819116375194598599193512981265682997072278631964394686243958989105159463105190885437258093111178664394786430767942639437287236999171486583513816766766869843448941665224796216610702708658300011987744401747551989248270799179750556330952646223694000679475842632497149402602469848595868051660228892506097962300820851000134370939783634534516434054009303981106884637932006844265722691022870174977860945699441650254771777451995160642261482879537396171107016491225773397809485749640163676209732235156461483660111845782227127763086286553520914359194795617080980736767821995556156173267185240945707717461037831992544868933876015548419376861213017988005848033349136839971120363078490938026883354839573512645985195570831018461470031329716026531550172207332072481279548470657090575709419245114386419567236219816237412255505882075283974654569995321334498673793010812162088796252555619242463561750801895032793870706949913548310632113206159695535952422316840587214237406730422405058644629458566515378607614900910335034732797410592671297941526063690060922625005949094383664832255082556088451940780657576420871470920836
bound = 2 ** (8 * 26)
S = sum([256 ** (26 * i) for i in range(1337)])
S_inv_e = pow(S, -e, n)
c_prime = (c * S_inv_e) % n
PR = PolynomialRing(Zmod(n), 'x')
x = PR.gen()
f = x**e - c_prime
roots = f.small_roots(X=bound, beta=0.4)
for r in roots:
    try:
        temp = int(r).to_bytes(26, 'big')
        if b"Alpaca{" in temp and temp.endswith(b"}"):
            print(temp.decode())
            break
    except:
        continue
else:
    print("fail")

OTEC

Source code:

import os
import signal
import secrets
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes

signal.alarm(60)

flag = os.environ.get("FLAG", "Alpaca{**** REDACTED ****}").encode()

# Oblivious Transfer using Elliptic Curves
G = secp256k1.G
a = secrets.randbelow(secp256k1.q)
A = a * G

print(f"{A.x = }")
print(f"{A.y = }")

x, y = map(int, input("B> ").split(","))
B = Point(x, y, secp256k1)

k0 = long_to_bytes((a * B).x, 32)
k1 = long_to_bytes((a * (B - A)).x, 32)

def encrypt(message, key):
    return AES.new(key, AES.MODE_ECB).encrypt(pad(message, 16))

print(encrypt(flag[0::3], k0).hex())
print(encrypt(flag[1::3], k1).hex())
print(encrypt(flag[2::3], bytes(c0 ^ c1 for c0, c1 in zip(k0, k1))).hex())

Tóm tắt: Bài kết hợp giữa Oblivious Transfer và ECC. Cụ thể nó sẽ tính hai giá trị $\displaystyle k_{0} ,k_{1}$ từ input và dùng làm key để mã hóa flag. Tiếp theo ta quan sát cách mà $\displaystyle k_{0} ,k_{1}$ được tính

\[\begin{gather*} k_{0} =aB_{x}\\ k_{1} =a( B-A)_{x} \end{gather*}\]

Nó sẽ lấy tọa độ $\displaystyle x$ của các điểm trên. Để giải bài này thì ta cần gửi 3 lần với 3 điểm $\displaystyle B$ khác nhau.

Đầu tiên để tính lại $\displaystyle k_{0}$ thì ta cần gửi $\displaystyle B=G$ thì lúc này $\displaystyle k_{0} =aG_{x} =A_{x}$ và giá trị này server cho ta biết mỗi lần truy vấn đến.

Tiếp theo là $\displaystyle k_{1}$. Ta có thể tính được giá trị này bằng cách cho $\displaystyle B=G+A$. Khi đó

\[\begin{equation*} a( B-A) =aG=A \end{equation*}\]

Cuối cùng là làm thế nào để tính $\displaystyle k_{0} \oplus k_{1}$. Cách đơn giản nhất là làm cho giá trị này triệt tiêu bằng cách chọn $\displaystyle B=\frac{A}{2}$. Thì khi đó

\[\begin{gather*} k_{0} =\frac{aA}{2}[x]\\ k_{1} =\frac{-aA}{2}[x] \end{gather*}\]

Và khi xor hai giá trị này lại thì ta được NULL key. Do ta đang làm việc trên nhóm các điểm trên đường cong nên phép chia 2 tương đương với phép nhân nghịch đảo theo modulo order.

Script solve:

from pwn import remote
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import long_to_bytes
from itertools import zip_longest

def decrypt(ciphertext, key):
    return unpad(AES.new(key, AES.MODE_ECB).decrypt(ciphertext), 16)

host = "34.170.146.252"
port = 62340
G = secp256k1.G

def get_flag_part_1():
    r = remote(host, port)
    A_x = int(r.recvline().decode().split('=')[1])
    A_y = int(r.recvline().decode().split('=')[1])
    A = Point(A_x, A_y, secp256k1)
    r.sendline(f"{G.x}, {G.y}".encode())
    r.recvuntil('B>')
    ct0 = r.recvline().decode().strip()
    ct1 = r.recvline().decode().strip()
    ct2 = r.recvline().decode().strip()
    ct0_bytes = bytes.fromhex(ct0)
    key = long_to_bytes(A.x, 32)
    r.close()
    return decrypt(ct0_bytes, key)

def get_flag_part_2():
    r = remote(host, port)
    A_x = int(r.recvline().decode().split('=')[1])
    A_y = int(r.recvline().decode().split('=')[1])
    A = Point(A_x, A_y, secp256k1)
    B = G + A
    r.sendline(f"{B.x}, {B.y}".encode())
    r.recvuntil('B>')
    ct0 = r.recvline().decode().strip()
    ct1 = r.recvline().decode().strip()
    ct2 = r.recvline().decode().strip()
    ct1_bytes = bytes.fromhex(ct1)
    key = long_to_bytes(A.x, 32)
    r.close()
    return decrypt(ct1_bytes, key)

def get_flag_part_3():
    r = remote(host, port)
    A_x = int(r.recvline().decode().split('=')[1])
    A_y = int(r.recvline().decode().split('=')[1])
    A = Point(A_x, A_y, secp256k1)
    order = secp256k1.q
    scale = pow(2, -1, order)
    B = A * scale
    r.sendline(f"{B.x}, {B.y}".encode())  
    r.recvuntil('B>')
    ct0 = r.recvline().decode().strip()
    ct1 = r.recvline().decode().strip()
    ct2 = r.recvline().decode().strip()
    ct2_bytes = bytes.fromhex(ct2)
    key = bytes([0] * 32)
    r.close()
    return decrypt(ct2_bytes, key)

if __name__ == "__main__":
    flag0 = get_flag_part_1()
    flag1 = get_flag_part_2()
    flag2 = get_flag_part_3()
    full_flag = bytes(
        [c for tup in zip_longest(flag0, flag1, flag2) for c in tup if c is not None]
    )
    print(full_flag.decode())

Flag Sharing

Source code của bài:

import os
import secrets
from Crypto.Util.number import getPrime, bytes_to_long

N = 10

def random_poly(t):
    return [secret] + [secrets.randbelow(p) for _ in range(t - 1)]

def evaluate(f, x):
    return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p

p = getPrime(512)
flag = os.environ.get("FLAG", "Alpaca{************* REDACTED *************}")
assert len(flag) == 44 and flag.startswith("Alpaca{") and flag.endswith("}")
secret = bytes_to_long(flag.encode())

xs = [secrets.randbelow(p) for _ in range(N)]
f = random_poly(N)
shares = [evaluate(f, x) for x in xs]

print(f"{p = }")
print(f"{xs = }")

for i, share in enumerate(shares, 1):
    print(hex(share)[:-i] + "?" * i)

p = 12365141388065062625077260205740439928957045314325264532059542415398828293027572720145795901343843814325416233731267497406464632644097256536195625423398329
xs = [9024669031252593327897115788636058229881883593851130409834652229020800893781516962782817569712189929166391142425795187729248117943564534157539427267590500, 11152152882093101942576045978011303484444618733519354813061575318498290787826300494915638608620977317735324643790889478037446560513035463364453543716441279, 8803735229013341319698271334776544561783985456011949104354000699623733722583973358206587557958265798130311525135964657805345666682047762837157659777561827, 11080225534044512670375167491346784128619567498763960249905467202817579825590747952669033375403774110858385610307092437190429868245133100184487796099009203, 7772050705584619428285655915779748018221838190050194391826189794703804391762913046416166751986327330143707735594181618718437045161386936514746718130041655, 5983489142454375601463129382251291030873841491669526200623319546244030870791372233539726708806879338050333042883945312581112156235224527627325335470544985, 1449997879651912856039054912159781623921452318720181422930018902693104010980832526151536178211389322386637691746213540660946033065614476870480953568160442, 563289638343122224467078928980573060897501637722249967091285678416716391884898838272314176446596029228228037030755737228223389202899122245854189369787494, 8505872836322254516510398100622100799568153459773201713556239118784359913601631340775091026774521383968068171494002014456159666069488857675856540983464174, 9988647067555581744324368769053700608242142012794052062158039897790485307686423023280316156819362786770896738794473777882784228477666060958140320376362290]
0x7ce981caac3eb64a330a1d0b681bd8891d7150cc26dacad5321fd803da1e445d96b0b41cd321a20d70c4abcbec401e9cdb1302b9e79af5ac8ecb5d7fbd6b050?
0x63cb7758413076cdd0b228a450374cea7577ff654395ac1e4d476a0e6990934dc854113051b653b9f9fb07a6a8b28aeecea9e1e2c053cfc838f549a990c79b??
0x5f2f515e27360d910011ebee8ee19cf87465ed48456ee04e117716adb2281c6c852f965ea3d5d8fb4025ff0dc765951781d49a79e450bee63a08e91d85d05???
0xcc16afb27a25961a2dfc29fa2a35e09edad115a87b07743bf2ec6d7743d4b63b962d75483efd8ba3aa4c773a92b9e87a8df00ba9c750828e733b301c2589????
0x7df5507fb88045a930b3227507672cbf91ced9ffd8c6fbc267a2cd621dbaa2d1bf7c6b6ffe6a6d33311428aad769266841916e5876309676b68e42d64e4?????
0xbd440fabdc813ee80f004034abd58301a2cc26bb5bf5a5b94e0b70706567e3847daaacb7427398095777569c3238c465888fa4fab0604e7bb2223994c4??????
0x528c49cb064b2cb6599880467d9216043f201ee6196c138eebf327953154483dd2f3b1f476df57e4ce6ae2f53bc23aede3393ba6e95bc38bc5b747ade???????
0x4bbd9e18c7b6bd0db9deeb30c8c027da2fe1a571f29438817bf63d26b7de3c28b45a908c4d7ae94b823835258bb56fe274bf20bc7f8d22213327baca????????
0x9c965b01b1e792011a564273b5ee0bb8f793d0cba75e481751cf63f69ec4dd769d1a53d4599fbe79afb1ad60ae6063cd7ff5089aa07823020f0791e?????????
0x93d6450c530d023ad2fdacb797c1d20293965a5231f009f64d90d7b1c1f08774dbeac3b7e7e3fce5ac28fcaa61cd2704c7d847e97c19cc62c970e??????????

Phân tích: Bài này sử dụng Shamir’s Secret Sharing Scheme nhưng một phần của các giá trị shares bị mất đi. Vậy ta cần phải tìm cách để khôi phục lại các giá trị shares này.