Our previous implementation was flawed!
I don't want to use the crypto/rand generator, as it is probably not quantum resistant! Instead, I modified all the rngCooked values in the previous generator.
There are so many values! It is impossible to retrieve them.
ots-sig.donjon-ctf.io:4001
File: challenge.go
Connecting to the address:
$ nc ots-sig.donjon-ctf.io 4001
Public key: [REDACTED]
Enter signature:
You failed! Private key was: [REDACTED]
Public key: [REDACTED]
Enter signature: ^CThis challenge is the continuation of One Time-Based Signature. This time we have this source:
package main
import (
"bufio"
"crypto/sha256"
"encoding/base64"
"fmt"
"io/ioutil"
"os"
"strings"
"time"
"./math/rand" // same as default implementation, with different rngCooked array
"github.com/dchest/wots"
)
const defaultFlag string = "CTF{xxx}"
func main() {
var message = []byte("Sign me if you can")
// Not so secure seed, but prng internals are secret
rng := rand.New(rand.NewSource(time.Now().UnixNano()))
for {
var ots = wots.NewScheme(sha256.New, rng)
priv, pub, _ := ots.GenerateKeyPair()
fmt.Println("Public key:", base64.StdEncoding.EncodeToString(pub))
reader := bufio.NewReader(os.Stdin)
fmt.Print("Enter signature: ")
text, err := reader.ReadString('\n')
if err != nil {
fmt.Println("Error occurred. Please try again later.")
return
}
text = strings.TrimSuffix(text, "\n")
signature, err := base64.StdEncoding.DecodeString(text)
if err != nil {
return
}
if ots.Verify(pub, message, signature) {
fmt.Print("Congratulations! Flag: ")
flag, err := ioutil.ReadFile("secret")
if err != nil {
fmt.Println(defaultFlag)
} else {
fmt.Println(string(flag))
}
} else {
fmt.Println("You failed! Private key was:", base64.StdEncoding.EncodeToString(priv))
fmt.Println()
}
}
}The time is still used to seed the PRNG but this time with all bits from time.Now().UnixNano(). It's also noted that we use this: "./math/rand" // same as default implementation, with different rngCooked array.
In One Time-Based Signature we only had one time-based public key, now we have an unlimited amount of private keys that are generated from a PRNG that's seeded only once.
If you've never attacked a PRNG before like me you might want to read this: https://insomniasec.com/cdn-assets/Not_So_Random_-_Exploiting_Unsafe_Random_Number_Generator_Use.pdf
The concept is simple:
- in a PRNG we have seeds, a state and a period
- the seed is used to create the initial state
- the current state contains the internal properties of the PRNG
- the period describes the length of all possible outputs before it's repeated
We are going to look at the math/rand source and create our own local version of the package to manipulate it and find out which functions are actually called, where to attack and what this has to do with rngCooked.
We need: math/rand/rng.go and math/rand/rand.go.
If you try this challenge yourself you might copy all from the math/rand folder, but these are the ones that are actually used in the challenge setup. They are typically in /usr/lib/go/src/ or here: https://golang.org/src/math/rand/
This is the relevant part merged from both files:
// NewSource returns a new pseudo-random Source seeded with the given value.
// Unlike the default Source used by top-level functions, this source is not
// safe for concurrent use by multiple goroutines.
func NewSource(seed int64) Source {
var rng rngSource
rng.Seed(seed)
return &rng
}
type rngSource struct {
tap int // index into vec
feed int // index into vec
vec [rngLen]int64 // current feedback register
}
const (
rngLen = 607
rngTap = 273
rngMax = 1 << 63
rngMask = rngMax - 1
int32max = (1 << 31) - 1
)
// Seed uses the provided seed value to initialize the generator to a deterministic state.
func (rng *rngSource) Seed(seed int64) {
rng.tap = 0
rng.feed = rngLen - rngTap
seed = seed % int32max
if seed < 0 {
seed += int32max
}
if seed == 0 {
seed = 89482311
}
x := int32(seed)
for i := -20; i < rngLen; i++ {
x = seedrand(x)
if i >= 0 {
var u int64
u = int64(x) << 40
x = seedrand(x)
u ^= int64(x) << 20
x = seedrand(x)
u ^= int64(x)
u ^= rngCooked[i]
rng.vec[i] = u
}
}
}
// seed rng x[n+1] = 48271 * x[n] mod (2**31 - 1)
func seedrand(x int32) int32 {
const (
A = 48271
Q = 44488
R = 3399
)
hi := x / Q
lo := x % Q
x = A*lo - R*hi
if x < 0 {
x += int32max
}
return x
}
// Uint64 returns a non-negative pseudo-random 64-bit integer as an uint64.
func (rng *rngSource) Uint64() uint64 {
rng.tap--
if rng.tap < 0 {
rng.tap += rngLen
}
rng.feed--
if rng.feed < 0 {
rng.feed += rngLen
}
x := rng.vec[rng.feed] + rng.vec[rng.tap]
rng.vec[rng.feed] = x
return uint64(x)
}The function seedrand can be ignored since it's not modified in the challenge.
Things we notice:
- the
int64 seedis convertedseed % int32max, so we don't have to guess 64 bits, only 32 bits from which some can be guessed based on the time (this is the seed) - special seeds like
seed < 0(which will not happen with time) orseed == 0(which could happen since the modulo can be zero, but can't take advantage of this, chances are 1 : int32max) are used - after a lot of deterministic calculation based on the seed we
XORthe resulting value withrngCooked, which we don't have (this is the initial state) - the resulting value is stored in
rng.vecand read withrng.tapandrng.feedproperties (this is the current state) - since
rng.tapandrng.feedare rolled over torngLen - values from these positions are added and stored back at
rng.feedin therng.vec(this increases the period)
Next we need to look at how the ots.GenerateKeyPair() call uses the provide PRNG to generate the private key.
Here are the relevant parts of wots.go from: https://github.com/dchest/wots
// Scheme represents one-time signature signing/verification configuration.
type Scheme struct {
blockSize int
hashFunc func() hash.Hash
rand io.Reader
}
// NewScheme returns a new signing/verification scheme from the given function
// returning hash.Hash type and a random byte reader (must be cryptographically
// secure, such as crypto/rand.Reader).
//
// The hash function output size must have minimum 16 and maximum 128 bytes,
// otherwise GenerateKeyPair method will always return error.
func NewScheme(h func() hash.Hash, rand io.Reader) *Scheme {
return &Scheme{
blockSize: h().Size(),
hashFunc: h,
rand: rand,
}
}
// PrivateKeySize returns private key size in bytes.
func (s *Scheme) PrivateKeySize() int { return (s.blockSize + 2) * s.blockSize }
// PublicKeySize returns public key size in bytes.
func (s *Scheme) PublicKeySize() int { return s.blockSize }
// SignatureSize returns signature size in bytes.
func (s *Scheme) SignatureSize() int { return (s.blockSize+2)*s.blockSize + s.blockSize }
// PublicKey represents a public key.
type PublicKey []byte
// PrivateKey represents a private key.
type PrivateKey []byte
// hashBlock returns in hashed the given number of times: H(...H(in)).
// If times is 0, returns a copy of input without hashing it.
func hashBlock(h hash.Hash, in []byte, times int) (out []byte) {
out = append(out, in...)
for i := 0; i < times; i++ {
h.Reset()
h.Write(out)
out = h.Sum(out[:0])
}
return
}
// GenerateKeyPair generates a new private and public key pair.
func (s *Scheme) GenerateKeyPair() (PrivateKey, PublicKey, error) {
if s.blockSize < 16 || s.blockSize > 128 {
return nil, nil, errors.New("wots: wrong hash output size")
}
// Generate random private key.
privateKey := make([]byte, s.PrivateKeySize())
if _, err := io.ReadFull(s.rand, privateKey); err != nil {
return nil, nil, err
}
publicKey, err := s.PublicKeyFromPrivate(privateKey)
if err != nil {
return nil, nil, err
}
return privateKey, publicKey, nil
}
// PublicKeyFromPrivate returns a public key corresponding to the given private key.
func (s *Scheme) PublicKeyFromPrivate(privateKey PrivateKey) (PublicKey, error) {
if len(privateKey) != s.PrivateKeySize() {
return nil, errors.New("wots: private key size doesn't match the scheme")
}
// Create public key from private key.
keyHash := s.hashFunc()
blockHash := s.hashFunc()
for i := 0; i < len(privateKey); i += s.blockSize {
keyHash.Write(hashBlock(blockHash, privateKey[i:i+s.blockSize], 256))
}
return keyHash.Sum(nil), nil
}The concept of wots is the Winternitz One-Time Signature described here: https://cryptoservices.github.io/quantum/2015/12/04/one-time-signatures.html
The security is based on the security of the one-way function, in this case sha256. Each block is hashed 256 times, the resulting hashes are also hashed. We can't attack that.
Things we notice instead:
- we use
io.ReadFullto read the random values intoprivateKey, which is a byte array of the private key size (in this case 1088) - that private key is returned, so the base64 encoded private key we receive from the server are the raw results from the read call
Now we need to look at the io.Reader in math/rand/rand.go:
// New returns a new Rand that uses random values from src
// to generate other random values.
func New(src Source) *Rand {
s64, _ := src.(Source64)
return &Rand{src: src, s64: s64}
}
// A Rand is a source of random numbers.
type Rand struct {
src Source
s64 Source64 // non-nil if src is source64
// readVal contains remainder of 63-bit integer used for bytes
// generation during most recent Read call.
// It is saved so next Read call can start where the previous
// one finished.
readVal int64
// readPos indicates the number of low-order bytes of readVal
// that are still valid.
readPos int8
}
func (r *Rand) Read(p []byte) (n int, err error) {
if lk, ok := r.src.(*lockedSource); ok {
return lk.read(p, &r.readVal, &r.readPos)
}
return read(p, r.src, &r.readVal, &r.readPos)
}
func read(p []byte, src Source, readVal *int64, readPos *int8) (n int, err error) {
pos := *readPos
val := *readVal
rng, _ := src.(*rngSource)
for n = 0; n < len(p); n++ {
if pos == 0 {
if rng != nil {
val = rng.Int63()
} else {
val = src.Int63()
}
pos = 7
}
p[n] = byte(val)
val >>= 8
pos--
}
*readPos = pos
*readVal = val
return
}
// Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
func (rng *rngSource) Int63() int64 {
return int64(rng.Uint64() & rngMask)
}We aren't using a locked source, so we can ingore that.
Things we notice:
- the
rng.Uint64()value is ANDed with therngMaskto get anint64 - that value is read one byte at a time and stored in the output byte array
- we only use 7 of 8 bytes of the generated integer
- if we don't read a multiple of 7 the remaining part of
valis stored inreadValandreadPosofrand.Rand
The func (r *Rand) Read(p []byte) only uses 7 of the 8 bytes. Our PrivateKeySize is 1088 bytes, we therefore have the last 3 bytes from another call of func (rng *RngSource) Uint64() since 1088 % 7 = 3. If we generate 7 keys our readPos is back at 0, the next call will read a fresh value since x * 7 % 7 = 0. This makes things easier I guess.
Now we know everything we need to start solving this challenge.
We need to attack the internals of golangs math/rand PRNG.
The server leaks us the generated bytes with the privatekey, we can use them to restore the internal state of the generator.
First thing we do: Removing all unnecessary functions from the copied math/rand package after removing files we don't need
Next:
- export all fields, functions and variables from our
math/randversion to access them in our main function - write a function to get the
uint64back from a 7 byte array - initialize our own PRNG to store the obtained state in it
This is my reverse of the uint64 problem:
func restoreUint64(a []byte) uint64 {
var val int64
for i := len(a) - 1; i >= 0; i-- {
val |= int64(a[i]) & rngMask
if i > 0 {
val <<= 8
}
}
return uint64(val)
}Because working with the remote data makes debugging harder I started off with a time-based PRNG and my 'attack' PRNG seeded with zero.
I then obtained rngLen bytes from it to write the calculated uint64 into the vec field of my 'attack' PRNG.
This would look something like this:
func main() {
timeRand := rand.New(rand.NewSource(time.Now().UnixNano()))
var leakedBytes []byte
for i := 0; i < rngLen; i++ {
random := make([]byte, 7)
timeRand.Read(random)
leakedBytes = append(leakedBytes, random...)
}
myRand := rand.New(rand.NewSource(0))
mySource := myRand.S64.(*rand.RngSource)
for i := 0; i < len(leakedBytes); i += 7 {
leak := leakedBytes[i : i+7]
mySource.Uint64() // calling here to forward feed and tap
mySource.Vec[mySource.Feed] = int64(restoreUint64(leak))
}
for i := 0; i < rngLen; i++ {
random, mybyte := make([]byte, 7), make([]byte, 7)
timeRand.Read(random)
mySource.Read(mybyte)
if !equals(random, mybyte) {
log.Fatal("Not matching!", random, mybyte)
}
}
}After encountering some bugs I thought that maybe an int64 overflow leading to negative values in the original vec was the problem so I simply used a modified array [rngLen][]int64 so that I could store more possible values for a single position in there. After rngLen rounds of restoring I tried adding the stored values from my own vec to compare them to the expected ones. Since there were now multiple values I calculated each possible combination using the cartesian product of vec[feed] and vec[tap].
I then fixed my bug and removed all of that again since it's not needed.
After verifying that everything works I changed the first loop to append a generated private key to the leakedBytes.
That worked too. So I replaced that with a loop that read 7 private keys from the remote host and added code that would then generate the eight private key and compare the pubkey to the one received from the remote.
If they are equal I sign the message.
The code now looks like this:
package main
import (
"./math/rand"
"bufio"
"crypto/sha256"
"encoding/base64"
"github.com/dchest/wots"
"log"
"net"
"strings"
)
const (
rngMax = 1 << 63
rngMask = rngMax - 1
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
func removeNewline(r string) string {
return strings.TrimSuffix(r, "\n")
}
func getPubKey(r string) string {
return removeNewline(strings.TrimPrefix(r, "Public key: "))
}
func getPrivKey(r string) string {
return removeNewline(strings.TrimPrefix(r, "You failed! Private key was: "))
}
func restoreUint64(a []byte) uint64 {
var val int64
for i := len(a) - 1; i >= 0; i-- {
val |= int64(a[i]) & rngMask
if i > 0 {
val <<= 8
}
}
return uint64(val)
}
func main() {
c, err := net.Dial("tcp", "ots-sig.donjon-ctf.io:4001")
check(err)
cReader := bufio.NewReader(c)
var leakedBytes []byte
for i := 0; i < 7; i++ {
_, err = cReader.ReadString('\n')
check(err)
_, err = cReader.Read([]byte("Enter signature: "))
check(err)
_, err = c.Write([]byte("\n"))
check(err)
privKeyLine, err := cReader.ReadString('\n')
check(err)
_, err = cReader.ReadByte()
check(err)
decoded, err := base64.StdEncoding.DecodeString(getPrivKey(privKeyLine))
check(err)
leakedBytes = append(leakedBytes, decoded...)
}
myRand := rand.New(rand.NewSource(0))
mySource := myRand.S64.(*rand.RngSource)
for i := 0; i < len(leakedBytes); i += 7 {
leak := leakedBytes[i : i+7]
mySource.Uint64()
mySource.Vec[mySource.Feed] = int64(restoreUint64(leak))
}
ots := wots.NewScheme(sha256.New, myRand)
priv, pub, _ := ots.GenerateKeyPair()
pubKeyLine, err := cReader.ReadString('\n')
check(err)
pubKey := getPubKey(pubKeyLine)
myPub := base64.StdEncoding.EncodeToString(pub)
log.Println("Having:", myPub)
log.Println("Given :", pubKey)
if myPub == pubKey {
var message = []byte("Sign me if you can")
log.Println("Looks fine! Let's sign!")
sig, err := ots.Sign(priv, message)
check(err)
sigBase := base64.StdEncoding.EncodeToString(sig)
_, err = c.Write([]byte(sigBase + "\n"))
check(err)
log.Println("Signature has been sent:", sigBase)
for {
status, err := cReader.ReadString('\n')
check(err)
log.Print(status)
}
}
return
}After executing:
$ go run solve.go
2020/XX/XX 21:58:57 Having: [PUB-BASE64]
2020/XX/XX 21:58:57 Given : [PUB-BASE64]
2020/XX/XX 21:58:57 Looks fine! Lets sign!
2020/XX/XX 21:58:57 Signature has been sent: [SIG-BASE64]
2020/XX/XX 21:58:57 Enter signature: Congratulations! Flag: CTF{m4th_RanD_1s_s0_pr3d1cT4bl3}
2020/XX/XX 21:58:57 Public key: [PUB2-BASE64]If you've read through the PDF above about attacking PRNGs you have read that he describes /dev/urandom as cryptographically secure PRNG. In his attack example he uses a value from there to seed his non-cryptographically secure PRNG. We now understand why using secure seeds doesn't solve the problem with deterministic PRNGs.
If you google for why isn't crypto/rand the default golang you will find this issue on GitHub: golang/go#11871
There have already been incidents where people didn't realize that math/rand was deterministic by default (example),
and even in security-related applications (example).
Additionally, tutorials tend to forego mentioning this potentially-catastrophic default (example).
To resolve this, I propose that the top-level math/rand functions be seeded by crypto/rand's Reader by default.
Someone commented this:
I think that seeding math/rand from crypto/rand will make the problem even worse, because then one could make an (ill-advised) argument for its security.