D^3CTF 2019 Crypto - Noise
Writeup: https://hackmd.io/@JHSN/r1r5vuO2B
File: https://gist.github.com/Chrstm/f225a5e67f12d20caba117224d1b4241
$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$.
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:
- Assumes that the $n$ ranges in $\left [2^{1023}, 2^{1024} \right ]$. (the possibility is about 50%, so take more tries if unlucky)
- 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$。
一种比较自然的想法是二分查找,但这样每次只能获取到 1 bit 信息且当区间大小接近噪声大小时就无法再缩小范围了。不过我们可以以这种方式切入,假设已知某个范围并想办法缩小它。
假设我们已有 $[L, R]$ 满足 $n \in [L, R]$。如果我们可以找到一对 $(I, t)$ 对于所有可能的 $n$ 和 $r$ 都满足:
$$f(I) = (I + r) \bmod n = I + r - tn$$
即
$$tn = I - f(I) + r$$
那么显然 $I - f(I) + r$ 是 $t$ 的倍数,它的范围只和 $r$ 有关。所以可得 $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}$。
现在的问题就转化为如何选取一对合适的 $(I, t)$ 并且 $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}$$
只要 $t$ 满足这个条件,我们就可以找到对应的 $I$。除此之外,因为 $t$ 参与除法,所以还有一个下界 $t\geq 1$,由此我们可以得到对 $L, R$ 的限制条件:
$$1 \leq t \leq \frac{L - s - 1}{R-L} \quad \Rightarrow \quad 2L\geq R + s + 1$$
有两种方法来设置合法的初始 $[L, R]$:
- 直接假设 $n$ 落在 $\left [2^{1023}, 2^{1024} \right ]$(这样的概率大约是 50%,所以如果假设不成立就多试几次)
- 二分查找(这是一种很显然的方法,详见 exp)
综上所述,首先选取一对 $L, R$ 作为 $n$ 的初始范围.然后令 $t$ 为最大值 $\frac{L - s - 1}{R-L}$ 并在区间 $[tR, (t + 1)L - s - 1]$ 中选择一个 $I$,由此可得新区间
$$n \in \left [ \left \lceil \frac{I - f(I)}{t}\right \rceil, \left \lfloor \frac{I - f(I) + s}{t}\right \rfloor \right ]$$
更新 $[L, R]$ 的值重复上述过程。$n$ 的范围跨度从 $\Delta \sim R-L$ 缩小到 $\Delta' \sim \frac{s}{t}$,有
$$\Delta' \sim \frac{s}{t} \sim \frac{s(R-L)}{L-s-1} \sim \frac{s\Delta}{L-s} \sim \frac{s\Delta}{n}$$
所以迭代次数大约是 $\log_s n$,一般在 45 次左右(同样如果一次不行,就多试几次)
FYI:这是一般性的做法。如果直接做一些假设(譬如假设 $n$ 落在某个范围,令 $I = tR$ 等等),可以省略掉一些繁琐的步骤得到一些更简单但需要多试几次的做法。