# 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:
- 
- 
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
Sign in with Wallet
Connect another wallet