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 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
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
Where
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
Notice that
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:
Where
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:
Where
Observe that
If we apply this procedure on the ECDSA equations we have, we will try to find the vector
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
#!/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
.