Imaginary CTF 2021

| 2021-07-28 |

Intro

The crypto problems were not too hard and there were nothing new and special except the last crypto problem "ZKPoD". This was my first time to implement LSB oracle attack, and the code was pretty messy. I refactored it based on oalieno's tutorial.

ZKPoD

Description

The problem has two modules. The first module is an RSA with fixed 2048-bit \(N\) and \(e = 65537\), and the second one is a signing process with a 2048-bit prime \(p\) and \(g = 2\). The signing process works as follow:

Randomly choose a \(k\) between \(0\) to \((p - 2)\). Let \(r = g^k \pmod p\)
\(e\) is a 1024-bit hash of \(r\), and \(s = (k - me) \pmod{p - 1}\), where \(m\) is the message to be signed.
The signature is \((r, s)\)

The problem first gives us the RSA-encrypted flag, then provide an oracle that decrypts the input and signs it.

N = 0xbb00128c1c1555dc8fc1cd09b3bb2c3efeaae016fcb336491bd022f83a10a501175c044843dbec0290c5f75d9a93710246361e4822331348e9bf40fc6810d5fc7315f37eb8f06fb3f0c0e9f63c2c207c29f367dc45eef2e5962eff35634b7a29d913a59cd0918fa395571d3901f8abd83322bd17b60fd0180358b7e36271adcfc1f9105b41da6950a17dba536a2b600f2dc35e88c4a9dd208ad85340de4d3c6025d1bd6e03e9449f83afa28b9ff814bd5662018be9170b2205f38cf3b67ba5909c81267daa711fcdb8c7844bbc943506e33f5f72f603119526072efbc5ceae785f2af634e6c7d2dd0d51d6cfd34a3bc2b15a752918d4090d2ca253df4ef47b8b
e = 0x10001
P = 0x199e1926f2d2d5967b1d230b33de0a249f958e5b962f8b82ca042970180fe1505607fe4c8cde04bc6d53aec53b4aa25255ae67051d6ed9b602b1b19e128835b20227db7ee19cf88660a50459108750f8b96c71847e4f38a79772a089aa46666404fd671ca17ea36ee9f401b4083f9ca76f5217588c6a15baba7eb4a0934e2026937812c96e2a5853c0e5a65231f3eb9fdc283e4177a97143fe1a3764dc87fd6d681f51f49f6eed5ab7ddc2a1da7206f77b8c7922c5f4a5cfa916b743ceeda943bc73d821d2f12354828817ff73bcd5800ed201c5ac66fa82df931c5bbc76e03e48720742ffe673b7786e40f243d7a0816c71eb641e5d58531242f7f5cfef60e5b
g = 2

def sign(x):
    k = getRandomRange(0, P - 1)
    r = pow(g, k, P)
    e = H(r) # a robust deterministic hash function 
    s = (k - x * e) % (P - 1)
    return r, s
    
print(pow(flag, e, N))
while True:
    print("> ", end="")
    c = int(input(), 16)
    m = pow(c, d, N)
    r, s = sign(m)
    print(f"r: {r}")
    print(f"s: {s}")

Solution

Recover LSB

The decryption oracle reminds us of the famous LSB oracle attack, but can we recover the least significant bit of \(m\) from the signature? The answer is yes. Since we know \(r\) and \(e\), we can calculate

\[g^{me} \equiv \left(\frac{r}{g^s}\right) \pmod p\]

if \(e\) is invertible modulo \((p - 1)\), then

\[g^m \equiv \left(g^{em}\right)^{e^{-1}} \pmod p\]

where \(e^{-1}\) is the inverse of \(e\) modulo \((p-1)\). Luckily, \(g\) is a primitive root of \(p\), so

\[g^m \text{ is a quadratic residue} \Leftrightarrow 2 \mid m\]

meaning we can recover the least significant bit of \(m\) easily by Euler's formula.

There are two important details:

\(e\) is not always invertible. We may have to ask for the signature of the same message multiple times, until we get a signature with invertible \(e\).
This only works when \(N < p\). If \(p\) is small, the least significant bit may be destroyed because of the modulo \((p - 1)\) operation. Formally, we use the fact that m % N % (p - 1) = m % N.

LSB oracle attack

It is a well known attack, and below we provide the essential idea of the attack.

Let the encrypted flag and flag be \(c\) and \(f\), respectively. The crucial observation is that when we feed in the input \(2^ec\), the decrypted message will be \(dm = 2f \pmod N\). If \(2f \ge N\), then \(dm = 2f-N\), an odd number; otherwise, \(dm = 2f\), an even number. This observation implies that based on the least significant bit of \(dm\), we can know if \(f\) is in \([0, \frac{N}{2})\) or \([\frac{N}{2}, N)\). In the next round, we feed in \(4^ec\) and so on, and we are able to binary search the value of \(f\).

The script is as follow:

import hashlib
from Crypto.Util.number import bytes_to_long, long_to_bytes
from pwn import *

r = remote("chal.imaginaryctf.org", 42012)
r.recvuntil(b"Here's my encrypted flag: ")
enc_flag = int(r.recvline().strip(b"\n"), 16)

def H(x):
    return bytes_to_long(hashlib.sha512(b"domain" + x).digest() + hashlib.sha512(b"separation" + x).digest())

N = 0xbb00128c1c1555dc8fc1cd09b3bb2c3efeaae016fcb336491bd022f83a10a501175c044843dbec0290c5f75d9a93710246361e4822331348e9bf40fc6810d5fc7315f37eb8f06fb3f0c0e9f63c2c207c29f367dc45eef2e5962eff35634b7a29d913a59cd0918fa395571d3901f8abd83322bd17b60fd0180358b7e36271adcfc1f9105b41da6950a17dba536a2b600f2dc35e88c4a9dd208ad85340de4d3c6025d1bd6e03e9449f83afa28b9ff814bd5662018be9170b2205f38cf3b67ba5909c81267daa711fcdb8c7844bbc943506e33f5f72f603119526072efbc5ceae785f2af634e6c7d2dd0d51d6cfd34a3bc2b15a752918d4090d2ca253df4ef47b8b
e = 0x10001
p = 0x199e1926f2d2d5967b1d230b33de0a249f958e5b962f8b82ca042970180fe1505607fe4c8cde04bc6d53aec53b4aa25255ae67051d6ed9b602b1b19e128835b20227db7ee19cf88660a50459108750f8b96c71847e4f38a79772a089aa46666404fd671ca17ea36ee9f401b4083f9ca76f5217588c6a15baba7eb4a0934e2026937812c96e2a5853c0e5a65231f3eb9fdc283e4177a97143fe1a3764dc87fd6d681f51f49f6eed5ab7ddc2a1da7206f77b8c7922c5f4a5cfa916b743ceeda943bc73d821d2f12354828817ff73bcd5800ed201c5ac66fa82df931c5bbc76e03e48720742ffe673b7786e40f243d7a0816c71eb641e5d58531242f7f5cfef60e5b
g = 2

def oracle(payload):
    while True:
        try:
            r.recvuntil(b"> ")
            r.sendline(hex(payload).encode())
            r.recvuntil(b"r: ")
            _r = int(r.recvline().strip(b"\n"))
            r.recvuntil(b"s: ")
            _s = int(r.recvline().strip(b"\n"))
            e = H(str(_r).encode() + b"Haha, arbitrary message")
            d = pow(e, -1, (p - 1))
            gm = pow(_r * pow(g, -_s, p), d, p)
            if pow(gm, (p - 1) // 2, p) == 1: # Euler's Formula
                return 0
            else:
                return 1
        except ValueError: # if e is not invertible
            print("Bad e :(")

L = 0
R = N
rd = 0

while L != R - 1:
    mid = (L + R) // 2
    rd += 1
    print(rd)

    if R > (1 << 400):
        R = mid
        continue

    payload = enc_flag << (rd * e)
    payload %= N
    if oracle(payload):
        R = mid
    else:
        L = mid

flag = L
print(bytes.fromhex(hex(flag)[2:]))

tags: #writeup