Dual_EC_DRBG

background

NIST 800-90 random

RFC 8937 Randomness Improvements for Security Protocols

http://blog.0xbadc0de.be/archives/155

随机数生成算法 NSA后门

这个问题在于dQ=P，而 \(i_2 .. i_n, o_1 .. o_n\) 可以交错链式生成（没有其他伪随机参数加入计算）。

因此直接回溯至 \(i_1Q = A\) ，而A不超过32 bytes，可以直接进行暴力猜解。

指定x解椭圆方程求出可行的y，再计算比对 \(o_1\) 。。。

从这点看，结尾说的没错，确实疯狂。

detail

Dual EC: A Standardized Back Door

如果通过output可以推测PRNG的某些内部状态，进而可以推测后续的output，则PRNG是有问题的。

密码算法：设计，分析，标准化，选择，实现，部署

\[ \begin{align}\begin{aligned}state-based PRNG, with f and g s_1 = f(s_0) r_1 = g(s_1)\\ s_2 = f(s_2) r_2 = g(s_2)\end{aligned}\end{align} \]

显然，f and g 应该是one way function, 且如果是

Basic Dual EC

\[ \begin{align}\begin{aligned}s_1 = x(s_0 * P)，r_1 = x(s_1 * Q) ，显然，如果知道P=d*Q，则整个 s_i, r_i 的交错序列就可以递推出来。\\假设 r = (r_1, y_r_1) = s_1*Q\\d*r = d*s_1*Q = s_1*d*Q = s_1*P s_2 = x(d*r) = x(s_1*P) //可见，s_2 内部状态可通过 r_1 ，结合d推导出来\end{aligned}\end{align} \]

Dual EC 2006 with additional input

\[ \begin{align}\begin{aligned}t_0 = s_0 xor H(adin0)\\s_1 = x(t_0 * P) r_1 = x(s_1 * Q) t_1 = s_1 xor H(adin1)\\s_2 = x(t_1 * P) // 可见，此时 s_2 与 r_1 之间没有递推关系 r_2 = x(s_2 * Q)\\s_3 = x(s_2 * P) // s_3 = x(d * r_2) = x(d * s_2 * Q) = x(s_2 * P)，s_3与s_2/r_2之间。。。 r_3 = x(s_3 * Q)\end{aligned}\end{align} \]

Dual EC 2007 with additional input

\[ \begin{align}\begin{aligned}t_0 = s_0 xor H(adin_0)\\s_1 = x(t_0 * P) r_1 = x(s_1 * Q)\\s_2 = x(s_1 * P) t_2 = s_2 xor H(adin_2)\\s_3 = x(t_2 * P) r_3 = x(s_3 * Q)\\s_4 = x(s_3 * P) // 可见，s_2 与 s_1/r_1、s_4 与 s_3/r_3 ，s_5 与 s_4/r_4 之间。。。 r_4 = x(s_4 * Q)\\s_5 = x(s_4 * P)\end{aligned}\end{align} \]