Bernstein蛮力的小键搜索电路

Question

我试图理解伯恩斯坦的理解蛮力。我不明白描述的机器怎么能用暴力强迫AES。

攻击者建立了一个非常小的密钥搜索电路。密钥搜索电路有三个输入:一个12字节字符串\beta、一个4字节整数n和一个16字节字符串s.密钥搜索电路有一个输出:一个由Z(\beta, 0, s) = s和Z(\beta, n + 1, s) = Z(\beta, n, H(s \oplus (\beta, n))递归定义的16字节字符串D7。

Answer 1

关键的部分不仅仅是Z的定义，它是可能的密钥中的随机游走。这也是你如何使用它，在下一页：

1. 搜索Z(\beta, 2^{23}, r_j)在Z(\beta, 0, H(k_i)), Z(\beta, 1, H(k_i)), Z(\beta, 2, H(k_i)), \dots, Z(\beta, 2^{23} - 1, H(k_i)).
2. 如果您找到了那个Z(\beta, 2^{23}, r_j) = Z(\beta, \ell, H(k_i))，那么您将有一个候选跟踪！
3. 在本例中，从计算Z(\beta, 2^{23}, r_j)开始，但只执行2^{23} - \ell - 1步骤直到状态(\beta, \ell + 1, s)，而不是一直到(\beta, 0, s')为止。
4. 如果是H(s \oplus (\beta, \ell)) = H(k_i)，您已经找到了k_i的候选人，即s \oplus (\beta, \ell)。

查看它的一种方法是:函数H (例如，k \mapsto \operatorname{AES}_k(18238))表示一个有向图，其中每个节点k正好有一个后续的H(k)。把这张图想象成一个地形上的河流网络。它们并不都是连接在一起的，但它们只向一个方向流动。

1. 你被传送到河中央的一个节点，你试图找到你身后的节点，但你不能看那里。
2. 你射出一堆廉价的无人机。他们将记录他们降落的节点，然后在停止并埋入河床之前，准确地沿着河上的2^{23}步骤流动。
3. 你睡一觉吧。早上，你沿着河拖网寻找一架无人驾驶飞机。如果您在\ell步骤之后找到了一个步骤，那么您将进入2^{23} - \ell - 1步骤开始并向前移动的点，并查看下一个节点是否是您在开始时所处的节点。

当然，你发现的无人机可能是从河的另一条支流下来的，所以你可能不得不用另一架无人机重试。

这是一个粗略的想法:模型崩溃是因为河流从来不循环，其优势要么来自于(a)无人机降落的预先计算(就像在预先计算的彩虹表中那样)，这样你就可以通过重复使用它们来节省很多拖网的精力，或者(b)同时进行拖网捕捞，同时发射无人驾驶飞机，然后通过对无人机降落的节点和你拖网过的节点进行排序来寻找碰撞。