ข้อโต้แย้งต่อการคำนวณระดับความปลอดภัยของ Kyber-512 โดย NIST
(blog.cr.yp.to)- แก่นของคำวิจารณ์คือ ในกระบวนการที่ NIST ผลักดัน Kyber-512 ให้เป็น มาตรฐานการเข้ารหัสยุคหลังควอนตัม นั้น NIST คำนวณต้นทุนการโจมตีผิดพลาดจนทำให้ระดับความปลอดภัยถูกประเมินสูงเกินจริง
- ประเด็นอยู่ที่ควรต้องนำ ต้นทุนการคำนวณ และ ต้นทุนการเข้าถึงหน่วยความจำ ที่เกิดขึ้นในแต่ละรอบมาบวกกัน แต่ NIST กลับปฏิบัติต่อมันเหมือนกับนำมาคูณกัน ทำให้การประเมิน 2^137 ของ Matzov ถูกเติม “ความปลอดภัยเพิ่มอีก 40 บิต” เข้าไป
- Kyber-512 ถูกเสนอว่ามีระดับ Core-SVP ที่ 2^118 และ NIST พยายามให้เทียบเท่ากับมาตรฐาน AES-128 ซึ่งอยู่ที่ประมาณ 2^143 bit operations แต่ถูกวิจารณ์ว่าหน่วยและความหมายของตัวเลขที่นำมารวมกันนั้นไม่สอดคล้องกัน
- Kyber ให้เพียง ตัวเลือกพารามิเตอร์ที่จำกัด เช่น Kyber-512, Kyber-768, Kyber-1024 ขณะที่มีการเปรียบเทียบว่า NTRU และ NTRU Prime ให้ตัวเลือกด้านขนาดและระดับความปลอดภัยที่ละเอียดกว่า
- การทำให้ Kyber-512 เป็นมาตรฐานมีปัญหาทั้งความไม่แน่นอนของการวิเคราะห์การโจมตี การยังไม่ได้วัดเชิงปริมาณของโมเดลต้นทุนหน่วยความจำ และการตรวจสอบสาธารณะที่ไม่เพียงพอ ผู้เขียนจึงเรียกร้องให้ถอด Kyber-512 ออกและให้ NIST เปิดเผยข้อผิดพลาดในการคำนวณ
แก่นของข้อผิดพลาดในการคำนวณ
- จุดตั้งต้นคือ ตัวอย่างง่าย ๆ ที่ว่า “2^40 + 2^40 ไม่ใช่ 2^80 แต่เป็น 2^41”
- หากสับสนระหว่างตัวเลขที่ต้องคูณกับตัวเลขที่ต้องบวก ระดับความปลอดภัยอาจถูกพองขึ้นอย่างมาก
- โครงสร้างที่เป็นปัญหาในข้อถกเถียงเรื่องระดับความปลอดภัยของ Kyber-512 มีดังนี้
- การโจมตีประกอบด้วย รอบซ้ำ (iteration) จำนวนมาก
- แต่ละรอบมีต้นทุนการคำนวณและต้นทุนการเข้าถึงหน่วยความจำ
- ต้นทุนรวมต้องคำนวณเป็น
จำนวนรอบ × ต้นทุนต่อรอบ - ภายในต้นทุนต่อรอบ ต้อง บวก ต้นทุนการคำนวณกับต้นทุนการเข้าถึงหน่วยความจำเข้าด้วยกัน
- คำวิจารณ์หลักคือ NIST ไม่ได้บวกต้นทุนการคำนวณกับต้นทุนการเข้าถึงหน่วยความจำ แต่ทำให้เกิดผลเหมือนการคูณกัน
- เช่น 2^25 bit operations/iteration กับ 2^35 bit operations/iteration ควรต้องนำมาบวกกัน
- หากนำมาคูณ หน่วยจะกลายเป็น
bitops^2/iter^2ซึ่งไม่ใช่หน่วยของต้นทุนการโจมตี - การคูณแบบนี้อาจพองต้นทุนการโจมตีได้มากกว่าหลายล้านเท่า
พื้นหลังของ NISTPQC และ Kyber-512
- NIST ประกาศแผนทำ Kyber-512 ให้เป็นมาตรฐานในปี 2022 และออกมาตรฐานฉบับร่างของ Kyber-512 ในปี 2023
- จุดเน้นของคำวิจารณ์อยู่ที่การที่ NIST ทำผิดพลาดร้ายแรงในการคำนวณระหว่างการให้เหตุผลรองรับระดับความปลอดภัยของ Kyber-512
- ในเดือนมีนาคม 2022 มีการยื่นคำขอ FOIA เรื่อง NSA, NIST, and post-quantum cryptography และต่อมามีการฟ้องร้องจนเอกสารภายในบางส่วนของ NIST ถูกเปิดเผย
- จากการเปรียบเทียบเอกสารที่เปิดเผยกับเอกสารที่ไม่เปิดเผย ผู้เขียนมองว่าการมีส่วนร่วมของ NSA ในกระบวนการ NISTPQC มีมากกว่าที่ NIST อธิบายต่อสาธารณะ
- มีการระบุว่าในรายชื่อทีม
pqc@nist.govปี 2016 มีบุคลากรจาก NSA มากกว่าบุคลากรจาก NIST - NIST เคยระบุในเอกสารสาธารณะปี 2020 ว่าข้อเสนอแนะจาก NSA ไม่ได้มีผลต่อการตัดสินใจ และมีเพียง NIST เท่านั้นที่ตัดสินใจบนพื้นฐานของข้อมูลสาธารณะ
- ในเดือนมกราคม 2023 มีการยื่นคำขอ FOIA ใหม่เกี่ยวกับข้อกล่าวอ้างเรื่องระดับความปลอดภัยของ Kyber-512 และระบุว่า NIST ได้ล่าช้าในการตอบอีกครั้ง จนนำไปสู่การฟ้องร้องใหม่
ตัวเลือกพารามิเตอร์ที่จำกัดของ Kyber
- มีการชี้ว่า Kyber เพิ่มระดับความปลอดภัยทีละน้อยด้วยขนาดที่ต้องการได้ยาก ต่างจาก RSA, ECC, McEliece, NTRU
- ไม่มี Kyber-576 และตัวเลือกที่แข็งแกร่งกว่า Kyber-512 คือ Kyber-768 ซึ่งต้องเพิ่มมิติขึ้น 50%
- ตัวเลือกที่แข็งแกร่งกว่า Kyber-768 คือ Kyber-1024
- ไม่มีตัวเลือกที่แข็งแกร่งกว่า Kyber-1024 ให้ใช้
- เอกสารทางการของ Kyber ชูจุดเด่นว่าสามารถจัดการพารามิเตอร์ทุกชุดด้วย “dimension-256 NTT” ได้ แต่ในโครงสร้างนี้ มิติที่ไม่ใช่พหุคูณของ 256 จะต้องเปลี่ยนการออกแบบหลัก
- ในแอปพลิเคชันที่จำกัดไว้ 1KB การใช้ Kyber-768 ทำได้ยาก และ Kyber-512 จึงกลายเป็นตัวเลือก Kyber ที่มีความปลอดภัยสูงสุด
- Kyber-768 ใช้ public key ขนาด 1184-byte และ ciphertext ขนาด 1088-byte
- Kyber-512 ใช้ key ขนาด 800-byte และ ciphertext ขนาด 768-byte
- ภายใต้ข้อจำกัด 1KB เดียวกัน มีการเปรียบเทียบว่าตระกูล NTRU ให้ค่าประมาณ Core-SVP ที่สูงกว่า
sntrup653: key 994-byte, ciphertext 897-byte, Core-SVP 2^129- NTRU-677 (
ntruhps2048677): key 931-byte, ciphertext 931-byte, Core-SVP 2^145 - Kyber-512 เวอร์ชัน round-3 ถูกเสนอว่ามี Core-SVP 2^118
- Core-SVP เป็นกลไกที่ทีม Kyber ใช้ประเมินระดับความปลอดภัยในการส่งเข้าประกวด round-1 และ round-2 และรายงาน round-2 ปี 2020 ของ NIST ก็ใช้ Core-SVP ในการเปรียบเทียบเช่นกัน
เกณฑ์ประเมินของ NIST และการเปรียบเทียบกับ NTRU
- คำขอให้ส่งข้อเสนออย่างเป็นทางการของ NIST ในปี 2016 รวม ความยืดหยุ่น (flexibility) ไว้ในเกณฑ์ประเมิน
- โดยมองว่าภายใต้สมมติฐานว่ามี “ความปลอดภัยและประสิทธิภาพโดยรวมที่ดี” วิธีที่มีความยืดหยุ่นมากกว่าจะตอบสนองความต้องการของผู้ใช้ได้มากกว่า
- ระบุชัดว่าแม้ภายในหมวดหมู่เดียวกัน ก็สามารถเสนอพารามิเตอร์หลายชุดเพื่อปรับประสิทธิภาพหรือระยะเผื่อด้านความปลอดภัยได้
- ในปี 2020 NIST ตัด NewHope ออก โดยยกเหตุผลข้อหนึ่งว่า Kyber รองรับชุดพารามิเตอร์ category 3 ได้อย่างเป็นธรรมชาติ
- หาก Kyber-512 ไม่ผ่านระดับความปลอดภัยขั้นต่ำ Kyber จะเหลือเพียง Kyber-768 และ Kyber-1024 ทำให้ปัญหาเรื่องความยืดหยุ่นด้อยกว่า NTRU เด่นชัดขึ้น
- selection report ปี 2022 ของ NIST ระบุว่ามั่นใจในความปลอดภัยของทั้ง Kyber และ NTRU และประเมินว่าประสิทธิภาพโดยรวมของ KEM ยอมรับได้สำหรับแอปพลิเคชันใช้งานทั่วไป
- ภายใต้เงื่อนไขนี้ ตรรกะคือหากตัด Kyber-512 ออก NTRU จะได้เปรียบกว่า Kyber เพราะให้ตัวเลือกที่เล็กกว่า ตัวเลือกที่ปลอดภัยกว่า และ trade-off ระหว่างขนาดกับความปลอดภัยที่ละเอียดกว่า
ข้อวิจารณ์สี่ข้อว่า NIST ทำให้การแข่งขันเอนเอียง
-
1. มองข้ามความยืดหยุ่นเพิ่มเติมของ NTRU
- ระบุว่าวรรณกรรมของ NTRU แสดงให้เห็นมานานแล้วว่าสามารถให้ตัวเลือกหลายระดับความปลอดภัยและหลายขนาดได้
- NIST ประกาศในปี 2020 ว่า “parameter sets มากเกินไปทำให้การประเมินและการวิเคราะห์ยากขึ้น”
- มีการชี้ว่าในเกณฑ์อย่างเป็นทางการ ความยืดหยุ่นถูกนำเสนอเป็นข้อดี แต่ระหว่างทางกลับมีคำวิจารณ์เรื่อง “too many” ปรากฏขึ้น และ NIST ไม่ได้ตอบเกณฑ์นั้นให้ชัดเจน
-
2. กล่าวเกินจริงเรื่องต้นทุนการสร้างคีย์
- ใน benchmark บน Golden Cove, Kyber-512 ใช้ encapsulation 25829 cycles และ decapsulation 20847 cycles
- NTRU-509 ใช้ encapsulation 15759 cycles และ decapsulation 25134 cycles โดยระบุว่าผลรวมการประมวลผล ciphertext น้อยกว่า Kyber-512 อยู่ 13%
- ขณะที่ key generation ของ NTRU-509 ใช้ 112866 cycles ซึ่งมากกว่า 17777 cycles ของ Kyber-512
- อย่างไรก็ตาม มีการโต้แย้งว่า KEM สามารถนำคีย์กลับมาใช้กับ ciphertext หลายรายการได้ ต้นทุนการส่งรับไบต์สำคัญกว่า cycle มาก และสามารถเร่ง key generation ของ NTRU ได้ด้วย Montgomery trick
-
3. ปกปิดระดับความปลอดภัยที่สูงกว่าของ NTRU
- NIST เริ่มแนะนำอย่างหนักแน่นให้มีชุดพารามิเตอร์ category 5 ในรายงาน round-2 ปี 2020
- NTRU เสนอ NTRU-1229 และ NTRU-HRSS-1373 ซึ่งระบุว่ามี Core-SVP 2^301 และ 2^310 ตามลำดับ สูงกว่า 2^254 ของ Kyber-1024
- NTRU Prime ก็เสนอทางเลือกอย่าง
sntrup1277,ntrulpr1277ที่มี Core-SVP 2^270, 2^271 - กราฟของ NIST ถูกวิจารณ์ว่าไม่ได้แสดงตัวเลือก NTRU ที่มีความปลอดภัยสูงเหล่านี้อย่างเพียงพอ
-
4. ตัด NTRU-509 ซึ่งเป็นตัวเลือกประสิทธิภาพสูงสุดออก
- มีการชี้ว่า NIST ตัด NTRU-509 ออกจากกราฟขนาดใหญ่ รวมถึงรูปและตารางใน selection report ภายหลัง
- NTRU-509 ให้ key และ ciphertext ที่เล็กกว่า Kyber-512 ซึ่งไม่สอดคล้องกับคำบรรยายของ NIST ที่ว่า “public key และ ciphertext ของ NTRU ค่อนข้างใหญ่กว่า Kyber”
- หากจะตัด NTRU-509 ออก ต้องบอกว่าไม่ถึงระดับความปลอดภัยขั้นต่ำ AES-128 แต่การยังคง Kyber-512 ไว้ด้วยเกณฑ์เดียวกันถูกวิจารณ์ว่าเป็นการแบ่งแยกที่เปราะบางมาก
ความไม่แน่นอนหลัง Core-SVP
- Core-SVP ของ Kyber-512 คือ 2^118 และต้นทุนการโจมตี AES-128 ถูกประเมินว่าสูงกว่า 2^140 bit operations เล็กน้อย
- เอกสารส่งประกวด Kyber ปี 2017 และ 2019 อ้างว่าปลอดภัยกว่า Core-SVP อย่างน้อย 30 บิต แต่ถูกวิจารณ์ว่าหลักฐานบางส่วนผิดหรือไม่เพียงพอ
- rounding noise ไม่ได้ใช้กับการโจมตีคีย์ จึงไม่ใช่เหตุผลของการเพิ่มความปลอดภัย
- ข้ออ้างเรื่องต้นทุน sieving ที่เพิ่มขึ้นแบบ subexponential ไม่มีหลักฐานรองรับ และมองว่า asymptotics จริงอาจเร็วกว่า Core-SVP
- จำนวนการเรียก SVP oracle และ gate count อาจสมเหตุสมผลในระดับหนึ่ง แต่ดูเหมือนไม่พอจะช่วย Kyber-512 ได้
- ต้นทุนการเข้าถึงหน่วยความจำอาจสำคัญต่อต้นทุนการโจมตีจริง แต่เกณฑ์ทางการของ NIST ต้องการ “classical gates” 2^143 จึงยากจะใช้เป็นตรรกะช่วย Kyber-512 โดยตรง
- การส่ง Kyber round-3 เปลี่ยน Kyber-512 และเปลี่ยนนิยาม Core-SVP จึงได้ 2^118 แทนที่จะเป็น 2^112
- การส่งครั้งนี้เสนอความปลอดภัยของ Kyber-512 เป็น 151 bits ±16 และอ้างว่าแม้จะลดลงถึง 135 ก็ไม่ถึงขั้น “catastrophic” เพราะข้อกำหนดด้านหน่วยความจำ
- หลังจากนั้น เมื่อมีการวิเคราะห์การโจมตี lattice หลายรายการ เช่นของ Matzov ปรากฏขึ้น การประเมินความปลอดภัยของ Kyber-512 ก็ซับซ้อนและไม่เสถียรมากขึ้น
ตรรกะของ NIST ในการช่วย Kyber-512
- call อย่างเป็นทางการของ NIST ระบุว่าแต่ละหมวดหมู่ความปลอดภัยใช้ primitive อ้างอิงอย่าง AES-128 เป็นขอบล่างใน metric หลากหลายแบบที่ “potentially relevant”
- กล่าวคือ การโจมตีใด ๆ ต้องใช้ทรัพยากรมากกว่าหรือเท่ากับเกณฑ์ในทุก metric ที่ NIST มองว่าอาจเกี่ยวข้องกับความปลอดภัยเชิงปฏิบัติ
- NIST หลีกเลี่ยงคำขอให้กำหนด “classical gates” อย่างชัดเจนมานาน และใน selection report ปี 2022 อธิบายว่าอนุญาตให้ one-bit memory read/write มีค่าเป็น cost-1 gate
- NIST ถูกวิจารณ์ว่าใช้ “non-local cost model” หรือเกณฑ์ที่มองว่าต้นทุนการเข้าถึงหน่วยความจำแทบฟรี เมื่อตัด NTRU-509 ออก
- ในทางกลับกัน เมื่อยังคง Kyber-512 ไว้ใน category 1 NIST กลับมองว่าเมื่อพิจารณา “realistic memory access costs” แล้วจะเป็นไปตาม category 1
- ผลคือมีการชี้ว่า NIST ใช้ free-memory metric กับ NTRU-509 แต่ใช้ memory-expensive metric กับ Kyber-512
NISTBS: ข้อโต้แย้งต่อคำอธิบายวันที่ 7 ธันวาคม 2022
- วันที่ 7 ธันวาคม 2022 NIST อธิบายเหตุผลที่มองว่า Kyber-512 เป็นไปตาม NIST category I และบทความนี้เรียกคำอธิบายนั้นว่า “NISTBS”
- NISTBS เริ่มจากการที่รายงานของ Matzov ประเมินต้นทุนการโจมตี Kyber-512 ไว้ที่ 2^137 bit operations
- ต้นทุนการโจมตีแบบคลาสสิกของ AES-128 ถูกประเมินไว้ประมาณ 2^143 bit operations
- ดังนั้นจึงขาดอยู่ 6 บิต
- NISTBS อธิบายว่าการโจมตีแบบ lattice sieving ต้องเข้าถึงหน่วยความจำขนาดใหญ่แบบไม่มีโครงสร้าง และ RAM model ละเลยต้นทุนนี้
- จากนั้นอ้างอิงการประเมินจากเอกสารส่งประกวดของ NTRU และ NTRU Prime โดยคำนวณว่าในการโจมตี sieving ระดับ category 1 หากพิจารณาต้นทุนการเข้าถึงหน่วยความจำ อาจสูงกว่า RAM model “20~40 bits”
- ปัญหาคือดูเหมือนว่า NIST นำ 40 บิตของ NTRU Prime ไปบวกกับ 2^137 ของ Matzov และตีความเป็นระดับ 2^177
- 40 บิตของ NTRU Prime ดูเหมือนมาจากส่วนต่างระหว่าง “real” 2^169 กับ “free” 2^129 ใน
sntrup653 - มีการชี้ว่า 2^129 คือ Core-SVP หรือก็คือจำนวนรอบคร่าว ๆ ไม่ใช่ gate count ของ RAM model ตามที่ NIST กล่าว
- ต้นทุนการเข้าถึงหน่วยความจำต้องบวกเข้ากับต้นทุนต่อรอบ และไม่สามารถนำไปคูณกับต้นทุนการคำนวณรวมที่นับเป็น bit operation แล้ว หรือบวกในรูปเลขชี้กำลังได้
- 40 บิตของ NTRU Prime ดูเหมือนมาจากส่วนต่างระหว่าง “real” 2^169 กับ “free” 2^129 ใน
ความหมายของตัวเลขจริง
- เอกสาร NTRU Prime รายงาน Core-SVP 2^129 สำหรับ
sntrup653- นี่คือค่าประมาณจำนวนรอบโดยคร่าว
- เอกสารเดียวกันประเมินต้นทุนรวมของการเข้าถึงหน่วยความจำเทียบเท่า 2^169 bit operations
- Kyber-512 ถูกเสนอว่ามี Core-SVP 2^118
- หากประเมินต้นทุนการเข้าถึงหน่วยความจำแบบหยาบด้วยวิธีเดียวกัน จะเทียบเท่าประมาณ 2^154 bit operations
- ค่าประมาณ “gates” 2^151 ในเอกสาร Kyber ไม่ใช่ค่าประมาณต้นทุนการเข้าถึงหน่วยความจำ
- แต่มันคือค่าประมาณจำนวน bit operations ภายในกระบวนการคำนวณของการโจมตี
- เมื่อคำนึงถึง “known unknowns” จึงเสนอเป็นช่วง 2^135~2^167
- ดังนั้นค่าประมาณต้นทุนการคำนวณ 2^151 กับค่าประมาณต้นทุนการเข้าถึงหน่วยความจำ ไม่ใช่พจน์ที่ต้องนำมาคูณกัน แต่เป็นพจน์ที่ต้องปรับความหมายให้อยู่ในมิติต้นทุนต่อรอบแล้วนำมาบวกกัน
เหตุใดจึงมองว่าจับข้อผิดพลาดได้ง่าย
- sanity check ง่าย ๆ มีดังนี้
- เอกสาร Kyber ประเมินต้นทุนการคำนวณของการโจมตี Kyber-512 ไว้ที่ 2^135~2^167 bit operations
- NTRU Prime ประเมินต้นทุนการเข้าถึงหน่วยความจำของ
sntrup653ซึ่งดูโจมตียากกว่า Kyber-512 ไว้เทียบเท่า 2^169 bit operations - มีการชี้ว่าเป็นเรื่องแปลกที่เมื่อการโจมตีดีขึ้น 2^14 แล้ว NIST กลับคำนวณต้นทุนการโจมตี Kyber-512 เป็น 2^177
- NISTBS เขียนว่าเอกสาร NTRU Prime ประเมินว่า “มีความปลอดภัยเพิ่ม 40 bits เมื่อเทียบกับ RAM model” แต่ระบุว่าใน Section 6.11 ของเอกสารนั้นไม่มีถ้อยคำ “40” หรือ “RAM model” โดยตรง
- คำวิจารณ์คือ เพื่อการตรวจสอบที่ชัดเจน NIST ควรอธิบายว่า 40 มาจากไหนแน่ และเป็นค่าของ metric ใด
- หลังเดือนธันวาคม 2022 มีคำถามยืนยันเกี่ยวกับ scenario X อย่างเจาะจงว่า “คำนวณเป็น 137+40=177 ใช่หรือไม่” แต่ระบุว่า NIST ไม่ตอบ
- ต่อมา NIST ตอบว่าอีเมลดังกล่าว “speaks for itself” และถูกวิจารณ์ว่าไม่ได้ยืนยันการตีความเฉพาะของการคำนวณหรือเสนอการตีความทางเลือก
งานวิจัยที่จำเป็นสำหรับการคำนวณที่ถูกต้อง
- การคำนวณที่ถูกต้องต้องแยกผลสองอย่างออกจากกัน
- ส่วนหนึ่งของการประเมินความปลอดภัยที่สูงกว่า Core-SVP มาจากต้นทุน bit operations ของการคำนวณภายในรอบ
- อีกส่วนมาจากลูปภายนอกที่ทำให้จำนวนรอบเองเพิ่มขึ้นเมื่อเทียบกับ Core-SVP
- ผลที่ทำให้จำนวนรอบเพิ่มขึ้นสามารถนำไปคูณกับต้นทุนการเข้าถึงหน่วยความจำได้
- ในทางกลับกัน ต้นทุนการคำนวณภายในรอบกับต้นทุนการเข้าถึงหน่วยความจำภายในรอบต้องนำมาบวกกัน และการคูณสองสิ่งนี้คือข้อผิดพลาดหลัก
- การคำนวณที่แม่นยำต้องตามอ่านงานวิจัยหลายร้อยหน้าที่เกี่ยวกับ state-of-the-art lattice attacks และต้องปรับเพิ่มประสิทธิภาพของสแต็กการโจมตีทั้งหมดใหม่เมื่อรวมต้นทุนการเข้าถึงหน่วยความจำ
- เช่น ภายใน BKZ ควรใช้ low-memory enumeration หรือ high-memory sieving จึงจะได้เปรียบ ก็ต้องคำนวณใหม่เมื่อใส่ต้นทุนการเข้าถึงหน่วยความจำเข้าไป
มาตรฐานฉบับร่างและประเด็นความรับผิดชอบ
- ในเดือนสิงหาคม 2023 NIST เผยแพร่ร่างมาตรฐาน Kyber คือร่าง ML-KEM
- ML-KEM-512 เป็น security category 1
- ML-KEM-768 เป็น category 3
- ML-KEM-1024 ถูกเขียนว่า “claimed” เป็น category 5
- ปัญหาคือไม่ชัดเจนว่าใครเป็นผู้ “claimed”
- มีการชี้ว่าไม่ชัดว่า NIST เป็นผู้กล่าวอ้าง ผู้ออกแบบเป็นผู้กล่าวอ้าง หรือเป็นข้อกล่าวอ้างของใครอื่น
- Appendix A ของร่างเสนอเกณฑ์อีกครั้งว่า category ต้องเหนือกว่า AES-128, AES-192, AES-256 ในทุก potentially relevant metric
- การวิเคราะห์ล่าสุดในเอกสาร Kyber เสนอว่าต้นทุนการโจมตี Kyber-512 อาจต่ำถึง 2^135 “classical gates” ซึ่งต่ำกว่าค่าประมาณ 2^143 gates ของ AES-128 โดย NIST
- ดังนั้นจึงจำเป็นต้องมีการวิเคราะห์สาธารณะว่า NIST ให้เหตุผลอย่างไรว่า Kyber-512 สูงกว่า AES-128 ในทุก metric ที่เกี่ยวข้อง
บทสรุปและข้อเสนอ
- ข้อสรุปคือพื้นผิวการโจมตี lattice ยังไม่เสถียรและยังไม่เป็นที่เข้าใจเพียงพอ ดังนั้นการทำ Kyber-512 ให้เป็นมาตรฐานจึงเป็นความเสี่ยงเกินไป
- มีความเป็นไปได้ว่า Kyber-512 จะโจมตีได้ง่ายกว่า AES-128 มาก แม้พิจารณาการโจมตีที่เผยแพร่แล้วและต้นทุนการเข้าถึงหน่วยความจำ แต่ก็มีความเป็นไปได้ในทางตรงข้ามด้วย หากต้องการเปิดเผยสภาพจริงจำเป็นต้องมีงานวิจัยที่ยาก
- มีการชี้ว่าแม้แต่ AES-128 เอง ในการโจมตีแบบหลายเป้าหมาย การเจาะหนึ่งในหนึ่งล้านล้านคีย์อาจอยู่ที่ระดับ 2^88 computations ดังนั้นการสูญเสีย 10~30 บิตจึงไม่ใช่เรื่องที่มองข้ามได้ง่าย
- หาก Kyber-512 ยังเป็นตัวเลือกมาตรฐานอยู่ แอปพลิเคชันที่สามารถรองรับ Kyber-1024 หรือ NTRU-1229 ได้ก็มีแนวโน้มจะเลือกตัวเลือกที่เร็วกว่า
- ข้อเสนอสุดท้ายคือให้ถอด Kyber-512 ออก และให้ NIST ยอมรับต่อสาธารณะถึงข้อผิดพลาดในการคำนวณระดับความปลอดภัยของ Kyber-512 รวมถึงการเลือกข้อมูลที่ไม่โปร่งใสในกระบวนการเปรียบเทียบกับ NTRU
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
สิ่งที่ต้องรู้ก่อนอ่านบทความนี้คือ NIST กับ NSA ไม่ได้เป็นผู้สร้างอัลกอริทึมนี้ แต่เป็นผู้ตัดสินการแข่งขัน
การวิเคราะห์ส่วนใหญ่ดำเนินการโดยผู้เข้าแข่งขันและแวดวงวิชาการ และทีม Kyber ก็มี Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, Damien Stehlé รวมถึง Peter Schwabe ผู้ร่วมงานของ Bernstein อยู่ด้วย
ในอดีตมักมีเพียงผู้ชนะเท่านั้นที่ถูกนำไปใช้ ลองดูการแข่งขัน AES ก็ได้ แค่คิดว่า Serpent ซึ่งถูกประเมินว่ามี margin ด้านความปลอดภัยมากกว่า Rijndael ถูกพูดถึงบ่อยแค่ไหนก็พอ
ดูเหมือนว่า NIST ไม่ได้ออกคำแนะนำโดยอาศัยการวิเคราะห์ลับอะไรบางอย่าง
ความจริงที่น่าเสียดายคือ Bernstein อาจพูดถูกก็ได้ แต่ก็แยกได้ยากว่าควรมองคำตอบหรือการไม่ตอบของฝั่ง NIST ว่าเป็น การหลอกลวง หรือแค่พวกเขาไม่อยากเข้าไปพัวพันกับคนที่เข้ามาด้วยท่าทีก้าวร้าวมากกันแน่
ที่ NIST ก็มีคนธรรมดาทำงานอยู่ และมีความเป็นไปได้สูงว่าพวกเขารับมือกับคำขอให้ชี้แจงแบบมีคมมีดแฝงอยู่ คล้ายกับวิธีที่พวกเราส่วนใหญ่รับมือกับรายงานบั๊กที่ก้าวร้าว
การกล่าวหาแบบเกินจริงอย่าง “ทำให้ข้อมูลผู้ใช้ 3 ปีถูกเปิดโปงต่อผู้โจมตี เพราะบอกให้ใช้ Kyber ตั้งแต่ตอนที่ใบอนุญาตสิทธิบัตรจะมีผลในปี 2024 และไม่ได้บอกให้ใช้ NTRU ตั้งแต่ปี 2021” ไม่ได้ช่วยอะไร คงยังไม่มีที่ไหนรีบ deploy การเข้ารหัสต้านควอนตัมแบบเดี่ยว ๆ ไปอีกสักพัก และในปี 2021 NIST ก็มีทางเลือกที่อาจเสนอได้หลายตัว SIKE เองก็ดูค่อนข้างดีจนกระทั่งถูกทำลายได้เมื่อปีก่อน
NIST ไม่ได้มีชื่อเสียงไร้ตำหนิในสาขานี้ก็จริง แต่ถ้าจะวิจารณ์อัลกอริทึมหรือกระบวนการ ก็น่าจะมีสรุปสั้น ๆ ว่าทำไมถึงเป็นเช่นนั้น พร้อมหลักฐานชี้ขาดสักหนึ่งหรือสองชิ้น การวิเคราะห์อีเมลจำนวนมาก การเทียบกับผลงานที่ส่งเข้ามาเพียงรายการเดียว และการกล่าวหาทำนองว่าทุกคนถ่วงเวลาเพื่อดูดข้อมูล ทำให้ยากที่จะรับฟังอย่างจริงจัง ถ้า Kyber-512 อันตรายจริง ๆ ถึงระดับนี้ ก็ควรสื่อสารให้ชัดเจนกว่านี้
ประเด็นใหญ่คือหน้านั้นยาวถึง 17,000 คำ แม้เทียบกับ Harry Potter ผู้อ่านทั่วไปก็ต้องใช้เวลาราว 70 นาทีในการอ่าน แต่บทความนี้ไม่ใช่นิยาย หากเต็มไปด้วยตัวเลข ประเด็นที่ต้องพิจารณา และประโยคที่ต้องชั่งน้ำหนักการเลือกใช้คำ เช่นคำอ้างอิงจาก NIST ต่อให้มีพื้นฐานพอจะเข้าใจการเข้ารหัสต้านควอนตัมอยู่แล้ว ก็ยากที่จะอ่านเร็วเหมือนหนังสือทั่วไป
ช่วงต้นผมกดตรง “That lawsuit has been gradually secret NIST documents, shedding some light on what was actually going on behind the scenes” แล้วโดนดูดไปอ่านบทความอื่น แต่หน้าที่ลิงก์ไปนั้นก็ยาวอีก 54,000 คำ บนมือถือไม่มีแถบเลื่อนเลยไม่รู้ว่ามันยาวแค่ไหน จึงไล่อ่านแบบเส้นตรงไปเรื่อย ๆ จนถึงจุดหนึ่งรู้สึกเหมือนตัวเองไปลงทะเบียนโครงการวิจัยระดับปริญญาเอกเข้าแล้ว เลยปิดแท็บและกลับมาบทความเดิม
ผู้อ่าน HN จำนวนมากฉลาดและมีพื้นฐานเทคนิค แต่ก็มาจากหลากหลายสาขา จึงยากที่จะประเมินอย่างมีเหตุผลต่อหลักฐานที่เต็มไปด้วยศัพท์เฉพาะซึ่งอ้างว่าสนับสนุนว่า “NIST=แย่” ผมอยู่ในสาขาใกล้เคียงและคิดว่าตัวเองเข้าใจมากกว่าผู้อ่านเฉลี่ย แต่ก็ไม่รู้สึกว่ามีสิทธิ์ตัดสินโดยไม่ได้อ่านอย่างถี่ถ้วน แม้บทความจะอธิบายบริบทและตัวย่อ แต่ปริมาณมากเกินไป จนไม่แน่ใจว่าคนที่ไม่ได้รู้อยู่แล้วจะอยากอ่านไปทำไม ไม่จำเป็นที่ submission ทุกชิ้นต้องเข้าใจได้สำหรับทุกคน แต่บทความนี้มีข้อกล่าวหาอยู่ด้วย เลยสงสัยว่าเหมาะกับ HN หรือไม่
ดังนั้นผมอาจถอนคำพูดด้านล่างไปบ้าง หรืออย่างน้อยเมื่อคิดถึงประวัติที่ djb มีกับคำแนะนำของ NIST ก็เข้าใจโทนที่ก้าวร้าวได้มากขึ้น ข้อมูลที่เกี่ยวข้องอยู่ที่ https://en.wikipedia.org/wiki/Daniel_J._Bernstein#Cryptograp...
ผมไม่ชอบการให้ความสำคัญกับรูปแบบมากกว่าเนื้อหามากเกินไป แต่กรณีนี้รูปแบบของบล็อกแย่มากจนประเมินได้ยากว่าเนื้อหามีคุณค่าหรือไม่ ผมไม่ใช่คนในวงการคริปโตจึงประเมินประเด็นหลักไม่ได้ แต่การเหน็บแนมและดูแคลนที่ไม่จำเป็นทำให้สารดูน่าสงสัยมาก แม้ดูเหมือนจะชี้จุดที่ดี แต่โทนโดยรวมคล้ายวิดีโอ YouTube แนว “WhaT ThE ElITe DoN'T WanT YoU TO KnoW!!” และต่อให้พูดถูก ผู้เขียนก็ฟังดูไม่น่าคบเอามาก ๆ
ผมยังสงสัยด้วยว่ามีใครอ่านจบจริงไหม การบอกว่าอินเทอร์เน็ตฆ่าสมาธิของเราก็อาจจริง แต่กลับกัน ตอนนี้ข้อมูลมีมากเกินไปจนเราต้องเลือกอย่างเข้มงวดมากว่าจะใช้เวลากับอะไร ถ้าเป็นบล็อกโพสต์ รายละเอียดที่เกี่ยวข้องกับ สรุป ควรอยู่ในไม่กี่ย่อหน้าแรก แล้วค่อยเอาบันทึกการไล่ค้นยาว ๆ ไปไว้ด้านหลัง ถ้าชิ้นส่วนสำคัญซ่อนอยู่ในบันทึกยืดยาวเหมือนเกม Where's Waldo ก็ยากที่จะคาดหวังให้คนอ่านจนจบ
แก่นที่เขาถามซ้ำ ๆ คือทำไมเกณฑ์การประเมินจึงถูกเปลี่ยนเรื่อย ๆ หลังจากนั้น ทำไมจึงนำเสนอผลลัพธ์ให้ชวนเข้าใจผิด และทำไมจึงมีข้อผิดพลาดในการคำนวณพื้นฐาน คนเหล่านี้เป็นผู้เชี่ยวชาญ แต่เรื่องทั้งหมดนี้กลับส่งผลเอื้อให้กับอัลกอริทึมตัวเดียว
ในสายตาผม นั่นดูเป็นสัญญาณว่าพวกเขาอยากผลักดันให้อัลกอริทึมนั้นกลายเป็นมาตรฐาน เมื่อบวกกับข้อเท็จจริงที่ว่า NSA มีส่วนเกี่ยวข้องมากกว่าที่เคยรู้กันมาก และพยายามปกปิดเรื่องนี้ ก็ยิ่งทำให้ผมสงสัยมาตรฐานนี้อย่างรุนแรง
เรื่องนี้เป็นปัญหา เพราะอัลกอริทึมเหล่านี้กำลังจะถูกฝังลงในฮาร์ดแวร์ในไม่ช้า
เมื่อ implementation ที่จะถูกทำให้เป็นมาตรฐานถูกกำหนดแล้ว ผู้ผลิตฮาร์ดแวร์ก็น่าจะเริ่มออกแบบบล็อกที่คำนวณมาตรฐาน FIPS 203 ได้มีประสิทธิภาพมากขึ้น บางรายอาจออกแบบไปแล้วด้วยซ้ำ
เมื่อดูว่าคาดว่าจะเผยแพร่มาตรฐานในปี 2024 และการตรวจสอบโมดูล FIPS โดย NIST CMVP ใช้เวลา 1–2 ปี ก็ไม่น่าแปลกใจหากราวกลางปี 2026 จะมีโมดูลฮาร์ดแวร์ FIPS 140-3 ที่มี ML-KEM (เช่น Kyber) ออกมา
แก่นสำคัญน่าจะเป็นประโยคใน [1] ที่ว่า “อย่างไรก็ตาม NIST ไม่ได้ให้คำกล่าวแบบ end-to-end ที่ชัดเจนว่า Kyber-512 มีส่วนเผื่อความปลอดภัย N บิตในสถานการณ์ X สำหรับ (N,X) ที่ระบุไว้อย่างชัดเจน”
ใน [2] djb สรุป “สถานการณ์ X” ที่เขาพูดถึงไว้อย่างกระชับ และบอกว่าต้องการเพียงคำตอบใช่/ไม่ใช่ เขากำลังถามคนที่จำเป็นต้องรู้เรื่องนี้จริง ๆ และมีพื้นฐานทางเทคนิคพอจะอภิปรายได้ เขาโพสต์ [1] เพราะไม่ได้รับคำตอบ
คำตอบของ NIST ใน [3] ปัด [1] ทิ้งไปโดยไม่อภิปรายเรื่องความปลอดภัยเอง โดยเฉพาะย่อหน้าที่สองชวนอึดอัดมาก “อีเมลที่อ้างถึง (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...) พูดแทนตัวมันเองอยู่แล้ว NIST ยังคงสนใจความคิดเห็นของผู้คนว่าแผนปัจจุบันที่จะทำให้ Kyber512 เป็นมาตรฐานนั้นดีหรือไม่ ผู้ตรวจทานมีอิสระที่จะลองโต้แย้งสิ่งที่ดูเหมือนว่า NIST อ้างเกี่ยวกับส่วนเผื่อความปลอดภัยเพื่อความสนุกได้ แต่ผลลัพธ์นั้นคงไม่ได้มีประโยชน์เป็นพิเศษต่อกระบวนการมาตรฐาน ข้ออ้างก่อนหน้าของ NIST และการตีความข้ออ้างเหล่านั้นไม่เกี่ยวข้องกับว่าผู้คนเชื่อหรือไม่ว่าการทำ Kyber512 ให้เป็นมาตรฐานเป็นความคิดที่ดี”
หาก NIST มองข้ออ้างด้านความปลอดภัยของผู้ตรวจทานว่า “ไม่ได้มีประโยชน์เป็นพิเศษต่อกระบวนการมาตรฐาน” แล้วเมื่อคิดว่าผู้ตรวจทานเหล่านั้นเป็นนักวิทยาการเข้ารหัสลับ สาธารณชนควรเชื่อถือมาตรฐานนั้นเพราะอะไร
คงไม่มีหลักฐานชี้ขาดได้อยู่แล้ว เพราะประเด็นตอนนี้ก็คือ การขาดคำอธิบายที่ชัดเจน หากอธิบายได้ว่าคำนวณระดับความปลอดภัยของ Kyber-512 อย่างไร เรื่องก็คงเป็นอีกแบบ
ตอนนี้จากการประเมินของบุคคลที่สาม ค่าที่ค่อนข้างคลุมเครืออย่างระดับความปลอดภัยของ Kyber-512 ออกมาต่ำกว่าข้อกำหนดเดิม จึงดูเหมือนจำเป็นต้องมีคำชี้แจงหรือเหตุผลรองรับ
[1]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
[2]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
[3]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
ถ้าเรื่องนี้เป็นบทความจากคนไร้ชื่อเสียง ผมอาจจะเห็นด้วยก็ได้ แต่ผู้เขียนคือ DJB หรือ Tanja Lange และทั้งสองคนก็ไม่ใช่คนไร้ชื่อเสียง
เรื่องแบบนี้ย่อมต้องมีความเป็นปฏิปักษ์อยู่บ้างในระดับหนึ่ง การถอดรหัสลับก็ต้องอาศัยท่าทีแบบนั้นด้วย และก็เพราะในอดีตเคยมีเรื่องน่าสงสัยหลายอย่างเกิดขึ้นด้วย มันเป็นส่วนหนึ่งของวงการและการเมือง จึงเลี่ยงได้ยาก
นี่ใกล้เคียงกับ บันทึกส่วนตัว มากกว่าบทความ มีศัพท์เฉพาะเยอะ จัดระเบียบไม่ดี วนไปวนมาอยู่ที่เดิม และตามอ่านยากมาก
ถึงอย่างนั้นตัวข้อมูลเองก็อาจสำคัญได้ มีนัยชัดเจนว่า NIST จงใจทำให้อัลกอริทึมที่อ่อนแอเป็นมาตรฐานโดยได้รับความช่วยเหลือจาก NSA
ทุกคนก็รู้ว่าเรื่องแบบนั้นเป็นไปได้
แต่ถ้ามีใครติดตามสาขานี้อย่างใกล้ชิดกว่านี้ อยากให้ช่วยอธิบายว่าตัวเลขตรงนี้หมายถึงอะไร ผมคิดมาตลอดว่าการทำให้การเข้ารหัสแบบกุญแจสาธารณะอ่อนแอลงแบบนี้เป็นการเดิมพันที่เสี่ยง เพราะรับประกันไม่ได้ว่าผู้โจมตีจะค้นพบข้อเท็จจริงเดียวกันได้เองหรือไม่ คีย์ลับสำหรับแบ็กดอร์อาจซ่อนได้ ข้อสงสัยตอน Dual_EC_DRBG ออกมาก็เป็นแบบนั้น แต่ผลลัพธ์ทางคณิตศาสตร์นั้นซ่อนยากจริง ๆ
ทำไมถึงพยายามรับความเสี่ยงแบบนั้นตรงนี้
ตอนนี้ไม่รู้แล้วด้วยซ้ำว่าทำไมต้องมีการอภิปรายแบบนี้ เราไม่ต้องการพวกเขาอีกต่อไปแล้ว ข้อจำกัดการส่งออกก็หายไปแล้ว
สิ่งที่ต้องมีคือคอนซอร์เทียมที่จะดึงความสนใจจากผู้ผลิตฮาร์ดแวร์ และจำกัด NIST กับ NSA ให้อยู่ในฐานะผู้เข้าร่วมธรรมดาเท่านั้น แบบนั้นต่อให้รัฐบาลนำมาตรฐานที่มีแบ็กดอร์ไปใช้ ก็จะมีแค่พวกเขาเองที่ใช้
ทำไมพวกเขาต้องสนใจเรื่องนั้นด้วย
ข้อสันนิษฐานปัจจุบันเกี่ยวกับสิ่งที่อาจเกิดขึ้นกับเส้นโค้งวงรีของ NIST ก็อยู่ทางนี้
ถ้าเป็นเช่นนั้น มันก็อาจกลายเป็นแบ็กดอร์ที่แทบจะใช้ได้เฉพาะสหรัฐฯ เป็นเวลานานมาก
แนวคิดคือพวกเขาจะนำหน้าในการโจมตีได้ และเมื่อถึงเวลาที่คีย์ 56 บิตโดยทั่วไปอ่อนแอเกินไป DES ก็คงถูกอย่างอื่นมาแทนที่แล้ว เสี่ยงไหม? ใช่ แต่ในบางความหมายมันก็ “สำเร็จ” ดังนั้นผมจะไม่สมมติว่าเรื่องคล้ายกันจะไม่เกิดขึ้นอีก
ทฤษฎีเบื้องหลังนั้นเรียกว่า kleptography หรือการเข้ารหัสเพื่อขโมยข้อมูล ซึ่งก็หมายความว่า NSA เพ้อฝันพอจะคิดว่าตัวเองสามารถขโมยข้อมูลได้อย่าง “ปลอดภัย”
ปีที่แล้วมีเธรดที่เกี่ยวข้องซึ่งมีคอมเมนต์ 443 รายการ
https://news.ycombinator.com/item?id=32360533 ("NSA, NIST, and post-quantum crypto: my second lawsuit against the US government (cr.yp.to)")
“การค้นหาวิธีทำงานลับของ NISTPQC เดือนมีนาคม 2022 ผมยื่นคำขอ FOIA ชื่อ ‘NSA, NIST, and post-quantum cryptography’ NIST ถ่วงเวลาโดยละเมิดกฎหมาย สำนักงานกฎหมายสิทธิพลเมือง Loevy & Loevy ยื่นฟ้องแทนผม”
ส่วนตัวแล้วผมค่อนข้างไม่ชอบ djb โดยรวม แต่ในทางวิชาชีพ เขาตามไล่บี้รัฐบาลกลางในศาลอย่างสม่ำเสมอ จึงสนับสนุนเสมอ ดีใจมากที่เห็นว่าเขายังทำต่ออยู่
นอกเหนือจากข้อเท็จจริงที่ว่า DJB เป็นบุคคลสำคัญในวงการวิทยาการเข้ารหัสลับ และผมไม่รู้รายละเอียดจำนวนมากตรงนี้ มีจุดหนึ่งที่ทำให้ความน่าเชื่อถือลดลงมาก
โดยเฉพาะในส่วนกราฟ เขาบอกว่า “NIST ตัดสินใจใช้แท่งสีแดงที่บางกว่าในกราฟแบนด์วิดท์เพื่อให้เน้นน้อยลง” แต่หลักฐานที่ยกมาไม่ได้พิสูจน์เรื่องนั้นเลย มีคำอธิบายที่สมเหตุสมผลกว่ามาก กราฟที่มีแท่งบางกว่าคือกราฟแท่งที่มีจุดข้อมูลมากกว่ากราฟอื่น ลองเปิดเครื่องมือทำแผนภูมิอะไรก็ได้ แล้วเทียบกราฟที่มีจุดข้อมูล 12 จุดกับกราฟที่มี 9 จุด ก็ย่อมเป็นธรรมดาที่เส้นของกราฟ 12 จุดจะบางลง ตรงจุดนี้ผมรู้สึกอย่างแรงว่าเขาพยายามตีความทุกการกระทำให้เป็นเจตนาร้ายที่สุดเท่าที่จะเป็นไปได้
ในรายการถัดมา เขาบ่นว่าไม่ได้ใช้ แกนลอการิทึม ทั้งที่ค่าต่าง ๆ อยู่ในช่วงหลักเดียวกัน ฟังดูไม่เหมือนกรณีที่เหมาะกับการใช้แกนลอการิทึม และผมก็ไม่แน่ใจว่ากรณีนี้จะให้เหตุผลรองรับได้อย่างไร
เมื่อรู้ว่า DJB มีส่วนเกี่ยวข้องกับ NTRU ก็ยากที่จะสลัดความรู้สึกว่าส่วนใหญ่ของเรื่องนี้เป็นปฏิกิริยาเคือง ๆ ต่อการแพ้ในการแข่งขัน
การสันนิษฐานแบบอื่น อย่างน้อยสำหรับผม ดูค่อนข้างไร้เดียงสา
มีเหตุผลพอให้สงสัย
เป็นเรื่องธรรมดาที่คู่แข่งในสาขานี้จะมาตรวจทานงานของกันและกัน
สิ่งที่ได้เรียนรู้จากการเฝ้าดูศึกเดือดของนักวิทยาการเข้ารหัสลับเป็นงานอาชีพ: อย่าเดิมพันสวน Bernstein และ อย่าเชื่อ NIST
NIST ตอบแล้ว: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VO...
ไม่แน่ใจว่า N(IST)SA ยังเหลือความน่าเชื่อถืออยู่ไหม
เป็นเรื่องน่ายินดีที่ curve25519 ถูกใช้แพร่หลายกว่าเส้นโค้ง P ของพวกเขา และหวังว่าชุมชนจะเดินต่อในทิศทางนี้พร้อมกับโดยมากไม่สนใจพวกเขาในอนาคต
รัฐบาลไม่ควรเป็นผู้นำหรือเป็นผู้ตัดสินใจ ในเรื่อง FIPS กฎระเบียบ ฯลฯ ควรจัดโครงสร้างโดยเน้นบทบาทในการรวบรวมและปฏิบัติตามฉันทามติปัจจุบันมากกว่า