[Donjon CTF 2020] BLS Signatures and Secret RNG

This post originally appeared on the Cryptohack blog, feel free to read it there. It is presented here as a form of archival and to collect all my posts in one place.

Following on from our Fast Multisignatures and One Time-Based Signature writeups for Ledger Donjon CTF, here are two more for vulnerable signatures schemes from the pure cryptography category. Writeups by Robin_Jadoul.

BoLoS BLS on BLS (100pts)

This signature scheme sounds really good and efficient.

We’re given a README and two files with Python code. The file app.py is just the web interface we can use to interact with the server and isn’t really interesting otherwise, so we’ll ignore that here. The README has a very brief explanation of how the BLS signature scheme works and how the challenge applies it and modifies it.

BLS elliptic curves

The letters BLS occur several times in the challenge name, and they do have different meanings. The first of these meanings that we’ll investigate is Barreto-Lynn-Scott: the inventors of a pairing-friendly elliptic curve. We don’t need to know a lot about pairing-friendly curves and pairings to be able to solve this challenge, but a bare minimum is definitely useful. A pairing-friendly elliptic curve is (as the name might clearly imply) an elliptic curve for which we know how to efficiently compute a pairing. A pairing is a bilinear map $$e : \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$$ where $\mathbb{G}_1$, $\mathbb{G}_2$, $\mathbb{G}_T$ are groups of the same order with respectively generators $g_1$, $g_2$ and $g_T$ such that $e([a]g_1, [b]g_2) = [ab]g_T$.

This means that we can use pairings to solve the Decisional Diffie–Hellman problem (DDH), or even more or less solve the DDH problem once. Note that because the groups don’t necessarily coincide, we might not actually be able to solve the Computational Diffie–Hellman problem (CDH) outside of $\mathbb{G}_T$.

BLS signatures

The second occurrence of BLS refers to the Boneh–Lynn–Shacham signature scheme, that relies on pairing-friendly elliptic curves (so we can instantiate that curve with a BLS curve for example). The first thing we need for this is a function $H$ that maps (hashes) an arbitrary message $m$ onto the group $\mathbb{G}_1$. Our public keys will live in $\mathbb{G}_2$. We write the keypair $(sk, pk) = (sk, [sk]g_2)$.

Now to sign a message $m$, we compute $\sigma = [sk]H(m)$, and to verify the signature, we can check that $$e(\sigma, g_2) = e(H(m), pk)$$, since:

$$e(\sigma, g_2) = e([sk]H(m), g_2) = e(H(m), [sk]g_2) = e(H(m), pk)$$

by the bilinearity of the pairing.

Forgery ahead

The vulnerability in this challenge now comes from the choice of $H$:

$$H(m) = [SHA256(m)]g_1.$$

To see why this is a problem, we will show how transform a signature $\sigma$ for a message $m$ into a valid signature $\sigma'$ for an arbitrary message $m'$. Consider $\sigma = [sk][S]g_1 = [sk \cdot S]g_1$ where for convenience, we will write $S$ (resp. $S'$) to denote the SHA256 hash of $m$ (resp. $m'$). Similarly, we want to obtain the value $\sigma' = [sk][S']g_1 = [sk \cdot S']g_1$. Now it’s fairly easy to see that, knowing both $S$ and $S'$, we can compute $\sigma' = \left[\frac{S'}{S}\right]\sigma$, where of course, the division is modular division $\mod \|g_1\|$.

Implementing it is equally as easy, when we use the same library as the challenge already used. One thing to pay attention to is not to forget to normalize the curve point of $\sigma'$ before sending it to the server, since we can only send the x and y coordinates of the projective representation.

s1 = normalize(multiply(s0, (map_to_field(m1) * inverse(map_to_field(m0), curve_order)) % curve_order))
print(verify_signature(int(s1[0]).to_bytes(48, 'big').hex() + int(s1[1]).to_bytes(48,  'big').hex(), m1))

What was a bit confusing at this point, is that the local file tries to decode the signature as utf8 after it is validated, which will crash. When trying our signature on the server instead, however, we simply get the flag instead of this exception.

Flag: CTF{How_did_you_get_here_and_where's_my_key!?}

Secret RNG (300pts)

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.

In this challenge, we’re given the source code of a Golang application that uses the same one-time signature library as before, but is now using a version of the Golang math/rand library where they replaced all the rngCooked array with their own values. We can get an arbitrary number of public keys, and if for any of those public keys we are able to sign the message "Sign me if you can", we obtain the flag. If our attempted signature was incorrect, the server reveals the private key. The seed used for the PRNG is based on the current time in nanosecond resolution, so we might have a bruteforce opportunity there.

PRNG(o)

Now let’s have a look at what the default Golang PRNG is actually doing.

You can inspect the actual source code here, but for convenience, we will present it here in a simplified version, rewritten in python.

import random

LEN = 607
TAP = 273
class Rng:
    def seed(self, s):
        # This is based on the rngCooked values that we don't know
        # So let's consider this as perfectly unknown and random for now
        self.vec = [random.getrandbits(64) for _ in range(LEN)]
        self.tap = 0
        self.feed = LEN - TAP

    def next(self):
        self.tap -= 1
        if self.tap < 0:
            self.tap = LEN - 1
        self.feed -= 1
        if self.feed < 0:
            self.feed = LEN - 1
        self.vec[self.feed] = (self.vec[self.feed] + self.vec[self.tap]) % (2**64)
        return self.vec[self.feed]

To summarize: there are two pointers (feed and tap) moving over vec in a circular fashion, at a fixed distance from each other. To obtain 64 bits of randomness, we take the value $\text{vec}[\text{feed}] \oplus \text{vec}[\text{tap}]$, which we then also store back into vec[feed]. One other important thing to find in the Golang source code (the parts that are relevant to what the wots library uses, that is), is that of every 64 bits we obtain from our RNG, we only use the lower 56 bits/7 bytes. Observe that this doesn’t impact us in any way since these unknown bits will only ever be XORed with other unknown bits.

This means that we can query enough keys to reconstruct the current value of vec, by each of the vec[feed] values that are present in the revealed private key. Once we have reconstructed the RNG state, it’s only a matter of using it to construct the next private key, verify it matches the provided public key, sign the message and profit.

Aside: Given the length of vec, we need to recover 607 values, each 64 (or 56 in this case) bits to reconstruct the entire PRNG state. If we compare this to the classical weak PRNG, the MT19937 Mersenne Twister, we see that this amount to just a bit less than double the amount of bits we need there: 624 values of 32 bits each.

Imp(y)lementation

The code to reconstruct the PRNG state is presented here (courtesy of esrever):

#!/usr/bin/python3
import socket

class Socket(socket.socket):
    def recvpred(self, pred):
        data = b''
        while not pred(data):
            try:
                buffer = self.recv(1)
                data += buffer
            except:
                print('\n'.join([
                    '[Error] In recvpred:',
                    '\texpected={}'.format(expected),
                    '\tpartial data={}'.format(data),
                ]))
                raise
        return data

    def recvuntil(self, expected):
        return self.recvpred(lambda s: expected in s)

    def recvn(self, n):
        return self.recvpred(lambda s: len(s) == n)

    def recvline(self):
        return self.recvuntil(b'\n')

    def sendafter(self, expected, msg):
        data = self.recvuntil(expected)
        self.sendall(msg)
        return data

    def interact(self):
        '''
        Use Telnet.interact().
        May break with non-printable characters, especially IAC (0xFF).

        Possible enhancement: adopt tube.interactive() in pwnlib.
        https://github.com/Gallopsled/pwntools/blob/dev/pwnlib/tubes/tube.py
        '''
        from telnetlib import Telnet

        def listener():
            '''
            Modified from Telnet.listener() so that it stops itself.
            '''
            from sys import stdout
            while not finished:
                try:
                    data = tn.read_eager()
                except EOFError:
                    print('*** Connection closed by remote host ***')
                    return
                if data:
                    stdout.write(data.decode('ascii'))
                else:
                    stdout.flush()

        print('*** Interact starts ***')
        finished = False
        tn = Telnet()
        tn.listener = listener
        tn.sock = self

        tn.interact()

        finished = True
        tn.sock = None
        print('*** Interact ends ***')

# ===== END OF TEMPLATE =====


import base64
import re


LEN = 607
TAP = 273
class Rng:
    def __init__(self):
        # Can't really know anything here without correlating different seeds
        self.vec = [0] * LEN
        self.tap = 0
        self.feed = LEN - TAP

        self.pos = 7
        self.val = 0

        self.set_count = 0

    def next(self):
        self.tap -= 1
        if self.tap < 0:
            self.tap = LEN - 1
        self.feed -= 1
        if self.feed < 0:
            self.feed = LEN - 1
        self.vec[self.feed] = (self.vec[self.feed] + self.vec[self.tap]) % (2**64)
        return self.vec[self.feed]

    def next_bytes(self, n):
        bs = bytearray(n)
        for i in range(n):
            if self.pos == 0:
                self.pos = 7
                self.val = self.next()
            bs[i] = self.val & 0xff
            self.val >>= 8
            self.pos -= 1
        return bytes(bs)

    def set_next(self, val):
        self.set_count += 1
        self.tap -= 1
        if self.tap < 0:
            self.tap = LEN - 1
        self.feed -= 1
        if self.feed < 0:
            self.feed = LEN - 1
        self.vec[self.feed] = val

    def set_next_bytes(self, bs):
        n = len(bs)
        for i in range(n):
            if self.pos == 0:
                self.pos = 7
                self.set_next(self.val)
                self.val = 0
            self.val = self.val | (bs[i] << (8 * (7 - self.pos)))
            self.pos -= 1

    def ready(self):
        return self.set_count >= LEN


def get_priv():
    line = conn.sendafter(b'Enter signature: ', b'\n')
    line = conn.recvline()
    priv_b64 = re.findall(r'You failed! Private key was: (.*)\n', line.decode())[0]
    priv = base64.b64decode(priv_b64)
    return priv


host = 'ots-sig.donjon-ctf.io'
port = 4001
conn = Socket()
conn.connect((host, port))

# Put your code here!
cnt = 0
rng = Rng()
while not rng.ready():
    rng.set_next_bytes(get_priv())
_ = rng.next_bytes(7)  # align feed

assert rng.next_bytes(1088) == get_priv()

print('next private key:', base64.b64encode(rng.next_bytes(1088)))
conn.interact()

To patch this together with the signing process, we copy-pasted the private key and signature between this code and the following quick-and-ugly go code.

package main

import (
    "bufio"
    "crypto/sha256"
    "encoding/base64"
    "fmt"
    "os"
    "strings"
    "time"

    "github.com/dchest/wots"
    "math/rand" // The real one, not *really* used
)

func main() {
    var message = []byte("Sign me if you can")

    // Not *really* used, but too lazy to figure out how to generate
    // a new wots scheme without rng :)
    rng := rand.New(rand.NewSource(time.Now().UnixNano()))

    for {
        var ots = wots.NewScheme(sha256.New, rng)

        reader := bufio.NewReader(os.Stdin)
        fmt.Print("Enter privkey: ")
        text, err := reader.ReadString('\n')
        if err != nil {
            fmt.Println("Error occurred. Please try again later.")
                return
        }

        text = strings.TrimSuffix(text, "\n")
        priv, err := base64.StdEncoding.DecodeString(text)
        if err != nil {
            return
        }

        sign, err := ots.Sign(priv, message);
        fmt.Print(base64.StdEncoding.EncodeToString(sign));
    }
}

All of this eventually coming together to grant us the flag: CTF{m4th_RanD_1s_s0_pr3d1cT4bl3}.