<- CRYPTO

Waiting List

7 minutes to read

We are provided with the server source code in Python (challenge.py):

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


FLAG = 'HTB{dummyflag}'
class ECDSA:
    def __init__(self):
        self.n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
        self.k = 0
        self.g = 5
        self.key = ... #choose your own key

    def sign(self, pt):
        h = sha1(pt).digest()
        h = bytes_to_long(h)
        h = bin(h)[2:]
        h = int(h[:len(bin(self.n)[2:])], 2)
        self.k = randint(1, self.n-1)
        r = pow(self.g, self.k, self.n)
        s = (pow(self.k, -1, self.n) * (h + self.key * r)) % self.n
        lsb = self.k % (2 ** 7)
        return {"h": hex(h)[2:], "r": hex(r)[2:], "s": hex(s)[2:], "lsb": bin(lsb)[2:] }

    def verify(self, pt, sig_r, sig_s):

        h = sha1(pt).digest()
        h = bytes_to_long(h)
        h = bin(h)[2:]
        h = int(h[:len(bin(self.n)[2:])], 2)
        sig_r = int(sig_r, 16)
        sig_s = int(sig_s, 16)
        
        c = pow(sig_s, -1, self.n)
        k = (c *(h +self.key*sig_r)) %self.n
        
        if sig_r== pow(self.g,k,self.n ):
            if pt ==b'william;yarmouth;22-11-2021;09:00':
                return 'Your appointment has been confirmed, congratulations!\n' +\
                        'Here is your flag: ' + FLAG
            else:
                return 'Your appointment has been confirmed!\n'
        else: return 'Signature is not valid\n'


def challenge(req):
    cipher = ECDSA()
    
    req.sendall(b'Welcome to the SteamShake transplant clinic where our mission is to deliver the most vintage and high tech arms worldwide.\n'+\  
                    b'Please use your signature to verify and confirm your appointment.\nEstimated waiting for next appointment: 14 months\n> ')
    try:
            
        dt = json.loads(req.recv(4096).strip())

        res = cipher.verify(dt['pt'].encode(), dt['r'], dt['s'])
        req.sendall(res.encode())
    except Exception as e:
        req.sendall(b'Invalid payload.\n')
        exit(1)
    
    

class incoming(socketserver.BaseRequestHandler):
    def handle(self):
        signal.alarm(300)
        req = self.request
        challenge(req)

class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


def main():
    socketserver.TCPServer.allow_reuse_address = True
    server = ReusableTCPServer(("0.0.0.0", 2310), incoming)
    server.serve_forever()

if __name__ == "__main__":
    main()

We are also given two CSV files called appointments.txt and signatures.txt:

$ head appointments.txt
first_name;last_name;date;time
jamesrobert;cornes;05-01-2021;16:00
lyontine;buziak;11-10-2021;09:00
cassandr;carnell;26-09-2021;11:00
jaqueline;brummett;10-01-2021;15:00
norvol;moatz;09-04-2021;14:00
celestina;moog;02-11-2021;13:00
espute;nirjala;21-11-2021;10:00
bosten;inniss;09-05-2021;10:00
kardarius;hernandez-baranda;22-04-2021;17:00

$ head signatures.txt
h;r;s;k_lsb
7a143bfddd768449bf2808513f35f53758020c1f;1a42a9c82c8eb242b832199d068bcfba53089fae7f4fcd02754893943d6bb884;a1c09c0f8ebf0a109673af60e6b5e270f2fa55b73f5314871486d3fe3480d942;1001001  
73c9e4487fbebc39eb4dcd1d92a3ba92d9d41ef8;3b1f1f5fb4aab1366ddb9a90dbec9a305606fef4226aa8d29e22f50dca3275f8;772b335fab52f06d7e274cdbb478da9e1dfd4445d3fd58ddad2e8a2f4bd4dd97;110101
21f07d3d82c5f89df812c6d7fea96b5637a9bc0d;848f21ad03f005ddd4bd38d0623dc5042f452c3160315ef203a04f38fd1ca2ad;ef19a1aa75c4430439e7a0900499f03c4c0f65b787c5053ee2a18d24af108f87;1110011
1deebeeddef3d3385703be677f45c2c61c5176aa;e7c43a7d237695d8e74a5e841f1d5c19a4f99cfc34413c5046d6063e7e13430b;3fd1c99cf9aa68def64b829c133c4e142eeb80e36fab8d6d3cd569348af93f20;1100010
b787146842b6faa23e69f1e97c3ce997f1a0612e;8fdc3ab9597442f3b0084a405b8dd4e2e143ec38ef7dc9c92dcff0755f7afef1;c9cd09095cfb5aae68a8eb19049f271e1e7274f115733a9ba4862eb6e9478017;111110
68cf88eda82006e5fdc818b5ac0e9247b5c97db4;e6c69f2947bfc0e94ec41de13a21c50f5041a15ee728b24e6d77103130bc91e;91b9fb3c39ec0cc46f3a65d1e25c7671aeea883a2076ba27d978405a309cd7cf;1001001
4ddacfec5160ee3ffb04108ed575883d7585397d;6284198683d767d4d39ca7631972691719c1af456068811b64fb7e7d3cb6738;301c93e7fa0de59dc9c25869012aa92b18e9117f10fe75b3ff04f448c55003cc;1100100
3ff6701d470eb511e4e8d54d8c28d7e55a4a3f3f;2cdb804e31396d692c8ea5893e3f9aaaa30ab93ac12e7dadb35060ca1cbd4eeb;15995cc5781c30aafb52c2716c364e183876c63daeb6b98cd1aeb4907393dc94;1010101
68f4293eda88207d716bee27cbad956c4ae75e36;107b1829c5a3f7e2c3069f413c51df90fc752f0aa07b1b44dc11400e58b8d492;a79de81c865646c3fe64b1fff6b691b3a0f5b1d62a245bdc9aa164adba15098a;1110000

Source code analysis

The server implements an Elliptic Curve Digital Signature Algorithm (ECDSA) to sign appointments from different users. The signed message has format first_name;last_name;date;time. The purpose of the challenge is to forge a signature for the message william;yarmouth;22-11-2021;09:00, as shown in verify:

    def verify(self, pt, sig_r, sig_s):

        h = sha1(pt).digest()
        h = bytes_to_long(h)
        h = bin(h)[2:]
        h = int(h[:len(bin(self.n)[2:])], 2)
        sig_r = int(sig_r, 16)
        sig_s = int(sig_s, 16)
        
        c = pow(sig_s, -1, self.n)
        k = (c *(h +self.key*sig_r)) %self.n
        
        if sig_r== pow(self.g,k,self.n ):
            if pt ==b'william;yarmouth;22-11-2021;09:00':
                return 'Your appointment has been confirmed, congratulations!\n' +\  
                        'Here is your flag: ' + FLAG
            else:
                return 'Your appointment has been confirmed!\n'
        else: return 'Signature is not valid\n'

For that, we need to find the value of self.key, which is redacted:

    def __init__(self):
        self.n = 115792089210356248762697446949407573529996955224135760342422259061068512044369  
        self.k = 0
        self.g = 5
        self.key = ... #choose your own key

For that, we will need to use the provided messages and signatures.

ECDSA implementation

The code for the ECDSA is correct (more information here). In order to sign messages, it uses SHA1 as hash function and computes:

$$ h = \mathrm{SHA1}{(m)} $$

$$ r = g^k \mod{n} $$

$$ s = k^{-1} \cdot \left(h + x \cdot r\right) \mod{n} $$

We have used $x$ for self.key and $m$ for pt. The output signature is the pair $(r, s)$. The code of the function is self-explanatory:

    def sign(self, pt):
        h = sha1(pt).digest()
        h = bytes_to_long(h)
        h = bin(h)[2:]
        h = int(h[:len(bin(self.n)[2:])], 2)
        self.k = randint(1, self.n-1)
        r = pow(self.g, self.k, self.n)
        s = (pow(self.k, -1, self.n) * (h + self.key * r)) % self.n
        lsb = self.k % (2 ** 7)
        return {"h": hex(h)[2:], "r": hex(r)[2:], "s": hex(s)[2:], "lsb": bin(lsb)[2:] }

The security flaw

The problem here is that the server also returns the 7 least significant bits of the nonces $k$ (self.k) as lsb:

        lsb = self.k % (2 ** 7)

This gift allows us to model the Hidden Number Problem (HNP) to find $x$.

Hidden Number Problem

The HNP is usually defined as:

$$ t_i \cdot \alpha + a_i \equiv b_i \pmod{p} $$

Where $\alpha$ is the hidden number and both $t_i$ and $a_i$ are known, given $i$ equations. We can apply the ECDSA signature formula to this format:

$$ s_i \equiv k_i^{-1} \cdot \left(h_i + x \cdot r_i\right) \pmod{n} $$

$$ s_i k_i \equiv h_i + x \cdot r_i \pmod{n} $$

$$ r_i \cdot x + h_i \equiv s_i k_i \pmod{n} $$

$$ (s_i^{-1} r_i) \cdot x + (s_i^{-1} h_i) \equiv k_i \pmod{n} $$

Moreover, we know 7 bits from $k_i$, so $k_i = 2^7 \cdot k^\mathrm{(MSB)}_i + k^\mathrm{(LSB)}_i$. It follows that

$$ (s_i^{-1} r_i) \cdot x + (s_i^{-1} h_i) \equiv 2^7 \cdot k^\mathrm{(MSB)}_i + k^\mathrm{(LSB)}_i \pmod{n} $$

$$ (2^{-7} s_i^{-1} r_i) \cdot x + \left(2^{-7} (s_i^{-1} h_i - k^\mathrm{(LSB)}_i)\right) \equiv k^\mathrm{(MSB)}_i \pmod{n} $$

We can define a lattice that contains the solution for the HNP. In the definition, we can use the lattice spanned by the columns of:

$$ M = \begin{pmatrix} p & & & & t_1 & a_1 \\ & p & & & t_2 & a_2 \\ & & \ddots & & \vdots & \vdots \\ & & & p & t_i & a_i \\ & & & & X / p & \\ & & & & & X \\ \end{pmatrix} $$

Where $X$ is an upper bound for the $b_i$ values. Notice that the vector $(b_1, \dots, b_i, \alpha, X \alpha / p, X)$ is in the lattice:

$$ \begin{pmatrix} p & & & & t_1 & a_1 \\ & p & & & t_2 & a_2 \\ & & \ddots & & \vdots & \vdots \\ & & & p & t_i & a_i \\ & & & & X / p & \\ & & & & & X \\ \end{pmatrix} \cdot \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_i \\ \alpha \\ 1 \end{pmatrix} = \begin{pmatrix} c_1 p + \alpha t_1 + a_1 \\ c_2 p + \alpha t_2 + a_2 \\ \vdots \\ c_i p + \alpha t_i + a_i \\ X \alpha / p \\ X \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_i \\ X \alpha / p \\ X \end{pmatrix} $$

Notice that $c_i$ are just arbitrary integer numbers, they are irrelevant because we are working $\mod{p}$. The target vector is supposed to be short, so that it can be found in the reduced lattice after applying LLL.

We can use Python to generate the matrix substituting the values above:

n = 115792089210356248762697446949407573529996955224135760342422259061068512044369  
g = 5
pt = b'william;yarmouth;22-11-2021;09:00'

hs, rs, ss, ks_lsb = [], [], [], []

with open('signatures.txt') as f:
    f.readline()
    while (line := f.readline()):
        values = line.split(';')
        hs.append(int(values[0], 16))
        rs.append(int(values[1], 16))
        ss.append(int(values[2], 16))
        ks_lsb.append(int(values[3], 2))

p = n

a_i = list(
    map(
        lambda s, h, k_lsb: pow(2, -7, p) * (pow(s, -1, p) * h - k_lsb) % p,
        ss, hs, ks_lsb
    )
)

t_i = list(
    map(
        lambda r, s: pow(2, -7, p) * pow(s, -1, p) * r % p,
        rs, ss
    )
)

X = 2 ** (n.bit_length() - 7)

raw_matrix = []

for i in range(len(a_i)):
    raw_matrix.append([0] * i + [p] + [0] * (len(a_i) - i + 1))

raw_matrix.append(t_i + [X / p, 0])
raw_matrix.append(a_i + [0, X])

If the vector $(b_1, \dots, b_i, X \alpha / p, X)$ is short enough, the LLL algorithm will reduce the lattice basis and the target vector will appear in the basis. In other words, we are solving the Shortest Vector Problem (SVP). This can be done importing some functions from SageMath:

M = Matrix(QQ, raw_matrix)
L = M.LLL()

for row in L.rows():
    k = int(row[0] * 2 ** 7 + ks_lsb[0])

    if rs[0] == pow(g, k, n) and row[-1] == X:
        key = (ss[0] * k - hs[0]) * pow(rs[0], -1, n) % n
        h = sha1(pt).digest()
        h = bytes_to_long(h)
        h = bin(h)[2:]
        h = int(h[:len(bin(n)[2:])], 2)
        r = pow(g, k, n)
        s = (pow(k, -1, n) * (h + key * r)) % n

        io = remote(host, port)
        io.sendlineafter(b'> ', json.dumps({'pt': pt.decode(), 'r': hex(r), 's': hex(s)}).encode())  
        io.success(io.recv().decode())

As can be seen, we iterate though the rows of the reduced basis (SageMath applies LLL in rows, that’s why we defined the input matrix in rows as well). If for a given row, the $r$ value equals $g^k$ with the corresponding $k$ (taking into account MSB and LSB), and also the last element of the vector is $X$ (the upper bound), then we have the target vector and we can find $x$ (self.key) in order to forge a signature for the expected message.

Finally, we send it to the server and wait to see the flag.

Flag

If we run the script, we will see the flag:

$ python3 solve.py 142.93.47.151:30991
[+] Opening connection to 142.93.47.151 on port 30991: Done
[+] Your appointment has been confirmed, congratulations!
    Here is your flag: HTB{t3ll_m3_y0ur_s3cr37_w17h0u7_t3ll1n9_m3_y0ur_s3cr37_1fam31l}  
[*] Closed connection to 142.93.47.151 port 30991

The full script can be found in here: solve.py.