Instantly share code, notes, and snippets.

# Chrstm/noise.py

Last active Oct 25, 2020
D^3CTF 2019 Crypto - Noise
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/usr/bin/env python3 from os import urandom import signal def getrandbits(bit): return int.from_bytes(urandom(bit >> 3), "big") def main(): signal.alarm(60) secret = getrandbits(1024) print("Listen...The secret is...M2@...f*#...z()I!(...3;J..." "Hello?...really noisy here...God bless you get it...") for i in range(50): op = input().strip() num = input().strip() if not str.isnumeric(num): print("INVALID NUMBER") continue num = int(num) if op == 'god': print((num + getrandbits(1000)) % secret) elif op == 'bless': if num == secret: print("CONGRATULATIONS", FLAG) return print("WRONG SECRET") main()
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 import random import socket class Socket: def __init__(self, host, port): self.s = socket.socket() self.s.connect((host, port)) def send(self, m, output=True, end=b'\n'): if isinstance(m, str): m = m.encode('Latin1') m += end if output: print("send:", m) self.s.send(m) def recv(self, rec_bytes=2048, output=True): m = self.s.recv(rec_bytes).decode('Latin1') if output: print("recv:\n{}\n".format(m)) return m NUM_BIT = 1024 NOISE_BIT = 1000 scope = 1 << NOISE_BIT s = Socket('localhost', 23334) s.recv() cnt = 0 def oracle(num, op='god'): global cnt cnt += 1 if cnt > 50: print("Not very lucky ... try it again") exit(0) s.send(op) s.send(str(num)) resp = s.recv().strip() if op == 'god': return int(resp) return resp def check(L, R): t = (L - scope - 1) // (R - L) I = random.randint(t * R, (t + 1) * L - scope - 1) assert (I // L == t) assert (I // R == t) out = oracle(I) LL = I - out RR = I - out + scope ans_L, ans_R = (LL + t - 1) // t, RR // t return ans_L, ans_R L = 0 R = 1 << NUM_BIT while True: if L * 2 >= R + scope + 1: break mid = (L + R) >> 1 if oracle(mid) > mid: # mid < mid + r < n L = mid + 1 else: # n <= mid + r <= mid + scope R = min(R, mid + scope) while L < R: try: L, R = check(L, R) except: break for i in range(L, R + 1): if "CONGRATULATIONS" in oracle(i, op='bless'): break print("total:", cnt)

# Noise Writeup

D^3CTF 2019 Crypto - Noise

## Problem

$n$ is an unknown constant integer (1024 bits). You can interactive with an oracle for less than 50 times: given a non-negative integer $x$, return $f(x) = (x + r) \bmod n$ where $r$ is an inconstantly random integer (1000 bits). Retrieve the $n$.

## Solution

One natural way is the binary search. In this way, we can get only one bit each round and it doesn't work when the length of the range of the $n$ is close to the noise. However, maybe it's a good idea for breaking through the problem to start from a rough range and make it smaller.

Assumes that we have already known a rough integer interval $[L, R]$ satisfying $n \in [L, R]$. If we can find a pair of integer $(I, t)$ where the following equation holds for all possible $n$ and $r$:

$$f(I) = (I + r) \bmod n = I + r - tn$$

in other words,

$$tn = I - f(I) + r$$

Obviously $I - f(I) + r$ is a multiple of $t$ and its range is only related to the $r$. Thus a different range of $n$ comes out:

$$n = \frac{I - f(I) + r}{t} \in \left [ \frac{I - f(I) + r_{\min}}{t} , \frac{I - f(I) + r_{\max}}{t} \right ]$$

The $r$ ranges in $\left [0, 2^{1000} \right ]$. Let $s = r_{\max} = 2^{1000}$ and the length of the above range of $n$ is around $\frac{s}{t}$.

Now the problem is how to choose a proper pair $(I, t)$ and make the $t$ as large as possible to get a small range of $n$. Look back to the assumption,

$$\forall r \in [0, s], n \in [L, R], \quad tn \leq I + r < (t+1)n$$

in other words,

$$(tn - r){\max} \leq I < ((t + 1)n - r){\min}$$

thus,

$$(tn - r){\max} = tR \quad < \quad ((t + 1)n - r){\min} = (t + 1)L - s$$

$$\Leftrightarrow \quad tR \leq (t + 1)L - s - 1$$

$$\Leftrightarrow \quad t \leq \frac{L - s - 1}{R-L}$$

The $I$ always exists as long as the $t$ satisfies this inequation. Besides, the $t$ has a lower bound $t\geq 1$ such that the division makes sense. So we have requirements for the $L, R$:

$$1 \leq t \leq \frac{L - s - 1}{R-L} \quad \Rightarrow \quad 2L\geq R + s + 1$$

There are two ways to pick out valid $[L, R]$ at the beginning:

1. Assumes that the $n$ ranges in $\left [2^{1023}, 2^{1024} \right ]$. (the possibility is about 50%, so take more tries if unlucky)
2. Binary search. (it's trivial and see more detail in the exp script)

Let's take a summary. Try to pick a valid pair $L, R$ as the initial interval of $n$. Then Let the $t$ be the maximum $\frac{L - s - 1}{R-L}$ and select a $I$ from the range $[tR, (t + 1)L - s - 1]$, so

$$n \in \left [ \left \lceil \frac{I - f(I)}{t}\right \rceil, \left \lfloor \frac{I - f(I) + s}{t}\right \rfloor \right ]$$

Let the $[L, R]$ be the new interval and repeat for a couple of times. The range of $n$ shrinks from $\Delta \sim R-L$ to $\Delta' \sim \frac{s}{t}$ where

$$\Delta' \sim \frac{s}{t} \sim \frac{s(R-L)}{L-s-1} \sim \frac{s\Delta}{L-s} \sim \frac{s\Delta}{n}$$

The number of iterations is about $\log_s n$, typically around 45 times. (similarly, take more tries if not lucky enough)

FYI: This is a general solution. You will find some much easier ways to retrieve it if you just make some assumptions (such as assume that the $n$ is in a certain range, let $I = tR$, etc.), simplify the above steps and try a couple of times.

## 问题

$n$ 是一个未知整数 (1024 bits)。你可以访问一个黑盒函数不超过 50 次：给定一个非负整数 $x$，返回 $f(x) = (x + r) \bmod n$，$r$ 是一个每次都重新生成的随机数 (1000 bits)。 求 $n$

## 解答

$$n = \frac{I - f(I) + r}{t} \in \left [ \frac{I - f(I) + r_{\min}}{t} , \frac{I - f(I) + r_{\max}}{t} \right ]$$

$r$ 的范围是 $\left [0, 2^{1000} \right ]$。令 $s = r_{\max} - r_{\min} = 2^{1000}$，则上述区间长度大约是 $\frac{s}{t}$

$$\forall r \in [0, s], n \in [L, R], \quad tn \leq I + r < (t+1)n$$

$$(tn - r){\max} \leq I < ((t + 1)n - r){\min}$$

$$(tn - r){\max} = tR \quad < \quad ((t + 1)n - r){\min} = (t + 1)L - s$$

$$\Leftrightarrow \quad tR \leq (t + 1)L - s - 1$$

$$\Leftrightarrow \quad t \leq \frac{L - s - 1}{R-L}$$

$$1 \leq t \leq \frac{L - s - 1}{R-L} \quad \Rightarrow \quad 2L\geq R + s + 1$$

1. 直接假设 $n$ 落在 $\left [2^{1023}, 2^{1024} \right ]$（这样的概率大约是 50%，所以如果假设不成立就多试几次）
2. 二分查找（这是一种很显然的方法，详见 exp

$$n \in \left [ \left \lceil \frac{I - f(I)}{t}\right \rceil, \left \lfloor \frac{I - f(I) + s}{t}\right \rfloor \right ]$$

$$\Delta' \sim \frac{s}{t} \sim \frac{s(R-L)}{L-s-1} \sim \frac{s\Delta}{L-s} \sim \frac{s\Delta}{n}$$

FYI：这是一般性的做法。如果直接做一些假设（譬如假设 $n$ 落在某个范围，令 $I = tR$ 等等），可以省略掉一些繁琐的步骤得到一些更简单但需要多试几次的做法。