Biased Heritage

7 minutes to read

This challenge is kind of a continuation of Colliding Heritage. We are provided with the server source code in Python:

#!/usr/bin/env python3

import signal
from secrets import randbelow
from hashlib import sha256
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long

FLAG = "HTB{???????????????????????????????????????}"


class SHA256chnorr:

    def __init__(self):
        # while True:
        #     self.q = getPrime(512)
        #     self.p = 2*self.q + 1
        #     if isPrime(self.p):
        #         break
        self.p = 0x184e26a581fca2893b2096528eb6103ac03f60b023e1284ebda3ab24ad9a9fe0e37b33eeecc4b3c3b9e50832fd856e9889f6c9a10cde54ee798a7c383d0d8d2c3  
        self.q = (self.p - 1) // 2
        self.g = 3
        self.x = randbelow(self.q)
        self.y = pow(self.g, self.x, self.p)

    def H(self, msg):
        return bytes_to_long(2 * sha256(msg).digest()) % self.q

    def sign(self, msg):
        k = self.H(msg + long_to_bytes(self.x))
        r = pow(self.g, k, self.p) % self.q
        e = self.H(long_to_bytes(r) + msg)
        s = (k - self.x * e) % self.q
        return (s, e)

    def verify(self, msg, sig):
        s, e = sig
        if not (0 < s < self.q):
            return False
        if not (0 < e < self.q):
            return False
        rv = pow(self.g, s, self.p) * pow(self.y, e, self.p) % self.p % self.q
        ev = self.H(long_to_bytes(rv) + msg)
        return ev == e


def menu():
    print('[S]ign a message')
    print('[V]erify a signature')
    return input('> ').upper()[0]


def main():
    sha256chnorr = SHA256chnorr()
    print('g:', sha256chnorr.g)
    print('y:', sha256chnorr.y)
    print('p:', sha256chnorr.p)

    for _ in range(3):
        choice = menu()

        if choice == 'S':
            msg = bytes.fromhex(input('Enter message> '))
            if b'right hand' in msg:
                print('No!')
            else:
                sig = sha256chnorr.sign(msg)
                print('Signature:', sig)

        elif choice == 'V':
            msg = bytes.fromhex(input('Enter message> '))
            s = int(input('Enter s> '))
            e = int(input('Enter e> '))
            if sha256chnorr.verify(msg, (s, e)):
                if msg == b'right hand':
                    print(FLAG)
                else:
                    print('Valid signature!')
            else:
                print('Invalid signature!')

        else:
            print('Invalid choice...')


if __name__ == '__main__':
    signal.alarm(30)
    main()

Schnorr signature

The challenge implements a signing server using Schnorr signature. The algorithm to sign a message $m$ is the following:

Choose a private signing key $x$ and a prime number $p$ such that $q = \displaystyle\frac{p - 1}{2}$ is a prime number as well
Choose a random nonce value $k$
Let $r = (g^k \mod{p}) \mod{q}$
Let $e = H(r \;||\; m)$ where $H$ is a hash function and $||$ denotes concatenation
Let $s = k - xe$

The signature is the pair $(s, e)$.

Challenge implementation

In this challenge, the class SHA256chnorr uses SHA256 as hash function $H$ and the nonce value $k$ is not chosen randomly, but as $k = H(m \;||\; x)$:

    def H(self, msg):
        return bytes_to_long(md5(msg).digest()) % self.q  

    def sign(self, msg):
        k = self.H(msg + long_to_bytes(self.x))
        r = pow(self.g, k, self.p) % self.q
        e = self.H(long_to_bytes(r) + msg)
        s = (k - self.x * e) % self.q
        return (s, e)

The security flaw

The server allows us to use two options but only three times. The two options are to sign message and to verify a message. The flag will appear as long as we can verify a specific message ("right hand"). Obviously, we can’t use option S to sign that specific message:

    for _ in range(3):
        choice = menu()

        if choice == 'S':
            msg = bytes.fromhex(input('Enter message> '))  
            if b'I am the left hand' in msg:
                print('No!')
            else:
                sig = md5chnorr.sign(msg)
                print('Signature:', sig)

        elif choice == 'V':
            msg = bytes.fromhex(input('Enter message> '))
            s = int(input('Enter s> '))
            e = int(input('Enter e> '))
            if md5chnorr.verify(msg, (s, e)):
                if msg == b'I am the left hand':
                    print(FLAG)
                else:
                    print('Valid signature!')
            else:
                print('Invalid signature!')

        else:
            print('Invalid choice...')

So, we will use option S two times and then V to send the required message but signed appropriately. Therefore, with the first two signatures, we must somehow find the private key $x$, needed to sign arbitrary messages.

Digital signature algorithms can be comprimised if a nonce value $k$ is reused in different message signatures, how we forced in Colliding Heritage. This approach is no longer feasible since SHA256 is collision-resistant.

When I noticed the word “Biased” in the name of the challenge, that reminded me to a paper called Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies. In this paper, LLL lattice reduction is used to solve the Hidden Number Problem (HNP) on Elliptic Curve Digital Signature Algorithm (ECDSA) when the nonces $k$ are not correctly chosen (for instance, their value is much shorter than the value of $q$).

HNP on biased nonces

I knew that this was the intended approach since SHA256 outputs a 256-bit number (64 bytes) and the prime number $p$ is huge (and thus $q$). Therefore, we have the following setup given the fact that we must sign two arbitrary messages $m_1$ and $m_2$:

$$ s_1 = k_1 - x e_1 \mod{q} \\ s_2 = k_2 - x e_2 \mod{q} \\ $$

The HNP tries to solve the equation $a_i + k_i = \alpha \cdot t_i \mod{n}$, where $\alpha$ is the hidden number and $k_i < 2^l$, for some $l \in \mathbb{Z}$. The values of $a_i$ and $b_i$ are known. We can reformulate the HNP for our situation as follows:

Let $a_i = -s_i$
Let $t_i = e_i$
Let $\alpha = x$
Let $n = q$

So we get the equation $s_i = k_i - x \cdot e_i \mod{q}$. Before going on with the solution, notice that the hash function actually outputs two times the digest:

    def H(self, msg):
        return bytes_to_long(2 * sha256(msg).digest()) % self.q

This fact broke my plans for a minute, because now $k$ had 512 bits and it was much closer to $q$ than before. However, then I realized that the HNP was still solvable because the digest was repeated, so if $k’$ is the duplicated digest, we have $k’ = k \;||\; k = 2^{256} k + k = (2^{256} + 1) k$. So we can add this condition to the HNP equation as follows (let $M = (2^{256} + 1)^{-1} \mod{q}$):

$$ s_i = k'_i - x \cdot e_i \mod{q} $$

$$ s_i = (2^{256} + 1) k_i - x \cdot e_i \mod{q} $$

$$ M s_i = k_i - x \cdot M e_i \mod{q} $$

Taking again the standard HNP parameters, we have:

Let $a_i = - M s_i$
Let $t_i = M e_i$

At this point, the HNP is solvable using the following lattice basis ($R = 2^{256}$, an upper-bound for $k_i$):

$$ \begin{pmatrix} q & 0 & 0 & 0 \\ 0 & q & 0 & 0 \\ t_1 & t_2 & R / q & 0 \\ a_1 & a_2 & 0 & R \\ \end{pmatrix} $$

The algorithm to solve the HNP involves the use of LLL to reduce the lattice basis and find a short vector whose components are $(-k_1, -k_2, R \alpha / q, R)$. More information can be found in this paper.

Once we have the value of $k_1$ or $k_2$, it is trivial to find $x$ and thus sign the required message to find the flag.

Python implementation

Using some SageMath’s functions, we can write these sentences to solve the challenge:

io = get_process()

io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'Enter message> ', b'A'.hex().encode())
io.recvuntil(b'Signature: ')
s1, e1 = eval(io.recvline().decode())

io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'Enter message> ', b'B'.hex().encode())
io.recvuntil(b'Signature: ')
s2, e2 = eval(io.recvline().decode())

R = 2 ** 256
M = pow(R + 1, -1, q)

a1 = -M * s1 % q
a2 = -M * s2 % q
t1 = M * e1 % q
t2 = M * e2 % q

M = matrix(QQ, [
    [q,  0,  0,     0],
    [0,  q,  0,     0],
    [t1, t2, R / q, 0],
    [a1, a2, 0,     R],
])

B = M.LLL()

for row in B.rows():
    k1, k2 = -row[0], -row[1]

    x1 = ((R + 1) * k1 - s1) * pow(e1, -1, q) % q
    x2 = ((R + 1) * k2 - s2) * pow(e2, -1, q) % q

    if (s1, e1) == sign(b'A', x1):
        x = x1
    elif (s2, e2) == sign(b'B', x2):
        x = x2
    else:
        continue

    s, e = sign(b'right hand', x)

    io.sendlineafter(b'> ', b'V')
    io.sendlineafter(b'Enter message> ', b'right hand'.hex().encode())  
    io.sendlineafter(b'Enter s> ', str(s).encode())
    io.sendlineafter(b'Enter e> ', str(e).encode())

    io.success(io.recv().decode())
    break

Flag

The algorithm is not fully reliable, but eventually it will print out the flag:

$ python3 solve.py 209.97.134.50:30631
[+] Opening connection to 209.97.134.50 on port 30631: Done  
[+] HTB{full_s1z3_n0nc3_l4cks_ful1_s1z3_3ntr0py}
[*] Closed connection to 209.97.134.50 port 30631

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