Рейтинг:6

Есть ли у Poly1305 слабые ключи, такие как GCM/GHASH?

флаг in

Некоторые ключи блочного шифра ненадежны при использовании с GCM; видеть этот вопрос. Это происходит, когда множитель $Ч$ определяется ключом, попадает в подгруппу меньшего порядка $\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\}$.

kelalaka avatar
флаг in
Обратите внимание, что обоснованность самого вопроса подвергается сомнению, подробности см. в [чате побочного канала] (https://chat.stackexchange.com/transcript/message/59102677#59102677).
kelalaka avatar
флаг in
Обратите внимание, что [Poly1305 более безопасен, чем GCM] (https://crypto.stackexchange.com/q/88716/18298) и при атаках оракула разделов. Вместо AES-GCM следует предпочесть xCHaCha20-Poly1305.
Рейтинг:5
флаг ru

Есть наверное несколько ключей, которые можно обнаружить путем замены блоков в аутентифицированном сообщении длиной в несколько десятков миллионов блоков. Есть также тривиальный нулевой слабый ключ и тривиальный ключ 1.

Напомним, что добавка Poly1305 MAC рассчитывается как $$\left(\sum_i c_i r^i\pmod{2^{130}-5}\right)\pmod{2^{128}}$$ куда $c_i$ представляет собой мягкую подделку блока сообщений и $г$ является MAC-ключом. Очевидно, что если $г=0$ то добавка всегда равна нулю. Это тривиально обнаружить, так как любая модификация сообщения все равно будет аутентифицироваться. Если $г=1$, замена любого $c_i$ и $c_j$ добавку не менял. Это достигается заменой двух блоков сообщений при условии, что ни один из них не является последним блоком сообщения.

Аналогично, если $ г \ эквив -1 \ pmod {2 ^ {130} - 5} $ (соответствует подгруппе порядка 2), то замена $c_i$ и $c_j$ куда $я$ и $j$ иметь одинаковую четность не изменило бы аддитивную замену блоков $m_i$ и $m_j$ добьется этого при условии, что ни один из них не является конечным блоком. Однако это $г$ не может встречаться как ключ Poly1305, поскольку его двоичное выражение равно 11111111....11010, а ключи Poly1305 должны иметь нулевые биты в позициях 28, 29, 30, 31, 32, 33, 60, 61, 62, 63, 64, 65, 66, 92, 93, 94, 95, 96, 97, 124, 125, 126, 127, 128 и 129 (обратите внимание, что это примерно $2^{-24}$ условие на элементы мода $2^{130}-5$).

Пишу $р=2^{130}-5$ и отметив, что 2 - это примитивный корневой мод $р$, мы пишем $\omega_{23}\equiv 2^{(p-1)/23}\pmod p$ и полномочия $\омега_{23}$ все порядка 23. Перестановка $c_i$ и $c_j$ где находятся $я$ и $j$ конгруэнтны по модулю 23, не изменит добавку, когда $ г \ эквив \ омега_ {23} ^ к $ для некоторых $к$ давая еще 23 возможных слабых ключа. Однако ни один из этих ключей вряд ли удовлетворяет битовым условиям для $г$ (я не проверял). То же самое для других 23 ключей порядка 46.

Однако, если мы напишем $\omega_{32985101}\equiv 2^{(p-1)/32985101}\pmod p$, обмен $c_i$ и $c_j$ где находятся $я$ и $j$ конгруэнтны, мод 32985101 не изменит добавку, когда $ г \ эквив \ омега_ {32985101} ^ к $ для некоторых $к$ и это гораздо большее семейство потенциально слабых ключей, полдюжины из которых, вероятно, будут соответствовать ограничениям на $г$ (поиском не пользовался, но все понятно). Сообщения более $2^{25}$ блоки не исключены.

Также, вероятно, будет еще несколько ключей, соответствующих элементам порядка. $2\раз 32985101$, $23\раз 32985101$ и 46$\раз 32985101$. Элементы, где 897064739519922787230182993783 делят свой порядок, также теоретически соответствуют другим слабым ключам, но длина сообщения составляет около $2^{100}$ блоки нереалистичны, и их, вероятно, следует избегать по другим причинам.

Myria avatar
флаг in
Прочитав ваш ответ (спасибо!), я перечислил все слабые ключи, которые все еще могут произойти, несмотря на маску $r$ Poly1305. Смотри ниже.
Рейтинг:1
флаг in

После ответа Дэниела С. выше я написал код для исчерпывающего поиска всех элементов, порядок которых $\ле {2*23*32985101}$--слабые ключи -- при совпадении с Poly1305 $г$ маска.

Вот полный список всех $76$ слабые ключи $г$ значения как байты с прямым порядком байтов, при условии, что я сделал это правильно. Конечно, попадая в любой из этих $76$ ключей с соответствующим образом сгенерированным ключом шифрования смехотворно маловероятно, поэтому, вероятно, это не имеет значения, кроме как теоретически.

# Заказать бесконечность
{ 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 }
# Заказ 1
{ 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 }
# Порядок 2 невозможен из-за маски r
# Заказ 23 невозможен из-за маски r
# Порядок 2 * 23 = 46 невозможен из-за маски r
№ Заказ 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 }
# Заказ 2 * 32985101 = 65970202
{E2 21 46 0C 48 03 02 06 00 0B 5F 03 B8 01 EF 02}
#Заказ 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 до н.э. 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}
{ДД 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 АА 51 03 А8 АА 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 }
#Заказ 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 }
{ 5А 9А 12 08 5С 87 76 01 5С 5А 32 00 F8 17 В7 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 ДБ 02 9C 98 56 07 24 АБ 66 01 4C 69 23 0B }
{0F ДД 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 }

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.