การเข้ารหัสหลังควอนตัม – อัลกอริธึมใหม่ “หายไปใน 60 นาที”

เราได้เขียนเกี่ยวกับ PQC ย่อมาจาก การเข้ารหัสหลังควอนตัมหลายครั้งก่อนหน้านี้

ในกรณีที่คุณพลาดความตื่นเต้นของสื่อในช่วงไม่กี่ปีที่ผ่านมาเกี่ยวกับสิ่งที่เรียกว่าการคำนวณควอนตัม...

…มันคือ (ถ้าคุณจะให้อภัยสิ่งที่ผู้เชี่ยวชาญบางคนอาจพิจารณาว่าเป็นการทำให้เข้าใจง่ายเกินไปโดยประมาท) เป็นวิธีการสร้างอุปกรณ์คอมพิวเตอร์ที่สามารถติดตามได้ ผลลัพธ์ที่เป็นไปได้หลายอย่าง ของการคำนวณไปพร้อม ๆ กัน

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

การเพิ่มความเร็วเชิงการเข้ารหัสที่น่าสนใจสองรายการสามารถทำได้โดยใช้อุปกรณ์คอมพิวเตอร์ควอนตัม โดยสมมติว่าอุปกรณ์ที่ทรงพลังและเชื่อถือได้อย่างเหมาะสมสามารถสร้างได้:

• อัลกอริทึมการค้นหาควอนตัมของ Grover โดยปกติ หากคุณต้องการค้นหาชุดคำตอบที่เรียงลำดับแบบสุ่มเพื่อดูว่าคำตอบของคุณอยู่ในรายการหรือไม่ อย่างแย่ที่สุดคือต้องค้นหาคำตอบทั้งหมดก่อนที่จะได้คำตอบที่สรุปได้ ตัวอย่างเช่น หากคุณต้องการค้นหาคีย์ถอดรหัส AES 128 บิตเพื่อถอดรหัสเอกสาร คุณจะต้องค้นหารายการคีย์ที่เป็นไปได้ทั้งหมด โดยเริ่มต้นที่ 000..001, ..2, ..3และอื่นๆ ไปจนถึง FFF..FFF (ค่า . 16 ไบต์ FF) เพื่อความมั่นใจในการจบปัญหา กล่าวอีกนัยหนึ่ง คุณต้องใช้งบประมาณเพื่อลองทั้งหมด 2¹²⁸ คีย์ที่เป็นไปได้ก่อนที่จะค้นหาคีย์ที่ถูกต้อง หรือพิจารณาว่าไม่มีคีย์ อย่างไรก็ตาม อัลกอริธึมของ Grover ได้ใช้คอมพิวเตอร์ควอนตัมที่ใหญ่และทรงพลังเพียงพอ อ้างว่าสามารถทำสิ่งเดียวกันนี้ได้สำเร็จด้วย รากที่สอง ของความพยายามตามปกติจึงถอดรหัสรหัสในทางทฤษฎีในเวลาเพียง2⁶⁴ พยายามแทน
• อัลกอริทึมการแยกตัวประกอบควอนตัมของ Shor อัลกอริธึมการเข้ารหัสแบบร่วมสมัยหลายแบบอาศัยความจริงที่ว่าการคูณจำนวนเฉพาะขนาดใหญ่สองตัวเข้าด้วยกันสามารถทำได้อย่างรวดเร็ว ในขณะที่การหารผลคูณกลับเป็นตัวเลขสองตัวที่คุณเริ่มด้วยนั้นเป็นเรื่องที่ดีและเป็นไปไม่ได้ เพื่อให้ได้ความรู้สึกนี้ ลองคูณ 59×87 โดยใช้ปากกาและกระดาษ อาจใช้เวลาสักครู่เพื่อเอามันออก (5133 คือคำตอบ) แต่ก็ไม่ได้ยากขนาดนั้น ตอนนี้ลองวิธีอื่น หาร 4171 กลับเป็นสองปัจจัย ยากกว่าเยอะ! (ขนาด 43×97) ทีนี้ลองนึกภาพว่าทำสิ่งนี้ด้วยตัวเลขที่มีความยาว 600 หลัก พูดง่ายๆ ก็คือ คุณติดอยู่กับการพยายามหารตัวเลข 600 หลักด้วยทุกๆ จำนวนเฉพาะ 300 หลักที่เป็นไปได้ จนกว่าคุณจะถูกแจ็กพอต หรือพบว่าไม่มีคำตอบ อย่างไรก็ตาม อัลกอริธึมของ Shor สัญญาว่าจะแก้ปัญหานี้ด้วย ลอการิทึม จากความพยายามตามปกติ ดังนั้นการแยกตัวประกอบเลขฐานสองจำนวน 2048 หลักจึงควรใช้เวลานานเป็นสองเท่าของการแยกตัวประกอบตัวเลข 1024 บิต ไม่เกินสองเท่าของการแยกตัวประกอบตัวเลข 2047 บิต ซึ่งแสดงถึงการเร่งความเร็วอย่างมาก

รับมือภัยคุกคาม

ภัยคุกคามจากอัลกอริธึมของ Grover สามารถตอบโต้ได้ง่ายๆ โดยการเพิ่มขนาดของตัวเลขที่คุณใช้โดยการยกกำลังสอง ซึ่งหมายความว่าจะเพิ่มจำนวนบิตในแฮชเข้ารหัสของคุณหรือคีย์การเข้ารหัสแบบสมมาตรของคุณเป็นสองเท่า (กล่าวอีกนัยหนึ่ง ถ้าคุณคิดว่า SHA-256 ใช้ได้ในขณะนี้ การใช้ SHA-512 จะเป็นทางเลือกที่ทนต่อ PQC แทน)

แต่อัลกอริธึมของ Shor ไม่สามารถโต้กลับได้ง่ายๆ

คีย์สาธารณะขนาด 2048 บิตจะต้องเพิ่มขนาดแบบทวีคูณ ไม่ใช่เพียงแค่ยกกำลังสอง ดังนั้นแทนที่จะต้องใช้คีย์ขนาด 2×2048=4096 บิต คุณจึงต้องการคีย์ใหม่ที่มีขนาดเป็นไปไม่ได้ที่ 2²⁰⁴⁸ บิต…

…หรือคุณจะต้องใช้ระบบเข้ารหัสหลังควอนตัมแบบใหม่โดยสิ้นเชิง ซึ่งอัลกอริธึมของ Shor ไม่ได้ใช้

หน่วยงานมาตรฐานของสหรัฐอเมริกา NIST ได้ดำเนินการ a PQC "การแข่งขัน" ตั้งแต่ปลายปี 2017

กระบวนการนี้เปิดกว้างสำหรับทุกคน โดยยินดีต้อนรับผู้เข้าร่วมทุกคน อัลกอริทึมทั้งหมดได้รับการเผยแพร่อย่างเปิดเผย และการตรวจสอบจากสาธารณะไม่เพียงแต่เป็นไปได้เท่านั้น กำลังใจอย่างแข็งขัน:

โทรสำหรับข้อเสนอ [ปิดให้บริการ 2017-11-30]. […] มีจุดมุ่งหมายว่ามาตรฐานการเข้ารหัสคีย์สาธารณะใหม่จะระบุลายเซ็นดิจิทัลที่ไม่จัดประเภทและเปิดเผยต่อสาธารณะ การเข้ารหัสคีย์สาธารณะและอัลกอริธึมการสร้างคีย์ที่มีอยู่ทั่วโลกอย่างน้อยหนึ่งรายการและสามารถปกป้องข้อมูลของรัฐบาลที่ละเอียดอ่อนได้ ในอนาคตอันใกล้นี้ รวมทั้งหลังจากการถือกำเนิดของคอมพิวเตอร์ควอนตัม

หลังจากส่งผลงานและอภิปรายไปสามรอบ NIST ประกาศเมื่อวันที่ 2022-07-05 ว่าได้เลือกอัลกอริธึมสี่แบบที่ถือว่าเป็น "มาตรฐาน" โดยมีผลทันที ทั้งหมดนี้มีชื่อที่น่าฟัง: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONและ SPHINCS+.

คนแรก (CRYSTALS-KYBER) ใช้เป็นสิ่งที่เรียกว่า กลไกข้อตกลงที่สำคัญ (KEM) ที่ปลายทั้งสองด้านของช่องทางการสื่อสารสาธารณะสร้างคีย์เข้ารหัสส่วนตัวแบบใช้ครั้งเดียวอย่างปลอดภัยเพื่อแลกเปลี่ยนข้อมูลมูลค่าของเซสชันอย่างเป็นความลับ (พูดง่ายๆ ว่า ผู้สอดแนมเพิ่งได้รับกะหล่ำปลีหั่นฝอย ดังนั้นพวกเขาจึงไม่สามารถดักฟังการสนทนาได้.)

อีกสามอัลกอริทึมใช้สำหรับ ลายเซ็นดิจิทัลโดยคุณสามารถมั่นใจได้ว่าข้อมูลที่คุณได้รับในตอนท้ายของคุณตรงกับข้อมูลที่ผู้ส่งใส่เข้าไป ซึ่งจะช่วยป้องกันการปลอมแปลงและรับรองความสมบูรณ์ (พูดง่ายๆ ว่า ถ้าใครพยายามทำให้ข้อมูลเสียหายหรือเสียหาย คุณก็จะรู้.)

ต้องการอัลกอริธึมเพิ่มเติม

ในขณะเดียวกัน ในการประกาศมาตรฐานใหม่ สวทช. ยังได้ประกาศ a รอบที่สี่ ของการแข่งขัน โดยนำอัลกอริธึมอีกสี่ตัวไปข้างหน้าเป็น KEM ทางเลือกที่เป็นไปได้ (โปรดจำไว้ว่า ในขณะที่เขียน เรามีอัลกอริธึมลายเซ็นดิจิทัลที่ได้รับอนุมัติแล้วสามแบบให้เลือก แต่มี KEM อย่างเป็นทางการเพียงรายการเดียวเท่านั้น)

เหล่านี้คือ: BIKE, Classic McEliece, HQC และ SIKE.

ที่น่าสนใจคือ อัลกอริทึม McEliece ถูกคิดค้นขึ้นในปี 1970 โดย Robert Mc Eliece นักเข้ารหัสชาวอเมริกัน ซึ่งเสียชีวิตในปี 2019 หลังจากการแข่งขันของ NIST กำลังดำเนินไป

อย่างไรก็ตาม มันไม่เคยใช้ได้เลย เพราะต้องใช้วัสดุหลักจำนวนมากเมื่อเทียบกับอัลกอริธึม Diffie-Hellman-Merkle ทางเลือกที่ได้รับความนิยมในปัจจุบัน (DHM หรือบางครั้งก็แค่ DH)

น่าเสียดายที่หนึ่งในสามอัลกอริธึม Round Four คือ SIKE, ดูเหมือนจะแตก

ในกระดาษบิดสมองเรื่อง การโจมตีการกู้คืนคีย์อย่างมีประสิทธิภาพบน SIDH (เวอร์ชันเบื้องต้น)Wouter Castryk และ Thomas Decru นักเข้ารหัสชาวเบลเยี่ยมดูเหมือนจะจัดการกับอัลกอริธึม SIKE ที่อันตรายถึงชีวิต

ในกรณีที่คุณสงสัย SIKE ย่อมาจาก การห่อหุ้มคีย์ไอโซเจนีเหนือเอกพจน์และ SIDH ย่อมาจาก เอกพจน์ Isogeny Diffie-Hellman, การใช้เฉพาะของ อัลกอริทึม SIKE โดยที่ปลายทั้งสองด้านของช่องทางการสื่อสารจะทำ "การเข้ารหัส" ที่เหมือน DHM เพื่อแลกเปลี่ยนข้อมูลสาธารณะจำนวนมากที่ช่วยให้ปลายแต่ละด้านได้รับค่าส่วนตัวเพื่อใช้เป็นคีย์การเข้ารหัสลับแบบใช้ครั้งเดียว

เราจะไม่พยายามอธิบายการโจมตีที่นี่ เราจะทำซ้ำสิ่งที่กระดาษอ้างว่า:

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

แต่เอาท์พุตที่ดึงออกมา (ข้อมูลเรียกว่า ไอโซเจนี φ ด้านบน) ควรจะเป็นส่วนที่ไม่เคยเปิดเผยของกระบวนการ – คีย์ส่วนตัวที่เรียกว่า

กล่าวอีกนัยหนึ่ง จากข้อมูลสาธารณะเพียงอย่างเดียว เช่น ข้อมูลที่แลกเปลี่ยนอย่างเปิดเผยระหว่างการตั้งค่าคีย์ นักเข้ารหัสอ้างว่าสามารถกู้คืนคีย์ส่วนตัวของหนึ่งในผู้เข้าร่วมได้

และเมื่อคุณรู้รหัสส่วนตัวของฉันแล้ว คุณสามารถแกล้งทำเป็นว่าฉันได้อย่างง่ายดายและตรวจไม่พบ ดังนั้นกระบวนการเข้ารหัสจึงพัง

เห็นได้ชัดว่าอัลกอริธึมการแคร็กคีย์ใช้เวลาประมาณหนึ่งชั่วโมงในการทำงาน โดยใช้ซีพียูคอร์เพียงตัวเดียวที่มีพลังการประมวลผลแบบที่คุณพบในแล็ปท็อปทุกวัน

ซึ่งขัดกับอัลกอริทึม SIKE เมื่อกำหนดค่าให้ตรงตามระดับ 1 ซึ่งเป็นระดับความปลอดภัยของการเข้ารหัสขั้นพื้นฐานของ NIST

จะทำอย่างไร?

ไม่มีอะไร!

(นั่นเป็นข่าวดี)

ตามที่ผู้เขียนบทความแนะนำ หลังจากที่สังเกตว่าผลลัพธ์ยังอยู่ในขั้นเบื้องต้น “ด้วยสถานะปัจจุบัน SIDH ดูเหมือนจะถูกทำลายอย่างสมบูรณ์สำหรับเส้นโค้งพื้นฐานที่สร้างต่อสาธารณะ”

(นั่นคือข่าวร้าย.)

อย่างไรก็ตาม ให้อัลกอริธึม SIKE ยังไม่ได้รับการอนุมัติอย่างเป็นทางการ ตอนนี้มันสามารถปรับให้เข้ากับการป้องกันการโจมตีโดยเฉพาะ (สิ่งที่ผู้เขียนยอมรับอาจเป็นไปได้) หรือเพียงแค่ทิ้งไปโดยสิ้นเชิง

ไม่ว่าจะเกิดอะไรขึ้นกับ SIKE ในที่สุด นี่เป็นเครื่องเตือนใจที่ยอดเยี่ยมว่าทำไมการพยายามประดิษฐ์อัลกอริทึมการเข้ารหัสของคุณเองจึงเต็มไปด้วยอันตราย

นอกจากนี้ยังเป็นตัวอย่างที่ชัดเจนว่าเหตุใดระบบเข้ารหัสที่เป็นกรรมสิทธิ์ ที่อาศัยความลับของอัลกอริทึมนั่นเอง การรักษาความปลอดภัยของพวกเขาเป็นสิ่งที่ยอมรับไม่ได้ในปี 2022

หากอัลกอริธึม PQC เช่น SIKE รอดจากการโน้มน้าวใจและการตรวจสอบโดยผู้เชี่ยวชาญจากทั่วโลกมานานกว่าห้าปี แม้จะเปิดเผยอย่างเจาะจงเพื่อให้ถูกตรวจสอบโดยสาธารณะ...

…จากนั้นก็ไม่จำเป็นต้องถามตัวเองว่าอัลกอริธึมการเข้ารหัสแบบซ่อนจากมุมมองที่ทำเองที่บ้านของคุณน่าจะได้ผลดีแค่ไหนเมื่อเปิดตัวสู่สาธารณะ!

---