bi0sCTF 2024
Tuần trước, mình có chơi bi0sCTF với team G.0.4.7 và làm được 5/6 bài crypto. Sau đây là chi tiết write-up cho những bài mình làm được (và có thể update luôn bài cuối nếu làm ra 😥)
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
lalala - 80 solves
- out.py
- Đây là một bài đơn giản về giải hệ phương trình. Ở đây đề bài tạo ra một mảng
unknows
chưa biết, sau đó thực hiện các phép tính gì đó trên unknows
. Nhận thấy rằng nếu có được unknows
thì ta dễ dàng tìm được flag bằng cách chia lấy dư mỗi phần tử cho 1000 nhờ vào dòng này.
- Mục tiêu chính của ta là phải tìm bằng được
unknows
. Chương trình sẽ tạo ra các mảng aa, bb, cc, sau đó thực hiện phép tính sau:
Vì aa đã biết => tổng các a cũng đã có, coi unknows[b]^2*unknowns[c]^3 := u_{10b+c}
, ta có thể dễ dàng lập được 1 phương trình 100 ẩn từ u0 đến u99. Để ý rằng chương trình tạo ra 100 lần lặp như vậy, do đó ta cũng thu được 100 phương trình tương ứng. Vấn đề còn lại bây giờ chỉ là giải hệ phương trình, còn việc giải như thế nào chắc mọi người đều biết rồi ha :)).
Image Not Showing
Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
challengename - 54 solves
from ecdsa.ecdsa import Public_key, Private_key
from ecdsa import ellipticcurve
from hashlib import md5
import random
import os
import json
flag = open("flag", "rb").read()[:-1]
magic = os.urandom(16)
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a =
b =
G =
q = G.order()
def bigsur(a,b):
a,b = [[a,b],[b,a]][len(a) < len(b)]
return bytes([i ^ j for i,j in zip(a,bytes([int(bin(int(b.hex(),16))[2:].zfill(len(f'{int(a.hex(), 16):b}'))[:len(a) - len(b)] + bin(int(b.hex(),16))[2:].zfill(len(bin(int(a.hex(), 16))[2:]))[:len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:])][i:i+8], 2) for i in range(0,len(bin(int(a.hex(), 16))[2:]) - len(bin(int(b.hex(), 16))[2:]),8)]) + b)])
def bytes_to_long(s):
return int.from_bytes(s, 'big')
def genkeys():
d = random.randint(1,q-1)
pubkey = Public_key(G, d*G)
return pubkey, Private_key(pubkey, d)
def sign(msg,nonce,privkey):
hsh = md5(msg).digest()
nunce = md5(bigsur(nonce,magic)).digest()
sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nunce))
return json.dumps({"msg": msg.hex(), "r": hex(sig.r), "s": hex(sig.s)})
def enc(privkey):
x = int(flag.hex(),16)
y = pow((x**3 + a*x + b) % p, (p+3)//4, p)
F = ellipticcurve.Point('--REDACTED--', x, y)
Q = F * privkey.secret_multiplier
return (int(Q.x()), int(Q.y()))
pubkey, privkey = genkeys()
print("Public key:",(int(pubkey.point.x()),int(pubkey.point.y())))
print("Encrypted flag:",enc(privkey))
nonces = set()
for _ in '01':
try:
msg = bytes.fromhex(input("Message: "))
nonce = bytes.fromhex(input("Nonce: "))
if nonce in nonces:
print("Nonce already used")
continue
nonces.add(nonce)
print(sign(msg,nonce,privkey))
except ValueError:
print("No hex?")
exit()
- Đây là một bài về nonce reuse attack trong ECDSA. Ban đầu server cung cấp cho ta 2 điểm (1 public key và encrypted flag) nằm trên một hidden curve. Để xử lý được phần attack sau thì mình cần recover curve parameters từ 2 điểm đã cho.
Find curve parameters
Ta có phương trình curve là: , thay tọa độ của 2 điểm đã cho và giải hpt để tìm a,b:
Nonce reuse attack
- Server cho ta 2 lần ký, mỗi lần ta sẽ phải cung cấp
msg
và nonce
. Đọc trong hàm sign()
ta thấy server ký msg
với giá trị nunce=md5(bigsur(nonce,magic)).digest()
. Ta phải tìm cách cung cấp 2 giá trị nonce sao cho thu được 2 nunce giống nhau. Sau một hồi phân tích hàm bigsur()
thì mình nhận ra source code dài ngoằng của nó chỉ có tác dụng tương đương với hàm sau:
Đại khái là gán a là chuỗi bytes dài hơn, b là chuỗi bytes ngắn hơn trong 2 chuỗi a,b. Sau đó thêm null bytes vào trước chuỗi b sao cho dài bằng chuỗi a rồi xor 2 chuỗi lại.
- Nắm được điều đó, nếu gởi 2 nonce là
b'\0'
và b'\0\0'
thì chắc chắn rằng 2 nunce thu được giống nhau mặc dù không biết giá trị của magic
=> nonce reuse attack :D.
- solve.py

rr - 24 solves
Tìm ks
- Để tìm được ks, ta cần giải quyết bài toán logarit rời rạc: . Đây là các trường đặc biệt hay nói cách khác là bài toán logarithm rời rạc trên các số p-adic: Tham khảo.
Tìm flag
- Nhìn vào cách c1 và c2 được tính, ta thấy flag là nghiệm của 2 đa thức trên Zmod(n) sau:
- Do f1 và f2 có nghiệm chung => chứa nhân tử chung. Để tìm nhân tử chung thì ta tìm GCD của 2 đa thức bằng thuật toán Euclid.
- Sau khi in ra thì mình thấy r bậc nhất, do đó dễ dàng tìm nghiệm của r (cũng là nghiệm chung của f1 và f2, và cũng là flag ¯\(ツ)/¯)
Flag: bi0sctf{https://www.youtube.com/watch?v=soDR-BctVeE___1e9c4e8dba79812bd81ec4c2}
daisy_bell - 18 solves
- Đây là một bài về parital key leak trong RSA, cụ thể bài này sẽ phải sử dụng coppersmith method. Điều quan trọng trong dạng bài này chính là build đa thức sao cho hợp lý và sử dụng coppersmith (coppersmith 2 biến mình hay tham khảo của defund).
- Bài này cho ta MSB của p và LSB của q_p (
pow(q,-1,p)
), ta thực hiện một vài biến đổi sau:
Vậy ta sẽ build đa thức 2 biến trên Zmod(n**2)
- Dùng Coppersmith của defund để tìm x,y. Tuy nhiên ta cần chọn 2 tham số m,d phù hợp thì mới ra được kết quả mong muốn. Sau một hồi bruteforce thì mình tìm được m=2 và d=7. Có được x,y, ta dễ dàng tính được p và decrypt flag.
- solve.sage
Flag: bi0sctf{https://www.youtube.com/watch?v=uerNtYhgzSw___f4e2788de0dbce918e411f35}
Katyusha's Campervan - 16 solves
- Tiếp tục là một bài về partial key leak :v. Bài này cho ta LSB của dp (
pow(e,-1,p-1)
). Bài này mình build đa thức như sau:
Vậy đa thức ta build được là trên Zmod(n)
.
Defund's Coppersmith
- Cũng tương tự challenge trước, trong giải mình dùng Coppersmith của defund, không hẳn là của defund vì đã nó đã có 1 vài sửa đổi nhỏ, mình tham khảo tại đây (tại chạy code gốc ếu ra :)).
Factos: mình đã treo máy đâu đó 30 phút mới ra 😥
- Sau giải, mình mới tìm hiểu được 1 implementation tốt hơn của Coppersmith của kiona. Theo mình tìm hiểu nó sử dụng fplll và flatter để reduce lattice, vì vậy tốc độ được cải thiện đáng kể.
Decrypt flag
(đoạn này mình có tham khảo blog này của anh m1dm4n)
- Sau khi có giá trị x,k, dễ dàng tính được
p = gcd(f(x,k), n)
.
- Tới đây ta thấy flag được giấu qua c như sau:
với r = random.randint(0,n**5)
. Để bài toán trên trở về bài toán DLP thì phải làm sao để mất r
. Để ý rằng với , khi đó .
- Tới đây là bài toán DLP, dựa vào challenge trên thì ta dễ dàng tính dlog trên 2 trường con và
- Tuy nhiên , do đó việc tính dlog trên các số p-adic chỉ trả về 1 số thuộc subgroup có order của
GF(p**5)
, tương tự với q. Để tìm được "chính xác" a thì ta cần tính dlog trên 2 trường con p-1 và q-1, rồi dùng CRT đề gom lại để khôi phục a. Tuy nhiên p và q không phải là 2 smooth prime, do đó việc tính toán trên 2 trường con p-1 và q-1 là gần như bất khả thi. Tới đây đoán rằng độ dài flag chắc không vượt quá (tâm linh vl 🤣) nên mình thử tính luôn a trên subgroup có order = (dùng CRT để gộp 2 subgroup mod và ) và cuối cùng cũng recover được flag 🤣.

Hmm hình như họ cố tình padding space vào đề flag dài hơn thì phải, may là không dài quá
Flag: bi0sctf{https://www.youtube.com/watch?v=ugaq46wedOk__________09f05ff4f5d5b6c2f}