Rating:
## Frozen
### Challenge
The server implements a signature scheme where we can get the parameters, the public key, and a signature for one sample message. We have to forge the signature for a second message.
The key generation works as follows:
- Start with a prime $p$ and random $r$, which we know. We work in $\mathbb{Z}\_p$, so everything below is implicitly done modulo $p$.
- Pick a random $r$, which we don't know.
- Build the array $U_i = r^{i+1}s$.
- For the public key $pub$, take $U$ and mask the bottom 32 bits of each element.
- The remaining bottom 32 bits of each element are the private key $priv$.
To sign a message $M_i$, interpreted as an array of 32-bit integers:
- Let $q$ be a prime larger than all elements of $M$.
- The signature is $sig_i = M_i priv_i \text{ mod } q$.
```python
#!/usr/bin/env python3
from Crypto.Util.number import *
from gmpy2 import *
import sys, random, string
flag = 'fakeflag{}'
def genrandstr(N):
return ''.join(random.choice(string.ascii_uppercase + string.digits + string.ascii_lowercase) for _ in range(N))
def paramaker(nbit):
p = getPrime(nbit)
r = getRandomRange(1, p)
return p, r
def keygen(params, l, d):
p, r = params
s = getRandomRange(1, p)
U = [pow(r, c + 1, p) * s % p for c in range(0,l)]
V = [int(bin(u)[2:][:-d] + '0' * d, 2) for u in U]
S = [int(bin(u)[2:][-d:], 2) for u in U]
privkey, pubkey = S, V
return pubkey, privkey
def sign(msg, privkey, d):
msg = msg.encode('utf-8')
l = len(msg) // 4
M = [bytes_to_long(msg[4*i:4*(i+1)]) for i in range(l)]
q = int(next_prime(max(M)))
sign = [M[i]*privkey[i] % q for i in range(l)]
return sign
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.readline().strip()
def main():
border = "+"
pr(border*72)
pr(border, " hi young cryptographers, welcome to the frozen signature battle!! ", border)
pr(border, " Your mission is to forge the signature for a given message, ready?!", border)
pr(border*72)
randstr = genrandstr(20)
nbit, dbit = 128, 32
params = paramaker(nbit)
l = 5
pubkey, privkey = keygen(params, l, dbit)
while True:
pr("| Options: \n|\t[S]how the params \n|\t[P]rint pubkey \n|\t[E]xample signature \n|\t[F]orge the signature \n|\t[Q]uit")
ans = sc().lower()
if ans == 's':
pr(f'| p = {params[0]}')
pr(f'| r = {params[1]}')
elif ans == 'p':
pr(f'pubkey = {pubkey}')
elif ans == 'e':
pr(f'| the signature for "{randstr}" is :')
pr(f'| signature = {sign(randstr, privkey, dbit)}')
elif ans == 'f':
randmsg = genrandstr(20)
pr(f'| send the signature of the following message like example: {randmsg}')
SIGN = sc()
try:
SIGN = [int(s) for s in SIGN.split(',')]
except:
die('| your signature is not valid! Bye!!')
if SIGN == sign(randmsg, privkey, dbit):
die(f'| Congrats, you got the flag: {FLAG}')
else:
die(f'| Your signature is not correct, try later! Bye!')
elif ans == 'q':
die("Quitting ...")
else:
die("Bye ...")
if __name__ == '__main__':
main()
```
### Solution
If we look at the first element of the signature, we have:
$$
sig_0 = M_0 priv_0 \text{ mod } q
$$
Since we can compute $q$ (as we know the message $M$), we can find the multiplicative inverse of $M_0$ and recover the first element of the private key modulo $q$:
$$
priv_0 = M_0^{-1} sig_0 \text{ mod } q
$$
The real private key is 32 bits long, and $q$ is around $2^{30}$, so around one try in four this will be the real value of $priv_0$. If this doesn't work, we can proceed by trying $M^0{-1} sig_0 + kq$ for increasing values of $k$, and will recover the correct $priv_0$ in a
few tries.
For each candidate value, we can combine it with $pub_0$ to get $U_0 = rs$. Since we know $r$, we have $s = U_0 r^{-1}$ (in $\mathbb{Z}\_p$), which we can use to re-generate the entire public and private key and see if the public key matches the one we were given.
Once we find one that does, all that's left is to use the provided signing function to forge the signature.
Here is a hacky script written during the CTF -- it doesn't work properly when the recovered $priv_0$ is wrapped by the modulus, but that just means we need to run it a few times to get the flag:
```py
#! /usr/bin/env python
from pwn import *
from Crypto.Util.number import *
from gmpy2 import *
l = 5
def keygen(params, l, d, s):
p, r = params
U = [pow(r, c + 1, p) * s % p for c in range(0,l)]
V = [int(bin(u)[2:][:-d] + '0' * d, 2) for u in U]
S = [int(bin(u)[2:][-d:], 2) for u in U]
privkey, pubkey = S, V
return pubkey, privkey
def sign(msg, privkey, d):
msg = msg.encode('utf-8')
l = len(msg) // 4
M = [bytes_to_long(msg[4*i:4*(i+1)]) for i in range(l)]
q = int(next_prime(max(M)))
sign = [M[i]*privkey[i] % q for i in range(l)]
return sign
def break_key(p, r, pubkey, msg, sig):
q = int(next_prime(max(msg)))
pk0_base = (sig[0] * pow(msg[0], -1, q)) % q
print(pk0_base, sig[0], pow(msg[0], -1, q))
for pk0 in range(pk0_base, q, 2**32):
rs = pubkey[0] + pk0
s = (rs * pow(r, -1, p)) % p
outpub, outpriv = keygen((p, r), 5, 32, s)
print(pubkey, outpub)
if outpub == pubkey:
return outpub, outpriv
raise Exception("Could not find key!")
serv = pwnlib.tubes.remote.remote('03.cr.yp.toc.tf', 25010)
#serv = pwnlib.tubes.process.process('./frozen.py')
serv.recvuntil('[Q]uit')
serv.sendline('s')
serv.readline()
p = int(serv.readline().rstrip().split()[-1])
r = int(serv.readline().rstrip().split()[-1])
print('p =', p)
print('r =', r)
serv.recvuntil('[Q]uit')
serv.sendline('e')
serv.readline()
msg_b = serv.recvline().decode('utf-8').split('"')[1]
sig = eval(serv.recvline().decode('utf-8').split('=')[1]) # lol
msg = [bytes_to_long(msg_b.encode('utf-8')[4*i:4*(i+1)]) for i in range(l)]
print('msg =', msg)
print('sig =', sig)
serv.recvuntil('[Q]uit')
serv.sendline('p')
serv.readline()
pubkey = eval(serv.recvline().decode('utf-8').split('=')[1]) # lol again
print('pubkey =', pubkey)
pub, priv = break_key(p, r, pubkey, msg, sig)
serv.recvuntil('[Q]uit')
serv.sendline('f')
serv.readline()
forge = serv.recvline().rstrip().decode('utf-8').split()[-1]
forge_sig = sign(forge, priv, 32)
serv.sendline(','.join(str(x) for x in forge_sig))
serv.interactive()
```
##### Flag
`CCTF{Lattice_bA5eD_T3cHn1QuE_70_Br34K_LCG!!}`
