SIDH และ SIKE: การออกแบบและการวิเคราะห์การเข้ารหัส

Supersingular Isogeny Diffie-Hellman (SIDH) ซึ่ง Jao และ De Feo เสนอในปี 2011 เป็นโพรโทคอลแลกเปลี่ยนกุญแจสาธารณะที่คล้ายกับ Diffie-Hellman แต่ใช้ไอโซเจนีบนเส้นโค้งวงรีซูเปอร์ซิงกูลาร์ ทั้งสองฝ่ายเริ่มต้นด้วยเส้นโค้งซูเปอร์ซิงกูลาร์เดียวกัน E เหนือ Fp2 Alice คำนวณไอโซเจนีลับ phi_A: E -> E_A (เคอร์เนลสุ่มในกลุ่มทอร์ชัน 2^a) แล้วเผยแพร่ E_A และภาพของตัวกำเนิดทอร์ชันของ Bob ภายใต้ phi_A Bob คำนวณ phi_B: E -> E_B (เคอร์เนลสุ่มในกลุ่มทอร์ชัน 3^b) แล้วเผยแพร่ E_B และภาพของตัวกำเนิดทอร์ชันของ Alice ภายใต้ phi_B Alice ใช้ข้อมูลที่ Bob เผยแพร่เพื่อคำนวณ phi_A': E_B -> E_AB ส่วน Bob คำนวณ phi_B': E_A -> E_AB ทั้งสองฝ่ายได้ค่า j(E_AB) เป็นความลับร่วม

รูปแบบพิเศษของจำนวนเฉพาะของ SIDH คือ p = 2^a * 3^b * f - 1 (โดย f เป็นตัวประกอบร่วมขนาดเล็กสำหรับการทดสอบความเป็นจำนวนเฉพาะ) ซึ่งทำให้เส้นโค้ง E เหนือ Fp2 มีโครงสร้างกลุ่มทอร์ชันที่จำเป็น สำหรับ SIKEp434 (ระดับ 1 ของ NIST, ความปลอดภัยหลังยุคควอนตัม 128 บิต): p = 2^216 * 3^137 - 1, a = 216, b = 137 นั่นหมายความว่า Alice เดินตามเส้นทาง 216 ขั้นของไอโซเจนี 2 ส่วน Bobเดินตามเส้นทาง 137 ขั้นของไอโซเจนี 3 ขนาดกุญแจ: กุญแจสาธารณะของ Alice ประกอบด้วย E_A และจุด Fp2 สองจุด (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 ไบต์ SIKEp751 มุ่งเป้าความปลอดภัยระดับ 192 บิตในกรณีคลาสสิกและ 128 บิตในกรณีควอนตัม และมีกุญแจสาธารณะขนาด 564 ไบต์ กุญแจเหล่านี้เป็นกุญแจสาธารณะที่มีขนาดเล็กที่สุดในบรรดาผู้สมัคร PQC ของ NIST ทั้งหมด โดยแลกกับความเร็วที่ช้าลง 100-1000 เท่า

SIKE (การห่อหุ้มกุญแจด้วยไอโซเจนีซูเปอร์ซิงกูลาร์) เป็น KEM ที่มีความปลอดภัยแบบ IND-CCA2 ซึ่งสร้างจาก SIDH โดยใช้การแปลง Fujisaki-Okamoto SIKE.Encaps: สุ่มข้อความ m คำนวณ (c0 = กุญแจสาธารณะ SIDH ที่ใช้เมล็ด m, c1 = H2(m) XOR pk) แล้วส่ง (c0, c1) SIKE.Decaps: กู้คืน m จาก c0 โดยใช้กุญแจลับ ตรวจสอบ c1 คำนวณ (c0, c1) ใหม่เพื่อตรวจสอบความสอดคล้อง แล้วส่งออก K = H3(m, c0) การแปลง FO เปลี่ยนการแลกเปลี่ยนที่ปลอดภัยแบบ CPA ของ SIDH ให้เป็น KEM ที่ปลอดภัยแบบ CCA2 SIKE เข้าร่วมการแข่งขัน PQC ของ NIST ครบทั้งสี่รอบ (2017-2022) และผ่านการวิเคราะห์การเข้ารหัสอย่างกว้างขวางมาได้ จนกระทั่งการโจมตีแบบคลาสสิกที่ร้ายแรงอย่างยิ่งปรากฏขึ้นในเดือนกรกฎาคม 2022

ตั้งแต่ปี 2011 ถึง 2022 SIDH ต้านทานความพยายามวิเคราะห์การเข้ารหัสครั้งสำคัญมาได้ การโจมตี SIDH ที่เป็นที่รู้จักว่าดีที่สุด ได้แก่: (1) อัลกอริทึม SSIP ทั่วไป: O(p^{1/4}) ในกรณีคลาสสิก และ O(p^{1/6}) ในกรณีควอนตัมโดยใช้อัลกอริทึมของ Tani (2) การค้นหาจากทั้งสองฝั่งบนเส้นทางไอโซเจนี: O(p^{1/4}) ในกรณีคลาสสิก ซึ่งเท่ากับ SSIP (3) อัลกอริทึมเวลาพหุนามสำหรับการโจมตีเชิงโครงสร้างเฉพาะ (van Oorschot-Wiener): ใช้กับ SIDH ไม่ได้ มีบทความหลายสิบฉบับวิเคราะห์ความปลอดภัยของ SIDH และตลอด 11 ปีก็ยังไม่พบการโจมตีแบบคลาสสิกหรือควอนตัมในเวลาพหุนาม ประวัติผลงานนี้ทำให้ SIKE เป็นผู้เข้ารอบสุดท้ายของ NIST ที่น่าเชื่อถือ อย่างไรก็ตาม การทำลายในท้ายที่สุดไม่ได้มาจากการโจมตี SSIP โดยตรง แต่มาจากการใช้ประโยชน์จากข้อมูลจุดทอร์ชันเสริมของ SIDH

เมื่อวันที่ 30 กรกฎาคม 2022 Wouter Castryck และ Thomas Decru เผยแพร่บทความฉบับร่างที่แสดงการโจมตี SIDH แบบคลาสสิกในเวลาพหุนาม การโจมตีนี้ใช้ข้อมูลเพิ่มเติมในจุดทอร์ชันเสริมของ SIDH ได้แก่ phi_A(P_B), phi_A(Q_B) โดยข้อมูลดังกล่าวเปิดเผยการกระทำของ phi_A บนกลุ่มย่อยทอร์ชัน 3^b แทบทั้งหมด เมื่อนำมารวมกับเส้นโค้งภาพ E_A ข้อมูลนี้ทำให้สามารถสร้างเคอร์เนลของ phi_A ขึ้นใหม่ได้ และจึงสร้าง phi_A เองได้ โดยใช้เทคนิคจากทฤษฎีเส้นโค้งวงรีที่มีการคูณเชิงซ้อนและไอโซเจนี Richelot การโจมตีใช้เวลา 62 นาทีบนแล็ปท็อปสำหรับ SIKEp434 ซึ่งเป็นชุดพารามิเตอร์ที่คาดว่าจะให้ความปลอดภัยหลังยุคควอนตัม 128 บิต ภายในไม่กี่วัน นักวิจัยอิสระได้ยืนยันและต่อยอดการโจมตีนี้กับพารามิเตอร์ SIDH ทั้งหมด

การออกแบบ SIDH กำหนดให้ทั้งสองฝ่ายเผยแพร่ภาพของจุดฐานทอร์ชันของอีกฝ่ายภายใต้ไอโซเจนีลับของตน สิ่งนี้จำเป็นต่อการทำงานของโพรโทคอล เพราะหากไม่มี phi_A(P_B) และ phi_A(Q_B) Bob จะไม่สามารถย้ายไอโซเจนีของตนไปยังเส้นโค้งของ Alice เพื่อคำนวณความลับร่วมได้ แต่ข้อมูลเพิ่มเติมนี้ ซึ่งเปิดเผยการกระทำของ phi_A ที่จำกัดอยู่บนกลุ่มทอร์ชัน 3^b กลับให้ข้อมูลมากเกินกว่าที่คาดไว้อย่างร้ายแรง การโจมตีของ Castryck-Decru ใช้เส้นโค้งสกุล 2 (ไอโซเจนี Richelot) เพื่อยกระดับปัญหาไปยังวัตถุที่มีสกุลสูงกว่า ซึ่งการกระทำที่ถูกจำกัดนั้นสามารถกำหนด phi_A ได้อย่างสมบูรณ์ การรั่วไหลนี้เป็นปัญหาเชิงโครงสร้างของ SIDH และไม่สามารถแก้ไขได้หากไม่เปลี่ยนการออกแบบพื้นฐานของโพรโทคอล

เมื่อวันที่ 5 กรกฎาคม 2022 (ก่อนการโจมตีของ Castryck-Decru) NIST ประกาศตัวเลือกเบื้องต้นสำหรับการทำมาตรฐาน PQC ได้แก่ ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+) และ FN-DSA (Falcon) โดยไม่มี SIKE อยู่ในกลุ่มนี้ เพราะ SIKE อยู่ในการพิจารณารอบที่สอง การโจมตีของ Castryck-Decru ในเดือนกรกฎาคม 2022 ทำให้ NIST ตัด SIKE ออกจากการพิจารณาอย่างเป็นทางการโดยสิ้นเชิง NIST ระบุว่า: "SIKE is no longer under consideration for standardization." นี่เป็นพัฒนาการด้านการวิเคราะห์การเข้ารหัสที่รุนแรงที่สุดในการแข่งขัน PQC ของ NIST และแสดงให้เห็นว่าแม้โครงร่างที่ผ่านการวิเคราะห์มา 11 ปีโดยยังไม่ถูกโจมตี ก็อาจถูกทำลายได้ด้วยข้อค้นพบทางคณิตศาสตร์ใหม่ที่แตกต่างโดยพื้นฐาน

ภายในหนึ่งสัปดาห์หลังการโจมตีของ Castryck-Decru Thomas Decru และ Luciano Maino ได้เผยแพร่การปรับปรุงเพิ่มเติมโดยอิสระ และต่อมา Damien Robert ก็เผยแพร่ผลงานของตน รูปแบบการโจมตีของ Robert ใช้ข้อสังเกตเดียวกัน แต่คำนวณริงเอนโดมอร์ฟิซึมของ E_A แทนการคำนวณเคอร์เนลของไอโซเจนีโดยตรง และอาจอธิบายได้ง่ายกว่าในทางคณิตศาสตร์ การค้นพบซ้ำโดยอิสระอย่างรวดเร็วเหล่านี้ยืนยันว่าการโจมตีของ Castryck-Decru ระบุจุดอ่อนเชิงโครงสร้างพื้นฐาน ไม่ใช่กลเม็ดเฉพาะทางที่คลุมเครือ ความรวดเร็วของบทความที่ตามมายังสะท้อนว่ามีนักวิจัยจำนวนมากศึกษาการรั่วไหลของจุดทอร์ชันใน SIDH ในฐานะช่องทางโจมตีที่อาจเป็นไปได้อยู่แล้ว โดยตระหนักว่านี่เป็นการเปิดเผยข้อมูลที่ผิดปกติ แต่ยังไม่สามารถใช้ประโยชน์ได้จนกระทั่ง Castryck และ Decru ค้นพบสะพานเชื่อมไปยังสกุล 2

FESTA (การเข้ารหัสที่รวดเร็วจากการโจมตีทอร์ชันซูเปอร์ซิงกูลาร์, 2023) เป็นการออกแบบ KEM ที่ได้รับแรงบันดาลใจจาก SIDH แต่หลีกเลี่ยงข้อมูลจุดทอร์ชันเสริม FESTA ใช้โครงสร้างโพรโทคอลที่แตกต่างออกไป โดยกุญแจสาธารณะจะไม่รวมภาพของฐานทอร์ชันของคู่สื่อสาร แต่จะผูกมัดไอโซเจนีลับไว้ด้วยเส้นโค้งภาพเพียงอย่างเดียว โดยไม่มีจุดเสริม FESTA เข้ารหัสโดยใช้ไอโซเจนีในลักษณะที่เปิดเผยข้อมูลเชิงโครงสร้างน้อยกว่า การวิเคราะห์ความปลอดภัยในระยะแรกชี้ว่า FESTA หลีกเลี่ยงโครงสร้างการโจมตีของ Castryck-Decru ได้ อย่างไรก็ตาม FESTA เป็นโครงร่างที่ใหม่กว่าและได้รับการตรวจสอบวิเคราะห์น้อยกว่าประวัติการวิเคราะห์ SIKE ที่ยาวนาน 11 ปี ชุมชนไอโซเจนีจึงระมัดระวังในการนำโครงร่างใหม่ไปใช้งานก่อนผ่านการวิเคราะห์อย่างกว้างขวาง

การทำลาย SIKE ให้บทเรียนสำคัญหลายประการ (1) การเปิดเผยข้อมูลเสริมเป็นอันตราย: ข้อมูลจุดทอร์ชันเพิ่มเติมของ SIDH จำเป็นต่อการทำงานของโพรโทคอล แต่กลับทำให้ข้อมูลรั่วไหลจนระบบถูกทำลาย นักออกแบบโพรโทคอลต้องวิเคราะห์ข้อมูลสาธารณะทุกชิ้น ไม่ใช่เฉพาะค่าหลัก (2) ประวัติผลงานไม่ใช่ข้อพิสูจน์ความปลอดภัย: การไม่พบการโจมตีเป็นเวลา 11 ปีช่วยสร้างความมั่นใจ แต่ไม่ใช่หลักประกัน ข้อพิสูจน์การเข้ารหัส ซึ่งลดรูปปัญหาไปยังปัญหายากที่นิยามไว้อย่างชัดเจน มีความน่าเชื่อถือมากกว่าการอ้างอิงอำนาจหรือการที่โครงร่างผ่านการตรวจสอบมาได้ (3) เครื่องมือทางคณิตศาสตร์ใหม่สร้างความเสี่ยง: การโจมตีของ Castryck-Decru ใช้ไอโซเจนี Richelot ของเส้นโค้งสกุล 2 ซึ่งเป็นเครื่องมือจากคณิตศาสตร์ที่ไม่เคยนำมาใช้กับการวิเคราะห์การเข้ารหัสด้วยไอโซเจนีมาก่อน นักวิเคราะห์การเข้ารหัสที่สำรวจโครงสร้างพื้นฐานใหม่ต้องพิจารณาขอบเขตทางคณิตศาสตร์ใหม่ ๆ ด้วย

แม้ SIKE จะถูกทำลายแล้ว แต่การเข้ารหัสที่อาศัยไอโซเจนียังคงดำเนินต่อไปในฐานะสาขาวิจัย ลายเซ็น SQISign (177 ไบต์ที่ระดับ 1) ยังคงเป็นลายเซ็น PQC ที่กะทัดรัดที่สุดเท่าที่ทราบ และใช้สมมติฐานความยากที่แตกต่างกัน คือปัญหาริงเอนโดมอร์ฟิซึม ซึ่งไม่ได้รับผลกระทบจากการโจมตี SIDH โพรโทคอลที่อาศัย CSIDH ใช้โครงสร้างการกระทำของกลุ่มคลาส หรือไอโซเจนีแบบสลับที่ได้ (commutative isogenies) โดยไม่มีการรั่วไหลของจุดทอร์ชัน แม้ CSIDH จะมีความท้าทายของตนเอง เช่น ช้ากว่า SIDH ในอดีต และการวิเคราะห์ความปลอดภัยควอนตัมยังดำเนินอยู่ ชุมชนไอโซเจนีมองการทำลาย SIKE เป็นประสบการณ์ที่ช่วยให้เข้าใจชัดเจนขึ้นว่าข้อมูลใดต้องถูกปกปิดในโพรโทคอลไอโซเจนี ซึ่งเป็นความรู้ที่มีคุณค่าสำหรับการออกแบบโครงร่างในอนาคต

SIDH ใช้ห่วงโซ่ไอโซเจนี 2^a และ 3^b แบบสลับกันระหว่างสองฝ่าย โดยแบ่งปันภาพของจุดทอร์ชันเสริมเพื่อให้การแลกเปลี่ยนกุญแจทำงานได้ SIKE ครอบ SIDH ด้วยการแปลง Fujisaki-Okamoto เพื่อให้มีความปลอดภัยแบบ CCA2 SIKE มีกุญแจขนาดเล็กที่สุดในบรรดาผู้สมัคร PQC ของ NIST ทั้งหมด (374 ไบต์) แต่ช้ากว่า 100-1000 เท่า หลังจากมีประวัติความปลอดภัยยาวนาน 11 ปี Castryck-Decru ก็ทำลาย SIKE ในเดือนกรกฎาคม 2022 โดยใช้ไอโซเจนี Richelot ของเส้นโค้งสกุล 2 เพื่อใช้ประโยชน์จากการรั่วไหลของจุดทอร์ชัน NIST ตัด SIKE ออกจากการพิจารณา FESTA หลีกเลี่ยงการเปิดเผยจุดทอร์ชัน SQISign ยังคงใช้สมมติฐานความยากของริงเอนโดมอร์ฟิซึม การทำลาย SIKE แสดงให้เห็นว่าข้อมูลสาธารณะเสริมต้องได้รับการวิเคราะห์อย่างรอบคอบเช่นเดียวกับค่าหลักของโพรโทคอล