Bài đầu thì không có gì khó. Mình chỉ cần lấy ra p sử dụng factordb sau đó tiến hành decrypt là ra được flag
from Crypto.Util.number import *
n = 23690620655271165329693230765997410033604713853187305472268813793031152348107488119317901392104240429826482611449247251262846508667797483465355228800439339041030982259847598574606272955688345490638311164838117491821117626835340577511562130640807587611523935604871183668968359720411023759980144229161581597397061850707647104033348795132205561234674677139395868595692235525931999596382758921793937149945229459379437008216713404350896206374483356969246476531491049930769999387038678280465689487577291475554699094024761030833540509263174840007922218340417888061099317752496279552046029470370474619439450870110783844218281
e = 65537
ct = 11420169733597912638453974310976296342840438772934899653944946284527921765463891354182152294616337665313108085636067061251485792996493148094827999964385583364992542843630846911864602981658349693548380259629884212903554470004231160866680745154066318419977485221228944716844036265911222656710479650139274719426252576406561307088938784324291655853920727176132853663822020880574204790442647169649094846806057218165102873847070323190392619997632103724159815363319643022552432448214770378596825200154298562513279104608157870845848578603703757405758227316242247843290673221718467366000253484278487854736033323783510299081405
p = 136883787266364340043941875346794871076915042034415471498906549087728253259343034107810407965879553240797103876807324140752463772912574744029721362424045513479264912763274224483253555686223222977433620164528749150128078791978059487880374953312009335263406691102746179899587617728126307533778214066506682031517
q = n // p
d = inverse(e, (p-1)*(q-1))
print(long_to_bytes(pow(ct, d, n)))
Đọc kĩ lại đề bài, mặc dù thoạt tiên mình thấy nó chả có mẹ gì hint cả. Ai chả biết là flag format vẫn thế @@??? Tuy nhiên, do e=3, mình chợt nhớ ra có một kiểu tấn công nâng cao và mình chưa tiếp xúc nhiều lắm
Stereotyped messages
Chúng ta đều biết việc tìm nghiệm của 1 đa thức trên trường số nguyên có thể nói là rất dễ dàng. Tuy nhiên, tìm nghiệm của 1 đa thức trong 1 trường hữu hạn là một vấn đề khó để giải quyết:
f(x) = 0 mod N
Hãy ký hiệu N là một số nguyên lớn và chúng ta có đa thức nguyên đơn biến f(x) với bậc n, tức là:
Hơn nữa, giả sử có một nghiệm nguyên x0 cho phương trình modulo f(x) ≡ 0 mod N, x0 < N^(1/n). D. Coppersmith đã chỉ ra cách có thể khôi phục giá trị này trong thời gian đa thức bằng cách sử dụng định lý của Howgrave-Graham
Định lý: Xét g(x) là đa thức một biến có n đơn thức (đa thức chỉ có một số hạng) và m là một số nguyên dương. Nếu chúng ta có một số giới hạn X và các phương trình sau đúng:
sau đó g(x0) = 0 có nghiệm là một số nguyên.
Lý do sử dụng lattice:
Sau đó, bằng cách sử dụng thuật toán LLL trên lattice được thiết kế đặc biệt, trong thời gian đa thức, chúng ta có thể tìm thấy một cơ sở lattice rút gọn khác, sao cho chuẩn của vectơ ngắn nhất từ cơ sở rút gọn sẽ thỏa mãn bất đẳng thức (10) đã nêu ở trên.
Vì g(x) nằm trên mạng tinh thể nên chúng ta biết rằng:
Theo các kết quả từ định lý trên, chúng ta có thể kết luận rằng g(x) = 0 đúng với các số nguyên.
Bây giờ, hãy tưởng tượng Eve chặn được một tập hợp các tin nhắn ở dạng rõ ràng giữa Alice và Bob. Các tin nhắn là:
The password for AES usage is: 4{8dXY!
The password for AES usage is: 31kTbwj
The password for AES usage is: 2rr#ETh
···
The password for AES usage is: &H,45zU
Sau đó, Alice và Bob bắt đầu trao đổi các tệp được mã hóa bằng AES bằng mật khẩu đã giao tiếp. Nếu nhận được mật khẩu mới, họ sẽ bắt đầu sử dụng ngay lập tức. Tuy nhiên, họ nhận ra rằng điều này hoàn toàn không an toàn và đã tăng cường bảo mật bằng cách sử dụng RSA.
Giả sử Alice muốn gửi một thông điệp chuỗi mã hóa RSA s cho Bob. Đầu tiên cô ấy chuyển nó thành số nguyên m. Sau đó, cô ấy mã hóa nó bằng cách sử dụng khóa công khai Bob(N,e), tức là c = m**e mod n và gửi tin nhắn được mã hóa c qua địa chỉ không an toàn.
Khóa công khai của Bob là (N,3), trong đó độ dài bit của N là 512. Ta có thể thấy các thông điệp trên có phần đầu giống hệ nhau chỉ khác 7 bytes cuối hay còn gọi là stereotyped messages. Và chúng ta có thể dựa và điều này để khai triển cuộc tấn công. Vậy thông điệp sẽ có cấu trúc như sau:
s' = "The password for AES usage is: C1C2…C7"
Mục tiêu sẽ là tìm nghiệm x của đa thưc có dạng như sau:
Ta sẽ tách phần đầu của thông điệp ra và thêm các bytes b'\x00' vào cuối.
sage: padding = b'\x00'*7
sage: B = b'The password for AES usage is: '
sage: a = B + padding
sage: a
b'The password for AES usage is: \x00\x00\x00\x00\x00\x00\x00'
sage: x = b'\xff'*7
Để minh họa cuộc tấn công tốt hơn, chúng ta sẽ xây dựng một đa thức nhiều biến trên vành số nguyên, thay vì một biến.
sage: R.<X,N,a,c> = ZZ[]
Bây giờ, chúng ta đã sẵn sàng xây dựng đa thức f(X):
sage: f = (X+a)**3 - c
sage: f
X^3 + 3*X^2*a + 3*X*a^2 + a^3 - c
Lattice của ta đã sẵn sàng. Chúng ta có thể bắt đầu thuật toán LLL:
sage: B = M.LLL()
Vectơ ngắn nhất B[0] trong cơ sở rút gọn của chúng ta chứa các hệ số mà chúng ta cần để xây dựng đa thức g trên vành hữu tỉ. Chúng ta có thể dễ dàng xây dựng nó bằng cách sử dụng SageMath
sage: R.<x> = QQ[]
sage: Q = sum([B[0][i]*(x**i)/(X_const**i) for i in range(4)])
Theo định lý đã nêu, đa thức cuối cùng phải có nghiệm là các số nguyên. Và thực sự như vậy:
sage: sol = Q.roots(ring=ZZ)[0][0]
sage: type(sol)
<type ’sage.rings.integer.Integer’>
Như vậy sol chính là giá trị mà ta cần tìm.
Solution
Đống lý thuyết thì có vẻ lú. Sau cùng, nếu đã hiểu sơ qua, bạn chỉ cần tìm một script thực hiện cuộc tấn công này và thay một số tham số để cho phù hợp
Ở đây, do không biết độ dài của đoạn flag chưa biết, mình sẽ bruteforce nó:
from Crypto.Util.number import *
from sage.all import *
from tqdm import tqdm
n = 103805634552377307340975059685101156977551733461056876355507089800229924640064014138267791875318149345634740763575673979991819014964446415505372251293888861031929442007781059010889724977253624216086442025183181157463661838779892334251775663309103173737456991687046799675461756638965663330282714035731741912263
e = 3
c = 24734873977910637709237800614545622279880260333085506891667302143041484966318230317192234785987158021463825782079898979505470029030138730760671563038827274105816021371073990041986605112686349050253522070137824687322227491501626342218176173909258627357031402590581822729585520702978374712113860530427142416062
known = b"squ1rrel{"
known_int = bytes_to_long(known)
for i in tqdm(range(100)):
try:
x = PolynomialRing(Zmod(n), 'x').gen()
f = (known_int * 2**(i * 8) + x)**e - c
ans = f.small_roots(X = 2**(i * 8), beta = 0.5)[0]
print(known.decode() + long_to_bytes(int(ans)).decode())
break
except:
continue
Bằng 1 cách nào đó, khi mình thử các script khác thì cái của mình nhanh vl :v
Squ1rrel treasury
Description:
We recently opened a new bank, our exchange rate is pretty poor though
nc treasury.squ1rrel-ctf-codelab.kctf.cloud 1337
Attachment:
chal.py
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Util.strxor import strxor
from Crypto.Cipher import AES
import os
from secrets import KEY, FLAG
import random
ACCOUNT_NAME_CHARS = set([chr(i) for i in range(ord('a'), ord('z')+1)] + [chr(i) for i in range(ord('A'), ord('Z')+1)])
FLAG_COST = random.randint(10**13, 10**14-1)
def blockify(text: str, block_size: int):
return [text[i:i+block_size] for i in range(0, len(text), block_size)]
def pad(blocks: list, pad_char: chr, size: int):
padded = []
for block in blocks:
tmp = block
if len(block) < size:
tmp = tmp + pad_char*(size-len(tmp))
elif len(block) > size:
print("Inconsistent block size in pad")
exit(1)
padded.append(tmp)
return padded
class Account:
def __init__(self, iv: bytes, name: str, balance: int):
self.__iv = iv
self.__name = name
self.__balance = balance
def getIV(self):
return self.__iv
def getName(self):
return self.__name
def getBalance(self):
return self.__balance
def setBalance(self, new_balance):
self.__balance = new_balance
def getKey(self):
save = f"{self.__name}:{self.__balance}".encode()
blocks = blockify(save, AES.block_size)
pblocks = pad(blocks, b'\x00', AES.block_size)
cipher = AES.new(KEY, AES.MODE_ECB)
ct = []
for i, b in enumerate(pblocks):
if i == 0:
tmp = strxor(b, self.__iv)
ct.append(cipher.encrypt(tmp))
else:
tmp = strxor(strxor(ct[i-1], pblocks[i-1]), b)
ct.append(cipher.encrypt(tmp))
ct_str = f"{self.__iv.hex()}:{(b''.join(ct)).hex()}"
return ct_str
def load(key: str):
key_split = key.split(':')
iv = bytes.fromhex(key_split[0])
ct = bytes.fromhex(key_split[1])
cipher = AES.new(KEY, AES.MODE_ECB)
pt = blockify(cipher.decrypt(ct), AES.block_size)
ct = blockify(ct, AES.block_size)
for i, p in enumerate(pt):
if i == 0:
pt[i] = strxor(p, iv)
else:
pt[i] = strxor(strxor(ct[i-1], pt[i-1]), p)
pt = b''.join(pt)
pt_split = pt.split(b':')
try:
name = pt_split[0].decode()
except Exception:
name = "ERROR"
balance = int(pt_split[1].strip(b'\x00').decode())
return Account(iv, name, balance)
def accountLogin():
print("\nPlease provide your account details.")
account = input("> ").strip()
account = Account.load(account)
print(f"\nWelcome {account.getName()}!")
while True:
print("What would you like to do?")
print("0 -> View balance")
print(f"1 -> Buy flag ({FLAG_COST} acorns)")
print("2 -> Save")
opt = int(input("> ").strip())
if opt == 0:
print(f"Balance: {account.getBalance()} acorns\n")
elif opt == 1:
if account.getBalance() < FLAG_COST:
print("Insufficient balance.\n")
else:
print(f"Flag: {FLAG}\n")
account.setBalance(account.getBalance()-FLAG_COST)
elif opt == 2:
print(f"Save key: {account.getKey()}\n")
break
def accountNew():
print("\nWhat would you like the account to be named?")
account_name = input("> ").strip()
dif = set(account_name).difference(ACCOUNT_NAME_CHARS)
if len(dif) != 0:
print(f"Invalid character(s) {dif} in name, only letters allowed!")
print("Returning to main menu...\n")
return
account_iv = os.urandom(16)
account = Account(account_iv, account_name, 0)
print(f"Wecome to Squirrel Treasury {account.getName()}")
print(f"Here is your account key: {account.getKey()}\n")
if __name__ == "__main__":
while True:
print(r"""
⠀⠀⠀⠀⠀⠀⠀ ⢀⣀⣤⣄⣀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⢴⣶⠀⢶⣦⠀⢄⣀⠀⠠⢾⣿⠿⠿⠿⠿⢦⠀⠀ ___ __ _ _ _/ |_ __ _ __ ___| |
⠀⠀⠀⠀⠀⠀⠀⠀⠺⠿⠇⢸⣿⣇⠘⣿⣆⠘⣿⡆⠠⣄⡀⠀⠀⠀⠀⠀⠀⠀/ __|/ _` | | | | | '__| '__/ _ \ |
⠀⠀⠀⠀⠀⠀⢀⣴⣶⣶⣤⣄⡉⠛⠀⢹⣿⡄⢹⣿⡀⢻⣧⠀⡀⠀⠀⠀⠀⠀\__ \ (_| | |_| | | | | | | __/ |
⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣶⣤⡈⠓⠀⣿⣧⠈⢿⡆⠸⡄⠀⠀⠀⠀|___/\__, |\__,_|_|_| |_| \___|_|
⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⣈⠙⢆⠘⣿⡀⢻⠀⠀⠀⠀ |_|
⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠀⠹⣧⠈⠀⠀⠀⠀ _____
⠀⠀⠀⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠈⠃⠀⠀⠀⠀/__ \_ __ ___ __ _ ___ _ _ _ __ ___ _ _
⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠁⠀⠀⠀⠀⠀ / /\/ '__/ _ \/ _` / __| | | | '__/ _ \ | | |
⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠀⠀⠀⠀⠀⠀ / / | | | __/ (_| \__ \ |_| | | | __/ |_| |
⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠀⠀⠀⠀⠀⠀⠀ \/ |_| \___|\__,_|___/\__,_|_| \___|\__, |
⠀⠀⠀⢹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀ |___/
⠀⠀⠀⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢠⣿⣿⠿⠿⠿⠿⠿⠿⠟⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
""")
print("Welcome to squ1rrel Treasury! What would you like to do?")
print("0 -> Login")
print("1 -> Create new account")
opt = int(input("> ").strip())
if opt == 0:
accountLogin()
elif opt == 1:
accountNew()
Solution:
Với bài này, khi kết nối tới server, ta sẽ có 2 lựa chọn là tạo tài khoản hoặc login. Với chức năng tạo tài k
def accountNew():
print("\nWhat would you like the account to be named?")
account_name = input("> ").strip()
dif = set(account_name).difference(ACCOUNT_NAME_CHARS)
if len(dif) != 0:
print(f"Invalid character(s) {dif} in name, only letters allowed!")
print("Returning to main menu...\n")
return
account_iv = os.urandom(16)
account = Account(account_iv, account_name, 0)
print(f"Wecome to Squirrel Treasury {account.getName()}")
print(f"Here is your account key: {account.getKey()}\n")
Ta sẽ được yêu cầu nhập tên tài khoản. Có một số ràng buộc là nó chỉ được chứa các chữ cái trong bảng chữ cái (được phép viết hoa). Sau đó, nó sẽ tiến hành tạo ra một key cho tài khoản của chúng ta sử dụng để đăng nhập. Key này được tạo như sau:
def getKey(self):
save = f"{self.__name}:{self.__balance}".encode()
blocks = blockify(save, AES.block_size)
pblocks = pad(blocks, b'\x00', AES.block_size)
cipher = AES.new(KEY, AES.MODE_ECB)
ct = []
for i, b in enumerate(pblocks):
if i == 0:
tmp = strxor(b, self.__iv)
ct.append(cipher.encrypt(tmp))
else:
tmp = strxor(strxor(ct[i-1], pblocks[i-1]), b)
ct.append(cipher.encrypt(tmp))
ct_str = f"{self.__iv.hex()}:{(b''.join(ct)).hex()}"
return ct_str
Đầu tiên, nó tạo ra một chuỗi bytes chứa name:balance, ở đây balance được truyền vào là 0. Tiến hành chia chuỗi trên thành từng block 16-bytes. Với các block không đủ 16-bytes, ta sẽ tiến hành padding bằng các bytes \x00. Quá trình mã hóa được tiến hành như sau:
Block đầu tiên sẽ được XOR với IV (được tạo random 16-bytes) trước đó. Sau đó tiến hành encrypt sử dụng AES_ECB.
Với các block còn lại, chúng sẽ được XOR với block được mã hóa trước đó và encrypt sử dụng AES_ECB.
Có thể thấy thật ra đây là một dạng AES_CBC với phương thức mã hóa sử dụng ECB. Cuối cùng, key sẽ được trả về dưới dạng chuỗi iv:ciphertext.
Đến với chức năng đăng nhập, ta có như sau:
def accountLogin():
print("\nPlease provide your account details.")
account = input("> ").strip()
account = Account.load(account)
print(f"\nWelcome {account.getName()}!")
while True:
print("What would you like to do?")
print("0 -> View balance")
print(f"1 -> Buy flag ({FLAG_COST} acorns)")
print("2 -> Save")
opt = int(input("> ").strip())
if opt == 0:
print(f"Balance: {account.getBalance()} acorns\n")
elif opt == 1:
if account.getBalance() < FLAG_COST:
print("Insufficient balance.\n")
else:
print(f"Flag: {FLAG}\n")
account.setBalance(account.getBalance()-FLAG_COST)
elif opt == 2:
print(f"Save key: {account.getKey()}\n")
break
Ta sẽ được yêu cầu nhập key của tài khoản để đăng nhập. Key này sẽ được truyền vào hàm load để check độ legit:
def load(key: str):
key_split = key.split(':')
iv = bytes.fromhex(key_split[0])
ct = bytes.fromhex(key_split[1])
cipher = AES.new(KEY, AES.MODE_ECB)
pt = blockify(cipher.decrypt(ct), AES.block_size)
ct = blockify(ct, AES.block_size)
for i, p in enumerate(pt):
if i == 0:
pt[i] = strxor(p, iv)
else:
pt[i] = strxor(strxor(ct[i-1], pt[i-1]), p)
pt = b''.join(pt)
pt_split = pt.split(b':')
try:
name = pt_split[0].decode()
except Exception:
name = "ERROR"
balance = int(pt_split[1].strip(b'\x00').decode())
return Account(iv, name, balance)
Nó sẽ tách iv và ciphertext ra để tiến hành giải mã. Đoạn này cũng giống kiểu giải mã của AES_CBC, các bạn có thể xem qua ở ảnh dưới. Kết quả trả về iv, name và balance của tài khoản chứa trong key.
Sau khi đăng nhập thành công, ta sẽ có thể mua flag với một giá ngẫu nhiên trong 10**13, 10**14-1. Với balance bằng 0 được truyền vào từ đầu thì có vẻ là sẽ không đủ để mua. Vậy ta phải tìm cách để có thể tăng số balance này lên.
Để ý, ta có thể kiểm soát được iv truyền vào. Ở đây mình sẽ sử dụng kỹ thuật Bit flip trong AES_CBC. Giả sử mình có một tài khoản tên là t. Khi đó, plaintext trước khi mã hóa sẽ chỉ có 1 block và có dạng
Block trên sẽ được XOR với IV và ra được ciphertext sau khi decrypt bằng ECB (trước khi XOR với IV để ra lại plaintext). Ở bài này, KEY truyền vào AES_ECB là không đổi (có thể gây ra vuln), tuy nhiên miễn là vẫn đang trong 1 session thì ta sẽ không cần để ý tới điều này. Thật vậy, ta luôn có thể tính được giá trị của ciphertext sau khi decrypt bằng ECB bằng cách lấy IV gốc XOR với khối plaintext mình ghi phía trên. Giả sử mình ra được như sau:
Khi này, nếu ta đăng nhập với key dạng payload_iv:ciphertext, đoạn plaintext được tính ra chắc chắn sẽ là payload của chúng ta. Với số tiền là 13 số 9 (== 10**14 - 1), ta chắc chắn sẽ mua được FLAG.
Welcome to the squ1rrel lottery! 9 winning numbers will be selected, and if any of your tickets share 3 numbers with the winning ticket you'll win a flag!
Hint: This is a math challenge
nc 34.132.166.199 11112
Solution
Dự định là bài này sẽ là bài hay nhất :v Cơ mà khi đọc writeup thì mình thấy chán do không có kỹ thuật gì nên mình sẽ để wu ở đây
Nếu chúng ta có một số đa thức có cùng gốc x0 trên Nm , chúng ta có thể biểu diễn mỗi đa thức đó dưới dạng một hàng từ một lattice. Sau đó, mỗi tổ hợp tuyến tính của các hàng từ latice sẽ tạo ra một đa thức khác có nghiệm x0.
Hãy xác định vectơ ngắn nhất trong cơ sở rút gọn là v=(v0,v1,…,vn). Ta xây dựng đa thức g(x):
g(x)=v0+Xv1x+X2v2x2+...+Xnvnxn
g(x0)≡0modNm
∣x∣≤X
deg(g)=n
∣∣g(xX)∣∣<n+1Nm
Ta có thể dễ dàng tạo các đa thức cùng root x0 trên Nm . Xét họ các đa thức gi,j(x):
gi,j(x0)≡xjmodNm−ifi(x)
0≤i<m
0≤j<deg(f)
Theo thiết kế, tất cả chúng đều có chung gốc x0 trên Nm , tức là gi,j(x0)≡0modNm . Giá trị của m càng lớn thì ta lập được càng nhiều đa thức. Chúng ta xây dựng càng nhiều đa thức thì mạng càng lớn và thời gian thu gọn mạng sẽ càng lớn.
