Điểm:6

Poly1305 có các khóa yếu như GCM/GHASH không?

lá cờ in

Một số khóa mật mã khối yếu khi được sử dụng với GCM; xem câu hỏi này. Điều này xảy ra khi số nhân $H$ được quyết định bởi khóa kết thúc trong một nhóm con có thứ tự nhỏ của $\mathbb{F}_{2^{128}}$.

Poly1305 có cấu trúc rất giống với GHASH. Đó là cùng một ý tưởng: thêm vào một khối, sau đó nhân với một hằng số do khóa xác định, trong một trường. GHASH sử dụng $\mathbb{F}_{2^{128}}$ (trường nhị phân) và sử dụng Poly1305 $\mathbb{F}_{2^{130}-5}$ (trường số nguyên tố); những khác biệt khác là nhỏ.

Poly1305 có cùng vấn đề với các phím yếu không? Mệnh lệnh, $2^{130}-5-1$, có các yếu tố $\{2, 23, 32985101, 897064739519922787230182993783\}$.

kelalaka avatar
lá cờ in
Lưu ý rằng tính hợp lệ của chính câu hỏi đang bị nghi ngờ, vui lòng xem [trò chuyện trên kênh bên](https://chat.stackexchange.com/transcript/message/59102677#59102677) để biết chi tiết.
kelalaka avatar
lá cờ in
Lưu ý rằng [Poly1305 an toàn hơn GCM](https://crypto.stackexchange.com/q/88716/18298) đối với các cuộc tấn công tiên tri phân vùng. Người ta nên ưu tiên xCHaCha20-Poly1305 hơn AES-GCM.
Điểm:5
lá cờ ru

có thể một số khóa có thể được phát hiện bằng cách hoán đổi các khối trong một thông báo được xác thực dài vài chục triệu khối. Ngoài ra còn có khóa yếu 0 tầm thường và khóa 1 tầm thường.

Nhớ lại rằng phụ gia MAC Poly1305 được tính như $$\left(\sum_i c_i r^i\pmod{2^{130}-5}\right)\pmod{2^{128}}$$ ở đâu $c_i$ là một loại nấm nhẹ của khối tin nhắn và $r$ là khóa MAC. Rõ ràng, nếu $r=0$ thì cộng luôn bằng không. Điều này không đáng kể để phát hiện vì bất kỳ sửa đổi nào của tin nhắn sẽ vẫn được xác thực. Nếu $r=1$, hoán đổi bất kỳ $c_i$$c_j$ sẽ không thay đổi phụ gia. Trao đổi hai khối tin nhắn sẽ đạt được điều này miễn là không phải là khối tin nhắn cuối cùng.

Tương tự như vậy, nếu $r\equiv -1\pmod{2^{130}-5}$ (tương ứng với phân nhóm bậc 2) rồi đổi chỗ $c_i$$c_j$ ở đâu $i$$j$ có cùng tính chẵn lẻ sẽ không thay đổi các khối Hoán đổi phụ gia $m_i$$m_j$ sẽ đạt được điều này với điều kiện không phải là khối cuối cùng. Tuy nhiên điều này $r$ không thể xảy ra dưới dạng khóa Poly1305 vì biểu thức nhị phân của nó là 11111111....11010 và các khóa Poly1305 bắt buộc phải có bit 0 ở các vị trí 28, 29, 30, 31, 32, 33, 60, 61, 62, 63, 64, 65, 66, 92, 93, 94, 95, 96, 97, 124, 125, 126, 127, 128 và 129 (lưu ý rằng đây là số xấp xỉ $2^{-24}$ điều kiện trên phần tử mod $2^{130}-5$).

Viết $p=2^{130}-5$ và lưu ý rằng 2 là một mod gốc nguyên thủy $p$, chúng tôi viết $\omega_{23}\equiv 2^{(p-1)/23}\pmod p$ và quyền hạn của $\omega_{23}$ đều theo thứ tự 23. Hoán đổi $c_i$$c_j$ Ở đâu $i$$j$ đồng dư mod 23 sẽ không thay đổi phụ gia khi $r\equiv\omega_{23}^k$ cho một số $k$ đưa ra 23 khóa yếu có thể khác. Tuy nhiên, không có khóa nào trong số này có khả năng đáp ứng các điều kiện bit cho $r$ (Tôi chưa kiểm tra). Tương tự với 23 phím khác của thứ tự 46.

Tuy nhiên, nếu chúng ta viết $\omega_{32985101}\equiv 2^{(p-1)/32985101}\pmod p$, trao đổi $c_i$$c_j$ Ở đâu $i$$j$ đồng dư mod 32985101 sẽ không thay đổi phụ gia khi $r\equiv\omega_{32985101}^k$ cho một số $k$ và đây là một họ khóa yếu tiềm năng lớn hơn nhiều, trong đó nửa tá khóa như vậy sẽ có khả năng phù hợp với các ràng buộc trên $r$ (Tôi chưa thực hiện tìm kiếm, nhưng nó rất đơn giản). Tin nhắn của hơn $2^{25}$ các khối không phải là không thể tưởng tượng được.

Có khả năng cũng có thêm một số khóa tương ứng với các yếu tố của trật tự $2\lần 32985101$, $23\lần 32985101$$46\lần 32985101$. Các phần tử trong đó 897064739519922787230182993783 phân chia thứ tự của chúng về mặt lý thuyết cũng tương ứng với các khóa yếu khác, nhưng độ dài của thông báo khoảng $2^{100}$ các khối là không thực tế và có thể nên tránh vì những lý do khác.

Myria avatar
lá cờ in
Sau khi đọc câu trả lời của bạn (cảm ơn!), tôi đã liệt kê tất cả các khóa yếu vẫn có thể xảy ra bất chấp mặt nạ $r$ của Poly1305. Xem bên dưới.
Điểm:1
lá cờ in

Sau câu trả lời của Daniel S ở trên, tôi đã viết mã để tìm kiếm tất cả các phần tử có thứ tự $\le {2*23*32985101}$--các phím yếu--trong khi khớp với Poly1305's $r$ mặt nạ.

Đây là danh sách đầy đủ của tất cả $76$ phím yếu' $r$ các giá trị dưới dạng byte cuối nhỏ, giả sử rằng tôi đã làm đúng. Tất nhiên, đánh bất kỳ trong số này $76$ các khóa có khóa mật mã được tạo phù hợp là điều khó xảy ra, vì vậy nó có thể không quan trọng ngoài lý thuyết.

# Thứ tự vô cùng
{ 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 }
# Đặt hàng 1
{ 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 }
# Đơn hàng 2 không được do r khẩu trang
# Order 23 không được do r mask
# Không thể đặt hàng 2 * 23 = 46 do mặt nạ r
# Đặt hàng 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 }
# Đặt hàng 2 * 32985101 = 65970202
{ E2 21 46 0C 48 03 02 06 00 0B 5F 03 B8 01 EF 02 }
# Đặt hàng 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 TCN 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 }
# Đặt hàng 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 TCN 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 TCN 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 }

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.