# Commitment Issues

Authors: Jack

Tags: crypto

Points: 272 (16 solves)

Challenge Author: gripingberry

Description:

I created a new commitment scheme, but commitment is scary so I threw away the key.

## Challenge

from random import randrange
from Crypto.Util.number import getPrime, inverse, bytes_to_long, GCD

flag = b'dice{?????????????????????????}'
n = 5

def get_prime(n, b):
p = getPrime(b)
while GCD(p - 1, n) != 1:
p = getPrime(b)
return p

p = get_prime(n, 1024)
q = get_prime(n, 1024)
N = p*q
phi = (p - 1)*(q - 1)

e = 0xd4088c345ced64cbbf8444321ef2af8b
d = inverse(e, phi)

def sign(message):
m = bytes_to_long(message)
return pow(m, d, N)

def commit(s, key, n):
return (s + key) % N, pow(key, n, N)

def reveal(c1, c2, key, n):
assert pow(key, n, N) == c2
return (c1 - key) % N

r = randrange(1, N)
s = sign(flag)
c1, c2 = commit(s, r, n)

print(f'N = {hex(N)}')
print(f'c1 = {hex(c1)}')
print(f'c2 = {hex(c2)}')


## Solution

This challenge is based on a custom commitment scheme for RSA signatures. Before diving into the solution, let’s break down what we’re given and try and identify the insecure part of the scheme.

The RSA modulus $N=pq$ has 2048 bits, and is the product of two 1024 bit primes, which are generated such that $n = 5$ is not a factor of $(p-1)$ or $(q-1)$. From this alone, we will not be able to factor $N$.

The public exponent is unusual: e = 0xd4088c345ced64cbbf8444321ef2af8b, but it’s prime and not so large as to cause much suspicion. So far, so good (or bad for finding a solution, i suppose…).

We are given the length of the flag , which is 31 bytes or 248 bits long. The signature of the flag is $s = m^d \pmod N$, where $m$ is not padded before signing. This means that $m$ is relatively small compared to the modulus (Coppersmith should start being a thought we have now). However, we don’t have the value of the signature, only the commitment.

The commitment gives us two values, $c_1$ and $c_2$. Let’s look at how the commitment is made.

def commit(s, key, n):
return (s + key) % N, pow(key, n, N)

r = randrange(1, N)
s = sign(flag)
c1, c2 = commit(s, r, n)


First a random number $r$ is generated from r = randrange(1, N) as the key. The flag is signed and so we are left with two integers $(r,s)$ both approximately of size $N$. The commitment is made by adding together these integers modulo $N$:

$c_1 = (s + r) \pmod N.$

We can understand $r$ here as effectively being a OTP, obscuring the signature $s$. We cannot recover $s$ from $c_1$ without knowing $r$ and we cannot recover $r$ without knowing $s$.

The second part of the commitment depends only on the random number $r$ and is given by

$c_2 = r^5 \pmod N.$

Obtaining $r$ from $c_2$ is as hard as breaking RSA with the public key $(e=5,N)$. If $r$ was small, we could try taking the fifth root, but as it of the size of $N$, we cannot break $c_2$ to recover $r$.

So… either the challenge is impossible, or there’s a way to use our knowledge of $(c_1,c_2)$ together to recover the flag.

### Combining Commitments

Let’s write down what we know algebraically:

\begin{aligned} s &= m^d &&\pmod N, \\ c_1 &= s + r &&\pmod N, \\ c_2 &= r^5 &&\pmod N. \end{aligned}

Additionally, we know that $m$ is small with respect to $N$, so if we could write down a polynomial $g(m) = 0 \pmod N$, we could use Coppersmith’s small roots to recover $m$ and hence the flag!

Note: The following solution was thought up by my teammate, Esrever, so all credit to him.

Consider the polynomial in the ring $R = (\mathbb{Z}/N\mathbb{Z})[X]$:

$f(X) = (c_1 - X)^e \pmod N,$

we have the great property that $f(r) = m$. However, written like this, the polynomial will be enormous, as $e$ is a (moderately) large prime [Maybe this is the reason $e$ was chosen to be in the form we see in the challenge].

Esrever’s great idea was to work in the quotient ring $K = R[X] / (X^5 - c_2)$, using the additional information we get from $c_2$. This allows us to take the $e$ degree polynomial $f(X)$ and recover a (at most) degree four polynomial by repeatedly substituting in $X^5 = c_2$.

Taking powers of the polynomial, we have that

$m^k = f^k(r) = (c_1 - r)^{e\cdot k} \pmod N$

The hope was that by taking a set of these polynomials, we could write down a linear combination of $m^k$ such that all $r$ cancel, leaving a univariate polynomial in $m$. This is exactly what we need to find if we hope to solve using small roots.

We were able to accomplish this with a bit of linear algebra. Let’s go through step by step.

### Linear Algebra to the Rescue

First let us write the $k^{\text{th}}$ power of $f(X)$ as $f^k(X)$ with coefficients $b_{ki}$:

$f^k(X) = \sum_{i=0}^{4} b_{ki} \cdot X^i$

Taking $k \in \{1,\ldots 5 \}$ we can write down five degree four polynomials using a $5\times5$ matrix and column vector:

$\mathbf{M} = \begin{pmatrix} b_{10} & b_{11} & b_{12} & b_{13} & b_{14} \\ b_{20} & b_{21} & b_{22} & b_{32} & b_{24} \\ b_{30} & b_{31} & b_{32} & b_{33} & b_{34} \\ b_{40} & b_{41} & b_{42} & b_{43} & b_{44} \\ b_{50} & b_{51} & b_{52} & b_{53} & b_{54} \\ \end{pmatrix} \quad \mathbf{x} = \begin{pmatrix} X^0 \\ X^1 \\ X^2 \\ X^3 \\ X^4 \\ \end{pmatrix}.$

With these, our polynomials can be recovered from matrix multiplication:

$\mathbf{F} = \mathbf{M}(\mathbf{x}) = \begin{pmatrix} f^1(X) \\ f^2(X) \\ f^3(X) \\ f^4(X) \\ f^5(X) \\ \end{pmatrix}$

To solve the challenge, our goal is to find a vector $\mathbf{a} = (\alpha_1, \alpha_2, \alpha_3, \alpha_4, \alpha_5)^\top$ such that

$\mathbf{M}^\top(\mathbf{a}) = (1,0,0,0,0)^\top.$

This is equivalent to finding simultaneous solutions to

$\sum_{k=1}^5 \alpha_k \cdot b_{k0} = 1, \quad \sum_{k=1}^5 \alpha_k \cdot b_{kj} = 0, \quad j \in \{1,\ldots 4\}$

Practically, finding this vector $\mathbf{a}$, allows us to derive the linear combination

$g(m) = \sum_{i=1}^5 \alpha_i f^i(X) = \sum_{i=1}^5 \alpha_i \cdot m^i.$

with no dependency on the variable $X$, allowing us to understand $g(m)$ as a univariate polynomial in $m$, precisely what we need for small roots!!

Recovering $\mathbf{a}$ is possible as long as $\mathbf{M}$ has an inverse, as we can write

$\mathbf{a} = (\mathbf{M}^\top)^{-1} (1,0,0,0,0)^\top$

Using SageMath, this is as easy as

M = ... # Matrix of coefficients
v = vector(Zmod(N), [1,0,0,0,0])
a = M.transpose().solve_right(v)


With the polynomial $g(m)$ recovered, we can apply SageMath’s .small_roots() method on our univariate polynomial and recover the flag!

## Implementation

##################
# Challenge Data #
##################

e  = 0xd4088c345ced64cbbf8444321ef2af8b

##################
#    Solution    #
##################

R.<X> = PolynomialRing(Zmod(N))
R.<X> = R.quo(X^5 - c2)

f1 = (c1 - X)^e
f2 = f1^2
f3 = f1^3
f4 = f1^4
f5 = f1^5

M = Matrix(Zmod(N),
[f1.lift().coefficients(sparse=False),
f2.lift().coefficients(sparse=False),
f3.lift().coefficients(sparse=False),
f4.lift().coefficients(sparse=False),
f5.lift().coefficients(sparse=False)]).transpose()

v = vector(Zmod(N), [1,0,0,0,0])

sol = list(M.solve_right(v))

K.<m> = PolynomialRing(Zmod(N), implementation='NTL')
g = -1
for i,v in enumerate(sol):
g += v*m^(i+1)

flag = g.monic().small_roots(X=2**(31*8), beta=1, epsilon=0.05)[0]
print(int(flag).to_bytes(31, 'big'))


## Flag

dice{wh4t!!-wh0_g4ve_u-thE-k3y}