<div style="text-align:center">
<h1>Nullcon HackIM CTF Berlin 2025</h1>
</div>
## Power tower
Source code :
```python=
from Crypto.Cipher import AES
from Crypto.Util import number
# n = number.getRandomNBitInteger(256)
n = 107502945843251244337535082460697583639357473016005252008262865481138355040617
primes = [p for p in range(100) if number.isPrime(p)]
int_key = 1
for p in primes: int_key = p**int_key
key = int.to_bytes(int_key % n,32, byteorder = 'big')
flag = open('flag.txt','r').read().strip()
flag += '_' * (-len(flag) % 16)
cipher = AES.new(key, AES.MODE_ECB).encrypt(flag.encode())
print(cipher.hex())
# b6c4d050dd08fd8471ef06e73d39b359e3fc370ca78a3426f01540985b88ba66ec9521e9b68821fed1fa625e11315bf9
```
Nhìn sơ qua Source code thì ta biết được đây là một dạng mã hóa **AES.MODE_ECB**. Tuy nhiên, key của ta được tạo ra theo một cách rất đặc biệt. Cụ thể :
```python=
n = 107502945843251244337535082460697583639357473016005252008262865481138355040617
primes = [p for p in range(100) if number.isPrime(p)]
int_key = 1
for p in primes: int_key = p**int_key
key = int.to_bytes(int_key % n,32, byteorder = 'big')
```
Đầu tiên, Source sẽ tạo ra một list gồm tất cả các số nguyên tố nhỏ hơn $100$, sau đó là tính Key theo dạng :
```=
Loop 1 : key = 2^1 = 2
Loop 2 : key = 3^2 = 9
Loop 3 : key = 5^9 = 1953125
Loop 4 : key = 7^1953125 = ...
...
Loop 25 : key = 97^... = final_key
```
Giá trị cuối cùng sau tất cả vòng lặp trên sẽ được đem đi tính Modulo $n$ mà Source đã cho ở trên, rồi cuối cùng chuyển kết quả số nguyên có được sang chuỗi bytes có độ dài là $32$.
Đó chính là quy trình tạo Key để mã hóa AES. Ta hoàn toàn có thể làm lại y chang quá trình trên để có thể lấy được Key, rồi từ đó giải mã AES và lấy được Flag. Tuy nhiên liệu điều đó có dễ không?
Tất nhiên, khi ta thử tính key lại bằng cách này :
```python=
from Crypto.Util import number
n = 107502945843251244337535082460697583639357473016005252008262865481138355040617
primes = [p for p in range(100) if number.isPrime(p)]
int_key = 1
for p in primes: int_key = p**int_key
print(int_key)
```
thì nó sẽ không cho kết quả. Bởi lẽ, phép tính lũy thừa này không hề có áp dụng Modulo $n$ vào trong từng phép tính. Chính vì vậy, khi đến với vòng lặp tính thứ $4$ thì ta sẽ có một số như sau :
$$
7^{1953125}
$$
Đây là một con số rất lớn, một máy tính cá nhân thông thường không thể tính toán nổi, mà trong khi đó đây mới chỉ là lần tính thứ $4$, chúng ta vẫn cần phải tính cho tới số nguyên tố cuối cùng trong danh sách này là $97$. Tổng cộng có $25$ lần tính để tạo nên giá trị `int_key` cuối cùng. Vậy hướng đi tiếp theo sẽ là gì?
Ý tưởng đầu tiên có thể sử dụng là ta sẽ thêm bước tính Modulo vào trong phép tính key ở trên. Cụ thể nó sẽ là :
```python=
from Crypto.Util import number
n = 107502945843251244337535082460697583639357473016005252008262865481138355040617
primes = [p for p in range(100) if number.isPrime(p)]
int_key = 1
for p in primes: int_key = pow(p, int_key, n) #Thêm pow vào
print(int_key)
```
Khi đó, ta sẽ có thể dễ dàng tính được giá trị `int_key` cuối cùng khi mà sau mỗi lần tính thì phép Modulo sẽ giúp giảm giá trị đi về giá trị bé hơn $n$. Tuy nhiên, khi ta thử đem giá trị `int_key` này đi giải mã AES thì đây sẽ là kết quả :
```python=
from Crypto.Cipher import AES
from Crypto.Util.number import isPrime, long_to_bytes
with open("cipher.txt", "r") as f:
ct = bytes.fromhex(f.read().strip())
n = 107502945843251244337535082460697583639357473016005252008262865481138355040617
primes = [p for p in range(100) if isPrime(p)]
int_key = 1
for p in primes: int_key = pow(p, int_key, n) #Thêm pow vào
key = int.to_bytes(int_key, 32, byteorder="big")
cipher = AES.new(key, AES.MODE_ECB)
pt = cipher.decrypt(ct)
print(pt)
# b'<{\xdbh\xb1\xe6D\xde\x94\xc3\x83#\xc3\x0f.\xb3\xd0\xd2\x0fI\xcb\xabB\x91\xc0\xd0K\x9bt\xb9|,\xaekg\x19$\x1f,\x9b-\x9d\xf09Q\x00\x9d:'
```
Nó chỉ là một chuỗi bytes không có nghĩa. Điều đó chứng tỏ là key của ta đã tính sai. Nếu như cách đó không khả thi thì còn cách nào khác nữa không?
Tất nhiên là vẫn còn. Khi xem xét lại công thức tính `int_key` thì ta có công thức sau :
$$
\text{int_key}\equiv97^{89^{83^{...^2}}}\pmod{n}
$$
Giá trị kia là một con số quá lớn để máy tính cá nhân thông thường có thể tính trực tiếp được. Tuy nhiên, ta vẫn có thể làm giảm đi giá trị của nó bằng cách biến đổi như sau :
Theo định lý Euler, với hai số nguyên dương $a,n$ thỏa $gcd(a,n)=1$ ta có :
$$
a^{\phi(n)}\equiv 1\pmod{n},
$$
Với mọi số $k$ và $r$ là hai số nguyên tố cùng nhau trong Modulo $\phi(n)$, tức là :
$$
k\equiv r\pmod{\phi(n)}
$$
$$
\Leftrightarrow k=q.\phi(n)+r
$$
Khi đó ta có :
$$
a^k=a^{q.\phi(n)+r}
$$
$$
\Leftrightarrow a^k=(a^{\phi(n)})^q.a^r
$$
$$
\Leftrightarrow a^k\equiv a^r\pmod{n}
$$
Vì $k$ và $r$ nguyên tố cùng nhau nên ta có thể viết lại thành :
$$
r=k\mod{\phi(n)}
$$
$$
\Rightarrow a^k\mod(n)\equiv a^{k\mod(\phi(n))}\mod(n)
$$
Như vậy, ta sẽ có tính chất sau :
>Với mọi số nguyên dương $k$ bất kì, ta có :
$$
a^k\mod(n)\equiv a^{k\mod(\phi(n))}\mod(n)
$$
>
>chỉ đúng khi $gcd(a,n)=1$
Áp dụng vào bài toán trên, ta có thể tính key như sau :
```python=
def compute_key(list_prime, modulo):
phi = euler_phi(modulo)
if len(list_prime) == 2:
key = pow(list_prime[0], list_prime[1], modulo)
else:
key = pow(list_prime[-1], compute_key(list_prime[:-1], phi), modulo)
return int(key)
```
Như vậy là ta đã có được key rồi!!! Giờ chỉ cần giải mã AES nữa là có được Flag.
Full script giải :
```python=
from Crypto.Cipher import AES
from Crypto.Util.number import isPrime, long_to_bytes
from sage.all import *
with open("cipher.txt", "r") as f:
ct = bytes.fromhex(f.read().strip())
n = 107502945843251244337535082460697583639357473016005252008262865481138355040617
primes = [p for p in range(100) if isPrime(p)]
def compute_key(list_prime, modulo):
phi = euler_phi(modulo)
if len(list_prime) == 2:
key = pow(list_prime[0], list_prime[1], modulo)
else:
key = pow(list_prime[-1], compute_key(list_prime[:-1], phi), modulo)
return int(key)
key = compute_key(primes, n)
key = int.to_bytes(key, 32, byteorder="big")
cipher = AES.new(key, AES.MODE_ECB)
pt = cipher.decrypt(ct)
print(pt.decode())
```
<details>
<summary>Flag</summary>
ENO{m4th_tr1ck5_c4n_br1ng_s0me_3ffic13ncy}______
</details>
## Simple ECDSA
Source code :
::: spoiler **ec**
```python=
#!/usr/bin/env python3
def inverse(a,n):
return pow(a,-1,n)
class EllipticCurve(object):
def __init__(self, p, a, b, order = None):
self.p = p
self.a = a
self.b = b
self.n = order
def __str__(self):
return 'y^2 = x^3 + %dx + %d modulo %d' % (self.a, self.b, self.p)
def __eq__(self, other):
return (self.a, self.b, self.p) == (other.a, other.b, other.p)
class ECPoint(object):
def __init__(self, curve, x, y, inf = False):
self.x = x % curve.p
self.y = y % curve.p
self.curve = curve
if inf or not self.is_on_curve():
self.inf = True
self.x = 0
self.y = 0
else:
self.inf = False
def is_on_curve(self):
return self.y**2 % self.curve.p == (self.x**3 + self.curve.a*self.x + self.curve.b) % self.curve.p
def copy(self):
return ECPoint(self.curve, self.x, self.y)
def __neg__(self):
return ECPoint(self.curve, self.x, -self.y, self.inf)
def __add__(self, point):
p = self.curve.p
if self.inf:
return point.copy()
if point.inf:
return self.copy()
if self.x == point.x and (self.y + point.y) % p == 0:
return ECPoint(self.curve, 0, 0, True)
if self.x == point.x:
lamb = (3*self.x**2 + self.curve.a) * inverse(2 * self.y, p) % p
else:
lamb = (point.y - self.y) * inverse(point.x - self.x, p) % p
x = (lamb**2 - self.x - point.x) % p
y = (lamb * (self.x - x) - self.y) % p
return ECPoint(self.curve,x,y)
def __sub__(self, point):
return self + (-point)
def __str__(self):
if self.inf: return 'Point(inf)'
return 'Point(%d, %d)' % (self.x, self.y)
def __mul__(self, k):
k = int(k)
base = self.copy()
res = ECPoint(self.curve, 0,0,True)
while k > 0:
if k & 1:
res = res + base
base = base + base
k >>= 1
return res
def __eq__(self, point):
return (self.inf and point.inf) or (self.x == point.x and self.y == point.y)
if __name__ == '__main__':
p = 17
a = -1
b = 1
curve = EllipticCurve(p,a,b)
P = ECPoint(curve, 1, 1)
print(P+P)
```
:::
```python=
#!/usr/bin/env python3
import os
import sys
import hashlib
from ec import *
def bytes_to_long(a):
return int(a.hex(),16)
#P-256 parameters
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
curve = EllipticCurve(p,a,b, order = n)
G = ECPoint(curve, 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
d_a = bytes_to_long(os.urandom(32))
P_a = G * d_a
def hash(msg):
return int(hashlib.md5(msg).hexdigest(), 16)
def sign(msg : bytes, DEBUG = False):
if type(msg) == str: msg = msg.encode()
msg_hash = hash(msg)
while True:
k = bytes_to_long(os.urandom(n.bit_length() >> 3))
R = G*k
if R.inf: continue
x,y = R.x, R.y
r = x % n
s = inverse(k, n) * (msg_hash + d_a) % n
if r == 0 or s == 0: continue
return r,s
def verify(r:int, s:int, msg:bytes, P_a):
r %= n
s %= n
if r == 0 or s == 0: return False
s1 = inverse(s,n)
u = hash(msg) * s1 % n
v = s1 % n
R = G * u + P_a * v
return r % n == R.x % n
def loop():
while True:
option = input('Choose an option:\n1 - get message/signature\n2 - get challenge to sign\n').strip()
if option == '1':
message = os.urandom(32)
print(message.hex())
signature = sign(message)
assert(verify(*signature,message,P_a))
print(signature)
elif option == '2':
challenge = os.urandom(32)
signature = input(f'sign the following challenge {challenge.hex()}\n')
r,s = [int(x) for x in signature.split(',')]
if r == 0 or s == 0:
print("nope")
elif verify(r, s, challenge, P_a):
print(open('flag.txt','r').read())
else:
print('wrong signature')
else:
print('Wrong input format')
if __name__ == '__main__':
print('My public key is:')
print(P_a)
try:
loop()
except Exception as err:
print(repr(err))
```
Nhìn qua Source code, cũng như ngay ở tên Challenge thì ta có thể thấy đây là một bài liên quan đến ECDSA cơ bản. Thay vì sử dụng các hàm trong SageMath để định nghĩa Elliptic Curve trên trường hữu hạn $GF(p)$ thì Source đã tự build cho mình một hàm tương tự như vậy trong file `ec.py`. Nhìn qua Source của file `chall.py` thì ta có thể biết một số thông tin về các giá trị như : $p,a,b$, order $n$ của Elliptic Curve cùng với đó là tọa độ của điểm sinh $G$. Source cũng cho luôn hai hàm là `sign` và `verify` chữ kí để thực hiện Challenge ở dưới.
Trong phần Challenge, ta sẽ nhận được Public_key là $P_A$, và có thêm hai option là :
- `1 - get message/signature`
- `2 - get challenge to sign`
Với option 1, ta sẽ nhận được một chuỗi $32$ ngẫu nhiên kèm với đó là chữ kí của chuỗi byte đó. Còn option 2 thì ta sẽ nhận tiếp một chuỗi byte cũng được sinh ra ngẫu nhiên, nhưng ta sẽ phải gửi cho Server cặp chữ kí $(r,s)$ đối với chuỗi byte đó thì mới nhận được Flag.
Đó chính là những gì mà Source code hoạt động. Bây giờ ta sẽ thử phân tích xem liệu chúng có lỗ hỏng gì không. Đầu tiên, ta biết được các tham số mà Source code cho chính là các tham số của đường cong **[secp256r1](https://www.secg.org/sec2-v2.pdf)**. Đó là một đường cong rất an toàn do chuyên gia chọn nên ta hoàn toàn có thể yên tâm về việc không có lỗ hỏng gì ở các tham số này. Vậy nếu như không có vấn đề gì thì khả năng cao lỗi sẽ xuất hiện ở trong các hàm `sign` và `verify` của ECDSA mà Source code cho. Và đúng là như vậy! Khi nhìn vào hàm `sign` thì ta sẽ thấy :
```python=
def sign(msg : bytes, DEBUG = False):
if type(msg) == str: msg = msg.encode()
msg_hash = hash(msg)
while True:
k = bytes_to_long(os.urandom(n.bit_length() >> 3))
R = G*k
if R.inf: continue
x,y = R.x, R.y
r = x % n
s = inverse(k, n) * (msg_hash + d_a) % n
if r == 0 or s == 0: continue
return r,s
```
Cụ thể hơn thì nó nằm ở chỗ này :
```python=
s = inverse(k, n) * (msg_hash + d_a) % n
```
Rõ rằng công thức tính giá trị $s$ của ta có vấn đề. Thay vì như công thức gốc thì nó sẽ là :
$$
s\equiv k^{-1}(z+r.d_A)\pmod{n}
$$
thì ở đây Source chỉ tính là :
$$
s\equiv k^{-1}(z+d_A)\pmod{n}
$$
Giá trị $r$ đã bị bỏ qua. Do đó, khi dùng hàm `verify` thì nó chỉ có như này :
```python=
def verify(r:int, s:int, msg:bytes, P_a):
r %= n
s %= n
if r == 0 or s == 0: return False
s1 = inverse(s,n)
u = hash(msg) * s1 % n
v = s1 % n
R = G * u + P_a * v
return r % n == R.x % n
```
Hàm chỉ trả về cho ta giá trị boolean của $r$ có đúng là tọa độ $x$ của điểm : $R=G.u+P_A.v$ hay không. Như vậy, để có thể lấy được Flag thì ta sẽ phải gửi đi cặp giá trị $(r,s)$ sao cho nó verify được $r$ hợp lệ là được. Vì ta có thể gửi $r$ và $s$ tùy ý nên nếu như ta chọn $s=1$ thì ta sẽ có :
$$
s_1\equiv 1^{-1}\pmod{n}\equiv 1\pmod{n}
$$
$$
\Rightarrow u\equiv\text{hash}(msg)\pmod{n}
$$
$$
\Rightarrow v\equiv 1\pmod{n}
$$
$$
\Rightarrow R=G.u+P_A.v=G.\text{hash}(msg)+P_A\pmod{n}
$$
với việc ta biết được các giá trị của điểm sinh $G$, $\text{hash}(msg)$ và khóa công khai $P_A$ nên việc có thể tính lại giá trị của $r$ là hoàn toàn dễ dàng. Như vậy là ta đã có thể verify được chữ kí và lấy được Flag rồi!!!
Full Script :
```python=
from ec import *
from pwn import remote
import hashlib
def hash(msg):
return int(hashlib.md5(msg).hexdigest(), 16)
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
curve = EllipticCurve(p,a,b, order = n)
G = ECPoint(curve, 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
io = remote("52.59.124.14", 5050)
io.recvline()
P_A = io.recvline().decode().split("(")[1].split(", ")
xP_A = int(P_A[0])
yP_A = int(P_A[1].split(")")[0])
P_A = ECPoint(curve, xP_A, yP_A)
io.recvline()
io.recvline()
io.recvline()
io.sendline(b"2")
challenge_mess = io.recvline().decode().split("challenge")[1].strip()
challenge_mess = bytes.fromhex(challenge_mess)
s = 1
s1 = inverse(s,n)
u = hash(challenge_mess) * s1 % n
v = s1 % n
R = G * u + P_A * v
r = R.x % n
io.sendline(f"{r},{s}".encode())
print(io.recvline().decode())
```
<details>
<summary>Flag</summary>
ENO{1her3_i5_4_lack_0f_r2dund4ncy}
</details>
## A slice of keys
Source code :
```python=
from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
flag = open('flag.txt','r').read().strip().encode()
pad = (16 - len(flag)) % 16
flag = flag + pad * int(16).to_bytes()
key = RSA.generate(2048, e = 1337)
n = key.n
e = key.e
d = key.d
AES_key = int(bin(d)[2:258:2],2).to_bytes(16)
crypter = AES.new(AES_key, AES.MODE_ECB)
cipher = crypter.encrypt(flag)
print(cipher.hex())
for _ in range(128):
user_input = input('(e)ncrypt|(d)ecrypt:<number>\n')
option,m = user_input.split(':')
m = int(m)
if option == 'e':
print(pow(m,e,n))
elif option == 'd':
print(pow(m,d,n))
else:
print('wrong option')
```
Nhìn qua Source code, đây vẫn là một dạng mã hóa **AES.MODE_ECB**. Tuy nhiên một lần nữa, cách tạo key của ta lại có chút khác biệt. Cụ thể :
```python=
from Crypto.PublicKey import RSA
key = RSA.generate(2048, e = 1337)
n = key.n
e = key.e
d = key.d
AES_key = int(bin(d)[2:258:2],2).to_bytes(16)
```
Trước hết, Source sẽ tạo ra hai cặp khóa công khai $(n,e)$ với $e=1337$ và khóa bí mật $(n,d)$ của RSA, sau đó sẽ lấy các bits chẵn trong $256$ bits đầu của giá trị $d$, xếp chúng lại thành một chuỗi, chuyển sang số nguyên và đưa về một chuỗi bytes để làm khóa AES mã hóa Flag của ta.
Ngoài ra, Source sẽ còn cho thêm một công cụ mã hóa và giải mã như sau :
```python=
for _ in range(128):
user_input = input('(e)ncrypt|(d)ecrypt:<number>\n')
option,m = user_input.split(':')
m = int(m)
if option == 'e':
print(pow(m,e,n))
elif option == 'd':
print(pow(m,d,n))
else:
print('wrong option')
```
Đó là tất cả những gì mà ta có thể thấy ở Source code. Đầu tiên, Source đã cho ta sẵn giá trị của $e$ là $1337$ nhưng lại không cho giá trị $n$. Ta có thể hoàn toàn tìm được giá trị của $n$ bằng cách như sau : gửi giá trị $-1$ tới Server bằng option **e** hay **d** đều được. Vì khi đó ta có :
$$
(-1)^e\pmod{n}
$$
$$
\Leftrightarrow (-1)^{1337}\pmod{n}
$$
$$
\Leftrightarrow (-1)\pmod{n}
$$
$$
\Leftrightarrow n-1\pmod{n}
$$
Khi đó, Server sẽ trả về giá trị $n-1$ cho ta. Khi này chỉ cần $+1$ vào kết quả là có $n$ rồi. Đó là xong bước đầu tiên.
Còn về vấn đề tính key thì nếu chỉ dựa vào công cụ mã hóa và giải mã kia thì mình không chắc có thể tìm lại được $d$, hoặc là các bits đầu của $d$ hay không. Tuy nhiên vẫn còn có một cách khá là hay khác để mình có thể tính được các giá trị bits đầu của $d$. Cụ thể ta có :
$$
e.d\equiv 1\pmod{\phi(n)}
$$
$$
\Leftrightarrow e.d=1+k.\phi(n)
$$
$$
\Leftrightarrow d=\frac{1+k.\phi(n)}{e}
$$
Tuy nhiên, vì không biết được giá trị của $\phi(n)$ nên ta sẽ thay thế nó bằng $n$. Khi này, ta sẽ có :
$$
d'\approx\frac{1+k.n}{e}
$$
Vì $\phi(n)<n$ nên với một vài giá trị $k\in[1,e-1]$ ta có thể tính được xấp xỉ của $d$ với các bits đầu là chính xác. Và với việc chỉ lấy tới $256$ bits đầu của $d$ thì ta sẽ hoàn toàn có thể brute-force $k\in[0,e-1]$ là có thể tìm lại được $256$ bits đầu của $d$ rồi!!! Giờ chỉ cần giải mã AES nữa là có được Flag.
Full Script
```python=
from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from pwn import remote
io = remote("52.59.124.14", 5103)
c = bytes.fromhex(io.recvline().decode())
print(io.recvline().decode())
io.sendline(b"e:-1")
n = int(io.recvline().decode()) + 1
print(n)
e = 1337
for k in range(0, e-1):
d = (1 + k*n)//e
AES_key = int(bin(d)[2:258:2],2).to_bytes(16)
crypter = AES.new(AES_key, AES.MODE_ECB)
flag = crypter.decrypt(c)
if b"ENO{" in flag:
print("Flag :", flag.decode())
print("k :", k)
break
```
<details>
<summary>Flag</summary>
ENO{you_kow_at_least_some_bits_of_the_private_exponent}
</details>
## decryption execution service
## Field trip
Source code :
```python=
#!/bin/python3
from hashlib import sha256
from Crypto.Util import number
from Crypto.Cipher import AES
BITS = 224
f = 26959946667150639794667015087019630673637144422540572481103610249993
g = 7
def reduce(a):
while (l := a.bit_length()) > 224:
a ^= f << (l - 225)
return a
def mul(a,b):
res = 0
for i in range(b.bit_length()):
if b & 1:
res ^= a << i
b >>= 1
return reduce(res)
def pow(a,n):
res = 1
exp = a
while n > 0:
if n & 1:
res = mul(res, exp)
exp = mul(exp,exp)
n >>= 1
return res
if __name__ == '__main__':
a = number.getRandomNBitInteger(BITS)
A = pow(g,a)
print(A)
b = number.getRandomNBitInteger(BITS)
B = pow(g,b)
print(B)
K = pow(A,b)
assert K == pow(A,b)
key = sha256(K.to_bytes(28)).digest()
flag = open('../meta/flag.txt','r').read().encode()
print(AES.new(key, AES.MODE_ECB).encrypt(flag + b'\x00' * (16 - len(flag) % 16)).hex())
```
```python=
# Output.txt :
A = 22740222493854193828995311834548386053886320984395671900304436279839
B = 13537441615011702013355237281886711701217244531581593794890884829133
ct = 9946ca81ffb1a741cff186a38ecbb4ddcf0e912764413642641fab7db83278a31268b5dc13e66cd86990ab1b65b73465
```
Giải thích sơ qua Source code thì đây là một mô phỏng lại của giao thức trao đổi khóa Diffie-Hellman. Tuy nhiên, thay vì thực hiện trong trường hữu hạn $GF(p)$, với $p$ là số nguyên tố, thì ở đây Source đang thực hiện giao thức này ở trong trường mở rộng $GF(p^k)$. Cụ thể hơn thì nó chính là trường mở rộng $GF(2^{224})$
Đầu tiên, Source cho ta hai giá trị là $f$ và $g$. Với $g$ là một điểm sinh trong trường mở rộng này, còn $f$ ở đây đóng vai trò như là một đa thức bất khả quy có bậc là $224$ trong trường mở rộng này. Cụ thể hơn, khi ta chuyển giá trị $f$ kia sang dạng bits thì ta sẽ có chuỗi bits như sau :
```python=
f = 26959946667150639794667015087019630673637144422540572481103610249993
print(bin(f)[2:])
# 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100001001
```
Chuyển chuỗi bits kia thành dạng đa thức, ta sẽ có :
```python=
from sympy import symbols
f = 26959946667150639794667015087019630673637144422540572481103610249993
bin_f = bin(f)[2:]
x = symbols('x')
degree = len(bin_f) - 1
poly_f = sum((int(bit) * x**(degree - i)) for i, bit in enumerate(bin_f))
print(poly_f)
# x**224 + x**9 + x**8 + x**3 + 1
```
Đó chính là đa thức bất khả quy của ta, và nó sẽ đóng vai trò tương tự như Modulo $p$ ở trong trường hữu hạn $GF(p)$, giúp cho các đa thức được tạo ra từ các phép tính nhân, cộng trên trường mở rộng $GF(2^{224})$ sẽ nằm trong trường này.
Sau đó Source cũng cho ta các hàm tính phép cộng và nhân trên trường mở rộng này nhằm để thuận tiện hơn cho việc thực hiện trao đổi khóa Diffie-Hellman ở dưới. Giá trị bí mật được chia sẻ chung sẽ được dùng làm khóa mã hóa **AES.MODE_ECB** để mã hóa Flag của ta. Sau cùng, những gì mà ta biết được là các giá trị : $f,g,A,B,ct$. Và từ đây ta sẽ phải tìm cách khôi phục lại Flag.
Đầu tiên như ta đã biết : Số phần tử (hay order) trong một trường hữu hạn $GF(p)$, với $p$ là số nguyên tố, sẽ là $p$, là tập hợp các số nguyên từ $0$ tới $p-1$. Mở rộng lên trường $GF(p^k)$ với $k$ là một số nguyên dương bất kì thì khi đó số phần tử (hay order) trong trường mở rộng này sẽ là $p^k$.
Tuy nhiên, nếu ta xét trong nhóm nhân của $GF(p)$ thì nó sẽ có order là $p-1$, bởi vì nó đã bỏ đi phần tử $0$. Điều đó cũng tương tự đối với trường mở rộng $GF(p^k)$, khi nó sẽ có order là $p^k-1$. Trong Challenge này, giao thức Diffie-Hellman đang thực hiện trên nhóm nhân của trường mở rộng $GF(p^k)$. Chính vì thế nên ta sẽ có order của nhóm nhân này là : $p^k-1$ hay nói đúng hơn là $2^{224}-1$.
Thực hiện tính factor của order trên thì ta sẽ có :
```python=
from sage.all import *
order = int(2**224 - 1)
print(factor(order))
# 3 * 5 * 17 * 29 * 43 * 113 * 127 * 257 * 449 * 2689 * 5153 * 65537 * 15790321 * 183076097 * 54410972897 * 358429848460993
```
Có thể thấy, order của trường mở rộng này là một **Smooth-number**. Điều đó dẫn đến việc ta có thể sử dụng thuật toán Pohlig-Hellman để có thể tính lại được các giá trị bí mật $a,b$ của hai bên, rồi từ đó có thể tìm lại khóa bí mật chung rồi giải mã AES lấy lại Flag rồi!!!
Full Script :
```python=
from hashlib import sha256
from Crypto.Cipher import AES
import sympy
from sympy.ntheory.modular import crt
BITS = 224
f = 26959946667150639794667015087019630673637144422540572481103610249993
g = 7
def reduce(a):
while (l := a.bit_length()) > BITS:
a ^= f << (l - (BITS+1))
return a
def mul(a, b):
res = 0
for i in range(b.bit_length()):
if b & 1:
res ^= a << i
b >>= 1
return reduce(res)
def pow(a, n):
res = 1
exp = a
while n > 0:
if n & 1:
res = mul(res, exp)
exp = mul(exp, exp)
n >>= 1
return res
def inv(a):
n_order = 2**BITS - 1
return pow(a, n_order - 1)
def bsgs(base, target, order):
m = int(sympy.sqrt(order)) + 1
baby = {}
current = 1
for j in range(m):
baby[current] = j
current = mul(current, base)
base_m = pow(base, m)
giant = inv(base_m)
current = target
for i in range(m):
if current in baby:
return i * m + baby[current]
current = mul(current, giant)
return None
def main():
with open("output.txt", 'r') as fin:
A = int(fin.readline().strip())
B = int(fin.readline().strip())
ciphertext_hex = fin.readline().strip()
ciphertext = bytes.fromhex(ciphertext_hex)
n_order = 2**BITS - 1
factors = sympy.factorint(n_order)
moduli = []
residues = []
for p, e in factors.items():
m = p**e
gamma = pow(g, n_order // m)
Abar = pow(A, n_order // m)
x = bsgs(gamma, Abar, m)
if x is None:
print(f"Discrete log not found for factor {p}")
return
residues.append(x)
moduli.append(m)
a = crt(moduli, residues)[0]
K = pow(B, a)
key = sha256(K.to_bytes(28)).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ciphertext)
print(flag.decode())
if __name__ == '__main__':
main()
```
Khi chạy với lệnh `time python3 solve.py` thì đây là kết quả :
>Mất khá nhiều time đấy :penguin:
<details>
<summary>Flag</summary>
ENO{1t_i5_no1_th3_fi3ld_5iz3_th4t_c0unts}
</details>
## decryption execution service
Source code :
```python=
from Crypto.Cipher import AES
import os
import json
class PaddingError(Exception):
pass
flag = open('flag.txt','r').read().strip()
key = os.urandom(16)
def unpad(msg : bytes):
pad_byte = msg[-1]
if pad_byte == 0 or pad_byte > 16: raise PaddingError
for i in range(1, pad_byte+1):
if msg[-i] != pad_byte: raise PaddingError
return msg[:-pad_byte]
def decrypt(cipher : bytes):
if len(cipher) % 16 > 0: raise PaddingError
decrypter = AES.new(key, AES.MODE_CBC, iv = cipher[:16])
msg_raw = decrypter.decrypt(cipher[16:])
return unpad(msg_raw)
if __name__ == '__main__':
while True:
try:
cipher_hex = input('input cipher (hex): ')
if cipher_hex == 'exit': break
cipher = decrypt(bytes.fromhex(cipher_hex))
json_token = json.loads(cipher.decode())
eval(json_token['command'])
except PaddingError:
print('invalid padding')
except (json.JSONDecodeError, UnicodeDecodeError):
print('no valid json')
except:
print('something else went wrong')
```
Nhìn qua Source code thì ta có thể thấy đây là một dạng Padding Oracle Attack trên **AES.MODE_CBC**. Trước hết, Source sẽ gen ra một chuỗi dài $16$ bytes và sẽ dùng nó làm key mã hóa AES. Ở đây, Source có cung cấp thêm cho ta một hàm `unpad` theo chuẩn **PKCS#7** cùng với đó là chỉ có duy nhất một hàm `decrypt` AES mà thôi. Điều đáng chú ý nằm ở đoạn này :
```python=
cipher_hex = input('input cipher (hex): ')
if cipher_hex == 'exit': break
cipher = decrypt(bytes.fromhex(cipher_hex))
json_token = json.loads(cipher.decode())
eval(json_token['command'])
```
Source sẽ thực hiện nhận vào một chuỗi hex bất kì và xem nó như là một Ciphertext đã được mã hóa bằng **AES.MODE_CBC**. Sau đó Source sẽ tiến hành giải mã chuỗi hex vừa mới nhận được đấy và sẽ kiểm tra xem nó có phải là một chuỗi JSON hợp lệ hay không. Một JSON hợp lệ trong Challenge này là JSON có `command` trong đó để thực thi lệnh ở ngay sau đó.
Đó là tất cả những gì mà Source code cho ta biết. Vậy thì ta sẽ khai thác bài này như thế nào? Như đã nói, Source code chỉ có duy nhất phần `decrypt` một chuỗi Ciphertext bất kì thành Plaintext, và bây giờ mục tiêu của ta là phải tìm một Ciphertext nào đó sao cho khi Decrypt nó sẽ ra một chuỗi JSON như thế này :
```python=
{"command":"print(flag)"}
```
Để ý kĩ thì chuỗi JSON trên có độ dài không chia hết cho $16$, do AES sẽ chỉ làm việc với các khối dữ liệu là bội của $16$, nên tất nhiên là ta sẽ phải padding thêm vào chuỗi JSON trên theo chuẩn **PKCS#7** và sẽ được :
```python=
BLOCK_SIZE = 16
def pkcs7_pad(data):
pad_len = BLOCK_SIZE - (len(data) % BLOCK_SIZE)
return data + bytes([pad_len]) * pad_len
pt = b'{"command":"print(flag)"}'
print(pkcs7_pad(pt))
# b'{"command":"print(flag)"}\x07\x07\x07\x07\x07\x07\x07'
```
Như đã nói, ta mong muốn rằng khi ta gửi một Ciphertext nào đó cho Server thì khi Server decrypt nó ra sẽ được chuỗi JSON như đã nói ở trên (chuỗi đã được Padding). Đầu tiên ta sẽ chia chuỗi đó thành hai phần có độ dài là $16$ bytes bằng nhau :
```python=
P1 = b'{"command":"prin'
P2 = b't(flag)"}\x07\x07\x07\x07\x07\x07\x07'
```
Gọi $D_1$ và $D_2$ là dạng giải mã của $C_1$ và $C_2$ khi chưa $\oplus$ với khối trước đó. Vì $P_1||P_2$ nên $C_1||C_2$ và ta sẽ có :
$$
P_2=D_2\oplus C_1
$$
Với $C_2$ thì ta có thể gửi một chuỗi $16$ bytes bất kì nào đó cũng được, quan trọng là ở chuỗi $C_1$. Vì Source sẽ trả lại thông báo mỗi lần giải mã xem Padding có hợp lệ hay không nên ta sẽ dựa vào đó để tấn công Padding Oracle Attack nhằm khôi phục lại $D_2$. Khi có được $D_2$ ta sẽ có thể dễ dàng tìm được $C_1$ với công thức là :
$$
C_1=P_2\oplus D_2
$$
>với $P_2$ là chuỗi mà ta muốn và $D_2$ có được từ việc Padding Oracle Attack
Sau khi tìm được điều kiện để Server decrypt ra được $P_2$ thì bây giờ ta sẽ tìm điều kiện để Server có thể Decrypt ra $P_1$. Nếu để ý trong hàm `decrypt` thì ta sẽ có đoạn như sau :
```python=
decrypter = AES.new(key, AES.MODE_CBC, iv = cipher[:16])
msg_raw = decrypter.decrypt(cipher[16:])
```
**IV** của ta sẽ được lấy bởi $16$ bytes đầu của chuỗi Ciphertext mà ta nhập vào, cùng với đó là chỉ giải mã từ Block thứ hai của Ciphertext trở đi. Tức là giờ đây, chuỗi Ciphertext mà ta phải gửi cho Server sẽ có dạng là :
$$
IV||C_1||C_2
$$
Ta sẽ tiếp tục thực hiện tấn công như ở trên, thực hiện thay đổi $IV$ sao cho :
$$
D_1=IV\oplus P_1
$$
Có được $D_1$ thì ta sẽ tìm được chuỗi $IV$ có thể dùng để Server giải mã ra được $P_1$. Như vậy là đã có được Flag rồi !!!
Full Script :
```python=
from pwn import *
import os
import json
import re
from tqdm import trange
HOST = "52.59.124.14"
PORT = 5102
BLOCK_SIZE = 16
def pkcs7_pad(data):
pad_len = BLOCK_SIZE - (len(data) % BLOCK_SIZE)
return data + bytes([pad_len]) * pad_len
def check_padding(payload):
io.sendlineafter(b'input cipher (hex): ', payload.hex().encode())
response = io.recvline().strip()
return response != b'invalid padding'
def get_intermediate_block(ciphertext_block):
log.info(f"Cracking intermediate state for block: {ciphertext_block.hex()}")
intermediate_state = bytearray(BLOCK_SIZE)
crafted_iv = bytearray(BLOCK_SIZE)
for i in range(BLOCK_SIZE - 1, -1, -1):
padding_byte = BLOCK_SIZE - i
progress = log.progress(f'Cracking byte {i}')
for j in range(i + 1, BLOCK_SIZE):
crafted_iv[j] = intermediate_state[j] ^ padding_byte
for guess in trange(256):
crafted_iv[i] = guess
payload = bytes(crafted_iv) + ciphertext_block
if check_padding(payload):
intermediate_state[i] = guess ^ padding_byte
progress.success(f"Found: {hex(intermediate_state[i])}")
break
else:
progress.failure("Failed to find byte")
return None
return bytes(intermediate_state)
def encrypt_payload(data):
padded = pkcs7_pad(data)
blocks = [padded[i:i+BLOCK_SIZE] for i in range(0, len(padded), BLOCK_SIZE)]
log.success(f"Padded payload split into {len(blocks)} blocks.")
final_ciphertext = os.urandom(BLOCK_SIZE) # random last block
for block in reversed(blocks):
intermediate = get_intermediate_block(final_ciphertext[:BLOCK_SIZE])
prev_cipher_block = xor(intermediate, block)
final_ciphertext = prev_cipher_block + final_ciphertext
log.success("Successfully crafted full ciphertext.")
return final_ciphertext
# io = process(["python", "chall.py"])
io = remote("52.59.124.14", 5102)
command = 'print(flag)'
json_payload = json.dumps({"command": command}).encode()
crafted_ciphertext = encrypt_payload(json_payload)
log.info("Sending final payload to server...")
io.sendlineafter(b'input cipher (hex): ', crafted_ciphertext.hex().encode())
response_bytes = io.recvall(timeout=5)
response_str = response_bytes.decode(errors='ignore')
m = re.search(r"ENO\{[^\}]+\}", response_str)
if m:
log.success(f"Flag: {m.group(0)}")
else:
log.failure("Could not find flag in response:\n" + response_str)
io.close()
```
<details>
<summary>Flag</summary>
ENO{the_oracle_can_also_create_messages_as_desired}
</details>
## PKCS
Source code :
```python=
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
BIT_LEN = 1024
k = RSA.generate(BIT_LEN, e = 3)
flag = open('flag.txt','r').read().encode()
encrypter = PKCS1_v1_5.new(k)
cipher1 = encrypter.encrypt(flag).hex()
cipher2 = encrypter.encrypt(flag).hex()
print(len(flag))
print(k.n)
print(cipher1)
print(cipher2)
```
Nhìn qua Source code có thể thấy đây là một dạng mã hóa RSA nhưng thay vì mã hóa theo dạng truyền thống thì Source đang mã hóa theo chuẩn **PKCS1_v1_5**, vốn là một chuẩn đã không còn sử dụng nhiều vì các lý do bảo mật. Source sẽ tạo ra cho ta một khóa công khai có Modulo $N$ dài $1024$ bits và số mũ công khai $e=3$. Sau đó, Source sẽ thực hiện mã hóa Flag của ta hai lần riêng biệt bằng **PKCS1_v1_5** và sẽ trả lại cho ta $(N,c_1,c_2)$ cùng với đó là độ dài của Flag.
Về cách thức mã hóa theo chuẩn **PKCS1_v1_5** thì bạn đọc thêm **[ở đây](https://tools.ietf.org/html/rfc8017#page-28)**.
Về cơ bản thì RSA làm việc trên số nguyên lớn. Nếu như Plaintext được mã hóa quá nhỏ thì nó sẽ rất dễ bị tấn công. Để khắc phục điều này, **PKCS#1 v1.5** yêu cầu đệm (padding) trước khi mã hóa.
Giả sử khóa RSA có độ dài là $k$ bytes, tức là Modulo $N$ có kích thước là $k$ bytes. Khi này, **PKCS#1_v1_5** sẽ padding vào Plaintext làm sao cho nó đủ độ dài là $k$ như Modulo $N$. Quá trình này hoạt động như sau:
- Khối Plaintext sẽ được đặt ở cuối cùng, phần đầu là của việc Padding
- Byte `0x00` sẽ luôn làm byte đầu tiên để phân biệt với số nguyên có dấu
- Byte thứ hai là một byte kiểu **BT (Block Type)**, gồm 2 lựa chọn chính :
- Byte `0x02` : Được sử dụng trong mã hóa dữ liệu.
- Byte `0x01` : Chỉ dùng trong chữ ký số (không dùng cho mã hóa).
- Phần tiếp theo sau byte kiểu **BT** là **PS (Padding String)** : là một dãy padding gồm các byte không phải `0x00`, giúp đảm bảo đủ độ dài
- Sau đó sẽ là byte `0x00` với mục đích đánh dấu sự kết thúc của padding.
- Và cuối cùng là phần Plaintext của chúng ta
Tham khảo sơ đồ này :
Đó là cách mã hóa theo chuẩn **PKCS1_v1_5**. Bây giờ ta sẽ thử phân tích xem có thể khai thác được gì không. Khi connect tới Server thì ta sẽ thu được thông tin như sau :
Có thể thấy, **len(Flag)** của ta có độ dài là $115$ bytes, kết hợp với đó là Modulo dài $1024\text{ bits}=128\text{ bytes}$. Như vậy, theo đúng cấu trúc trên thì phần **PS** của ta khi này chỉ còn có $10$ bytes mà thôi. Để dễ hình dung hơn, ta sẽ đặt :
```python=
off = int((b"\x00\x02" + b"\x00"*126).hex(), 16)
```
và thiết lập hai phương trình :
$$
\begin{cases}
g_1=(off+r_1\times 2^{8.(1+len(flag))}+0x00||M)^e-c_1\\
g_2=(off+r_2\times 2^{8.(1+len(flag))}+0x00||M)^e-c_2
\end{cases}
$$
Có thể thấy, $r_1$ và $r_2$ chính là hai chuỗi Padding khác nhau của hai Ciphertext $c_1$ và $c_2$. Nếu như ta đặt :
$$
\begin{cases}
x=r_1\times 2^{8.(1+len(flag))}+0x00||M\\
y=r_2-r_1
\end{cases}
$$
thì ta sẽ được :
$$
y=r_2-r_1
$$
$$
\Leftrightarrow r_2=r_1+y
$$
$$
\Leftrightarrow
\begin{cases}
g_1=(off+x)^e-c_1\\
g_2=(off+x+y\times 2^{8.(1+len(flag))})^e-c_2
\end{cases}
$$
Đến đây thì ý tưởng tiếp theo của mình là sẽ sử dụng `Groebner_basis` để đơn giản lại hai phương trình kia. Thế như ý tưởng đó lại nhanh chóng phá sản bởi vì :
```python=
from pwn import remote, process
from sage.all import *
from Crypto.Util.number import long_to_bytes
io = process(["python", "chall.py"])
# io = remote("52.59.124.14" ,"5101")
len = int(io.recvline().decode())
n = int(io.recvline().decode())
c1 = io.recvline().decode()
c2 = io.recvline().decode()
e = 3
io.close()
def gcd(a, b):
while b:
a, b = b, a % b
return a.monic()
x, y = PolynomialRing(Zmod(n), "x, y").gens()
off = int((b"\x00\x02" + b"\x00"*126).hex(), 16)
g1 = (x + off)**e - int(c1, 16)
g2 = (x + off + y*2**(8+(len*8)))**e - int(c2, 16)
I = Ideal([g1, g2])
g = I.groebner_basis()
R = PolynomialRing(Zmod(n), "x")
f1 = R(g[2])
f2 = R((x + off)**e - int(c1, 16))
z = gcd(f1, f2)
print(f1==f2) #True
```
Có thể thấy, sau khi dùng **Groebner_basis** thì mình có thu lại một phương trình chỉ toàn ẩn **x** thôi. Nhưng khi đem GCD nó với $g_1$ thì nó lại ra là $g_1$. Chịu luôn :penguin:. Như vậy là cách sử dụng **Groebner_basis** này không thể thực hiện được rồi. Vậy còn có cách nào khác không? Tất nhiên là có. Ở đây mình sẽ sử dụng một phương pháp mới để giải bài toán này, đó chính là sử dụng `Slyvester_Matrix`. Nói một cách ngắn gọn thì :
> Giả sử ta có hai đa thức một biến $f(x)$ và $g(x)$ với bậc lần lượt là $m$ và $n$ :
> $$
> f(x)=a_0+a_1x+...+a_mx^m
> $$
>
> $$
> g(x)=b_0+b_1x+...+b_nx^n
> $$
>
> Khi đó Sylvester matrix của $f(x)$ và $g(x)$ là một ma trận kích thước $(m+n)\times(m+n)$ được tạo ra từ các hệ số của hai đa thức này theo dạng :
> - Các hàng đầu tiên chứa hệ số của $f(x)$, dịch dần sang bên phải
> - Các hàng tiếp theo chứa hệ số của $g(x)$, cũng dịch dần sang phải.
>
> **Ý nghĩa** : Determinant của Sylvester matrix chính là resultant của hai đa thức $f$ và $g$ với tính chất :
> $$
> \text{Resultant}(f,g)=0\Rightarrow \text{f và g có nghiệm chung}
> $$
Có thấy rằng, cả hai đa thức $g_1$ và $g_2$ đều có chung nghiệm là $x$. Thế nên khi này ta sẽ tìm cách để loại bỏ biến $x$ đi để chỉ còn lại biến $y$ thì khi đó sẽ dễ giải hơn rất nhiều. Ta sẽ có cách bỏ biến $x$ bằng **Sylvester matrix** như sau :
```python=
M = g1.sylvester_matrix(g2)
res = M.det().polynomial(y)
rz = res.change_ring(Zmod(n))
rzz = rz.lc()**(-1) * rz #rz.monic()
```
Khi này, ta sẽ thu về một đa thức $f(y)$ và để tìm được $y$ thì ta sẽ dùng `small_roots` của SageMath để tìm. Với $y$ là phần chênh lệch giữa hai chuỗi Padding $r_1$ và $r_2$ nên giá trị tối đa mà $y$ có thể có là $2^{8\times 10}$. Cụ thể :
```python=
roots = rzz.small_roots(X=2**80, epsilon=0.02, delta=0.9999)
print(roots)
```
Sau khi có được $y$, ta sẽ thay đổi lại phương trình một chút thành :
$$
\begin{cases}
g_1=x^e-c_1\\
g_2=(x+y\times 2^{8.(1+len(flag))})^e-c_2
\end{cases}
$$
Khi này, hai đa thức của ta chỉ còn có một ẩn $x$. Chỉ cần tính GCD giữa chúng là ta đã có thể tìm lại được Flag rồi!!!
Full Script :
```python=
from pwn import remote, process
from sage.all import *
from Crypto.Util.number import long_to_bytes
io = process(["python", "chall.py"])
# io = remote("52.59.124.14" ,"5101")
len = int(io.recvline().decode())
n = int(io.recvline().decode())
c1 = io.recvline().decode()
c2 = io.recvline().decode()
e = 3
io.close()
def gcd(a, b):
while b:
a, b = b, a % b
return a.monic()
x, y = PolynomialRing(Zmod(n), "x, y").gens()
off = int((b"\x00\x02" + b"\x00"*126).hex(), 16)
g1 = (x + off)**e - int(c1, 16)
g2 = (x + off + y*2**(8+(len*8)))**e - int(c2, 16)
M = g1.sylvester_matrix(g2)
res = M.det().polynomial(y)
rz = res.change_ring(Zmod(n))
rzz = rz.lc()**(-1) * rz #rz.monic()
roots = rzz.small_roots(X=2**80, epsilon=0.02, delta=0.9999)
print(roots)
x = PolynomialRing(Zmod(n), "x").gen()
root = roots[0]
f1 = x**e - int(c1, 16)
f2 = (2**(8+(len*8))*root + x)**e - int(c2, 16)
h = gcd(f1, f2)
assert h.degree() ==1
print(long_to_bytes(int(-h[0]))[12:].decode())
```
<details>
<summary>Flag</summary>
ENO{PKCS_version_1_5_was_dead_before_the_Bleichenbacher_attack_since_long_messages_could_be_broken_by_coppersmith}
</details>
## Magnetic tape
Source code :
```python=
```
## Narrow DES
Source code :
```c=
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#define LB32_MASK 0x00000000ffffffff
#define LB24_MASK 0x0000000000ffffff
#define ROUNDS 32
/* Post S-Box permutation */
static char P[] = {
8, 18, 3, 2, 15, 24, 10, 14, 20, 7, 5, 13, 1, 6, 21, 9, 4, 11, 23, 22, 12, 19, 16, 17
};
/* The S-Box tables */
static char S[8][16] = {{
5, 3, 0, 2, 7, 1, 4, 6,
1, 6, 4, 7, 5, 0, 3, 2,
}, {
4, 1, 0, 5, 3, 7, 6, 2,
1, 4, 0, 5, 2, 6, 3, 7,
}, {
3, 4, 2, 0, 7, 6, 1, 5,
3, 7, 6, 0, 4, 2, 1, 5,
}, {
5, 6, 4, 2, 7, 0, 3, 1,
6, 5, 7, 2, 1, 3, 4, 0,
}, {
5, 6, 7, 3, 1, 0, 4, 2,
3, 6, 2, 1, 7, 4, 0, 5,
}, {
0, 3, 1, 4, 6, 5, 2, 7,
0, 3, 5, 4, 7, 6, 1, 2,
}, {
6, 0, 4, 2, 3, 5, 1, 7,
0, 6, 7, 3, 2, 1, 4, 5,
}, {
0, 5, 6, 2, 3, 7, 4, 1,
2, 4, 0, 7, 3, 1, 5, 6,
}};
uint64_t des(uint64_t msg, uint64_t key, char mode) {
int i, j;
uint32_t L = 0;
uint32_t R = 0;
uint32_t expanded = 0;
uint32_t s_output = 0;
uint32_t p_output = 0;
uint32_t temp = 0;
uint32_t sub_key[2] = {0};
L = (uint32_t)((msg >> 24) & LB24_MASK);
R = (uint32_t)(msg & LB24_MASK);
/* Calculation of the 16 keys */
sub_key[0] = (uint32_t)(key >> 32);
sub_key[1] = (uint32_t)(key & LB32_MASK);
for (i = 0; i < ROUNDS; i++) {
expanded = 0;
for (j = 0; j < 7; j++) {
expanded |= ((R >> (20 - 3*j)) & 0xf) << (28 - 4*j);
}
expanded |= (R & 7) << 1 | (R >> 23);
if (mode == 'd') {
expanded = expanded ^ sub_key[(i+1) % 2];
} else {
expanded = expanded ^ sub_key[i % 2];
}
s_output = 0;
for (j = 0; j < 8; j++) {
temp = (expanded >> (4*j)) & 0xf;
s_output <<= 3;
s_output |= (uint32_t) (S[j][temp]);
}
p_output = 0;
for (j = 0; j < 24; j++) {
p_output <<= 1;
p_output |= (s_output >> (24 - P[j])) & 1;
}
temp = R;
R = L ^ p_output;
L = temp;
}
return ((uint64_t) L) << 24 | R;
}
int main(int argc, const char * argv[]) {
char inputStr[769];
uint64_t key = 0x00000000;
printf("Give your message in hexadecimal.\n");
fflush(stdout);
uint64_t input, result;
char msg[13];
msg[12] = 0;
while(1) {
scanf("%768s" , inputStr);
for(int i = 0; i < 64; i++) {
memcpy(msg, inputStr + 12*i, 12);
input = (uint64_t)strtoull(msg, NULL, 16);
result = des(input, key, 'e');
printf("%012lx", result);
}
printf("\n");
fflush(stdout);
}
exit(0);
}
```
Sign in with Wallet
Connect another wallet