Score:6

Poly1305 มีคีย์ที่อ่อนแอเช่น GCM / GHASH หรือไม่

ธง in

คีย์เข้ารหัสบางบล็อกอ่อนแอเมื่อใช้กับ 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\}$.

kelalaka avatar
in flag
โปรดทราบว่ามีการสอบถามความถูกต้องของคำถาม โปรดดู [การแชทของช่องด้านข้าง](https://chat.stackexchange.com/transcript/message/59102677#59102677)เพื่อดูรายละเอียด
kelalaka avatar
in flag
โปรดทราบว่า [Poly1305 ปลอดภัยกว่า GCM](https://crypto.stackexchange.com/q/88716/18298) ในการโจมตีของพาร์ติชัน Oracle ด้วย เราควรเลือก xCHACha20-Poly1305 เทียบกับ AES-GCM
Score:5
ธง ru

มี อาจจะ คีย์จำนวนหนึ่งที่สามารถตรวจจับได้โดยการสลับบล็อกในข้อความที่ผ่านการรับรองความถูกต้องซึ่งมีความยาวไม่กี่สิบล้านบล็อก นอกจากนี้ยังมีคีย์อ่อนแอเล็กน้อยศูนย์และคีย์ 1 เล็กน้อย

จำได้ว่าสารเติมแต่ง Poly1305 MAC คำนวณเป็น $$\left(\sum_i c_i r^i\pmod{2^{130}-5}\right)\pmod{2^{128}}$$ ที่ไหน $c_i$ เป็นเชื้อราเล็กน้อยของบล็อกข้อความและ $r$ คือคีย์ MAC อย่างชัดเจน ถ้า $r=0$ จากนั้นสารเติมแต่งจะเป็นศูนย์เสมอ นี่เป็นเรื่องเล็กน้อยในการตรวจสอบเนื่องจากการแก้ไขข้อความจะยังคงตรวจสอบความถูกต้อง ถ้า $r=1$, การแลกเปลี่ยนใด ๆ $c_i$ และ $c_j$ จะไม่เปลี่ยนสารเติมแต่ง การสลับบล็อกข้อความสองบล็อกจะทำให้ได้สิ่งนี้ โดยมีเงื่อนไขว่าต้องไม่ใช่บล็อกข้อความสุดท้าย

ในทำนองเดียวกัน ถ้า $r\equiv -1\pmod{2^{130}-5}$ (ตรงกับกลุ่มย่อยของลำดับที่ 2) จากนั้นทำการสับเปลี่ยน $c_i$ และ $c_j$ ที่ไหน $i$ และ $เจ$ มีความเท่าเทียมกันจะไม่เปลี่ยนบล็อกการสลับเพิ่มเติม $m_i$ และ $m_j$ จะบรรลุสิ่งนี้โดยมีเงื่อนไขว่าไม่ใช่บล็อกสุดท้าย อย่างไรก็ตามสิ่งนี้ $r$ ไม่สามารถเป็นคีย์ 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}$ เงื่อนไขเกี่ยวกับ mod องค์ประกอบ $2^{130}-5$).

การเขียน $p=2^{130}-5$ และสังเกตว่า 2 เป็น mod root ดั้งเดิม $p$, พวกเราเขียน $\omega_{23}\equiv 2^{(p-1)/23}\pmod p$ และอำนาจของ $\omega_{23}$ ล้วนเป็นลำดับที่ 23. การแลกเปลี่ยน $c_i$ และ $c_j$ ที่ไหน $i$ และ $เจ$ มีความสอดคล้องกัน mod 23 จะไม่เปลี่ยนสารเติมแต่งเมื่อใด $r\equiv\omega_{23}^k$ สำหรับบางคน $k$ ให้อีก 23 คีย์ที่อ่อนแอที่เป็นไปได้ อย่างไรก็ตาม คีย์เหล่านี้ไม่น่าจะตรงตามเงื่อนไขบิตสำหรับ $r$ (ยังไม่ได้ตรวจสอบ). เหมือนกันสำหรับอีก 23 คีย์ของคำสั่ง 46

แต่ถ้าเราเขียน $\omega_{32985101}\equiv 2^{(p-1)/32985101}\pmod p$, การแลกเปลี่ยน $c_i$ และ $c_j$ ที่ไหน $i$ และ $เจ$ มีความสอดคล้องกัน mod 32985101 จะไม่เปลี่ยนสารเติมแต่งเมื่อ $r\equiv\omega_{32985101}^k$ สำหรับบางคน $k$ และนี่คือตระกูลคีย์ที่อ่อนแอที่มีศักยภาพซึ่งมีขนาดใหญ่กว่ามากซึ่งครึ่งหนึ่งโหลมีแนวโน้มที่จะตรงกับข้อ จำกัด $r$ (ฉันยังไม่ได้ทำการค้นหา แต่ตรงไปตรงมา) ข้อความของกว่า $2^{25}$ บล็อกเป็นไปไม่ได้

มีแนวโน้มที่จะมีคีย์อีกสองสามตัวที่สอดคล้องกับองค์ประกอบของคำสั่ง $2\คูณ 32985101$, $23\คูณ 32985101$ และ $46\คูณ 32985101$. องค์ประกอบที่ 897064739519922787230182993783 แบ่งลำดับ ในทางทฤษฎียังสอดคล้องกับคีย์ที่อ่อนแออื่นๆ แต่ข้อความมีความยาวประมาณ $2^{100}$ การบล็อกนั้นไม่สมจริงและควรหลีกเลี่ยงด้วยเหตุผลอื่นๆ

Myria avatar
in flag
หลังจากอ่านคำตอบของคุณแล้ว (ขอบคุณ!) ฉันแจกแจงคีย์ที่อ่อนแอทั้งหมดที่อาจเกิดขึ้นได้แม้จะมีหน้ากาก $r$ ของ Poly1305 ดูด้านล่าง
Score:1
ธง in

หลังจากคำตอบของ Daniel S ข้างต้น ฉันเขียนโค้ดเพื่อค้นหาองค์ประกอบทั้งหมดที่มีลำดับอย่างละเอียดถี่ถ้วน $\le {2*23*32985101}$-- คีย์ที่อ่อนแอ -- ในขณะที่จับคู่ของ Poly1305 $r$ หน้ากาก.

นี่คือรายการทั้งหมดของทั้งหมด $76$ กุญแจอ่อน' $r$ ค่าเป็นไบต์ little-endian โดยสมมติว่าฉันทำถูกต้อง แน่นอนว่าการกดปุ่มใด ๆ เหล่านี้ $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 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 พ.ศ. 01 50 47 71 02 EC 74 AD 0A }
{ โฆษณา 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 }
{ เอฟเอ 09 พ.ศ. 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 }
# สั่ง 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 เอฟซี 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 อีซี 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 }

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา