AlpacaHack Round 12

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ã $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 $b$ bất kì thì hàm bytes_to_long sẽ chuyển đổi giá trị từ bytes sang số nguyên như sau

b y t es - t o - l o n g (b) = i = 0 \sum l e n (b) - 1 b [i] \times 25 6^{l e n (b) - 1 - i}

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

m = 1337 f ∥ f ∥...∥ f

Cho nên

m = f \times 25 6^{26 (1337 - 1)} + f \times 25 6^{26 (1337 - 2)} + ... + f \times 25 6^{0} ⟹ m = f \times i = 0 \sum k - 1 B^{l i}

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

c = m^{e} = (f \times S)^{e} mod n

trong đó $S = i = 0 \sum 1336 25 6^{26 i}$ . Suy ra $f^{e} = c \times S^{- e} mod n$ . Đa thức mà ta khởi tạo sẽ là $f (x) = x^{e} - c^{'} mod n$ với $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ị $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à $k_{0}, k_{1}$ được tính

k_{0} = a B_{x} k_{1} = a (B - A)_{x}

Nó sẽ lấy tọa độ $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 $B$ khác nhau.

Đầu tiên để tính lại $k_{0}$ thì ta cần gửi $B = G$ thì lúc này $k_{0} = a G_{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à $k_{1}$ . Ta có thể tính được giá trị này bằng cách cho $B = G + A$ . Khi đó

a (B - A) = a G = A

Cuối cùng là làm thế nào để tính $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 $B = \frac{A}{2}$ . Thì khi đó

k_{0} = \frac{a A}{2} [x] k_{1} = \frac{- a A}{2} [x]

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())

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.

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

Ta có tổng cộng 10 cặp giá trị $(x_{i}, y_{i})$ nhưng các giá trị $y_{i}$ bị cắt mất đi các số cuối.
Việc cắt đi như vậy ảnh hưởng như thế nào tới các số $y_{i}$ gốc?

1 kí tự hex tương đương với 4 bit nên khi bỏ đi 1 kí tự hex ở cuối đồng nghĩa với việc ta đã bỏ đi 4 LSB của giá trị $a$ . Như vậy với $b$ là $a$ sau đi cắt đi 4 LSB thì ta sẽ có $a = b \times 16 + r$ trong đó $r$ là phần đã bị cắt đi.
Suy ra, với mỗi $y_{i} \sim$ là giá trị sau khi bị thay đổi thì ta có

y_{i} = y_{i} \sim \times 1 6^{i} + e_{i}

Crypto and Math

Trong bài này

AlpacaHack Round 12 - Crypto

RSARSARSARSARSARSA

OTEC

Biểu Đồ

Bảng Nội Dung

Crypto and Math

Trong bài này

AlpacaHack Round 12 - Crypto

RSARSARSARSARSARSA

OTEC

Flag Sharing

Biểu Đồ

Bảng Nội Dung