<- CTFZONE

Come on feel the nonce

7 minutos de lectura

Se nos proporciona el código fuente en 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
}

Además, se nos da un archivo llamado log.txt con un total de 608 firmas y la flag cifrada:

$ 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

Análisis del código fuente

El programa utiliza una implementación de ECDSA en la curva P256, genera un valor privado $x$ (priv) y lo usa para cifrar la 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))

El cifrado es solo un XOR entre la flag y el hash SHA256 del valor privado $x$. Por lo tanto, necesitamos encontrar el valor $x$ para descifrar la 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)  
}

Después de eso, el programa toma un total de 608 mensajes de la forma msg_i y firma cada uno de ellos con una implementación de ECDSA estándar:

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

Implementación del ECDSA

El código para el ECDSA es casi correcto (más información aquí). Para firmar mensajes, utiliza un punto generador $G$ y SHA256 como función hash. Entonces, el programa calcula:

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

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

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

Donde $n$ es el orden de la curva. La salida es la tupla $(h, r, s)$. El código empleado es este:

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
}

El fallo de seguridad

El problema aquí es que el servidor genera los nonces $k$ de manera incorrecta. Además, por el nombre del reto, podemos intuir que la solución debe involucrar a los nonces $k$.

Obsérvese que los $k$ son enteros aleatorios de 64 bits, mientras que la curva P256 tiene un orden de 256 bits.

Como resultado, podemos usar un ataque basado en retículo (lattice) y LLL para resolver el Hidden Number Problem. Encontré esta técnica en esta página web, que referencia a la sección 4 de este artículo.

Hidden Number Problem

El HNP generalmente se define como:

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

Donde $\alpha$ ese el número oculto y los valores $t_i$ y $a_i$ son conocidos, dadas $i$ ecuaciones. Podemos transformar la fórmula de la firma ECDSA a este formato:

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

Podemos definir un retículo que contenga la solución del HNP. En la definición, podemos usar el retículo formado por las columnas de:

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

Donde $X$ es una cota superior para los valores $b_i$. Obsérvese que el vector $(b_1, \dots, b_i, X \alpha / p, X)$ está en el retículo:

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

Nótese que $c_i$ son solo números enteros arbitrarios, son irrelevantes porque estamos trabajando $\mod{p}$. El vector objetivo debe ser un vector corto para que aparezca en la base reducida al aplicar el algoritmo LLL.

Si aplicamos este procedimiento en las ecuaciones de ECDSA que tenemos, trataremos de encontrar el vector $(k_1, \dots, k_i, X x / n, X)$. Sabemos que este vector es corto dentro del retículo ya que todos los $k_i$ son números de 64 bits y el retículo involucra vectores con entradas de 256 bits.

Implementación

Podemos usar Python con algunas funciones de SageMath para resolver el HNP mediante LLL. Usaremos toda la información que tenemos y al final obtendremos el valor privado $x$ una vez que conozcamos uno de los nonces $k_i$ para descifrar la 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

Si ejecutamos el script, obtendremos la flag:

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

El script completo se puede encontrar aquí: solve.py.