OK - zer0pts CTF 2022

tags: zer0pts CTF 2022

Writeups: https://hackmd.io/@ptr-yudai/rJgjygUM9

overview

The program implements Oblivisous Transfer by RSA. We can get either

$K$ or

$C$. Our purpose is to get

$K\oplus C$.

solution

step1

By sending

$v$ such that

$v-x_1\equiv -(v-x_2)\mathrm{mod}n$, the

$k_1\equiv -k_2\mathrm{mod}n$ stands.

Because

$k_1\equiv (v-x_1{)}^d\mathrm{mod}n$ and

$k_2\equiv (v-x_2{)}^d\equiv (-(v-x_1){)}^d\equiv -(v-x_1{)}^d\mathrm{mod}n$. (

$d$ is odd value)

Thus,

$c_1+c_2\equiv K+C\mathrm{mod}n$ where

$c_1\equiv k_1+K\mathrm{mod}n$,

$c_2\equiv k_2+C\mathrm{mod}n$ stands.

Additionaly, the LSB of

$c_1+c_2$ is always fixed because

$K\oplus C$ is consistent. Hence we can assume the parity of

$c_1+c_2$ and find

$K+C$ without modulo under the assumption. If the parity of

$K+C\mathrm{mod}n$ is different from our assumption, we can get

$K+C$ by adding

$n$ to

$|K+C\mathrm{mod}n|$. Otherwise

$|K+C\mathrm{mod}n|=K+C$. Because

$n$ is odd value.

Now we have

$K+C\mathrm{mod}n$. Can we determine

$K\oplus C$ uniquely?

Appearently no. But for now, we know

$K$ and

$C$ are different in every connection while

$K\oplus C$ is consistent. So considering about collecting some cases of

$(K,C)$ pair.

For now, the problem is turned into to find

$X=K_i\oplus C_i$ from some

$Y_i=K_i+C_i$.

step2

Therefore, if the following problem is solved, secret has been recovered.

Statement:
Generate an integer sequence

$B_i=A_i+(m\oplus A_i)$ from a random integer

$m$ of

$N$ bits and an integer sequence

$A$ of random

$N$ bits. Recover

$m$ from the integer sequence

$B$.
Constraints:

• $N=1024$
• $|A|=20$

First, let us make an observation about the generated number

$A_i+(m\oplus A_i)$. From the facts about addition, the following formula transformation holds.

$$\begin{array}{rl}{A}_i+(m\oplus A_i)& =(A_i\oplus m\oplus A_i)+2\cdot (A_i\mathrm{\&}(m\oplus A_i))\\ \text{(1)}& & =m+2\cdot (A_i\mathrm{\&}(m\oplus A_i))\end{array}$$

Here, the XOR in the

$A_i\mathrm{\&}(m\oplus A_i)$ part can be taken as inverting the bit extracted by &. So it should be the same if all the bits are inverted first and then extracted. Let us denote the bit inversion of

$x$ as

$\bar{x}$, then the following holds.

$$\begin{array}{rl}(1)& =m+2\cdot (A_i\mathrm{\&}\bar{m})\\ & =m+\bar{m}+(A_i\mathrm{\&}\bar{m})+((A_i\mathrm{\&}\bar{m})-\bar{m})\\ & =\bar{0}+(A_i\mathrm{\&}\bar{m})+((A_i\mathrm{\&}\bar{m})-((A_i\mathrm{\&}\bar{m})+(\overline{A_i}\mathrm{\&}\bar{m})))\\ \text{(2)}& & =\bar{0}+(A_i\mathrm{\&}\bar{m})-(\overline{A_i}\mathrm{\&}\bar{m})\end{array}$$

The equation transformation regarding bit inversion is a bit cumbersome, but it is no problem to think of it as the one's complement in a sufficiently large finite number of bits. In this case, since

$N=1024$ bits, we can write the following using

$C=2^{\mathrm{N}+1}-1$.

$$\begin{array}{rl}(2)& =C+(A_i\mathrm{\&}(C-m))-(\overline{A_i}\mathrm{\&}(C-m))\end{array}$$

This equation can be interpreted as a script like the following.

C = 2 ** (N + 1) - 1
B_i = C
for i in range(N):
  if not (C-m & (1 << i)): continue
  res += (1 << i) * choice([-1, 1])

Now consider the probability that the most significant bit of

$|B_i-C|$ is equal to the most significant bit of

$C-m$. It turns out that this is 1 if

$C-m$ and the most significant bit are equal, and 1/2 if they are not ((symmetry makes it clear)). Since the most significant bit is always smaller when they are not equal, we can find the most significant bit of

$C-m$ from the sequence

$B$ with probability more than

$1-2^{-|B|}$ by taking the largest most significant bit. Next, subtract the most significant bit from

$|B_i-C|$ and take its absolute value. Then we have the same problem for the second bit from the top.

Thus, we found that by repeating this process, we can find

$m$ with probability greater than

$(1-2^{-|B|}{)}^N$. The script will be as follows.

def solve(bs):
    BIT = 1024
    C = 2 ** (BIT + 1) - 1
    bs = [abs(b - C) for b in bs]

    res = C
    while not all([b == 0 for b in bs]):
        msb = 1 << (max(bs).bit_length() - 1)
        res -= msb
        bs = [abs(b - msb) for b in bs]
    if any([b != 0 for b in bs]): return None
    return res