Gambler (PRNG)
{"author" : ["ret2basic"]}

Challenge

Gamble as an ancient Philossepher!
nc 05.cr.yp.toc.tf 33371

Code Review

The server provides three functionalities: get ciphertext, get encryption function source code, and encrypt a plaintext:
1
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2
+ Hi, there is a strong relation between philosophy and the gambling! +
3
+ Gamble as an ancient philosopher and find the flag :) +
4
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
5
| Options:
6
| [C]ipher flag!
7
| [E]ncryption function!
8
| [T]ry the encryption
9
| [Q]uit
Copied!
The encryption function is a polynomial:
1
def encrypt(m, p, a, b):
2
assert m < p and isPrime(p)
3
return (m ** 3 + a * m + b) % p
Copied!
It is equivalent to:
f(m)=(m3+am+b)modpf(m)=(m^3+am+b) \bmod p

Solution

In this challenge, we are given an oracle that encrypts any plaintext that we provide, which is a typically Chosen Plaintext Attack (CPA) scenario. We will solve this challenge in 4 steps:
Step 1: compute
bb
In order to obtain
bb
, set
m=0m = 0
:
f(0)=(03+a0+b)modp=bmodpf(0) = (0^3 + a \cdot 0 + b) \bmod p = b \bmod p
Step 2: compute
aa
In order to obtain
aa
, set
m=1m = 1
:
f(1)=(13+a1+b)modpa(f(1)b1)modpf(1) = (1^3 + a \cdot 1 + b) \bmod p\\ a \equiv (f(1) - b - 1) \bmod p
Step 3: compute
pp
In order to obtain
pp
, set
mm
to a small number s.t.
f(m)>pf(m) > p
. For example, set
m=100m = 100
:
f(100)=(1003+a100+b)modpf(100)=(1003+a100+b)+kpkp=f(100)(1003+a100+b)p=f(100)(1003+a100+b)kf(100) = (100^3 + a \cdot 100 + b) \bmod p\\ f(100) = (100^3 + a \cdot 100 + b) + k \cdot p\\ k \cdot p = f(100) - (100^3 + a \cdot 100 + b)\\ p = \frac{f(100) - (100^3 + a \cdot 100 + b)}{k}
where
kZk \in \mathbb{Z}
. Although we don't the exact value of
kk
, we can simply brute-force it since it must be small.
Step 4: recover
mm
Now we know all the parameters in the polynomial, we can simply find all roots to
f(m)=m3+am+bmodpf(m)=m^{3}+am+b \bmod p
using Sage to recover
mm
.

Implementation

1
#!/usr/bin/env sage
2
from pwn import *
3
from Crypto.Util.number import long_to_bytes
4
5
#--------Setup--------#
6
7
host = "05.cr.yp.toc.tf"
8
port = 33371
9
10
#--------Data--------#
11
12
r = remote(host, port)
13
r.readuntil(b"[Q]uit\n")
14
r.sendline("C")
15
data = r.readuntil(b"[Q]uit\n")
16
enc = int(data.split()[3].decode().strip())
17
18
#--------Helper function--------#
19
20
def encrypt_int(n):
21
r.sendline("T")
22
r.readuntil(" your message to encrypt:\n")
23
r.sendline(str(n))
24
data = r.readuntil(b"[Q]uit\n")
25
b = int(data.split()[3].decode().strip())
26
return b
27
28
#--------Step 1: compute b--------#
29
30
b = encrypt_int(0)
31
32
#--------Step 2: compute a--------#
33
34
c = encrypt_int(1)
35
a = c - b - 1
36
37
#--------Step 3: compute p--------#
38
39
enc_kp = encrypt_int(100)
40
kp = (100**3 + a*100 + b) - enc_kp
41
p = max(f[0] for f in factor(kp))
42
43
#--------Step 4: recover m--------#
44
45
PR.<x> = PolynomialRing(GF(p))
46
f = x^3 + a * x + b - enc
47
roots = f.roots()
48
print(roots)
49
50
for root in roots:
51
flag = root[0]
52
print(long_to_bytes(flag))
53
54
r.interactive()
Copied!
Last modified 2mo ago