MiniCTF 22/7
Table of Contents
Mình xin trình bày một số bài mà mình làm được trong minictf tối 22/7 vừa qua
Cryptography
Flipping Login
server.py
#!/usr/bin/env python3
import json
import os
import signal
from base64 import b64decode, b64encode
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from secret import flag
key = os.urandom(32)
def menu_choice() -> str:
print(
"""Valid choices:
1. Login
2. Register
3. Quit"""
)
return input(">> ").strip()
def handler(_signum, _frame):
print("Time out!")
exit(0)
def encrypt(msg):
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
return iv+cipher.encrypt(pad(msg, 16))
def decrypt(iv, msg):
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
return unpad(cipher.decrypt(msg), 16)
def login():
enc_token = b64decode(input("Login token: ").strip())
token = decrypt(enc_token[:16], enc_token[16:])
token = json.loads(token)
return token['name'], token['admin']
def register():
name = input("Nickname: ").strip()
token = {
"admin": False,
"name": name
}
token = json.dumps(token).encode()
enc_token = b64encode(encrypt(token)).decode()
print("Here is your login token: " + enc_token)
def main():
signal.signal(signal.SIGALRM, handler)
signal.alarm(60)
name = 'N.A'
is_admin = False
print("Welcome to my under-development program. Who are you?")
while True:
choice = menu_choice()
match choice:
case '1':
name, is_admin = login()
break
case '2':
register()
print('')
case '3':
print("Bye bye!")
break
case _:
print("??????????????")
raise RuntimeError("I found a hacker")
if is_admin:
print(f"Hello {name}! Here is your secret: " + flag)
else:
print(f"Hello {name}! Sorry, only admin can read my secret!")
try:
main()
except Exception as E:
print(str(E))
Trong bài này, một json token được mã hõa bằng phương thức AES-CBC với “admin”: False. Ta cần phải tìm cách thay đổi sao cho “admin”: True
Với tiêu đề bài đã gợi ý cho ta sử dụng Bits Flipping Attack trong AES-CBC, mình đã search trên google và tìm được một tài liệu liên quan đến nó. Chi tiết về cách tấn công thì các bạn có thể đọc trên link mình vừa gửi, nhưng mình có thể tóm gọn lại như sau:
Ta có công thức để mã hóa trong AES - CBC là: $$\begin{aligned} C_0 &= E(P_0) \oplus IV \ C_i &= E(P_i) \oplus C_{i-1} \ {với \ i > 0} \end{aligned}$$ Và công thức để giải mã là: $$\begin{aligned} P_0 &= D(C_0) \oplus IV \ P_i &= D(C_i) \oplus P_{i-1} \ {với \ i > 0} \end{aligned}$$
Như vậy, khi mã hóa cũng như giải mã, nó sẽ xor với ciphertext block / plaintext block trước đó (hoặc $IV$). Chính vì vậy, ta có thể thay đổi nội dung của block để có thể tạo ra nội dung theo ý muốn
Ở trong bài này, vị trí của ‘“admin”: False, ’ nằm đủ 1 block thứ hai nên ta sẽ chỉnh block thứ nhất là $IV$ để khi mà xor với block thứ hai sẽ có được ‘“admin”: True , ‘. Các bạn có thể hiểu như thế này: $$\begin{aligned}IV \oplus D(C_1) &= ‘“admin”: False, ’ \ IV_{fake} \oplus D(C_1) &= ‘“admin”: True , ’ \ IV_{fake} &= IV \oplus ‘“admin”: False, ’ \oplus ‘“admin”: True , ’ \end{aligned}$$ Sau khi có được $IV_{fake}$, ta chỉ cần gửi cho server $IV_{fake}+token[16:]$ (Token là thứ ta nhận được sau khi register, 16 bytes đầu của nó là IV) và sẽ có flag
Phần code chính:
solve.py
from pwn import *
from base64 import b64decode, b64encode
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import *
token = input() #Sau khi register ở server sẽ có một cái login token, bạn sẽ nhập nó ở đây
token = b64decode(token)
iv = token[:16]
s = token[16:]
plaintext = b'"admin": False, '
target = b'"admin": True,, '
new_iv = bytes([x ^ y ^ z for (x, y, z) in zip(iv, plaintext, target)])
print(b64encode(new_iv+s)) #Gửi cái này lại cho server là được
Flag: W1{CBC_bit_flipping_attack_can_flip_your_system_https://tsublogs.wordpress.com/2015/07/18/bit-flipping-attack-on-cbc-mode}
Đúng cái mình search ban đầu luôn :)))
Anti Pollard p-1
chall.py
from math import prod
from Crypto.Util.number import *
from secret import flag, init
import os
assert isPrime(init) and 2**20 < init < 2**24
e = 0x10001
DEBUG = os.getenv("DEBUG", False)
def gen_smooth(init: int, bits: int, smoothness: int = 16) -> int:
q = 2*init
k = (bits - q.bit_length())//smoothness + 1
while True:
p = q * prod(getPrime(smoothness) for _ in range(k))
if GCD(e, p) == 1 and isPrime(p + 1):
return p + 1
p = gen_smooth(init, 768, 20)
q = gen_smooth(init, 768, 20)
N = p*q
pt = bytes_to_long(flag)
ct = pow(pt, e, N)
print(f"{e = }")
print(f"{N = }")
print(f"{ct = }")
if DEBUG:
print(f"{p = }")
print(f"{q = }")
Trong bài này, $p-1$ và $q-1$ đều là tích của các số nguyên tố nhỏ hơn 20 bits, vì vậy ta có thể nghĩ đến thuật toán Pollard p-1. Lưu ý rằng đối với bài này, ta sẽ không tính tích từ 1 đến $2^{20}$ mà sẽ shuffle lên rồi sau đó nhân lại dần.
Code để tìm $p$:
import gmpy2
from tqdm import tqdm
import random
n = gmpy2.mpz(N)
ar = list(range(2, 2**20))
random.shuffle(ar)
a = gmpy2.mpz(2)
for p in tqdm(ar):
a = gmpy2.powmod(a, 4 * init * init * p, n)
p = gmpy2.gcd(a - 1, n)
if 1 < p < n:
print(p)
break
#p = 2782649911045466726583702468234636496093912422560611231304084465742455791597284396733219895856691138873818553244424989101233983426332838798108072186621785877449683943964193663359691028105593053522429899787764095292535702906703651599
Sau khi đã có $p$, mọi chuyện còn lại là đơn giản:
solve.py
from Crypto.Util.number import *
from sage.all import *
e = 65537
N = ..
ct = ..
p = ..
q = N // p
phi = (p -1) * (q - 1)
d = pow(e, -1, phi)
m = pow(ct, d, N)
print(long_to_bytes(m))
flag: W1{tricked_Pollard_p-1_attack_7270278554bb1eebf73197e4c88099d9f636e1626a6fa124f6ae411bf171dd76}
Weird Primes
chall.py
import os
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, isPrime, inverse
from Crypto.Cipher import PKCS1_OAEP
from random import choices
from math import ceil
DEBUG = os.getenv("DEBUG", False)
digits = list("0123456789")
flag = b"W1{??????????????????????????????????}"
def getWeirdPrime(bit_length: int) -> int:
ndigits = ceil(bit_length/8)
while True:
p = ''.join(choices(digits, k=ndigits))
if isPrime(bytes_to_long(p.encode())):
return bytes_to_long(p.encode())
p = getWeirdPrime(1024)
q = getWeirdPrime(1024)
e = 0x10001
n = p*q
d = inverse(e, (p-1)*(q-1))
key = RSA.construct((n, e, d, p, q))
cipher = PKCS1_OAEP.new(key)
enc_flag = cipher.encrypt(flag).hex()
assert cipher.decrypt(bytes.fromhex(enc_flag)) == flag
print(f"{n = }")
print(f"{e = }")
print(f"{enc_flag = }")
if DEBUG:
print(f"{p = }")
print(f"{q = }")
Trong bài này, $p$ và $q$ là các số nguyên tố sao cho long_to_bytes(p) và long_to_bytes(q) đều chỉ có các kí tự số từ 0-9. Chính vì vậy, ta sẽ bruteforce dần các chữ số của long_to_bytes(p) và long_to_bytes(q) cho đến khi tìm được 2 số thỏa mãn, do chỉ có 128 bytes nên thời gian bruteforce sẽ rất nhanh:
solve.py
n = ..
e = 65537
enc_flag = ..
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
from Crypto.Cipher import PKCS1_OAEP
from random import choices
from math import ceil
digits = b'0123456789'
p = ''
q = ''
tempp = 0
tempq = 0
p = ''
q = ''
for step in range(128):
mod = 2**(8*step)
for dp in digits:
for dq in digits:
testp = bytes_to_long(p.encode()) + dp*mod
testq = bytes_to_long(q.encode()) + dq*mod
if (testp * testq)%(mod*256) == n%(mod*256):
p = long_to_bytes(dp).decode() + p
q = long_to_bytes(dq).decode() + q
else:
testp -= dp*mod
testq -= dq*mod
pp = bytes_to_long(p.encode())
qq = bytes_to_long(q.encode())
d = inverse(65537, (pp-1)*(qq-1))
key = RSA.construct((n, e, d, pp, qq))
cipher = PKCS1_OAEP.new(key)
#enc_flag = cipher.encrypt(flag).hex()
print(cipher.decrypt(bytes.fromhex(enc_flag)))
flag: W1{branch_and_prune_is_sometime_very_useful!!!!}