---
# System prepended metadata

title: 'SecurinetsCTF2025 - Write up '
tags: [CTF TIME]

---

# SecurinetsCTF2025
> Nhan_laptop|
> ---

> This wu for 2 chall Fl1pperZer0+1 - Securinets, both are  unintended.
> The main idea is recover the state of MT19937 for predicting the next state - private_key through the author's mistake in implementation. 
## Fl1pperZer0
chall:
:::spoiler
```python!
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from fastecdsa.curve import P256 as EC
from fastecdsa.point import Point
import os, random, hashlib, json
from secret import FLAG


class SignService:
    def __init__(self):
        self.G = Point(EC.gx, EC.gy, curve=EC)
        self.order = EC.q
        self.p = EC.p
        self.a = EC.a
        self.b = EC.b
        self.privkey = random.randrange(1, self.order - 1)
        self.pubkey = (self.privkey * self.G)
        self.key = os.urandom(16)
        self.iv = os.urandom(16)

    def generate_key(self):
        self.privkey = random.randrange(1, self.order - 1)
        self.pubkey = (self.privkey * self.G)

    def ecdsa_sign(self, message, privkey):
        z = int(hashlib.sha256(message).hexdigest(), 16)
        k = random.randrange(1, self.order - 1)
        r = (k*self.G).x % self.order
        s = (inverse(k, self.order) * (z + r*privkey)) % self.order
        return (r, s),k

    def ecdsa_verify(self, message, r, s, pubkey):
        r %= self.order
        s %= self.order
        if s == 0 or r == 0:
            return False
        z = int(hashlib.sha256(message).hexdigest(), 16)
        s_inv = inverse(s, self.order)
        u1 = (z*s_inv) % self.order
        u2 = (r*s_inv) % self.order
        W = u1*self.G + u2*pubkey
        return W.x == r

    def aes_encrypt(self, plaintext):
        cipher = AES.new(self.key, AES.MODE_GCM, nonce=self.iv)
        ct, tag = cipher.encrypt_and_digest(plaintext)


        return tag + ct

    def aes_decrypt(self, ciphertext):
        tag, ct = ciphertext[:16], ciphertext[16:]
        cipher = AES.new(self.key, AES.MODE_GCM, nonce=self.iv)
        plaintext = cipher.decrypt_and_verify(ct, tag)
        return plaintext

    def get_flag(self):
        key = hashlib.sha256(long_to_bytes(self.privkey)).digest()[:16]
        cipher = AES.new(key, AES.MODE_ECB)
        encrypted_flag = cipher.encrypt(pad(FLAG.encode(), 16))
        return encrypted_flag


if __name__ == '__main__':
    print("Welcome to Fl1pper Zer0 – Signing Service!\n")

    S = SignService()

    signkey = S.aes_encrypt(long_to_bytes(S.privkey))

    print(f"Here is your encrypted signing key, use it to sign a message : {json.dumps({'pubkey': {'x': hex(S.pubkey.x), 'y': hex(S.pubkey.y)}, 'signkey': signkey.hex()})}")

    while True:
        print("\nOptions:\n \
    1) sign <message> <signkey> : Sign a message\n \
    2) verify <message> <signature> <pubkey> : Verify the signed message\n \
    3) generate_key : Generate a new signing key\n \
    4) get_flag : Get the flag\n \
    5) quit : Quit\n")

        try:
            inp = json.loads(input('> '))

            if 'option' not in inp:
                print(json.dumps({'error': 'You must send an option'}))

            elif inp['option'] == 'sign':
                msg = bytes.fromhex(inp['msg'])
                signkey = bytes.fromhex(inp['signkey'])
                sk = bytes_to_long(S.aes_decrypt(signkey))

                (r, s),k = S.ecdsa_sign(msg, sk)
                print(json.dumps({'r': hex(r), 's': hex(s),'sk':k}))

            elif inp['option'] == 'verify':
                msg = bytes.fromhex(inp['msg'])
                r = int(inp['r'], 16)
                s = int(inp['s'], 16)
                px = int(inp['px'], 16)
                py = int(inp['py'], 16)
                pub = Point(px, py, curve=EC)

                verified = S.ecdsa_verify(msg, r, s, pub)

                if verified:
                    print(json.dumps({'result': 'Success'}))
                else:
                    print(json.dumps({'result': 'Invalid signature'}))

            elif inp['option'] == 'generate_key':
                S.generate_key()
                signkey = S.aes_encrypt(long_to_bytes(S.privkey))
                print("Here is your *NEW* encrypted signing key :")
                print(json.dumps({'pubkey': {'x': hex(S.pubkey.x), 'y': hex(S.pubkey.y)}, 'signkey': signkey.hex()}))

            elif inp['option'] == 'get_flag':
                encrypted_flag = S.get_flag()
                print(json.dumps({'flag': encrypted_flag.hex()}))

            elif inp['option'] == 'quit':
                print("Adios :)")
                break

            else:
                print(json.dumps({'error': 'Invalid option'}))

        except Exception:
            print(json.dumps({'error': 'Oops! Something went wrong'}))
            break
```
:::

Overview: 

At first glance, we will receive signkey: 
$$
    \text{signkey = AES-GCM.encrypt(private_key)} 
$$

In this chall, we have 3 options: 
- **Sign:** User allowed to sign user_message with signkey with the following process:
\begin{array}{c}
    \text{AES-GCM(signkey)}\\
    \downarrow\\
    \text{Sign(user_message)}\\
    \downarrow\\
    r = (k\ (\ = random(1,E.order()-1)\ ) * G).x \mod{E.order}\\
    s = k^{-1} *( hash(message) + r * private) \mod{E.order}
\end{array}
    - And what'll happend if we can get the list of `k = random(1,E.order()-1)` from `private_key = 0 `.
    

- **Verify:**  just verifying ( I did not use it so skipping it in this blog ).
- **Generate_key**: server will reset the private key and give signkey to us. 
    - ->> How can i project the next private key??? 
- **Get_flag**: 
$$
    ct = AES-ECB(key=private-key,\ flag)
$$

### First step: Recovering the E_k(Y_0) of Tag formula. 
> Note: I'll give you the formula and the way to get E_k(Y_0), I'll not explain clearly how it works, you can see the general concept in https://frereit.de/aes_gcm/#gcm-authentication . 
 
The vulneribility of this server is the mode AES_GCM within `reuse key - nonce`, take a look at [this blog](https://frereit.de/aes_gcm/#gcm-authentication), this vulner can leak the `GHASH()` to get `E_k(Y_0)` which can bypass the GCM authentication, and the formula Tag - authentication tag (the formula will be different without AHEAD in this chall) is:
\begin{array}{c}
\text{Tag} = C_{1}\cdot H^{3} \oplus C_{0}\cdot H^{2} \oplus L\cdot H \oplus E_k(Y_0)
\in \mathrm{GF}(2^{128}) \\
\text{where +, *, ^}  \text{ stand for } \oplus,\ \times,\ \text{power in } \mathrm{GF}(2^{128}).
\\
\left\{
\begin{aligned}
    T_1 &= C_{1_1}\cdot H^3 + C_{1_0}\cdot H^2 + L\cdot H + E_k(Y_0)\\
    T_2 &= C_{2_1}\cdot H^3 + C_{2_0}\cdot H^2 + L\cdot H + E_k(Y_0)\\
    T_3 &= C_{3_1}\cdot H^3 + C_{3_0}\cdot H^2 + L\cdot H + E_k(Y_0)
\end{aligned}
\right. \\
\Rightarrow
\left\{
\begin{aligned}
   T_1 - T_2 &= H^3\cdot (C_{1_1}-C_{2_1}) + H^2\cdot (C_{1_0}-C_{2_0})\\
   T_2 - T_3 &= H^3\cdot (C_{2_1}-C_{3_1}) + H^2\cdot (C_{2_0}-C_{3_0})
\end{aligned}
\right. \\
\text{Let }
\delta_1 = C_{1_1}-C_{2_1},\ 
\delta_2 = C_{1_0}-C_{2_0},\ 
\delta_3 = C_{2_1}-C_{3_1},\ 
\delta_4 = C_{2_0}-C_{3_0}.
\\
\Rightarrow
\left\{
\begin{aligned}
   T_1 - T_2 &= H^2\cdot(\delta_1 H + \delta_2)\\
   T_2 - T_3 &= H^2\cdot(\delta_3 H + \delta_4)
\end{aligned}
\right.
\\
\text{Define } T \;=\; \dfrac{T_1-T_2}{T_2-T_3}.
\quad\text{Then}
\quad
T \;=\; \dfrac{\delta_1 H + \delta_2}{\delta_3 H + \delta_4}.
\\
\text{Solve for } H:\qquad
T(\delta_3 H + \delta_4) = \delta_1 H + \delta_2
\end{array}

\begin{aligned}
&\; T\delta_3 H + T\delta_4 = \delta_1 H + \delta_2 \\
\Longrightarrow\;& (T\delta_3 - \delta_1)\,H = \delta_2 - T\delta_4 \\
\Longrightarrow\;&
\boxed{\, H = \dfrac{\delta_2 - T\delta_4}{T\delta_3 - \delta_1}\,}
\end{aligned}

scripts: 
:::spoiler

```python!
def split_tag_ct(hexs):
    b = bytes.fromhex(hexs)
    tag, ct = b[:16], b[16:]
    assert len(ct) == 32  # 2 block
    c1, c2 = int.from_bytes(ct[:16],'big'), int.from_bytes(ct[16:],'big')
    T = int.from_bytes(tag,'big')
    return T, c1, c2

T1,c1_1,c1_2 = split_tag_ct(signkey)
T2,c2_1,c2_2 = split_tag_ct(gen_key())
T3,c3_1,c3_2 = split_tag_ct(gen_key())

x = GF(2)["x"].gen()
gf2e = GF( 2**128 , name = "y" , modulus = x**128 + x**7 + x**2 + x + 1  )
# https://github.com/jvdsn/crypto-attacks/blob/master/attacks/gcm/forbidden_attack.py
def _to_gf2e(n):
    return gf2e([(n >> i) & 1 for i in range(127, -1, -1)])

def _from_gf2e(p):
    n = p._integer_representation()
    ans = 0
    for i in range(128):
        ans <<= 1
        ans |= ((n >> i) & 1)

    return ans

T1 = _to_gf2e(T1); T2 = _to_gf2e(T2); T3 = _to_gf2e(T3)
C1 = _to_gf2e(c1_1); C2 = _to_gf2e(c1_2); C2_1 = _to_gf2e(c2_1)
C2_2 = _to_gf2e(c2_2);C3_1 = _to_gf2e(c3_1); C3_2 = _to_gf2e(c3_2)

delta1 = C1 + C2_1;  delta2 = C2 + C2_2; 
delta3 = C2_1 + C3_1; delta4 = C2_2 + C3_2

T12 = T1 + T2
T23 = T2 + T3
T = T12 / T23

H = (delta2 - T*delta4) / (T*delta3 - delta1)
H_int = _from_gf2e(H)

Lbits = 256
S = T1 + C1*(H**3) + C2*(H**2) + _to_gf2e(Lbits)*H
assert T12 == (C1 + C2_1)*(H**3) + (C2 + C2_2)*(H**2)
S = _from_gf2e(S)
S = int(S)
```
:::

Do you consider that what'll i do with the E_k(Y_0)??

### Recovering MT19937's state and predicting the next state - the next private_key.
> You can see the core attack - break Pyrandom in https://rbtree.blog/posts/2021-05-18-breaking-python-random-module/


The next step is getting the list of `k = random( 1,E.order -1 )` ( state - random in Python ) to estimate the next state. 
The previous `S - E_k(Y_0)` (just recovered) can help us get k. 
If you send only `signkey = tag and message`, the server will calculate: 

\begin{aligned}
  tag,\ ct &:= \texttt{signkey[:16]} \;\|\; \texttt{signkey[16:]} \\
  \Rightarrow\ ct & = \text{""} \Leftrightarrow \text{user_private_key} =0  \\
  \Rightarrow\ s &\equiv k^{-1}\cdot \operatorname{hash}(m) \pmod{E.\mathrm{order}} \\
  \Rightarrow\ k &\equiv s^{-1} \cdot \operatorname{hash}(m) \pmod{E.\mathrm{order}}
\end{aligned}

Currently, we can get a list of random-k, so we just get enough samples to recover the state of MT19937.
Let see my workflow on it:
:::spoiler

```python!
import random,copy 
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937 #https://github.com/maple3142/gf2bv

lin = LinearSystem([32] * 624)
mt = lin.gens()

rng = MT19937(mt)
bs  = 32
q = 115792089210356248762697446949407573529996955224135760342422259061068512044369
rr = random.Random()
for i in range(4):
    print(rr.randrange(1,q-1))
    print("===")
    assert rr.randrange(1,q-1) == cc.getrandbits(256)+1
    rng.getrandbits(256)

zeros = [rng.getrandbits(256) ^(rr.randrange(1,q-1)-1) for _ in range(300)]
sol = lin.solve_one(zeros)
rng = MT19937(sol)
pyrand = rng.to_python_random()

for _ in range(4+ 300   ):
    pyrand.getrandbits(256)
```
:::

Note:
- we need run 4 times before getting samples because:
    - 1st: server random -> getting private_key 
    - 2,3,4th : we get the signkeys.
- And getrandbits(256) + start = randrange(1,q-1 ( 256bits)) ( where start $\in$ (1,2,3,...)) in this chall start = 1 like: 
- ![image](https://hackmd.io/_uploads/SkdbNEBpxx.png)
- ![image](https://hackmd.io/_uploads/ByykV4Hpxx.png)


If you confused why 300 samples can recover the MT19937-state instead of another number, because we lost 4 times getrandbits(256) $\sim$ 4 * 8 (state) = 32 state ~ 1024 freedom bit -> so we need at 300 ($\sim$ 76800 bits equations) samples to recover all state ( I tried many times to get the number of samples ).

scripts:
:::spoiler

```python!
def sign(m,signkey):
        (r.recvuntil("5"))
        (r.recvuntil("> "))
        r.sendline(json.dumps({
            "option":"sign",
            "msg": m.hex(),
            "signkey": signkey.hex()
        }))
        
        resp = r.recvline().strip().decode()
        resp = r.recvline().strip().decode()
        resp = eval(resp)
        return int(resp['r'],16), int(resp['s'],16)

from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
lin = LinearSystem([32] * 624)
mt = lin.gens()

rng = MT19937(mt)
for _ in range(4):
    rng.getrandbits(256)
zeros = []
import time,tqdm

for i in tqdm.tqdm(range(300)):
    m = b'123'
    h = hash(m)
    r1,s1= sign(m,long_to_bytes(S))
    k = int((h*inverse(s1,q))%q)
    zeros.append(rng.getrandbits(256) ^(k-1))

sol = lin.solve_one(zeros)
rng = MT19937(sol)
pyrand = rng.to_python_random()
```
:::

### Get_flag
:::spoiler

```python!
r.recv()
r.sendline(json.dumps({
    "option":"generate_key"
}))
print(r.recv().decode())
print(r.recv().decode())

r.sendline(json.dumps({
    "option": "get_flag",
}))
resp = r.recvline().strip().decode()
resp = r.recvline().strip().decode()
print(resp)
resp = eval(resp)
flag = resp['flag']
flag = bytes.fromhex(flag)
key = pyrand.randrange(1,q-1)
key = hashlib.sha256(long_to_bytes(key)).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
decrypted_flag = cipher.decrypt(flag)
print(decrypted_flag)
#Securinets{bea0c8b66714035aaa7e7035868dd58ac229399449b663da96cf637f2ced3d84}
```
:::
### The intended solution.

How about the bit-state of private_key, what can we do with them.
If you flip the ith-bit ( by $\pm 2^{i}$ ) ( i $\in$ [0,private_key.bit_length()]), you can see a rule as follows:
 - Assume that: ith-bit is '0' and we want to check it so let's flip to '1' by $\dotplus 2^{i}$: 
\begin{array}{c}
    \text{ith-bit = 0 / private_key}  + 2^{i} \rightarrow \text{ith-bit = 1} \\
     \downarrow \\ 
    \text{Forging the signkey:}  \\
    \left\{
        \begin{aligned}
        C_{new} &= 2^i + C = C1||C2 \\
        Tag_{new} &= C_1  \cdot H^3 + C_2 \cdot H^2 + L \cdot H + E_k(Y_0) )\ \ \ \ \text{(all operations are performed in } \mathbb{F}_{2^{128}})
         \end{aligned}
    \right.\\
    \downarrow\\
    \text{Getting signature to check bit-state:}\\
    \\
    \left\{
        \begin{aligned}
        r_{new} &= (\ \text{radom-k} \cdot G \ ).x \mod{E.order} \\
        s_{new} &= k^{-1}\cdot (\ \text{hash(message)}+ r_{new}\cdot \text{new_private_key} \ ) \mod {E.order}
         \end{aligned}
    \right.\\
    \downarrow\\
    \text{Calculating PublicKey-P}_{new} = P+2^i\cdot G =(\text{private_key +}2^i)\cdot G\\
    \downarrow\\
    \text{Verifying new P & (r, s): }\\
    \text{response = 1}\rightarrow \text{ith-bit = 0 else 1 }
\end{array}

::: spoiler
```python!
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from pwn import *
from fastecdsa.curve import P256 as EC
from fastecdsa.point import Point
import os, random, hashlib, json
# from secret import FLAG
from sage.all import *
FLAG = b"aaaaaaaaaaaaaaaa"



def hash(m):
    return int(hashlib.sha256(m).hexdigest(), 16)




"""
r = kG.x
s = k^-1(hash(m) + r*priv) mod n
s * k = hash(m) + r*priv mod n
k - h*s^-1 - r*s^-1*d = 0 mod n
"""
# r = process(['python3','chall.py'],level = 'debug')
r = process(['python3','chall.py'])
# r = remote('flipper.p2.securinets.tn',6000)

def sign(m,signkey):
    r.sendline(json.dumps({
        "option":"sign",
        "msg": m.hex(),
        "signkey": signkey.hex()
    }))
    resp = r.recvline().strip().decode()
    print(resp)
    resp = eval(resp)
    return int(resp['r'],16), int(resp['s'],16)



def gen_key():
    
    r.sendline(json.dumps({"option":"generate_key"}))
    r.recvuntil("encrypted signing key :")
    resp = r.recvline().strip().decode()
    resp = r.recvline().strip().decode()
    print(resp)
    # exit()
    resp = eval(resp)
    
    return (resp['signkey'])


E = EllipticCurve(GF(EC.p), [EC.a, EC.b])
q = EC.q

r.recvuntil(" use it to sign a message : ")

resp = r.recvline().strip().decode()
resp = eval(resp)
signkey =(resp['signkey'])



def split_tag_ct(hexs):
    b = bytes.fromhex(hexs)
    tag, ct = b[:16], b[16:]
    assert len(ct) == 32  # 2 block
    c1, c2 = int.from_bytes(ct[:16],'big'), int.from_bytes(ct[16:],'big')
    T = int.from_bytes(tag,'big')
    return T, c1, c2


T1,c1_1,c1_2 = split_tag_ct(signkey)
T2,c2_1,c2_2 = split_tag_ct(gen_key())
T3,c3_1,c3_2 = split_tag_ct(gen_key())

# exit()

x = GF(2)["x"].gen()
gf2e = GF( 2**128 , name = "y" , modulus = x**128 + x**7 + x**2 + x + 1  )

def _to_gf2e(n):
    return gf2e([(n >> i) & 1 for i in range(127, -1, -1)])

def _from_gf2e(p):
    n = p._integer_representation()
    ans = 0
    for i in range(128):
        ans <<= 1
        ans |= ((n >> i) & 1)

    return ans

"""
# T = C1 * H^3 + C2 * H^2 + L*H + E(y0)
T1 = c1_1 * H^3 + c1_2 * H^2 + L*H + E(y0)
T2 = c2_1 * H^3 + c2_2 * H^2 + L*H + E(y0)
T3 = c3_1 * H^3 + c3_2 * H^2 + L*H + E(y0)
T1 + T2 = (c1_1 + c2_1) * H^3 + (c1_2 + c2_2) * H^2
        = delta_C1 * H^3 + delta_C2 * H^2
T12     = H2 ( delta_C1 * H + delta_C2)
T2 + T3 = (c2_1 + c3_1) * H^3 + (c2_2 + c3_2) * H^2
        = delta_C3 * H^3 + delta_C4 * H^2
T23     = H2 ( delta_C3 * H + delta_C4)
T12/T23 = (delta_C1 * H + delta_C2)/(delta_C3 * H + delta_C4)
T' * (delta_C3 * H + delta_C4) = (delta_C1 * H + delta_C2)
T' * delta_C3 * H + T' * delta_C4 = delta_C1 * H + delta_C2

=> 
"""

T1 = _to_gf2e(T1)
T2 = _to_gf2e(T2)
T3 = _to_gf2e(T3)
C1 = _to_gf2e(c1_1)
C2 = _to_gf2e(c1_2)
C2_1 = _to_gf2e(c2_1)
C2_2 = _to_gf2e(c2_2)
C3_1 = _to_gf2e(c3_1)
C3_2 = _to_gf2e(c3_2)

delta1 = C1 + C2_1
delta2 = C2 + C2_2
delta3 = C2_1 + C3_1
delta4 = C2_2 + C3_2
T12 = T1 + T2
T23 = T2 + T3
T = T12 / T23
H = (delta2 - T*delta4) / (T*delta3 - delta1)

H_int = _from_gf2e(H)
print(f'{H_int = }')


Lbits = 256
S = T1 + C1*(H**3) + C2*(H**2) + _to_gf2e(Lbits)*H
assert T12 == (C1 + C2_1)*(H**3) + (C2 + C2_2)*(H**2)
S = _from_gf2e(S)
S = int(S)
def sign(m,signkey):
        (r.recvuntil("5"))
        (r.recvuntil("> "))
        r.sendline(json.dumps({
            "option":"sign",
            "msg": m.hex(),
            "signkey": signkey.hex()
        }))
        
        resp = r.recvline().strip().decode()
        print(resp)
        # resp = r.recvline().strip().decode()
        resp = eval(resp)
        return int(resp['r'],16), int(resp['s'],16), resp['sk']



def forge_public_key(c):
    c1,c2 = c[:16], c[16:]
    x = int.from_bytes(c1,'big')
    y = int.from_bytes(c2,'big')
    x = _to_gf2e(x)
    y = _to_gf2e(y)
    Tag = x * H**3 + y * H**2 + _to_gf2e(Lbits)*H + _to_gf2e(S)
    Tag = _from_gf2e(Tag)
    Tag = long_to_bytes(Tag)
    return Tag + c 



r.sendline(json.dumps({"option":"generate_key"}))
r.recvuntil("encrypted signing key :")
resp = r.recvline().strip().decode()
resp = r.recvline().strip().decode()
print(resp)
# exit()
resp = eval(resp)
x = resp['pubkey']['x']
y = resp['pubkey']['y']
x = int(x,16)
y = int(y,16)
pub = Point(x,y,curve=EC)
signkey = resp['signkey']
signkey = bytes.fromhex(signkey)
tag, ct = signkey[:16], signkey[16:]

def verify(m,_r,s,px,py):
    r.recvuntil("5")
    r.recvuntil("> ")
    r.sendline(json.dumps({
        "option":"verify",
        "msg": m.hex(),
        "r": hex(_r),
        "s": hex(s),
        'px': hex(px),
        'py': hex(py)
    }))
    resp = r.recvline().strip().decode()
    # resp = r.recvline().strip().decode()
    resp = eval(resp)
    return resp['result']

tmp = ''
for i in range(0,256):
    shift = (1 << i)
    print(shift)
    ct_new = xor(ct, shift.to_bytes(32,'big'))
    forged_signkey = forge_public_key(ct_new)
    m = b'12'
    _r,s,sk = sign(m,forged_signkey)
    P_new = pub - shift * EC.G

    res = verify(m,_r,s,P_new.x,P_new.y)
    if res == 'Success':
        tmp = '1' + tmp
        continue
    P_new = pub + shift * EC.G

    res = verify(m,_r,s,P_new.x,P_new.y)
    if res == 'Success':
        tmp = '0' + tmp
        continue


assert tmp.zfill(256) == bin(sk)[2:].zfill(256)

r.recvuntil("5")
r.recvuntil("> ")
r.sendline(json.dumps({"option":"get_flag"}))
resp = r.recvline().strip().decode()
resp = eval(resp)
encrypted_flag = bytes.fromhex(resp['flag'])

key = int(tmp.zfill(256),2)
key = long_to_bytes(key)
key = hashlib.sha256(key).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(encrypted_flag)
flag = flag.rstrip(b'\x04')
print(f'Flag: {flag.decode()}')
```

:::
## Fl1pperZer1

chall: 
:::spoiler

```python!
from sage.all import *
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from fastecdsa.curve import P256 as EC
from fastecdsa.point import Point
import os, random, hashlib, json

# load('secret.sage')
Flag = "FLAG{REDACTED_FOR_PRIVACY}"
class SecureSignService:
    def __init__(self):
        self.G = Point(EC.gx, EC.gy, curve=EC)
        self.order = EC.q
        self.p = EC.p
        self.a = EC.a
        self.b = EC.b
        self.privkey = random.randrange(1, self.order - 1)
        self.pubkey = (self.privkey * self.G)
        self.key = os.urandom(16)
        self.iv = os.urandom(16)

    def split_privkey(self, privkey):
        shares = []
        coeffs = [privkey]
        for _ in range(3):
            coeffs.append(random.randrange(1, self.order))

        P = PolynomialRing(GF(self.order),'x')
        x = P.gen()
        poly = sum(c*x**i for i, c in enumerate(coeffs))

        for x in range(1, 5):
            y = poly(x=x)
            shares.append((x, y))
        return shares

    def reconstruct_privkey(self, shares):
        P = PolynomialRing(GF(self.order),'x')
        x = P.gen()
        reconst_poly = P.lagrange_polynomial(shares)
        return int(reconst_poly(0))

    def shares_encrypt(self, shares):
        return [self.aes_encrypt(long_to_bytes(int(s[1]))).hex() for s in shares]

    def shares_decrypt(self, shares):
        return [(x+1, bytes_to_long(self.aes_decrypt(bytes.fromhex(y)))) for x, y in enumerate(shares)]

    def generate_key(self):
        self.privkey = random.randrange(1, self.order - 1)
        self.pubkey = (self.privkey * self.G)

    def ecdsa_sign(self, message, privkey):
        z = int(hashlib.sha256(message).hexdigest(), 16)
        k = random.randrange(1, self.order - 1)
        r = (k*self.G).x % self.order
        s = (inverse(k, self.order) * (z + r*privkey)) % self.order
        return (r, s), k

    def ecdsa_verify(self, message, r, s, pubkey):
        r %= self.order
        s %= self.order
        if s == 0 or r == 0:
            return False
        z = int(hashlib.sha256(message).hexdigest(), 16)
        s_inv = inverse(s, self.order)
        u1 = (z*s_inv) % self.order
        u2 = (r*s_inv) % self.order
        W = u1*self.G + u2*pubkey
        return W.x == r

    def aes_encrypt(self, plaintext):
        cipher = AES.new(self.key, AES.MODE_GCM, nonce=self.iv)
        ciphertext, tag = cipher.encrypt_and_digest(plaintext)
        return tag + ciphertext

    def aes_decrypt(self, ciphertext):
        tag, ct = ciphertext[:16], ciphertext[16:]
        cipher = AES.new(self.key, AES.MODE_GCM, nonce=self.iv)
        plaintext = cipher.decrypt_and_verify(ct, tag)
        return plaintext

    def get_flag(self):
        key = hashlib.sha256(long_to_bytes(self.privkey)).digest()[:16]
        cipher = AES.new(key, AES.MODE_ECB)
        encrypted_flag = cipher.encrypt(pad(FLAG.encode(), 16))
        return encrypted_flag


if __name__ == '__main__':
    print("Welcome to Fl0pper Zer1 – Secure Signing Service!\n")

    S = SecureSignService()

    signkey = S.shares_encrypt(S.split_privkey(S.privkey))

    print(f"Here are your encrypted signing key shares, use them to sign a message : {json.dumps({'pubkey': {'x': hex(S.pubkey.x), 'y': hex(S.pubkey.y)}, 'signkey': signkey})}")

    while True:
        print("\nOptions:\n \
    1) sign <message> <signkey> : Sign a message\n \
    2) verify <message> <signature> <pubkey> : Verify the signed message\n \
    3) generate_key : Generate new signing key shares\n \
    4) get_flag : Get the flag\n \
    5) quit : Quit\n")

        try:
            inp = json.loads(input('> '))

            if 'option' not in inp:
                print(json.dumps({'error': 'You must send an option'}))

            elif inp['option'] == 'sign':
                msg = bytes.fromhex(inp['msg'])
                signkey = inp['signkey']
                sk = S.reconstruct_privkey(S.shares_decrypt(signkey))

                (r, s),k = S.ecdsa_sign(msg, sk)
                print(json.dumps({'r': hex(r), 's': hex(s), 'k': (k)}))

            elif inp['option'] == 'verify':
                msg = bytes.fromhex(inp['msg'])
                r = int(inp['r'], 16)
                s = int(inp['s'], 16)
                px = int(inp['px'], 16)
                py = int(inp['py'], 16)
                pub = Point(px, py, curve=EC)

                verified = S.ecdsa_verify(msg, r, s, pub)

                if verified:
                    print(json.dumps({'result': 'Success'}))
                else:
                    print(json.dumps({'result': 'Invalid signature'}))

            elif inp['option'] == 'generate_key':
                S.generate_key()
                signkey = S.shares_encrypt(S.split_privkey(S.privkey))
                print("Here are your *NEW* encrypted signing key shares :")
                print(json.dumps({'pubkey': {'x': hex(S.pubkey.x), 'y': hex(S.pubkey.y)}, 'signkey': signkey}))

            elif inp['option'] == 'get_flag':
                encrypted_flag = S.get_flag()
                print(json.dumps({'flag': encrypted_flag.hex()}))

            elif inp['option'] == 'quit':
                print("Adios :)")
                break

            else:
                print(json.dumps({'error': 'Invalid option'}))

        except Exception as e:
            print(json.dumps({'error': 'Oops! Something went wrong'}))
            break

```

:::
Solve: 
There is the same mistake in implementation so we can use the way to solve above chall to do this chall.
However, the encrypt data is different. 
:::spoiler

```python!
 def split_privkey(self, privkey):
        shares = []
        coeffs = [privkey]
        for _ in range(3):
            coeffs.append(random.randrange(1, self.order))

        P = PolynomialRing(GF(self.order),'x')
        x = P.gen()
        poly = sum(c*x**i for i, c in enumerate(coeffs))

        for x in range(1, 5):
            y = poly(x=x)
            shares.append((x, y))
        return shares

    def reconstruct_privkey(self, shares):
        P = PolynomialRing(GF(self.order),'x')
        x = P.gen()
        reconst_poly = P.lagrange_polynomial(shares)
        return int(reconst_poly(0))

    def shares_encrypt(self, shares):
        return [self.aes_encrypt(long_to_bytes(int(s[1]))).hex() for s in shares]
    
signkey = S.shares_encrypt(S.split_privkey(S.privkey))
```
:::
It use the mixture SSS_s to encrypt data, but we can only send Tag to get the private_key = 0 to get k - random.
scripts:
:::spoiler

```python!
            <Recovering E_k(y_0)>

tmp = [long_to_bytes(S).hex() for x in range(4)] 
def sign(m,signkey):
    
    print(r.recv().decode())
    r.sendline(json.dumps({
        "option":"sign",
        "msg": m.hex(),
        "signkey": signkey
    }))
    resp = r.recvline().strip().decode()
    resp = r.recvline().strip().decode()
    resp = eval(resp)
    return (int(resp['r'],16), int(resp['s'],16))

from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
lin = LinearSystem([32] * 624)
mt = lin.gens()

rng = MT19937(mt)
for _ in range(4):
    rng.getrandbits(256)
zeros = []
import time,tqdm
def hash(m):
    return int(hashlib.sha256(m).hexdigest(), 16)


for i in tqdm.tqdm(range(300)):
    m = b'123'
    h = hash(m)
    (r1,s1)= sign(m,tmp)
    k = int((h*inverse(s1,q))%q)
    zeros.append(rng.getrandbits(256) ^(k-1))

sol = lin.solve_one(zeros)
rng = MT19937(sol)
pyrand = rng.to_python_random()
for _ in range(4+ 300):
    pyrand.getrandbits(256)

                            <Getting Flag>.

```
:::

### Intended solution: 
> Resource: https://en.wikipedia.org/wiki/Shamir%27s_secret_sharing#Reconstruction

**Recall:** The formula of Shamir's secret sharing (this chall): 
\begin{aligned} 
    f(x) & = \text{private_key} +k_1\cdot x + k_2\cdot x^2 + k_3\cdot x^3\ | \text{ki = random}\\
         & = y_0 \cdot l_0(x) + y_1 \cdot l_1(x) + y_2 \cdot l_2(x) + y_3 \cdot l_3(x)  \\
         & = \text{private_key  | at x = 0}
\end{aligned}
We only know the x-coordinate so it easy to see that we must use the 2nd-formula and because the properties of Lagrange basis polynomials, we can not directly flip bit, but we can modify one of these coefficient of f(x) :

\begin{array}{c}
    f(0) = (y_0 + 2^i ) \cdot l_0(0) + y_1 \cdot l_1(0) + y_2 \cdot l_2(0) + y_3 \cdot l_3(0)  \\
         = \text{private_key}+2^i \cdot l_0(0)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \\
         \downarrow\\
         \text{Getting new signature}\\
         \downarrow\\
         \text{Calculate: }\ P_{new} = P + 2^i\cdot l_0 *Q         
\end{array}

The next steps are similar with the previous chall.

:::spoiler
```python!
from sage.all import *
from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from fastecdsa.curve import P256 as EC
from fastecdsa.point import Point
from pwn import * 
import os, random, hashlib, json

# r = process(['python3', 'chall.py'], level='debug')
# r = process(['python3', 'server.py'], level='debug')
# r = process(['python3', 'server.py'])
ok = 1 
r = process(['python3', 'chall.py'])
# nc flopper.p2.securinets.tn 6002p
# r = remote("flopper.p2.securinets.tn", 6002)


r.recvuntil(" use them to sign a message : ")
resp = r.recvline().strip().decode()

resp = eval(resp)
px = int(resp['pubkey']['x'],16)
py = int(resp['pubkey']['y'],16)
E = EllipticCurve(GF(EC.p), [EC.a, EC.b])
P = E(px, py)
G = E(EC.gx, EC.gy)

signkey =(resp['signkey'])

q = EC.q
def split_tag_ct(hexs):
    b = bytes.fromhex(hexs)
    tag, ct = b[:16], b[16:]
    assert len(ct) == 32  # 2 block
    c1, c2 = int.from_bytes(ct[:16],'big'), int.from_bytes(ct[16:],'big')
    T = int.from_bytes(tag,'big')
    return T, c1, c2, ct

T1,c1_1,c1_2,c1 = split_tag_ct(signkey[0])
T2,c2_1,c2_2,c2 = split_tag_ct(signkey[1])
T3,c3_1,c3_2,c3 = split_tag_ct(signkey[2])
T4,c4_1,c4_2,c4 = split_tag_ct(signkey[3])

x = GF(2)["x"].gen()
gf2e = GF( 2**128 , name = "y" , modulus = x**128 + x**7 + x**2 + x + 1  )

def _to_gf2e(n):
    return gf2e([(n >> i) & 1 for i in range(127, -1, -1)])

def _from_gf2e(p):
    n = p._integer_representation()
    ans = 0
    for i in range(128):
        ans <<= 1
        ans |= ((n >> i) & 1)

    return ans

T1 = _to_gf2e(T1)
T2 = _to_gf2e(T2)
T3 = _to_gf2e(T3)
T4 = _to_gf2e(T4)
C1 = _to_gf2e(c1_1)
C2 = _to_gf2e(c1_2)
C2_1 = _to_gf2e(c2_1)
C2_2 = _to_gf2e(c2_2)
C3_1 = _to_gf2e(c3_1)
C3_2 = _to_gf2e(c3_2)
C4_1 = _to_gf2e(c4_1)
C4_2 = _to_gf2e(c4_2)

delta1 = C1 + C2_1
delta2 = C2 + C2_2
delta3 = C2_1 + C3_1
delta4 = C2_2 + C3_2
T12 = T1 + T2
T23 = T2 + T3
T = T12 / T23
H = (delta2 - T*delta4) / (T*delta3 - delta1)

H_int = _from_gf2e(H)

Lbits = 256
L = _to_gf2e(Lbits)
S = T1 + C1*(H**3) + C2*(H**2) + _to_gf2e(Lbits)*H
# print(S)
assert C4_1 * H**3 + C4_2 * H**2 + _to_gf2e(Lbits)*H + S == T4





q = EC.q
def lagrange_basis(idx):
    n = 1
    d = 1
    for i in range(1,5):
        if i == idx:
            continue
        n = n * (0- i )
        d = d * (idx - i )

    return n//d

lbasis = []
for i in range(1,5):
    lbasis.append(lagrange_basis(i))

print(lbasis)


r.recvuntil('5')
r.recvuntil('> ')

r.sendline(json.dumps({
    "option":"generate_key",
}))
resp = r.recvline().strip().decode()
resp = r.recvline().strip().decode()
resp = eval(resp)
x,y = int(resp['pubkey']['x'],16), int(resp['pubkey']['y'],16)
pub = Point(x,y, curve=EC) 
signkey = (resp['signkey'])

t1,c1 = signkey[0][:32], bytes.fromhex(signkey[0][32:])
t2,c2 = signkey[1][:32], bytes.fromhex(signkey[1][32:])
t3,c3 = signkey[2][:32], bytes.fromhex(signkey[2][32:])
t4,c4 = signkey[3][:32], bytes.fromhex(signkey[3][32:])


def forge_public_key(c):
    c1,c2 = c[:16], c[16:]
    x = int.from_bytes(c1,'big')
    y = int.from_bytes(c2,'big')
    x = _to_gf2e(x)
    y = _to_gf2e(y)

    Tag = x * H**3 + y * H**2 + _to_gf2e(256)*H + (S)
    Tag_int = _from_gf2e(Tag)
    Tag_bytes = Tag_int.to_bytes(16, 'big')
    return Tag_bytes + c


tmp  =''

listy = []
for j in range(4):
    tmp = ''
    for i in range(256):
        shift = (1 << i) 
        ct = bytes.fromhex(signkey[j][32:])
        c_new = xor(ct, shift.to_bytes(32,'big'))
        c_new = forge_public_key(c_new)
        fsign = []
        for t in range(4):
            if t == j: 
                fsign.append(c_new.hex())
            else:
                fsign.append(signkey[t])
        r.recvuntil('5')
        r.recvuntil('> ')
        m = b'12'
        r.sendline(json.dumps({
            "option":"sign",
            "msg": m.hex(),
            "signkey": fsign
        }))
        resp = r.recvline().strip().decode()
        # print(resp)
        resp = eval(resp)
        # exit()

        _r, s= int(resp['r'],16), int(resp['s'],16)
        # priv = resp['priv']
        shares = resp['shares']
        # exit()
        if lbasis[j]<0:
            shift = -shift
        P_new = pub - (shift*lbasis[j]) * EC.G


        r.recvuntil('5')
        r.recvuntil('> ')
        r.sendline(json.dumps({
            "option":"verify",
            "msg": m.hex(),
            "r": hex(_r),
            "s": hex(s),
            'px': hex(P_new.x),
            'py': hex(P_new.y)
        }))
        resp = r.recvline().strip().decode()
        resp = eval(resp)

        tmp1 = resp['result']
        if lbasis[j]>0:
            if resp['result'] == 'Success':
                tmp = '1'+tmp
            else:
                tmp = '0'+tmp
        else :
            if resp['result'] == 'Success':
                tmp = '0'+tmp
            else:
                tmp = '1'+tmp
    print(tmp)
    print(bin(int(shares[j],16))[2:])
    print()
    listy.append(int(tmp,2))
print(listy)
F = GF(EC.q)
P = PolynomialRing(F, 'x')
x = P.gen()
points = [(i+1, F(listy[i])) for i in range(4)]
poly = P.lagrange_polynomial(points)
flag_int = int(poly(0))

print(r.recv(1024).decode())
r.sendline(json.dumps({"option": "get_flag"}))

resp = r.recvline().strip().decode()
resp = eval(resp)
ct =  bytes.fromhex(resp['flag'])

key  = hashlib.sha256(long_to_bytes(flag_int)).digest()[:16]
cipher = AES.new(key,AES.MODE_ECB)
decrypted_flag  = cipher.decrypt(ct)
print(decrypted_flag)
```
:::

## Exclusive
The core attack is you can decrypt the second ciphertext as follow: 
\begin{array}{c}
    P_2^* =W\text{[:len(data)%16]} =  (D_K(C_2+T_2) + T_2 )\text{[:len(data)%16]}\\
    P_1^* = D_K(C_2||W\text{[len(data)%16:]} + T_1) +T_1 
    \\ \downarrow \\ 
    \text{let C2= 15* 'A', so you know the (15*'A'}+Block{Flag_{idex}})
\end{array}

And the first byte each block we can not recover so, brute each flag into server. 
find the last block: 
:::spoiler
```python!
from pwn import * 
from random import *
import string

# r = process(['python3.10', 'chall.py'],level = 'debug')
r = process(['python3.10', 'chall.py'])

r.recvuntil(b'> ')
r.sendline(b'5')
r.recvuntil(b'Your clue : ')
clue = r.recvline().strip().decode()
clue = bytes.fromhex(clue)
clue = [clue[i:i+16] for i in range(0, len(clue), 16)]

res = b''
for i in range(15,-1,-1):
    pay = clue[0] + b'A'*i 
    
    r.recvuntil(b'> ')
    r.sendline(pay.hex())
    r.recvuntil(b'Exclusive content : ')
    check = r.recvline().strip().decode()

    paylist = []
    for a in range(256): 
        tmp =  b'A'*i + bytes([a])  + res
        tmp = tmp.hex()
        tmp = tmp + '\n'
        paylist.append(tmp)
    payload = ''.join(paylist)
    r.send(payload)
    for j in range(256):
        r.recvuntil(b'Exclusive content : ')
        line = r.recvline().strip().decode()
        if check in line:
            print("oops")
            res =  bytes([j]) + res
            print(res)
print(res)



```
:::

find 4 - first block: 

:::spoiler
```python!
from pwn import * 
from random import *
import string

# r = process(['python3.10', 'chall.py'],level = 'debug')
r = process(['python3.10', 'chall.py'])

r.recvuntil(b'> ')
r.sendline(b'5')
r.recvuntil(b'Your clue : ')
clue = r.recvline().strip().decode()
clue = bytes.fromhex(clue)
clue = [clue[i:i+16] for i in range(0, len(clue), 16)]

res = b''
for i in range(15,-1,-1):
    pay = clue[1] + b'A'*i 
    
    r.recvuntil(b'> ')
    r.sendline(pay.hex())
    r.recvuntil(b'Exclusive content : ')
    check = r.recvline().strip().decode()

    paylist = []
    for a in range(256): 
        tmp =  b'A'*i + bytes([a])  + res
        tmp = tmp.hex()
        tmp = tmp + '\n'
        paylist.append(tmp)
    payload = ''.join(paylist)
    r.send(payload)
    for j in range(256):
        r.recvuntil(b'Exclusive content : ')
        line = r.recvline().strip().decode()
        if check in line:
            print("oops")
            res =  bytes([j]) + res
            print(res)
print(res)



```
:::
## References: 

[1] https://frereit.de/aes_gcm/
[2] https://github.com/jvdsn/crypto-attacks/blob/master/attacks/gcm/forbidden_attack.py