<- CTFZONE

Come on feel the nonce

7 minutes to read

We are given source code in Go:

package main

import (
        "crypto/elliptic"
        cryptorand "crypto/rand"
        "crypto/sha256"
        "encoding/base64"
        "fmt"
        "log"
        "math"
        "math/big"
        "math/rand"
        "os"
)

func randInt64() int64 {
        n, err := cryptorand.Int(cryptorand.Reader, big.NewInt(math.MaxInt64))
        if err != nil {
                panic(err)
        }
        return n.Int64()
}

func encrypt(data, priv []byte) string {
        res := make([]byte, 0)
        st := sha256.Sum256(priv)
        for i, b := range data {
                res = append(res, b^st[i])
        }
        return base64.StdEncoding.EncodeToString(res)
}

func decrypt(enc string, priv []byte) string {
        res := make([]byte, 0)
        data, _ := base64.StdEncoding.DecodeString(enc)
        st := sha256.Sum256(priv)
        for i, b := range data {
                res = append(res, b^st[i])
        }
        return string(res)
}

func main() {
        flag := os.Getenv("FLAG")

        curve := elliptic.P256()
        priv, _, _, err := elliptic.GenerateKey(curve, cryptorand.Reader)
        if err != nil {
                log.Fatal(err)
        }

        fmt.Printf("enc_flag = %q\n", encrypt([]byte(flag), priv))

        rand.Seed(randInt64())

        for i := int64(0); i < randInt64(); i++ {
                rand.Uint64()
        }

        for i := 0; i <= 607; i++ {
                msg := fmt.Sprintf("msg_%d", i)
                hash := sha256.Sum256([]byte(msg))
                h := new(big.Int).SetBytes(hash[:])

                r, s := Sign(curve, rand.Uint64(), priv, h)

                fmt.Printf("h[%[1]d] = %[2]s\nr[%[1]d] = %[3]s\ns[%[1]d] = %[4]s\n", i, h, r, s)  
        }
}

func Sign(curve elliptic.Curve, nonce uint64, priv []byte, h *big.Int) (*big.Int, *big.Int) {
        r := new(big.Int)
        s := new(big.Int)
        d := new(big.Int).SetBytes(priv)
        k := new(big.Int).SetUint64(nonce)

        x, _ := curve.ScalarBaseMult(k.Bytes())
        r.Mod(x, curve.Params().P)

        if r.Sign() == 0 {
                panic("bad nonce")
        }

        s.Mul(r, d)
        s.Mod(s, curve.Params().N)
        s.Add(s, h)
        s.Mod(s, curve.Params().N)
        k.ModInverse(k, curve.Params().N)
        s.Mul(s, k)
        s.Mod(s, curve.Params().N)

        return r, s
}

Moreover, we are given a file called log.txt with a total of 608 signatures and the encrypted flag:

$ head log.txt
enc_flag = "hOtHc2dafgWuv2nHQDGsoGoF+BmDhy3N0seYgY9kVnw="
h[0] = 106132995759974998927623038931468101728092864039673367661724550078579493516352  
r[0] = 18051166252496627800102264022724027258301377836259456556817994423615643066667
s[0] = 92640317177062616510163453417907524626349777891295335142117609371090060820235
h[1] = 7879316208808238663812485364896527134152960535409744690121857898575626153029
r[1] = 115471704120523893976825820273729861954380716558612823937677135779401972000099
s[1] = 88253444681758261894850337672595478098707689792795126664973754773335910861625
h[2] = 108514392945691456671012287741933342528603208652973703270072343215378534310088
r[2] = 17273357182041772804140680226822003503928964298970616439008405277082716423350
s[2] = 65509764364537601259350672638899752182831914240350569385339863955089362099960

$ wc -l log.txt
1825 log.txt

Source code analysis

The program uses an ECDSA implementation on curve P256, generates a private value $x$ (priv) and uses it to encrypt the flag:

        flag := os.Getenv("FLAG")

        curve := elliptic.P256()
        priv, _, _, err := elliptic.GenerateKey(curve, cryptorand.Reader)  
        if err != nil {
                log.Fatal(err)
        }

        fmt.Printf("enc_flag = %q\n", encrypt([]byte(flag), priv))

The encryption is just a XOR cipher between the flag and the SHA256 hash of the private value $x$. Therefore, we need to find the value $x$ to decrypt the flag.

func encrypt(data, priv []byte) string {
        res := make([]byte, 0)
        st := sha256.Sum256(priv)
        for i, b := range data {
                res = append(res, b^st[i])
        }
        return base64.StdEncoding.EncodeToString(res)  
}

After that, the program takes a total of 608 messages of the form msg_i and signs each of them with a standard ECDSA implementation:

        for i := 0; i <= 607; i++ {
                msg := fmt.Sprintf("msg_%d", i)
                hash := sha256.Sum256([]byte(msg))
                h := new(big.Int).SetBytes(hash[:])

                r, s := Sign(curve, rand.Uint64(), priv, h)

                fmt.Printf("h[%[1]d] = %[2]s\nr[%[1]d] = %[3]s\ns[%[1]d] = %[4]s\n", i, h, r, s)  
        }

ECDSA implementation

The code for the ECDSA is almost correct (more information here). In order to sign messages, it uses a generator point $G$ and SHA256 as hash function. Then, the program computes:

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

$$ r = (k \cdot G)_x $$

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

Where $n$ is the order of the curve. The output is the tuple $(h, r, s)$. The code is here:

func Sign(curve elliptic.Curve, nonce uint64, priv []byte, h *big.Int) (*big.Int, *big.Int) {  
        r := new(big.Int)
        s := new(big.Int)
        d := new(big.Int).SetBytes(priv)
        k := new(big.Int).SetUint64(nonce)

        x, _ := curve.ScalarBaseMult(k.Bytes())
        r.Mod(x, curve.Params().P)

        if r.Sign() == 0 {
                panic("bad nonce")
        }

        s.Mul(r, d)
        s.Mod(s, curve.Params().N)
        s.Add(s, h)
        s.Mod(s, curve.Params().N)
        k.ModInverse(k, curve.Params().N)
        s.Mul(s, k)
        s.Mod(s, curve.Params().N)

        return r, s
}

The security flaw

The problem here is that the server generates nonces $k$ wrongly. Also, by the challenge name we can guess that the solution must involve the nonces $k$.

Notice that $k$ are random 64-bit integers, whereas the curve P256 has a 256-bit order.

As a result, we can use a lattice-based attack and LLL to solve the Hidden Number Problem. I found this technique in this website, which points to section 4 of this paper.

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} $$

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} $$

Observe 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.

If we apply this procedure on the ECDSA equations we have, we will try to find the vector $(k_1, \dots, k_i, X x / n, X)$. We know this is a likely to be a short vector within the lattice since all $k_i$ are at most 64-bit numbers and the lattice is defined over a 256-bit order.

Implementation

We can use Python with some SageMath functions to solve the HNP using LLL. We will use all the information we have and in the end we will get the private value $x$ once we know one of the nonces $k_i$ to decrypt the flag:

#!/usr/bin/env python3

import json

from hashlib import sha256
from pwn import b64d, xor
from sage.all import Matrix, QQ

from Crypto.Util.number import long_to_bytes


n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551  
p = n

h, r, s = [], [], []

with open('log.txt') as f:
    enc_flag = b64d(f.readline().split(' = ')[1].strip())

    while (line := f.readline()):
        h.append(int(line.split(' = ')[1]))
        r.append(int(f.readline().split(' = ')[1]))
        s.append(int(f.readline().split(' = ')[1]))

a = list(map(lambda s_i, h_i: pow(s_i, -1, p) * h_i % p, s, h))
t = list(map(lambda r_i, s_i: pow(s_i, -1, p) * r_i % p, r, s))

X = 2 ** 64

raw_matrix = []

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

raw_matrix.append(t + [X / p, 0])
raw_matrix.append(a + [    0, X])

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

for row in L.rows():
    if row[-1] == X:
        k = list(map(int, row[:-2]))
        x = (s[0] * k[0] - h[0]) * pow(r[0], -1, p) % p
        key = sha256(long_to_bytes(x)).digest()
        flag = xor(enc_flag, key)
        print(flag.decode())

Flag

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

$ python3 solve.py
ctfzone{r3l4t3d_n0nc3$_4r3_b4d!}

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