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 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
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
Donde
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
Obsérvese que los
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:
Donde
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:
Donde
Nótese que
Si aplicamos este procedimiento en las ecuaciones de ECDSA que tenemos, trataremos de encontrar el vector
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
#!/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
.