ML-KEM (FIPS 203): มาตรฐาน CRYSTALS-Kyber

ML-KEM (กลไกการห่อหุ้มกุญแจที่อิงโครงสร้างแลตทิซของโมดูล) ซึ่งได้รับการกำหนดเป็นมาตรฐาน FIPS 203 ในเดือนสิงหาคม 2024 เป็นสิ่งทดแทนแบบหลังยุคควอนตัมสำหรับการแลกเปลี่ยนกุญแจด้วย Diffie-Hellman และ RSA กลไกนี้ห่อหุ้มกุญแจสมมาตรด้วยกุญแจสาธารณะ และสร้างความลับร่วมที่ทั้งสองฝ่ายสามารถใช้สำหรับการเข้ารหัสแบบสมมาตร ML-KEM พัฒนาต่อยอดจาก CRYSTALS-Kyber โดยปรับแก้เล็กน้อยเพื่อให้ข้อกำหนดมีความชัดเจนและเป็นระเบียบยิ่งขึ้น

ML-KEM กำหนดชุดพารามิเตอร์สามชุด ML-KEM-512 มุ่งให้มีความปลอดภัยประมาณ 128 บิตในกรณีการโจมตีแบบดั้งเดิม และ 100 บิตในกรณีหลังยุคควอนตัม โดยมีกุญแจสาธารณะขนาด 800 ไบต์และข้อความเข้ารหัสขนาด 768 ไบต์ ML-KEM-768 มุ่งให้มีความปลอดภัย 192 บิตในกรณีการโจมตีแบบดั้งเดิม (กุญแจสาธารณะ 1184 ไบต์ ข้อความเข้ารหัส 1088 ไบต์) ส่วน ML-KEM-1024 มุ่งให้มีความปลอดภัย 256 บิตในกรณีการโจมตีแบบดั้งเดิม (กุญแจสาธารณะ 1568 ไบต์ ข้อความเข้ารหัส 1568 ไบต์) NIST แนะนำให้ใช้ ML-KEM-768 สำหรับแอปพลิเคชันส่วนใหญ่

การสร้างกุญแจของ ML-KEM ทำงานดังนี้ สุ่มเลือกเมทริกซ์ A จากค่าเริ่มต้นโดยใช้ SHAKE-128 สุ่มเวกเตอร์ลับขนาดเล็ก s และเวกเตอร์ข้อผิดพลาด e จากนั้นคำนวณ t = As + e mod q กุญแจสาธารณะคือ (seed, t) ส่วนกุญแจส่วนตัวคือ s พร้อมแฮชของกุญแจสาธารณะ การใช้ค่าเริ่มต้นแทนการจัดเก็บ A ช่วยประหยัดหน่วยความจำและแบนด์วิดท์ได้อย่างมาก

ในการห่อหุ้ม ผู้ส่งจะสร้างข้อความสุ่ม m และหาคีย์สมมาตร K รวมทั้งค่าความสุ่ม r ผ่าน SHA-3 ข้อความเข้ารหัสประกอบด้วยสองส่วน ได้แก่ u = Ar + e1 mod q และ v = t^T r + e2 + encode(m) mod q ความลับร่วม K ได้มาจากแฮชของ m ส่วนค่าความสุ่มจะถูกสร้างจาก m แบบกำหนดแน่นอน ทำให้ข้อความเข้ารหัสผูกกับกุญแจ

การถอดห่อหุ้มจะกู้คืน m โดยคำนวณ v - s^T u แล้วถอดรหัส จากนั้นคำนวณ K ใหม่จาก m การแปลง Fujisaki-Okamoto เพิ่มขั้นตอนสำคัญด้วยการเข้ารหัส m ที่กู้คืนมาใหม่และตรวจสอบว่าข้อความเข้ารหัสตรงกันหรือไม่ หากไม่ตรงกัน ให้ส่งคืนค่าหลอกสุ่มที่ได้จากแฮชของกุญแจส่วนตัวและข้อความเข้ารหัส วิธีนี้ป้องกันการโจมตีแบบเลือกข้อความเข้ารหัสได้ โดยทำให้การถอดห่อหุ้มมีผลที่กำหนดแน่นอนและตรวจสอบได้

ML-KEM มีความปลอดภัยระดับ IND-CCA2 ในแบบจำลองแรนดอมออราเคิลเชิงควอนตัม (QROM) โดยพิสูจน์ภายใต้ข้อสมมติฐาน Module-LWE QROM มีความสำคัญเนื่องจากผู้โจมตีหลังยุคควอนตัมสามารถสอบถามฟังก์ชันแฮชในสถานะซ้อนทับได้ การพิสูจน์ความปลอดภัยของ Hofheinz, Hovelmanns และ Kiltz (กรอบงาน HHK) ให้การลดรูปที่รัดกุมจากความปลอดภัยของ Module-LWE ไปสู่ความปลอดภัยของ ML-KEM ใน QROM

ML-KEM มีประสิทธิภาพเหนือกว่า RSA อย่างมากสำหรับการแลกเปลี่ยนกุญแจที่ระดับความปลอดภัยเทียบเท่ากัน การสร้างกุญแจของ ML-KEM-768 ใช้เวลาประมาณ 16 ไมโครวินาทีบน CPU สมัยใหม่ การห่อหุ้มใช้เวลา 20 ไมโครวินาที และการถอดห่อหุ้มใช้เวลา 18 ไมโครวินาที ขณะที่การสร้างกุญแจ RSA-2048 ใช้เวลาหลายวินาที กุญแจสาธารณะของ ML-KEM (1184 ไบต์) มีขนาดใหญ่กว่า ECDH (32-64 ไบต์) แต่เล็กกว่า RSA-2048 มาก (256 ไบต์สำหรับกุญแจเพียงอย่างเดียว แต่โดยปฏิบัติจะยาวกว่านี้)

ในช่วงเปลี่ยนผ่าน การแลกเปลี่ยนกุญแจแบบผสมจะใช้ ML-KEM ร่วมกับอัลกอริทึมแบบดั้งเดิม (โดยทั่วไปคือ X25519 หรือ P-256 ECDH) ความลับร่วมคือแฮชของผลลัพธ์จาก KEM ทั้งสองชุด: K = Hash(K_classical || K_pqc) วิธีนี้ทำให้ความปลอดภัยไม่ด้อยกว่าส่วนประกอบใดส่วนประกอบหนึ่ง การใช้งาน TLS แบบผสมระบุไว้ใน draft-ietf-tls-hybrid-design และรองรับใน BoringSSL, OpenSSL 3.x และ Rustls

IETF กำหนด X25519ML-KEM-768 ให้เป็นส่วนแบ่งกุญแจแบบผสมสำหรับ TLS 1.3 (draft-ietf-tls-hybrid-design) Chrome เพิ่มการรองรับในเวอร์ชัน 124 (เมษายน 2024) และ Firefox ในเวอร์ชัน 132 (2024) Cloudflare นำ ML-KEM ไปใช้งานในโครงสร้างพื้นฐานสำหรับยุติการเชื่อมต่อ TLS การนำไปใช้อย่างรวดเร็วนี้ทำให้ปัจจุบันมีการเชื่อมต่อ TLS หลายร้อยล้านรายการต่อวันที่รวมการแลกเปลี่ยนกุญแจหลังยุคควอนตัมไว้ด้วย

เนื่องจากมีพจน์ข้อผิดพลาดใน LWE จึงมีความน่าจะเป็นเล็กน้อยมากที่การถอดห่อหุ้มจะล้มเหลวแม้ไม่มีผู้โจมตี สำหรับ ML-KEM-512 ความน่าจะเป็นของความล้มเหลวอยู่ที่ประมาณ 2^{-139} ส่วน ML-KEM-768 อยู่ที่ 2^{-164} อัตราเหล่านี้ต่ำกว่าระดับที่น่ากังวลในทางปฏิบัติมาก (เมื่อเปรียบเทียบกันแล้ว ข้อผิดพลาดของฮาร์ดแวร์เกิดขึ้นบ่อยกว่ามาก) และไม่ส่งผลต่อความปลอดภัย แต่ต้องนำมาพิจารณาในข้อกำหนด

ML-KEM มีการนำไปใช้ในไลบรารีโอเพนซอร์สจำนวนมาก การนำไปใช้อ้างอิงจากทีม Kyber เผยแพร่ในโดเมนสาธารณะ PQClean มีการนำไปใช้ด้วยภาษา C ที่ปรับปรุงให้สะอาดและพกพาได้ liboqs (โครงการ Open Quantum Safe) ผนวก ML-KEM เข้ากับตัวห่อหุ้มไลบรารี AWS-LC (สาขาที่ Amazon แยกมาจาก BoringSSL) มี ML-KEM สำหรับปลายทาง TLS ของ AWS มาตรฐาน NIST FIPS 203 มีรหัสเทียมโดยละเอียดสำหรับการดำเนินการทั้งหมด

NIST แนะนำชุดพารามิเตอร์ใดของ ML-KEM สำหรับแอปพลิเคชันส่วนใหญ่

ML-KEM (FIPS 203) คือ KEM หลังยุคควอนตัมที่ NIST กำหนดเป็นมาตรฐาน โดยอิงจาก Module-LWE ชุดพารามิเตอร์สามชุด (512/768/1024) ให้ความปลอดภัย 128/192/256 บิตในกรณีการโจมตีแบบดั้งเดิม การสร้างกุญแจสร้างกุญแจสาธารณะขนาดกะทัดรัดจากค่าเริ่มต้นสุ่ม การห่อหุ้มสร้างความลับร่วม และการถอดห่อหุ้มใช้การแปลง FO เพื่อให้มีความปลอดภัยระดับ CCA2 ML-KEM เร็วกว่า RSA อย่างมีนัยสำคัญ และมีการใช้งานแล้วใน Chrome, Firefox และ TLS ของ Cloudflare