# 33C3 CTF – Beeblebrox

This crypto challenge is a classic “fake-the-signature” crypto challenge, but with a somewhat unusual signature scheme that depends on the hardness of computing $n$th roots modulo a semiprime:

1. There is a publicly known semiprime $N = PQ$, whose two prime factors $P$ and $Q$ are known only to the signer. There is also a publicly known element $S$ of $\mathbb{Z}/N\mathbb{Z}$, and a publicly known hash-function $H$ which maps arbitrary-length inputs to 128-bit outputs (in our case, the 128-bit truncation of SHA-256).
2. To sign a message $M$, you first find a nonce $r$ so that $H(M||r)$ equals some prime, $k$.
3. The signer then computes a value $z$ that satisfies $z^k = S$ (i.e. $z$ is a $k$th root of $S$ modulo $N$). The signer returns $z$ as the signature.

In our challenge, you can pass any message $M$ along with a nonce $r$ to the signer, who will then sign it as long as $M$ is not the target message (“I, Zaphod Beeblebrox, hereby resign from my office as president of the Galaxy.”) and $H(M||r)$ is indeed prime.

Of course, as with Ichwixnisse, there is an implementation error here, and the signer’s code to check that $k$ is prime will actually accept any odd composite number. The question is, how can we abuse this?

Well, unless we can find some hash collisions, we’ll need to somehow find a $k$th root of $S$, where $k$ is in fact of the form $H(M_0||r)$, with $M_0$ being the target message. For convenience, write $S^{1/k}$ to represent some $k$th root of $S$.

Since we can sign other messages, we want to be able to generate roots of $S$ from other roots of $S$. Let’s start with some simple cases, then. If we have a 15th root of $S$, $S^{1/15}$, then we can easily construct a third root of $S$, since $((S^{1/15})^5)^{3} = (S^{1/15})^{15} = S$ (and similarly we can easily construct a fifth root of $S$). What about going the other way? If we’re given $S^{1/3}$ and $S^{1/5}$, can we construct a fifteenth root $S^{1/15}$?

Well, we might notice that $\frac{2}{3} - \frac{3}{5} = \frac{1}{15}$, so maybe $(S^{1/3})^{2}\cdot(S^{1/5})^{-3} = S^{1/15}$. And indeed, this is not hard to check:

$((S^{1/3})^{2}\cdot(S^{1/5})^{-3})^{15} = (S^{1/3})^{30}\cdot(S^{1/5})^{-45} = S^{10}\cdot S^{-9} = S$.

More generally, if we have $S^{1/a}$ and $S^{1/b}$, with $a$ and $b$ relatively prime, then we can compute $S^{1/ab}$ via a similar approach to the above (more specifically, running the extended Euclidean algorithm and finding $c$ and $d$ such that $ac + bd = 1$).

This turns out to be all the primitives we need. Our strategy for an attack is now as follows:

1. Find a specific nonce $r_0$ so that $H(M_0||r_0)$ is smooth, with all its prime factors as small as possible. There is a tradeoff here between the number of nonces you try and the size of the largest prime factor you’ll get; we tried around a million different nonces and found one that gave a $k$ whose largest prime factor was $32557549$.
2. Write this $k$ as the product $k = p_1\cdot p_2 \cdot \dots \cdot p_m$ of a bunch of primes (our number turned out to be square-free, but this approach should work in general). For each prime $p_i$, generate random messages $M_i$ and nonces $r_i$ until you find a pair that satisfies $p_i | H(M_{i}||r_i)$. Set $k_i = H(M_{i}||r_{i})$.
3. Ask the server to sign $M_{i}$ with nonce $r_{i}$, and hence obtain $S^{1/k_i}$.
4. Since $p_i | k_{i}$, from $S^{1/k_{i}}$, compute $S^{1/p_{i}}$.
5. Finally, using the extended Euclidean algorithm trick above, from all the roots $S^{1/p_{i}}$, compute $S^{1/(p_1p_2\dots p_{m})} = S^{1/k}$. This is the signature of the target message with nonce $r_0$.

The tricky step here is step 1, but since the hash has 128-bit outputs, it is not so bad; Sage can factor 128-bit integers relatively quickly, and there are enough smooth 128-bit integers whose factors are all at most around a million.

Most of this approach is implemented in the below code, but part of it (in particular factoring $k$ and step 5) was performed in a separate sage session.

#!/usr/bin/python3
from pwn import *
from hashlib import sha256
import base64
import random
import struct

# CONSTANTS
MODULUS = 16536507737844787892641865661863462397631522150212024091004887310964200827020178668239882145253630803151168956393779505928808506196120351189499349932786784708370138096658243543880715379147242259129181920278789039223128954389992858894196591733488967188941263924281855801225333337971369346979277183346095695839072573619497479683662969453719477093511680505106353869706149218300987922266699186873224155102741256320112045419277230096733452241250195932716682446395562027663309040452928460169789196285753228735312068600940483519875428506460333422009758551679944423660319026521184358407797626088473071231220477237579974133813
S = 2279870349089594676078131957223427526372940435342871764510345335207700176127662830938770929147412047169033459649625173227912122654011065802421796926972585798820409017163625434862756489760448381608543257498933257519457833349391617168881001250072857294234191917642557763462668502951731492599248590640073798156146984110885838926659848552808727770775032147602500322865941084978965993286193260974797123500037313973609102107825877355293422553505328529637538623308810977388182025133271286463800018303412599528683244178480216737543334821269172129558292624827118889631230859505678242114445252685966124989815656101539186906614
SEPARATOR = ";"
TARGET_MSG = "I, Zaphod Beeblebrox, hereby resign from my office as president of the Galaxy."
LISTEN_ON = ('0.0.0.0', 2048)
PROOF_OF_WORK_HARDNESS = 2**23

def encode(i, length):
i = i.to_bytes(length, 'little')
return base64.b64encode(i)

def decode(i, min, max):
i = base64.b64decode(i)
i = int.from_bytes(i, 'little')
if i < min:
raise ValueError("i too small")
if i >= max:
raise ValueError("i too large")
return i

def hash(msg, ctr):
h = sha256(msg.encode('ASCII') + ctr.to_bytes(4, 'little'))
h = h.digest()
h = h[0:16]
h = int.from_bytes(h, 'little')
return h

def is_prime(n, c):

if n <= 1: return False
if n == 2 or n == 3: return True
if n % 2 == 0: return False

for _ in range(c):
a = random.randrange(1, n)
if not pow(a, n-1, n) != 1:
return False

return True

def extended_gcd(a, b):

def _egcd(a, b):
if a % b == 0:
return b, 0, 1
else:
g, s, t = _egcd(b, a % b)
assert(s * b + t * (a % b) == g)
return g, t, s - t * (a // b)

if a < b:
g, d, c = _egcd(b, a)
else:
g, c, d = _egcd(a, b)

return g, c, d

def modinv(a, m):

""" compute the modular inverse of a modulo m.
Raises an error if a does not have an inverse, (i.e. gcd(a, m) != 1)."""

g, s, _ = extended_gcd(a, m)
if g != 1:
raise ValueError("cannot compute modular inverse of {} modulo {}. common divisor: {}".format(a, m, g))
return s % m

def random_string(length = 10):
characters = [chr(i) for i in range(ord('a'), ord('z') + 1)]
characters += [chr(i) for i in range(ord('A'), ord('Z') + 1)]
characters += [chr(i) for i in range(ord('0'), ord('9') + 1)]
result = ""
for _ in range(length):
result += random.choice(characters)
return result

h = sha256(task.encode('ASCII') + solution.to_bytes(4, 'little')).digest()
return int.from_bytes(h, 'little') < 1/PROOF_OF_WORK_HARDNESS * 2**256

def solve_pow(challenge):
sol = 0
while not proof_of_work_okay(challenge, sol):
sol += 1

return encode(sol, 8)

print(decode(encode(17,4), 1, 2**32))

def hash_msg(ctr):
h = hash(TARGET_MSG, ctr)
print (h, is_prime(h, 128))

def gen_hashes():
f = open('hashes', 'w')
for ctr in range(1, 2**15):
if ctr%1000 == 0:
print(ctr)
h = hash(TARGET_MSG, ctr)
if is_prime(h, 128):
f.write(str(ctr) + ' ' + str(h) + '\n')
f.close()

CTR = 28039
SMOOTH = 196938090168807626792794007952183901965
PS = [3, 5, 13, 53, 59, 257, 659, 10987, 47207, 252971, 446417, 32557549]

def get_hashes():
f = open('smooth', 'w')
ctr = 1
while len(PS)>0:
if ctr%1000 == 0:
print(ctr)
h = hash(TMP_MSG, ctr)
for p in PS:
if h%p == 0:
if is_prime(h, 128):
print("FOUND hash {} for {} (ctr: {})\n".format(h, p, ctr))
f.write(str(ctr) + ' ' + str(p) + ' ' + str(h) + '\n')
PS.remove(p)
ctr += 1

f.close()

SHS = [map(int, line.split()) for line in open('smooth', 'r')]

def sign_message(message, ctr):
conn = remote('78.46.224.72', 2048)
conn.recvlines(numlines=4)
line = conn.recvline()

challenge = line.split()[-1][1:-1].decode()
print(challenge)

sol = solve_pow(challenge)

qry = '{};{};{}'.format(sol.decode(), TMP_MSG, encode(ctr, 4).decode())
print(qry)

conn.sendline(qry)
conn.recvline()
ans = conn.recvline().strip()
print(ans)

ans = decode(ans, 2, MODULUS)
print(ans)

conn.close()
return ans

def get_roots():
f = open('smooth_roots', 'w')
for ctr, p, h in SHS:
print('signing {}'.format(p))
while True:
try:
s = sign_message(TMP_MSG, ctr)
break
except Exception as e:
pass
assert pow(s, h, MODULUS) == S
f.write('{} {} {} {}\n'.format(ctr, p, h, s))

SIG = 10046710453198653869945713165496623610820323221814622666839991465041139392570179022949783487488859077753923096380618154755009542268563420217091693707070813505760168604642800264056980874593981337386321657237512178944677244676923910868743471179486270114584325188712585502554288328117863276153029595806011408041854229317957431046180638335246591007562376714326425943487893455716894151591337693657560415560446490108686216255501236409614682398499209358273354613525819213526574094802255043973015915786776444513150315767890935111716566539656654373258130701747620810851966026397641489653155488557902816357288219315732601340228

def resign():
conn = remote('78.46.224.72', 2048)
conn.recvlines(numlines=5)

conn.sendline('Resign!')

line = conn.recvline()
print(line)
challenge = line.split()[-1][1:-1].decode()
print(challenge)

sol = solve_pow(challenge)

qry = '{};{};{};{}'.format(sol.decode(), TARGET_MSG, encode(CTR, 4).decode(), encode(SIG, 256).decode())
conn.sendline(qry)

print(conn.recvline())
print(conn.recvline())
print(conn.recvline())
print(conn.recvline())

resign()