# WRITE-UP

## ECCIBIDI

Bài này có 2 điểm mấu chốt:
- Đầu tiên là hàm random không secure, khi ta mở 2 connect tới server cùng lúc thì cả 2 sẽ sử dụng chung 1 seed

def getrandbits(nbits):
    rng = random.Random(int(time.time()) * S)
    return rng.getrandbits(nbits)

def randbelow(p):
    l = p.bit_length() // 2
    return ((random.getrandbits(l) << l) | getrandbits(l)) % p

- Điều này dẫn đến khi gọi hàm:

k = randbelow(curve_order)

Thì $k$ sẽ có một nửa bit cuối giống nhau.

- Thứ hai, server sử dụng chung một secret với mọi instance.

from secret import sk, S, FLAG

Tiếp theo ta sẽ cần biết về Hidden Number Problem:

https://hackmd.io/@nomorecaffeine/r1xstVfxC#III-Hidden-Number-Problem

Vậy từ những điều trên ta sẽ có được gì? Chú ý vào đoạn code tạo cookie sau:

s = (sk * tmp_hash + k) % curve_order

Và ta biết được với mỗi 2 connect đến server ta sẽ có được:
$$l = \frac{\text{curve_order.bit_length()}}{2}$$
$$s1 = (sk * \text{tmp_hash1} + k1) \mod \text{curve_order}$$
$$s2 = (sk * \text{tmp_hash2} + k2) \mod \text{curve_order}$$

$$\rightarrow s1 - s2 = (sk * (\text{tmp_hash1} - \text{tmp_hash2}) + (k1 - k2)) \mod \text{curve_order}$$
$$\rightarrow (s1 - s2) * 2^{-l} = (sk * (\text{tmp_hash1} - \text{tmp_hash2}) * 2^{-l}) \mod \text{curve_order}$$

Sau đó giải bài toán HNP là sẽ tìm được sk.

from pwn import *
from Crypto.Util.number import *
from hashlib import sha256 
from sage.all import *
import json

# context.log_level = 'error' 

curve_order = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
Xs = []
Cs = []
l = curve_order.bit_length() // 2
l_ = 124

for i in range(4):
    conn1 = process(["python3", "server.py"])
    conn2 = process(["python3", "server.py"])

    conn1.sendlineafter(b'>> ', b'1')
    conn1.recvuntil(b'Account information: ')
    hsh1 = bytes_to_long(sha256(conn1.recvline()[:-1]).digest())
    conn1.recvuntil(b'Cookie: ')
    cookie = conn1.recvlineS()
    s1, h = cookie.split(".")
    s1 = bytes_to_long(bytes.fromhex(s1))

    conn2.sendlineafter(b'>> ', b'1')
    conn2.recvuntil(b'Account information: ')
    hsh2 = bytes_to_long(sha256(conn2.recvline()[:-1]).digest())
    conn2.recvuntil(b'Cookie: ')
    cookie = conn2.recvlineS()
    s2, h = cookie.split(".")
    s2 = bytes_to_long(bytes.fromhex(s2))

    conn1.close()
    conn2.close()

    Xs.append((hsh1 - hsh2) * inverse(2 ** l, curve_order) % curve_order)
    Cs.append((s1 - s2) * inverse(2 ** l, curve_order) % curve_order)

k = 2 ** (l_ + 1)

B = Matrix(QQ, len(Xs) + 2, len(Xs) + 2)
for i in range(len(Xs)):
    B[i, i] = curve_order
    B[-2, i] = Xs[i]
    B[-1, i] = Cs[i]

B[-1, -1] = k
B[-2, -2] = QQ(k) / QQ(curve_order)
B = B.LLL()
for i in B:
    if abs(i[-1]) == k:
        sk = (-i[-2] * curve_order // k) % curve_order

print(f"{sk = }")

conn = process(["python3", "server.py"])

conn.sendlineafter(b'>> ', b'1')
conn.recvuntil(b'Account information: ')
hsh = bytes_to_long(sha256(conn.recvline()[:-1]).digest())
conn.recvuntil(b'Cookie: ')
cookie = conn.recvlineS()
s, h = cookie.split(".")
s = bytes_to_long(bytes.fromhex(s))

k = (s - sk * hsh) % curve_order
tmp = {"username" : 'ADP', "isAdmin" : True}
tmp["userID"] = os.urandom(16).hex()
tmp_hash = bytes_to_long(sha256(json.dumps(tmp).encode()).digest())
s_new = (sk * tmp_hash + k) % curve_order
cookie = long_to_bytes(s_new).hex() + '.' + h[:-1]

print(cookie)

conn.sendlineafter(b'>> ', b'2')
conn.sendlineafter(b'information: ', json.dumps(tmp).encode())
conn.sendlineafter(b'cookie: ', cookie.encode())
# print(conn.recvlineS())
conn.interactive()

## Warmup RSA

Với bài này ta có thể tính lại xấp xỉ của $p + q$ và $p - q$

Ta có biểu thức:

$$e * u = w + (p ^ 4 - 1) * (q ^ 4 - 1) * v$$
$$\rightarrow (p ^ 4 - 1) * (q ^ 4 - 1) = \frac{e * u}{v} - \frac{w}{v} \ (1) $$

Ta cũng có:

$$ (p ^ 4 - 1) * (q ^ 4 - 1) = n ^ 4 - (p ^ 4 + q ^ 4) + 1 $$

Đầu tiên ta sẽ xử lí $p + q$:

$$(p ^ 4 - 1) * (q ^ 4 - 1) = n ^ 4 - [(p + q) ^ 4 - 4n(p + q)^2 + 2n^2] + 1$$

$$(p ^ 4 - 1) * (q ^ 4 - 1) = (n^2 - 1)^2 - (p + q)^4 + 4n(p + q)^2 \ (2)$$

Từ $(1)$ và $(2)$:
$$(n^2 - 1)^2 - (p + q)^4 + 4n(p + q)^2 = \frac{e * u}{v} - \frac{w}{v}$$

$$\rightarrow ((p + q)^2)^2 - 4n(p + q)^2 - ((n^2 - 1)^2 - \frac{e * u}{v} + \frac{w}{v}) = 0$$

$$\Delta = 16n^2 + 4((n^2 - 1)^2 - \frac{e * u}{v} + \frac{w}{v}) \geq 0$$

$$(p + q)^2 = \frac{4n + 2\sqrt{((n^2 - 1)^2 - \frac{e * u}{v} + \frac{w}{v})}}{2}$$

$$(p + q) = \sqrt{2n + \sqrt{((n^2 - 1)^2 - \frac{e * u}{v} + \frac{w}{v})}}$$

$$\widehat{(p + q)} = \sqrt{2n + \sqrt{((n^2 - 1)^2 - \frac{e * u}{v}}}$$

Tương tự với $p - q$, ta có:

$$(p ^ 4 - 1) * (q ^ 4 - 1) = n ^ 4 - [(p - q) ^ 4 + 4n(p - q)^2 + 2n^2] + 1$$

$$(p ^ 4 - 1) * (q ^ 4 - 1) = (n^2 - 1)^2 - (p - q)^4 - 4n(p - q)^2 \ (3)$$

Từ $(1)$ và $(3)$:

$$((p - q)^2)^2 + 4n(p - q)^2 - ((n^2 - 1)^2 - \frac{e * u}{v} + \frac{w}{v}) = 0$$

$$\Delta = 16n^2 + 4((n^2 - 1)^2 - \frac{e * u}{v} + \frac{w}{v}) \geq 0$$

$$(p - q) = \sqrt{-2n + \sqrt{((n^2 - 1)^2 - \frac{e * u}{v} + \frac{w}{v})}}$$

$$\widehat{(p - q)} = \sqrt{-2n + \sqrt{((n^2 - 1)^2 - \frac{e * u}{v}}}$$

$$\hat{p} = \frac{\widehat{(p - q)} + \widehat{(p + q)}}{2}$$

from sage.all import *
from Crypto.Util.number import *
from sympy import sqrt

u = ...
v = ...
N = ...
e = ...
c = ...

appq = sqrt(2 * N + sqrt((N ** 2 + 1) ** 2 - e * u // v))
apnq = sqrt(-2 * N + sqrt((N ** 2 + 1) ** 2 - e * u // v))

ap = int(apnq + appq) // 2

def flatter(M):
    import re
    from subprocess import check_output
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), list(map(int, re.findall(b"-?\\d+", ret))))

def small_roots(self, X=None, beta=1.0, epsilon=None, **kwds):
    from sage.misc.verbose import verbose
    from sage.matrix.constructor import Matrix
    from sage.rings.real_mpfr import RR
 
    N = self.parent().characteristic()
 
    if not self.is_monic():
        raise ArithmeticError("Polynomial must be monic.")
 
    beta = RR(beta)
    if beta <= 0.0 or beta > 1.0:
        raise ValueError("0.0 < beta <= 1.0 not satisfied.")
 
    f = self.change_ring(ZZ)
 
    P, (x,) = f.parent().objgens()
 
    delta = f.degree()
 
    if epsilon is None:
        epsilon = beta / 8
    verbose("epsilon = %f" % epsilon, level=2)
 
    m = max(beta**2 / (delta * epsilon), 7 * beta / delta).ceil()
    verbose("m = %d" % m, level=2)
 
    t = int((delta * m * (1 / beta - 1)).floor())
    verbose("t = %d" % t, level=2)
 
    if X is None:
        X = (0.5 * N ** (beta**2 / delta - epsilon)).ceil()
    verbose("X = %s" % X, level=2)
 
    # we could do this much faster, but this is a cheap step
    # compared to LLL
    g = [x**j * N ** (m - i) * f**i for i in range(m) for j in range(delta)]
    g.extend([x**i * f**m for i in range(t)])  # h
 
    B = Matrix(ZZ, len(g), delta * m + max(delta, t))
    for i in range(B.nrows()):
        for j in range(g[i].degree() + 1):
            B[i, j] = g[i][j] * X**j
 
    B = flatter(B)
 
    f = sum([ZZ(B[0, i] // X**i) * x**i for i in range(B.ncols())])
    R = f.roots()
 
    ZmodN = self.base_ring()
    roots = set([ZmodN(r) for r, m in R if abs(r) <= X])
    Nbeta = N**beta
    return [root for root in roots if N.gcd(ZZ(self(root))) >= Nbeta]

x = polygen(Zmod(N))
f = (ap + x).monic()
rs = small_roots(f, X=2 ** 256, beta=0.499, epsilon=0.015)
p = int(ap + rs[0])
q = N // p
phi = (p - 1) * (q - 1)
print(long_to_bytes(pow(c, inverse(e, phi), N)))

W1{3z_c0pp3r5m1th_RSA!!!!!!!!!!!!!!}