用“自异或”输出函数攻击LCG？

Question

考虑一个普通的LCG模2^n，其内部状态为n比特，输出为n/2比特，而不是简单地截断状态以产生输出，我们将状态的上、下n/2比特合并在一起。

X_{i + 1} = A X_i + C \bmod{2^n} Y_i = (X_i / 2^{n/2}) \oplus (X_i \bmod 2^{n/2})

这类伪随机数产生器是否在某一篇文章中作过分析？当n很大(例如64或128位或更大)时，攻击它的核心思想是什么？我对输出预测或状态恢复中断特别感兴趣，但是有一个区分器也很好。我们可以假定LCG参数(乘数和增量)都是已知的和奇数的。

由于附加状态相关的非线性运算，通常的方法(如格)似乎不能适用于这种情况。

我试图从以下几个方面着手：

我们正在试图恢复初始状态X_0。我们可以收集一些输出\{ Y_i \}，并对X_0的LSB进行猜测。这将立即修复自X_i以来所有其他X_{i + 1} \equiv X_i + 1 \pmod{2}的LSB，从而根据输出函数的定义修复所有X_i的上半部分的LSB。

一些算术表明，对于所有的i \geq 0，我们都有

X_i \equiv A^i X_0 + C \sum_{k = 0}^{i - 1} A^k \equiv A^i X_0 + C_i \pmod{2^n}

现在，我们可以忽略上半部分(T-函数属性)的LSB之外的每一位，而专注于第一个n/2 + 1位。如果我们发现不存在剩余的n/2 - 1位X_0的赋值，那么对于收集到的所有Y_i，\mathrm{MSB}[\left ( A^i X_0 + C_i \right ) \bmod{2^{n/2 + 1}}] = \mathrm{LSB} \left [ Y_i \right ] \oplus \left ( \left ( X_0 + i \right ) \bmod{2} \right ) \tag{1}，我们肯定猜错了。这样做可能有更好的方法，但我们可以检查两次可满足性，一次使用我们的猜测，一次使用另一种猜测，添加更多的Y_i，直到任何一个系统变得不可满足为止，从而恢复两位X_0。原则上，在下一个最不重要的位上冲洗并重复，直到所有的X_0位都恢复为止。

检查可满足性需要O(2^{n/2})时间，因此，如果我们需要m输出最多以最天真的方式恢复状态，则O((n/2) \cdot 2^{n/2} \cdot m)比蛮力要快得多--强迫内部状态(假设m是合理的；我没有这方面的证据，但我怀疑m与n成正比，或者至少是多项式)。对于n = 64来说，它应该是(勉强)可行的，而n = 128的情况却是遥不可及的。

使用SMT解算器作为算法的一部分(我尝试过Z3和boolector)并没有给出任何加速，实际上比彻底的搜索要慢。这从直觉上讲是有意义的，因为不同A^i的乘法在位向量上是高度非线性的，所以求解器就会陷入困境，扩展和处理一个不断增长的、指数级的子句。

我们能做得更好吗？这里有什么可以应用的想法呢？

Answer 1

为了回答我自己的问题，经过一些研究和实验，我想出了一个快速算法来打破这种构造(实际上，下面的方法可以工作，即使增量C是未知的)。

1. 作为预处理步骤，找到一组m小权重\lvert w_i \rvert < W，以便

\sum_{i = 1}^{m} w_i A^i \equiv 0 \pmod{2^{n/2 + k}} \tag{1}

其中k是一些稍后定义的小整数。通过格基缩减，可以相当有效地找到这样一组权重(一般在多项式时间内)，例如在以下格基上运行LLL：

\begin{bmatrix} K A & K A^2 & \dots & K A^m & K \cdot 2^{n/2 + k} \\ 1 & 0 & \dots & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & 0 \\ 0 & 0 & \dots & 1 & 0 \end{bmatrix}

对于足够大的K，如Lagarias和Odlyzko所示。在实践中，我们期望这样的权重在

m \log_2(W) \approx n/2 + k

1. 猜测X_0的较低的k位，并使用LCG属性导出所有X_i的较低的D16位。
2. 使用Y_i获取所有X_i的上半部分的下k位。将X^*_i表示为X_i掩码，仅包括那些猜测的上位，即X^*_i = 2^{n/2} \times \mathrm{guess}。
3. 如果我们做一些基本代数，我们可以注意到下面的同余来自于(1)

\sum_{i = 1}^{m} w_i \left [ X_{i + 1} - X_i \right ] \equiv 0 \pmod{2^{n/2 + k}} \tag{2}

1. 由于w_i是由W有界的，并且我们知道所涉及的变量中最重要的部分，所以我们可以使用X^*_i来近似这个和。实际上，我们可以在\pm 2 m W \cdot 2^{n/2}中对其进行评估。计算：

Z = \sum_{i = 1}^{m} w_i \left [ X^*_{i + 1} - X^*_i \right ] \bmod{2^{n/2 + k}}

将\Delta设为Z与0或2^{n/2 + k}之间的区别，两者以最接近Z的值为准。

1. 如果是\Delta \geq 2mW \cdot 2^{n/2}，我们对X_0的低位数的猜测肯定是不正确的。否则，它对概率1 - 2mW \cdot 2^{-k}是正确的(这对Y_i的分布做了一些假设，但在实践中有效)。
2. 尝试所有2^k对输出Y_i的不同窗口的猜测(相应地调整，注意，即使用固定常数移动所有指数，关系(1)仍然有效)，直到步骤6中除一个以外的所有其他人都未能通过测试为止。最后的候选猜测将是X_0的较低位数。
3. 重复所有步骤，依次猜测更高的X_0位，直到整个内部状态恢复为止。

这是非常快的，因为k可以设置为不超过\log_2{mW}太大，因为步骤6中出现假阳性的概率足够小，例如0.5；如果k太小，那么我们不提取任何信息。

鉴于以上所述，我们应该在步骤1中尽量迫使W尽可能小，以尽量减少要猜测的位数，例如W \approx 2、m \approx n/2 + k so k \approx \log_2(n)，表明该攻击应该与n一起很好地扩展。

我已经实现了这一点，它运行得很好，并且成功地恢复了n = 128的内部状态。

此外，还可以将其扩展到未知增量C，唯一改变的是我们需要同时猜测C的较低位数与X_0的较低位数才能执行步骤2，其他一切都保持不变；我们通过相同的过程同时恢复C和X_0。

参考资料

这种方法是根据“格缩减:密码分析员工具箱”中所述的技术加以调整的。这篇论文包含了更复杂的技术来攻击类似的问题，并且是相当可读的。