NTRU私钥的中间会合攻击

Question

我想知道是否有人可以告诉我如何在NTRU私钥的中间相遇攻击中表示私钥f的向量的枚举。我不能理解这个例子，这里给出了http://securityinnovation.com/cryptolab/pdf/NTRUTech004v2.pdf，如果有人能给出一个详细的例子，我将非常感谢。

Answer 1

(全面披露:我在安全创新公司工作，并在SI收购我们之前为NTRU工作)

警告:答案很长！

让我们看一个玩具的例子:n= 11，q= 29。假设df = 3，因此f由等于1的3个系数和等于0的8个系数组成。假设dg = 5.并假设h= g*f^{-1} mod p，而不是使用f= 1+pF的优化。那么我们可能会有

f = [1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0]
finv = [16, 12, 4, 18, 17, 14, 9, 28, 8, 26, 3]
g = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0]
h = [15, 20, 1, 21, 4, 26, 14, 17, 25, 11, 12]

你可以在这里检查f*h =g。

攻击者想要找到f，所以他们可以对df = 3进行暴力搜索。他们可以利用这样一个事实来加快速度，即f会有一些旋转，第一个位置为1，因此他们只需要在(10 / 2)个可能的位置搜索f的另外两个非零系数。他们执行的完整搜索是：

           f*h (=g)                                       f
[9, 18, 7, 13, 26, 22, 15, 28, 27, 24, 19]; [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[23, 17, 4, 8, 16, 2, 3, 6, 10, 21, 11]; [1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[15, 2, 3, 5, 11, 21, 12, 23, 17, 4, 8]; [1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[12, 23, 17, 4, 8, 16, 2, 3, 5, 11, 20]; [1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[24, 20, 9, 18, 7, 13, 26, 22, 14, 28, 27]; [1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[2, 3, 6, 10, 21, 12, 23, 17, 4, 8, 15]; [1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[19, 10, 18, 7, 13, 26, 22, 14, 28, 27, 24]; [1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[28, 27, 25, 19, 10, 18, 7, 13, 25, 22, 14]; [1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[18, 7, 13, 26, 22, 15, 28, 27, 24, 19, 9]; [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[22, 14, 28, 27, 25, 19, 10, 18, 7, 13, 25]; [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[14, 28, 27, 24, 20, 9, 19, 6, 14, 25, 22]; [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[11, 20, 12, 23, 17, 4, 9, 15, 2, 3, 5]; [1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]
[23, 17, 4, 8, 16, 1, 4, 5, 11, 20, 12]; [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0]
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0]; [1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0]
[18, 7, 13, 26, 22, 14, 0, 26, 25, 19, 9]; [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0]
[27, 24, 20, 9, 19, 6, 14, 25, 22, 14, 28]; [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0]
[17, 4, 8, 16, 2, 3, 6, 10, 21, 11, 23]; [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]
[28, 27, 24, 19, 10, 18, 7, 13, 26, 22, 14]; [1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
[25, 19, 9, 18, 7, 13, 26, 22, 14, 0, 26]; [1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]
[8, 16, 1, 3, 6, 10, 21, 12, 23, 17, 4]; [1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0]
[15, 28, 27, 24, 20, 9, 18, 7, 13, 26, 21]; [1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]
[3, 6, 10, 21, 12, 23, 17, 4, 8, 16, 1]; [1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0]
[12, 23, 17, 4, 9, 15, 2, 3, 5, 11, 20]; [1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0]
[2, 3, 5, 11, 21, 12, 23, 17, 4, 8, 15]; [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1]
[17, 4, 8, 15, 2, 3, 6, 10, 21, 12, 23]; [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1]; [1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
[7, 13, 26, 21, 15, 28, 27, 24, 20, 9, 18]; [1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0]
[24, 20, 9, 18, 7, 13, 26, 21, 15, 28, 27]; [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0]
[4, 8, 16, 1, 4, 5, 11, 20, 12, 23, 17]; [1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0]
[23, 17, 4, 8, 16, 2, 3, 5, 11, 20, 12]; [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1]
[26, 22, 14, 28, 27, 24, 20, 9, 18, 7, 13]; [1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0]
[4, 5, 11, 20, 12, 23, 17, 4, 8, 16, 1]; [1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[21, 12, 23, 17, 4, 8, 16, 1, 3, 6, 10]; [1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0]
[1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0]; [1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0]
[20, 9, 18, 7, 13, 26, 22, 14, 28, 27, 24]; [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]
[16, 2, 3, 5, 11, 20, 12, 23, 17, 4, 8]; [1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0]
[4, 9, 15, 2, 3, 5, 11, 20, 12, 23, 17]; [1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0]
[13, 26, 22, 14, 0, 26, 25, 19, 9, 18, 7]; [1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0]
[3, 6, 10, 21, 12, 23, 17, 4, 8, 15, 2]; [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
[11, 21, 12, 23, 17, 4, 8, 15, 2, 3, 5]; [1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0]
[20, 9, 19, 6, 14, 25, 22, 14, 28, 27, 24]; [1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0]
[10, 18, 7, 13, 26, 22, 14, 28, 27, 24, 19]; [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
[8, 16, 2, 3, 6, 10, 21, 11, 23, 17, 4]; [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[27, 25, 19, 10, 18, 7, 13, 25, 22, 14, 28]; [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1]
[7, 13, 26, 22, 15, 28, 27, 24, 19, 9, 18]; [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]

向下扫描，您可以看到g出现在45行中的第14、26和34行。(g出现了三次，因为f中有三个1，所以f有三次旋转，其前导位置都是1)。

现在让我们看一下中间相遇攻击。攻击者使用公式

(f1+f2) * h = g

所以

f1*h = g - f2*h

使用ei表示e的第i个系数，这意味着攻击者知道

(f1*h)[i] = - (f2*h)[i] + 0 or 1

所以攻击者计算f1*h的所有可能值，将结果列表命名为{g1}。然后，他们计算-f2*h，并针对每个结果g2，查看g2是否与现有g1相同，或者g2是否与任何g1在每个系数中相差不超过1。换句话说，

[3, 10, 12, 7]

是否匹配

[4, 10, 12, 8]

通过这种方式，攻击者只需要完成以下工作：

• All 10 f1s，其中1位于领先位置，1 else
• All 10 f2s，单个1位于除领先的one

之外的任何位置

这给出了以下结果。我已经对列表进行了排序，以使匹配更容易识别。

          f1*h = g1                                           f1
[00, 08, 26, 03, 16, 12, 05, 18, 17, 15, 09]     [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[03, 16, 12, 04, 19, 17, 15, 09, 00, 08, 26]     [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[06, 21, 22, 25, 01, 11, 02, 13, 07, 23, 27]     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[07, 24, 27, 06, 21, 22, 25, 00, 11, 02, 13]     [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[11, 02, 13, 07, 24, 27, 06, 21, 22, 25, 00]     [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[12, 05, 18, 17, 15, 09, 00, 08, 26, 03, 16]     [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[16, 12, 05, 18, 18, 14, 10, 28, 08, 26, 03]     [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[19, 17, 15, 09, 00, 08, 26, 03, 16, 12, 04]     [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[26, 03, 16, 12, 05, 18, 18, 14, 10, 28, 08]     [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[27, 06, 21, 22, 25, 01, 11, 02, 13, 07, 23]     [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

         -f2*h = g2                                          f2
[03, 15, 12, 04, 18, 17, 14, 09, 28, 08, 25]     [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
[04, 18, 17, 14, 09, 28, 08, 25, 03, 15, 12]     [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[08, 25, 03, 15, 12, 04, 18, 17, 14, 09, 28]     [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[09, 28, 08, 25, 03, 15, 12, 04, 18, 17, 14]     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[12, 04, 18, 17, 14, 09, 28, 08, 25, 03, 15]     [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[15, 12, 04, 18, 17, 14, 09, 28, 08, 25, 03]     [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
[17, 14, 09, 28, 08, 25, 03, 15, 12, 04, 18]     [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[18, 17, 14, 09, 28, 08, 25, 03, 15, 12, 04]     [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[25, 03, 15, 12, 04, 18, 17, 14, 09, 28, 08]     [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[28, 08, 25, 03, 15, 12, 04, 18, 17, 14, 09]     [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]

您可以看到：

g1的

• 线路1与g2的线路10匹配，给出1，0，0，0，0，1，0，0，0，0，1，0
• g1的线路2与g2的线路1匹配，给出1，0，0，0，1，0，0，0
• g1的线路6与g2的线路5匹配，给出1，0，0，0，1，0，1，0，1，0，1，0，1，0，1，0，1，0，0，0与g2的线路6匹配，给出1，0，0，0，0，g1的0，1，0，0，0，1，0
• 行8与g2的行8匹配，给出1，0，1，0，0，0，0，0，1，0，0，0
• g1的行9与g2的行9匹配，给出1，0，1，0，0，0，0，0，0，1，0，0，0

这里有6次碰撞，因为有3次旋转，前导位置为1，对于每一次旋转，有两种方法来选取另外两个系数。

因此，攻击者必须做大约45/3 = 15的工作才能通过蛮力搜索找到密钥，而通过中间相遇攻击找到密钥需要做大约10次的工作(由于轮换，略少于10次，但我手头没有一个干净的公式)。

有各种优化，但这应该足以给您一个想法。

到目前为止，我还没有处理的一件事是如何减少搜索时间。要做到这一点，一种简单的方法是在进行过程中对结果进行排序。插入或查找与条目冲突的时间约为log_2(搜索空间的大小)。或者，以使用更多内存为代价，通过为g1的前几个系数的每个可能值保留一个块，可以将搜索时间减少到一个常数。

希望这能有所帮助。如果你还有什么问题，请告诉我。