Poly1305有像GCM/GHASH这样的弱键吗？

Question

当与GCM一起使用时，一些分组密码密钥是弱的；请参见这个问题。当由键决定的乘子H在\mathbb{F}_{2^{128}}的一个小阶子群中结束时，就会发生这种情况。

Poly1305的结构与GHASH非常相似。这也是一样的想法:在一个字段中，加一个块，然后乘以一个键决定的常数。GHASH使用\mathbb{F}_{2^{128}} (二进制字段)，Poly1305使用\mathbb{F}_{2^{130}-5} (素数字段)；其他差别很小。

Poly1305是否与弱密钥有相同的问题？订单，2^{130}-5-1，有因子\{2, 23, 32985101, 897064739519922787230182993783\}。

Answer 1

在丹尼尔S回答完上面的问题后，我写了一段代码来彻底搜索所有的元素，这些元素的顺序是\le {2*23*32985101}--弱键--同时匹配Poly1305's r掩码。

以下是所有76弱键的r值的完整列表，假设我这样做是正确的。当然，用适当生成的密码键来访问这些76密钥是不可能的，所以理论上可能并不重要。

# Order infinity
{ 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 }
# Order 1
{ 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 }
# Order 2 is impossible due to r mask
# Order 23 is impossible due to r mask
# Order 2 * 23 = 46 is impossible due to r mask
# Order 32985101
{ 0B 3C B5 01 AC 50 BA 0F EC D4 93 0E E0 15 87 0C }
{ F7 8A 43 04 90 81 58 0F 08 80 A4 07 00 E8 AE 03 }
# Order 2 * 32985101 = 65970202
{ E2 21 46 0C 48 03 02 06 00 0B 5F 03 B8 01 EF 02 }
# Order 23 * 32985101 = 758657323
{ 91 07 76 00 14 DA C3 04 00 6B C4 0D 50 D1 77 09 }
{ 72 3E B4 05 E8 1F 2F 09 BC 4F 60 04 6C 09 E2 09 }
{ 5B 63 19 05 48 93 CD 08 40 C5 2F 02 EC E5 76 0E }
{ 0C 11 BE 05 F0 3A 47 09 84 73 36 00 90 A4 14 01 }
{ C5 1B 20 09 60 4A A5 0F 14 04 E3 04 F4 1B 34 0E }
{ E2 0C CF 05 74 AB BF 09 08 EF F1 04 64 94 35 04 }
{ C6 88 DE 05 A8 ED 56 0F 08 34 ED 02 24 51 30 09 }
{ 91 8B 01 0B 54 C6 BE 01 50 47 71 02 EC 74 AD 0A }
{ AD B8 29 00 50 35 E9 0E D0 DA C1 0F 08 5D 66 06 }
{ 13 90 C9 05 34 C8 E0 03 04 6B DC 0B 3C 8F 0E 00 }
{ 38 59 5D 05 30 70 17 07 C8 12 EE 0C 0C 32 71 0B }
{ 04 AE 35 01 00 29 1D 0A 90 96 5A 0F 60 65 FD 05 }
{ 3C 6A 9B 02 CC 45 58 0F A0 D0 66 0B 4C 2B 3C 0F }
{ 9D B7 1F 0E 40 26 64 01 7C C6 85 08 1C 84 14 07 }
{ 7C FD 5E 03 D8 95 20 06 60 8E C7 07 30 3E 93 0B }
{ 0C 24 74 08 30 0E DF 06 DC 5A 20 01 9C 7F 2C 0C }
{ 1D F1 EC 05 A8 14 04 0C E0 3C C3 0C B8 5E 9D 07 }
{ FA 09 BE 01 8C 9D 55 01 08 39 1D 00 04 2B C2 09 }
{ DD F9 5C 06 C8 09 08 0E 8C A8 5E 01 E4 1F 99 00 }
{ 06 9F EB 09 30 3B FA 0F F4 D5 A1 0A 3C 8D DE 07 }
{ 8D EF B9 0F B0 70 08 0D 6C CB 27 02 4C 7E 21 06 }
{ B3 0D 1C 05 78 88 C0 07 18 E9 72 0A C0 AB 30 0A }
{ 1D F5 33 00 68 3D F9 00 3C 68 8E 0E 2C E2 7C 08 }
{ 2D 60 5E 04 A0 1A 52 0B C0 09 7F 0F 3C BF 17 04 }
{ 4D 92 28 0B 50 AA 51 03 A8 AA 14 07 88 97 D7 02 }
{ AB EE 3B 07 A4 F4 11 03 DC A6 79 04 14 6E 6F 05 }
{ C2 B8 A2 00 00 C2 FC 05 A4 4E E2 0E BC D7 65 01 }
{ C4 1A 2E 05 C0 DB 45 08 18 7E 5D 06 5C C8 B9 0F }
{ 44 8F 6D 0C 58 0E 43 00 30 87 35 0F 28 2E 3B 08 }
{ 69 29 E1 01 88 54 C4 0D 6C 15 FB 01 4C 6B C1 0C }
{ F6 7B 02 08 88 E6 C6 08 B0 75 01 0E A0 F5 C5 09 }
{ 41 9A 94 04 AC 76 87 04 A4 89 0D 01 C0 10 26 06 }
{ 4A C2 4B 0B FC 08 0B 00 BC 60 AC 0A AC D2 42 0E }
{ 06 DF 09 06 3C 7A A4 07 18 5A 4B 0C 1C 52 FF 0E }
{ AA 17 D2 03 2C F6 97 0E E8 C2 23 0E DC C1 51 02 }
{ 95 1A AE 05 F8 80 A0 07 48 A2 4D 05 1C F5 C8 0C }
{ B4 B0 C0 01 84 99 65 0B 2C 4D C0 0F 74 79 F8 0B }
{ 44 91 8A 03 98 9B 5C 07 F4 09 9C 09 E4 1F C7 0B }
# Order 2 * 23 * 32985101 = 1517314646
{ 79 D2 21 09 58 7B CD 0C 40 9B 15 0D D8 FB 25 05 }
{ 5F EC E4 03 B4 29 B8 04 1C F3 79 06 DC 09 9D 02 }
{ D5 E0 22 03 D8 EB 19 06 54 97 99 0D F8 06 9E 07 }
{ 36 E2 2B 09 60 28 16 0F 70 3A 42 0E 38 07 82 0E }
{ F5 98 38 0E 5C 18 FE 0E C4 F3 8E 00 84 BA DD 05 }
{ B0 8B 22 02 B8 5E A5 09 AC AE B5 0B D0 82 C9 0F }
{ 13 A8 D6 0A A0 E8 F4 00 54 0E 34 0A A0 3B 6F 0C }
{ 93 DA A6 01 E8 98 C5 08 00 93 BE 0E F8 28 1D 0A }
{ 10 6D 71 0B 40 D4 A3 00 34 E3 E1 09 74 F9 7A 05 }
{ 1C DA D4 09 BC 3B 84 03 58 34 B8 0C 84 BE DD 0A }
{ A1 C5 20 03 24 BD 5C 03 6C DE D4 04 DC 30 0B 0A }
{ 72 9C 3D 03 0C 21 47 07 C0 58 45 03 54 BA 23 02 }
{ 15 DE F2 0C FC 09 0F 06 90 A8 61 09 64 9E B7 00 }
{ 6F 07 F0 0A A0 3A 6E 09 08 58 F5 0B BC 1B E2 0E }
{ 5A 9A 12 08 5C 87 76 01 5C 5A 32 00 F8 17 B7 02 }
{ 32 B1 64 09 04 AF B0 04 A8 F3 9A 01 34 FD 85 0F }
{ E9 0E CB 06 34 C3 DD 07 7C 32 F0 06 54 1C D0 08 }
{ 11 05 EF 0C 4C A6 17 09 90 A9 20 00 0C 63 2B 00 }
{ 66 98 50 03 84 4E 31 09 C8 60 FA 0A 14 91 A3 07 }
{ 93 94 94 04 8C FE 91 01 F8 CB 8C 0D 70 9C BB 0C }
{ 96 A6 52 0C A8 CC 7B 0F FC 57 F2 07 E4 8A 5F 0E }
{ EC 42 ED 04 78 03 44 05 D4 29 61 03 D4 8B B1 00 }
{ 99 EC 16 0F 98 45 18 01 2C 90 28 05 E0 5C 7F 05 }
{ 45 84 D8 0D 58 A6 8D 02 E0 9F B3 07 08 DC D4 0C }
{ 11 7C D5 06 F8 43 47 0A 90 12 AB 07 68 33 1D 0B }
{ 1F 6B 25 01 28 F2 56 04 98 87 D8 00 A4 6F AB 05 }
{ 03 55 2C 08 44 9B 57 09 6C 76 AC 06 E8 9F E5 0C }
{ 8C 8F FE 0D E4 A3 D3 06 08 94 EB 05 20 B4 78 01 }
{ 64 1E 1F 08 2C 44 5F 03 04 61 9C 04 F8 36 11 02 }
{ 78 53 DB 02 9C 98 56 07 24 AB 66 01 4C 69 23 0B }
{ 0F DD 31 01 E8 A7 60 06 98 99 5A 03 E8 C2 37 00 }
{ 54 5E C5 0A 88 54 51 0F A0 3D B3 01 14 90 46 04 }
{ B9 FC C3 05 20 65 D7 06 2C C4 17 0D 44 5C 0D 00 }