Score:6

Does Poly1305 have weak keys like GCM/GHASH?

in flag

Some block cipher keys are weak when used with GCM; see this question. This happens when the multiplier $H$ decided by the key ends up in a small-order subgroup of $\mathbb{F}_{2^{128}}$.

Poly1305 has a very similar structure to GHASH. It's the same idea: add in a block, then multiply by a key-determined constant, within a field. GHASH uses $\mathbb{F}_{2^{128}}$ (binary field) and Poly1305 uses $\mathbb{F}_{2^{130}-5}$ (prime field); the other differences are minor.

Does Poly1305 have the same issue with weak keys? The order, $2^{130}-5-1$, has factors $\{2, 23, 32985101, 897064739519922787230182993783\}$.

kelalaka avatar
in flag
Note that the validity of the question itself is being questioned, please see [the side channel chat](https://chat.stackexchange.com/transcript/message/59102677#59102677) for details.
kelalaka avatar
in flag
Note that [Poly1305 is more secure than GCM](https://crypto.stackexchange.com/q/88716/18298) on partition oracle attacks, too. One should prefer xCHaCha20-Poly1305 against AES-GCM.
Score:5
ru flag

There are probably a handful of keys which could be detected by swapping blocks in an authenticated message that is a few tens of millions of blocks long. There's also the trivial zero weak key and the trivial 1 key.

Recall that the Poly1305 MAC additive is calculated as $$\left(\sum_i c_i r^i\pmod{2^{130}-5}\right)\pmod{2^{128}}$$ where $c_i$ is a mild funging of the message block and $r$ is the MAC key. Clearly if $r=0$ then the additive is always zero. This is trivial to detect as any modification of the message will still authenticate. If $r=1$, swapping any $c_i$ and $c_j$ would not change the additive. Swapping two message blocks will achieve this provided that neither is the final message block.

Likewise, if $r\equiv -1\pmod{2^{130}-5}$ (corresponding to the subgroup of order 2), then swapping $c_i$ and $c_j$ where $i$ and $j$ have the same parity would not change the additive Swapping blocks $m_i$ and $m_j$ will achieve this provided that neither is the final block. However this $r$ cannot occur as a Poly1305 key as its binary expression is 11111111....11010 and Poly1305 keys are required to have zero bits in positions 28, 29, 30, 31, 32, 33, 60, 61, 62, 63, 64, 65, 66, 92, 93, 94, 95, 96, 97, 124, 125, 126, 127, 128, and 129 (note that this is an approximately $2^{-24}$ condition on elements mod $2^{130}-5$).

Writing $p=2^{130}-5$ and noting that 2 is a primitive root mod $p$, we write $\omega_{23}\equiv 2^{(p-1)/23}\pmod p$ and the powers of $\omega_{23}$ are all of order 23. Swapping $c_i$ and $c_j$ where are $i$ and $j$ are congruent mod 23 will not change the additive when $r\equiv\omega_{23}^k$ for some $k$ giving another 23 possible weak keys. However, none of these keys is likely to satisfy the bit conditions for $r$ (I have not checked). Ditto for another 23 keys of order 46.

However, if we write $\omega_{32985101}\equiv 2^{(p-1)/32985101}\pmod p$, swapping $c_i$ and $c_j$ where are $i$ and $j$ are congruent mod 32985101 will not change the additive when $r\equiv\omega_{32985101}^k$ for some $k$ and this is a much larger family of potential weak keys of which half a dozen are so will likely match the constraints on $r$ (I've not done the search, but it is straightforward). Messages of over $2^{25}$ blocks are not inconceivable.

There are likely to also be a few more keys corresponding to elements of order $2\times 32985101$, $23\times 32985101$ and $46\times 32985101$. Elements where 897064739519922787230182993783 divides their order also theoretically correspond to other weak keys, but message lengths of around $2^{100}$ blocks are unrealistic and should likely be avoided for other reasons.

Myria avatar
in flag
After reading your answer (thanks!), I enumerated all the weak keys that could still happen despite Poly1305's $r$ mask. See below.
Score:1
in flag

After Daniel S's answer above, I wrote code to exhaustively search for all elements whose order $\le {2*23*32985101}$--the weak keys--while matching Poly1305's $r$ mask.

Here is the complete list of all $76$ weak keys' $r$ values as little-endian bytes, assuming that I did it right. Of course, hitting any of these $76$ keys with an appropriately generated cipher key is ridiculously unlikely, so it probably doesn't matter other than theoretically.

# 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 }
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.