On this CTF, I only worked on the crypto challenges. I managed to solve two crypto challenges. Here is my writeup for those challenges.
Crypto
Down the Rabinhole (325 pt)
Initial Analysis
We were given two files,
source.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from Crypto.Util.Padding import pad
import os
FLAG = b"HTB{--REDACTED--}"
def getPrimes(coefficient):
while True:
a = getPrime(512)
p = 3 * coefficient * a + 2
if isPrime(p):
break
while True:
b = getPrime(512)
q = 3 * coefficient * b + 2
if isPrime(q):
break
return p, q
def encrypt(message, coefficient):
p, q = getPrimes(coefficient)
n = p * q
padded_message = bytes_to_long(pad(message, 64))
message = bytes_to_long(message)
c1 = (message * (message + coefficient)) % n
c2 = (padded_message * (padded_message + coefficient)) % n
return (n, c1, c2)
def main():
coefficient = getPrime(128)
out = ""
message = FLAG[0:len(FLAG)//2]
n1, c1, c2 = encrypt(message, coefficient)
out += f"{n1}\n{c1}\n{c2}\n"
message = FLAG[len(FLAG)//2:]
n2, c3, c4 = encrypt(message, coefficient)
out += f"{n2}\n{c3}\n{c4}"
with open("out.txt", "w") as f:
f.write(out)
if __name__ == '__main__':
main()
|
and out.txt
1
2
3
4
5
6
|
59695566410375916085091065597867624599396247120105936423853186912270957035981683790353782357813780840261434564512137529316306287245132306537487688075992115491809442873176686026221661043777720872604111654524551850568278941757944240802222861051514726510684250078771979880364039814240006038057748087210740783689350438039317498789505078530402846140787188830971536805605748267334628057592989
206131769237721955001530863959688756686125485413899261197125641745745636359058664398433013356663394210624150086689905532
14350341133918883930676906390648724486852266960811870561648194176794020698141189777337348951219934072588842789694987397861496993878758159916334335632468891342228755755695273096621152247970509517996580512069034691932835017774636881861331636331496873041705094768329156701838193429109420730982051593645140188946
56438641309774959123579452414864548345708278641778632906871133633348990457713200426806112132039095059800662176837023585166134224681069774331148738554157081531312104961252755406614635488382297434171375724135403083446853715913787796744272218693049072693460001363598351151832646947233969595478647666992523249343972394051106514947235445828889363124242280013397047951812688863313932909903047
429546912004731012886527767254149694574730322956287028161761007271362927652041138366004560890773167255588200792979452452
29903904396126887576044949247400308530425862142675118500848365445245957090320752747039056821346410855821626622960719507094119542088455732058232895757115241568569663893434035594991241152575495936972994239671806350060725033375704703416762794475486000391074743029264587481673930383986479738961452214727157980946
|
Okay, so what this challenge do is basically:
- Split the flag to two parts
- Generate $\text{coeff}$ which is a prime ~$128$ bits
- Use this $\text{coeff}$ to generate a new prime which fulfill $\text{prime}=3.\text{coeff}.a +2$
- Use those generated primes to encrypt the partial flag with RSA.
- Each part got encrypted twice, the first one is without padding, and the second one is with padding
- And then, they provide us with $n_{1}, c_{1}, c_{2}, n_{2}, c_{3}, c_{4}$
So, with the given informations, we need to be able decrypt our flag.
Solution
Let’s try to create equations from the given source code on generating $n_{1}$ and $n_{2}$ ($c = \text{coeff}$).
$$
\begin{align*}
\tag{1}
n_1 &= p_1q_1 \\
&= (3ca_{11} + 2)(3ca_{12} + 2) \\
&= 9a_{11}a_{12}c^2 + 6c(a_{11}+a_{12}) + 4 \\
(n_1 - 4) &= 9a_{11}a_{12}c^2 + 6c(a_{11}+a_{12}) \\
(n_1 - 4) &= 3c(3a_{11}a_{12}c + 2(a_{11}+a_{12})) \\
\end{align*}
$$
$$
\begin{align*}
\tag{2}
n_2 &= p_2q_2 \\
&= (3ca_{21} + 2)(3ca_{22} + 2)\\
&= 9a_{21}a_{22}c^2 + 6c(a_{21}+a_{22}) + 4\\
(n_2 - 4) &= 9a_{21}a_{22}c^2 + 6c(a_{21}+a_{22})\\
(n_2 - 4) &= 3c(3a_{21}a_{22}c + 2(a_{21}+a_{22}))\\
\end{align*}
$$
Notice that both of them share common factors (which is $c$). $GCD$ both equations can help us to retrieve the $\text{coeff}$ value, because both of them share common factors $c$. Just do $GCD(n_1-4, n_2-4)$, factorize it, and take the prime which has ~$128$ bits (Because $\text{coeff}$ size is ~$128$ bits). Based on the given output, we get $\text{coeff} = GCD(n_1-4, n_2-4)//9$.
Now we have $\text{coeff}$. Now let re-visit the code on the encryption:
1
2
3
4
5
6
7
8
9
10
|
def encrypt(message, coefficient):
p, q = getPrimes(coefficient)
n = p * q
padded_message = bytes_to_long(pad(message, 64))
message = bytes_to_long(message)
c1 = (message * (message + coefficient)) % n
c2 = (padded_message * (padded_message + coefficient)) % n
return (n, c1, c2)
|
$n$ is ~$1280$ bits. And $c_1=m*(m+\text{coeff}) \mod n$. Notice that if $m$ bits is less than $640$ bits (~$80$ chars), we actually can ignore the mod operation, because $m*(m+\text{coeff})$ is less than $n$. I don’t think that the partial flag length will be larger than 80 chars, so I think we can actually solve the equations.
So let’s try to solve this quadratic equation $n = m*(m+\text{coeff})$. Turn out, we successfully retrieve the flag by solving those quadratic equations on each part.
Full Script
I use sage to solve the solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
from Crypto.Util.number import *
n1 = 59695566410375916085091065597867624599396247120105936423853186912270957035981683790353782357813780840261434564512137529316306287245132306537487688075992115491809442873176686026221661043777720872604111654524551850568278941757944240802222861051514726510684250078771979880364039814240006038057748087210740783689350438039317498789505078530402846140787188830971536805605748267334628057592989
c1 = 206131769237721955001530863959688756686125485413899261197125641745745636359058664398433013356663394210624150086689905532
c2 = 14350341133918883930676906390648724486852266960811870561648194176794020698141189777337348951219934072588842789694987397861496993878758159916334335632468891342228755755695273096621152247970509517996580512069034691932835017774636881861331636331496873041705094768329156701838193429109420730982051593645140188946
n2 = 56438641309774959123579452414864548345708278641778632906871133633348990457713200426806112132039095059800662176837023585166134224681069774331148738554157081531312104961252755406614635488382297434171375724135403083446853715913787796744272218693049072693460001363598351151832646947233969595478647666992523249343972394051106514947235445828889363124242280013397047951812688863313932909903047
c3 = 429546912004731012886527767254149694574730322956287028161761007271362927652041138366004560890773167255588200792979452452
c4 = 29903904396126887576044949247400308530425862142675118500848365445245957090320752747039056821346410855821626622960719507094119542088455732058232895757115241568569663893434035594991241152575495936972994239671806350060725033375704703416762794475486000391074743029264587481673930383986479738961452214727157980946
coeff = gcd(n1-4, n2-4) // 9
m1 = var('m1')
m2 = var('m2')
m1_roots = solve(m1*(m1+coeff) == c1, m1)
m2_roots = solve(m2*(m2+coeff) == c3, m2)
flag = b''
for root in m1_roots:
if root.right() > 0:
flag += long_to_bytes(int(root.right()))
for root in m2_roots:
if root.right() > 0:
flag += long_to_bytes(int(root.right()))
print(f'Flag: {flag.decode()}')
|
Flag: HTB{gcd_+_2_*_R@6in_.|5_thi5_@_cro55over_epi5ode?}
Mind in the Clouds (375 pt)
Initial Analysis
We were given a source code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
import json
import signal
import subprocess
import socketserver
from hashlib import sha1
from random import randint
from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key, Signature
import os
fnames = [b'subject_kolhen', b'subject_stommb', b'subject_danbeer']
nfnames = []
class ECDSA:
def __init__(self):
self.G = generator_256
self.n = self.G.order()
self.key = randint(1, self.n - 1)
self.pubkey = Public_key(self.G, self.key * self.G)
self.privkey = Private_key(self.pubkey, self.key)
def sign(self, fname):
h = sha1(fname).digest()
nonce = randint(1, self.n - 1)
sig = self.privkey.sign(bytes_to_long(h), nonce)
return {"r": hex(sig.r)[2:], "s": hex(sig.s)[2:], "nonce": hex(nonce)[2:]}
def verify(self, fname, r, s):
h = bytes_to_long(sha1(fname).digest())
r = int(r, 16)
s = int(s, 16)
sig = Signature(r, s)
if self.pubkey.verifies(h, sig):
return retrieve_file(fname)
else:
return 'Signature is not valid\n'
ecc = ECDSA()
def init_storage():
i = 0
for fname in fnames[:-1]:
data = ecc.sign(fname)
r, s = data['r'], data['s']
nonce = data['nonce']
nfname = fname.decode() + '_' + r + '_' + s + '_' + nonce[(14 + i):-14]
nfnames.append(nfname)
i += 2
def retrieve_file(fname):
try:
dt = open(fname, 'rb').read()
return dt.hex()
except:
return 'The file does not exist!'
def challenge(req):
req.sendall(b'This is a cloud storage service.\n' +
b'You can list the files inside and also see their contents if your signatures are valid.\n')
while True:
req.sendall(b'\nOptions:\n1.List files\n2.Access a file\n')
try:
payload = json.loads(req.recv(4096))
if payload['option'] == 'list':
payload = json.dumps(
{'response': 'success', 'files': nfnames})
req.sendall(payload.encode())
elif payload['option'] == 'access':
fname = payload['fname']
r, s = payload['r'], payload['s']
dt = ecc.verify(fname.encode(), r, s)
if ('not exist' in dt) or ('not valid' in dt):
payload = json.dumps({'response': 'error', 'message': dt})
else:
payload = json.dumps({'response': 'success', 'data': dt})
req.sendall(payload.encode())
else:
payload = json.dumps(
{'response': 'error', 'message': 'Invalid option!'})
req.sendall(payload.encode())
except:
payload = json.dumps(
{'response': 'error', 'message': 'An error occured!'})
req.sendall(payload.encode())
class incoming(socketserver.BaseRequestHandler):
def handle(self):
signal.alarm(30)
req = self.request
challenge(req)
class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
def main():
init_storage()
socketserver.TCPServer.allow_reuse_address = True
server = ReusableTCPServer(("0.0.0.0", 1337), incoming)
server.serve_forever()
if __name__ == "__main__":
main()
|
So, this is an ECDSA challenge. Let’s try to analysis the source code part by part.
1
2
3
4
5
|
def main():
init_storage()
socketserver.TCPServer.allow_reuse_address = True
server = ReusableTCPServer(("0.0.0.0", 1337), incoming)
server.serve_forever()
|
Okay, so this challenge will call init_storage and then turn up the server. Let’s check what init_storage do
1
2
3
4
5
6
7
8
9
10
11
12
|
fnames = [b'subject_kolhen', b'subject_stommb', b'subject_danbeer']
nfnames = []
...
def init_storage():
i = 0
for fname in fnames[:-1]:
data = ecc.sign(fname)
r, s = data['r'], data['s']
nonce = data['nonce']
nfname = fname.decode() + '_' + r + '_' + s + '_' + nonce[(14 + i):-14]
nfnames.append(nfname)
i += 2
|
Okay, so from the defined filenames, init_storage will only sign two files (which is subject_kolhen and subject_stommb), and then store it with format filename_r_s_nonce[(14+i):-14]. $(r, s)$ is the signature that is returned by ECDSA. Usually, in ECDSA scheme, we shouldn’t shared our $\text{nonce}$ or reused it, because knowning the $\text{nonce}$ will allow us to derive the secret key. Let’s try to remember how does ECDSA signature works first. We can sign a message with ECDSA by doing this:
$$
\tag{1}
s \equiv k^{-1}(h+r\alpha) \mod q
$$
where, $s=\text{signature}$, $k=\text{nonce}$, $h=\text{hash}(\text{msg})$, $\alpha=\text{secret}$.
Hence, if we know $\text{nonce}$, we can derive the $\text{secret}$ by doing this:
$$
\tag{2}
\alpha\equiv(ks-h)r^{-1} \mod q
$$
That’s why we shouldn’t share the $\text{nonce}$ that we use during signing a message. This challenge leaked the middle bits of the $\text{nonce}$ (First filename leaks ~$144$ middle bits, second filename leaks ~$136$ middle bits). We will keep this in our mind first.
Let’s check the challenge code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
def retrieve_file(fname):
try:
dt = open(fname, 'rb').read()
return dt.hex()
except:
return 'The file does not exist!'
def challenge(req):
req.sendall(b'This is a cloud storage service.\n' +
b'You can list the files inside and also see their contents if your signatures are valid.\n')
while True:
req.sendall(b'\nOptions:\n1.List files\n2.Access a file\n')
try:
payload = json.loads(req.recv(4096))
if payload['option'] == 'list':
payload = json.dumps(
{'response': 'success', 'files': nfnames})
req.sendall(payload.encode())
elif payload['option'] == 'access':
fname = payload['fname']
r, s = payload['r'], payload['s']
dt = ecc.verify(fname.encode(), r, s)
if ('not exist' in dt) or ('not valid' in dt):
payload = json.dumps({'response': 'error', 'message': dt})
else:
payload = json.dumps({'response': 'success', 'data': dt})
req.sendall(payload.encode())
else:
payload = json.dumps(
{'response': 'error', 'message': 'Invalid option!'})
req.sendall(payload.encode())
except:
payload = json.dumps(
{'response': 'error', 'message': 'An error occured!'})
req.sendall(payload.encode())
|
Okay, so basically, we can send two commands:
List files command will return two filenames with its signature, and access file will allow us to read the file’s content only if we provide the correct signature. Remember that the challenge is actually have three files.
We can deduce that on this challenges, given,
- Two messages (filename)
- Two signatures of the messages
- Two leaked middle bits of the used $\text{nonce}$ during signing each messages
we need to be able create a valid signature for the third filename, and then access its content.
Solution
We actually can represent the challenge problems into Hidden Number Problem which was introduced by Boneh and Venkatesan. There are a lot of existing papers those discussed about these problems (paper1, paper2, paper3). I choose to implement the first paper in order to solve this solutions (with some modifications). I will try to explain it.
Basically, given the leaked middle bits of the $k$, we can say that:
$$
\tag{3}
k_{i} = 2^{\ell_{i}}c_{1} + a_{1} + b_{1}
$$
where, $max(k_{bits})=256_{bits}$, $\ell_{i}=max(k_{bits})-leaked_{i_{bits}}$, $a_{i}=2^{56}leaked_{i}$, and $b_{i}$ is the $56$ lsb of the $k_{i}$.
So, in this case, $\ell_{1}$ will be ~$200$ (because $leaked_{i_{bits}}=144$) and $\ell_{2}$ will be ~$192$ (because $leaked_{i_{bits}}=136$). And $c_{1}$ will be $256-144-56=56$ bits, and $c_{2}$ will be $256-136-56=64$ bits.
Remember $\text{eq1}$ where,
$$
s \equiv k^{-1}(h+r\alpha) \mod q
$$
and we have two signatures
$$
\begin{align*}
\tag{4}
s_{1} &\equiv k_{1}^{-1}(h_{1}+r_{1}\alpha) \mod q \\
s_{1}k_{1} &\equiv h_{1}+r_{1}\alpha \mod q \\
\end{align*}
$$
$$
\begin{align*}
\tag{5}
s_{2} &\equiv k_{2}^{-1}(h_{2}+r_{2}\alpha) \mod q \\
s_{2}k_{2} &\equiv h_{2}+r_{2}\alpha \mod q \\
\end{align*}
$$
If we try to do elimination of $\alpha$ between the equations that we have by multiplying first equation with $r_{2}$ and second equation with $r_{1}$, we will get
$$
\begin{align*}
\tag{6}
r_{2}s_{1}k_{1} - r_{1}s_{2}k_{2} &\equiv r_{2}h_{1}+r_{2}r_{1}\alpha - (r_{1}h_{2}+r_{1}r_{2}\alpha) \mod q \\
r_{2}s_{1}k_{1} - r_{1}s_{2}k_{2} &\equiv r_{2}h_{1} - r_{1}h_{2} \mod q \\
k_{1} - r_{2}^{-1}s_{1}^{-1}r_{1}s_{2}k_{2} &\equiv s_{1}^{-1}h_{1} - r_{2}^{-1}s_{1}^{-1}r_{1}h_{2} \mod q \\
k_{1} - s_{1}^{-1}r_{1}s_{2}r_{2}^{-1}k_{2} + s_{1}^{-1}r_{1}r_{2}^{-1}h_{2} - s_{1}^{-1}h_{1} &\equiv 0 \mod q \\
k_{1} + tk_{2} + u &\equiv 0 \mod q\\
\end{align*}
$$
where $t=-s_{1}^{-1}r_{1}s_{2}r_{2}^{-1}$ and $u=s_{1}^{-1}r_{1}r_{2}^{-1}h_{2} - s_{1}^{-1}h_{1}$
Remember $\text{eq3}$ where we actually can expand the $k$ further. Putting it to $\text{eq6}$.
$$
\begin{align*}
\tag{7}
2^{\ell_{1}}c_{1} + a_{1} + b_{1} + t2^{\ell_{2}}c_{2} + ta_{2} + tb_{2} + u &\equiv 0 \mod q\\
b_{1} + 2^{\ell_{1}}c_{1} + tb_{2} + t2^{\ell_{2}}c_{2} + a_{1} + ta_{2} + u &\equiv 0 \mod q\\
b_{1} + 2^{\ell_{1}}c_{1} + tb_{2} + t2^{\ell_{2}}c_{2} + u' &\equiv 0 \mod q\\
b_{1} + 2^{\ell_{1}}c_{1} + tb_{2} + t2^{\ell_{2}}c_{2} + u' &\equiv 0 \mod q\\
\end{align*}
$$
where $u'= a_{1} + ta_{2} + u$.
Now, notice that $b_{1}$, $c_{1}$, $b_{2}$, $c_{2}$ are small unknowns. Based on the paper, we can construct a lattice where the result will contains 4 linear equations with 4 unknowns. Now, below is the lattice that I use.
$$
B =
\begin{bmatrix}
K & K2^{\ell_{1}} & Kt & Kt2^{\ell_{2}} & u' \\
0 & Kq & 0 & 0 & 0 \\
0 & 0 & Kq & 0 & 0 \\
0 & 0 & 0 & Kq & 0 \\
0 & 0 & 0 & 0 & q \\
\end{bmatrix}
$$
where for this challenge, I choose $K=2^{56}$ ($K$ is the expected bound for $b_{1}, c_{1}, b_{2}, c_{2}$). I know that $c_{2}$ value is expected to be larger than $K$ (remember that $c_{2}$ bits length should be around $64$), but this is enough for some cases (Refer to Extra Notes below).
Notes that the lattice is slightly different from the example in the paper, because on this challenge, the total leaked middle bits that we got on signature 1 and signature 2 is difference ($leaked_{1_{bits}}=~144$ and $leaked_{1_{bits}}=~136$). Hence, the $\ell_i$ value is difference.
Using this basis and reduce it with $LLL$, we will got matrix 5x5, where it contains vector
$$
v_{i} = (x_{0}Kb_{1}, x_{1}Kc_{1}, x_{2}Kb_{2}, x_{3}Kc_{2}, y_{i})
$$
where $x_{i}K$ is the coefficients of the linear equation and $y_{i}$ is the result of the linear equation.
Just like the paper said, the first 4 vector is actually a linear equation of 4 unknown variables. So the vector is basically represents:
$$
x_{0}Kb_{1} + x_{1}Kc_{1} + x_{2}Kb_{2} + x_{3}Kc_{2} - y_{i} = 0
$$
Solving the equations, we will be able to retrieve the $k_{1}$ and $k_{2}$ by putting the result into $\text{eq3}$. Refer to $\text{eq2}$, now we can recover the $\text{secret}$ ($\alpha$). After that, we can use the given ECDSA class in the source code to sign the third message subject_danbeer, and send it to the server. The server will give the content (which contains the flag) to us.
Flag: HTB{y0u_4r3_th3_m4st3r_0f_LLL}
The solution is unstable, which after testing in the local, I found out that we can only apply our constructed lattice only if the bits length of the $c_2$ is < $63$ bits. So, during the challenge, what I do is simply restart the docker so many times, until the $c_2$ value is < $63$ bits.
I believe one of the reason of this unstable result is due to the $K$ value that I set is $2^{56}$. I’m pretty sure that my lattice can be improved so that it can recover the $\text{nonce}$ even though the $c_2$ bits length is between ${63,64}$ bits. Also in the paper, it is stated that
The determinant bounds guarantee that we will find one short lattice vector, but do not guarantee that we will find four short lattice vectors. For that, we rely on the heuristic that the reduced vectors of a random lattice are close to the same length.
So maybe, it is expected that we might need to do several attempts to break the given ECDSA system.
Full Script
I use sage to run this script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
from pwn import *
from Crypto.Util.number import *
import json
from hashlib import sha1
from ecdsa.ecdsa import generator_256, Public_key, Private_key, Signature
import binascii
def retrieve_file(fname):
try:
dt = open(fname, 'rb').read()
return dt.hex()
except:
return 'The file does not exist!'
class ECDSA:
def __init__(self, key=-1):
self.G = generator_256
self.n = self.G.order()
if key == -1:
self.key = randint(1, self.n - 1)
else:
self.key = key
self.pubkey = Public_key(self.G, self.key * self.G)
self.privkey = Private_key(self.pubkey, self.key)
def sign(self, fname):
h = sha1(fname).digest()
nonce = randint(1, self.n - 1)
sig = self.privkey.sign(bytes_to_long(h), nonce)
return {"r": hex(sig.r)[2:], "s": hex(sig.s)[2:], "nonce": hex(nonce)[2:]}
def verify(self, fname, r, s):
h = bytes_to_long(sha1(fname).digest())
r = int(r, 16)
s = int(s, 16)
sig = Signature(r, s)
if self.pubkey.verifies(h, sig):
return retrieve_file(fname)
else:
return 'Signature is not valid\n'
def list_files(conn):
conn.sendlineafter(b'a file\n', b'{"option": "list"}')
response = json.loads(conn.recvuntil(b'\n').strip())
return response['files']
def access_file(conn, fname, r, s):
payload = json.dumps({
'option': 'access',
'fname': fname,
'r': r,
's': s,
})
conn.sendlineafter(b'a file\n', payload.encode())
response = conn.recvuntil(b'\n')
return json.loads(response)
url = 'localhost:1337'
host = url.split(':')[0]
port = int(url.split(':')[1])
conn = remote(host, port)
files = list_files(conn)
q = 115792089210356248762697446949407573529996955224135760342422259061068512044369
# Get first signature with its leaked nonce
fname1 = (files[0].split('_')[0] + '_' + files[0].split('_')[1]).encode()
h1 = bytes_to_long(sha1(fname1).digest())
r1 = int(files[0].split('_')[2], 16)
s1 = int(files[0].split('_')[3], 16)
leaked1 = int(files[0].split('_')[4], 16)
a1 = leaked1*(2**56)
# Get second signature with its leaked nonce
fname2 = (files[1].split('_')[0] + '_' + files[1].split('_')[1]).encode()
h2 = bytes_to_long(sha1(fname2).digest())
r2 = int(files[1].split('_')[2], 16)
s2 = int(files[1].split('_')[3], 16)
leaked2 = int(files[1].split('_')[4], 16)
a2 = leaked2*(2**56)
# Craft our lattice
k = 2**56
inv_s1 = int(inverse_mod(s1, q))
inv_r2 = int(inverse_mod(r2, q))
t = (-inv_s1*s2*r1*inv_r2) % q
u = (inv_s1*r1*h2*inv_r2 - inv_s1*h1) % q
uu = a1 + t*a2 + u
m = Matrix([
[k, k*2**200, k*t, k*t*2**192, uu],
[0, k*q, 0, 0, 0],
[0, 0, k*q, 0, 0],
[0, 0, 0, k*q, 0],
[0, 0, 0, 0, q],
])
m = m.LLL()
# Now, from the reduced basis, we try to solve the equations
new_m = []
res = []
for row in m[:-1]:
real_row = []
for val in row[:-1]:
real_row.append(val / k)
new_m.append(real_row)
res.append(-row[-1])
new_m = Matrix(new_m)
res = vector(res)
ans = new_m.solve_right(res)
# Now, we can get the nonce
k1 = ans[0] + ans[1]*2**200 + a1
k2 = ans[2] + ans[3]*2**192 + a2
print('nonce_1:', hex(k1))
print('nonce_2:', hex(k2))
# From the retrieved nonce, we get the secret (key)
secret = ((k1 * s1 - h1) * inverse_mod(r1, q)) % q
print('secret:', secret)
# Sign 'subject_danbeer'
new_ecc = ECDSA(secret)
filename = b'subject_danbeer'
signature = new_ecc.sign(b'subject_danbeer')
# Send its signature to the server
resp = access_file(conn, filename.decode(), signature['r'], signature['s'])
print('\nResponse:')
print(binascii.unhexlify(resp['data']).decode())
|
Follow me on twitter
On this CTF, I only worked on the crypto challenges. I managed to solve two crypto challenges. Here is my writeup for those challenges.