โครงการเข้ารหัส 'หลังควอนตัม' แตกบนแล็ปท็อป

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

เมื่อ (หรือ if) มีคอมพิวเตอร์ควอนตัมที่ทำงานได้อย่างสมบูรณ์นั่นคือสิ่งที่อาจเกิดขึ้นได้ ด้วยเหตุนี้ ในปี 2017 สถาบันมาตรฐานและเทคโนโลยีแห่งชาติ (NIST) ของรัฐบาลสหรัฐฯ ได้เปิดตัวการแข่งขันระดับนานาชาติเพื่อค้นหาวิธีที่ดีที่สุดในการบรรลุการเข้ารหัสแบบ “หลังควอนตัม”

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

จากนั้นเมื่อวันที่ 30 กรกฎาคม นักวิจัยคู่หนึ่งเปิดเผยว่าพวกเขามี หักหนึ่งในผู้สมัครเหล่านั้น ในหนึ่งชั่วโมงบนแล็ปท็อป (ตั้งแต่นั้นมา คนอื่นๆ ก็ได้ทำให้การโจมตีเร็วขึ้น ทำลายโปรโตคอลภายในเวลาไม่กี่นาที) “การโจมตีที่น่าทึ่งและทรงพลังมาก … ค่อนข้างน่าตกใจ” กล่าว สตีเว่น กัลเบรธนักคณิตศาสตร์และนักวิทยาศาสตร์คอมพิวเตอร์ที่มหาวิทยาลัยโอ๊คแลนด์ในนิวซีแลนด์ คณิตศาสตร์ไม่เพียงแต่เป็นรากฐานของการโจมตีที่น่าประหลาดใจเท่านั้น แต่ยังลดความหลากหลาย (จำเป็นมาก) ของการเข้ารหัสหลังควอนตัม - กำจัดโปรโตคอลการเข้ารหัสที่ทำงานแตกต่างจากแผนส่วนใหญ่ในการแข่งขัน NIST

“ขี้งอนนิดหน่อย” กล่าว คริสโตเฟอร์ Peikert, นักเข้ารหัสที่มหาวิทยาลัยมิชิแกน

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

Secret Walks ท่ามกลางเส้นโค้ง

Jao และ De Feo ได้เห็นโอกาสสำหรับระบบการเข้ารหัสที่ทั้งคล้ายกันและแตกต่างอย่างเหมาะสมจากโปรโตคอลที่รู้จักกันดี โครงการนี้เรียกว่า supersingular isogeny Diffie-Hellman protocol (SIDH) ซึ่งเกี่ยวข้องกับเส้นโค้งวงรี ซึ่งเป็นวัตถุทางคณิตศาสตร์แบบเดียวกับที่ใช้ในการเข้ารหัสประเภทที่แพร่หลายที่สุดประเภทหนึ่งในปัจจุบัน แต่มันใช้ในทางที่ต่างไปจากเดิมอย่างสิ้นเชิง นอกจากนี้ยังเป็นโครงการที่กระชับที่สุดที่ NIST กำลังพิจารณา (ด้วยการแลกเปลี่ยนที่ช้ากว่าผู้สมัครรายอื่น ๆ หลายคน)

และ “ในทางคณิตศาสตร์ มันช่างงดงามจริงๆ” Jao กล่าว “ในตอนนั้น ดูเหมือนเป็นความคิดที่สวยงาม”

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

กราฟของ Alice และ Bob มีจุดเหมือนกันทั้งหมด แต่ขอบต่างกัน — ถูกกำหนดโดยไอโซเจนียีที่ต่างกัน อลิซและบ็อบเริ่มต้นจากจุดเดียวกัน และพวกเขาแต่ละคนกระโดดไปตามขอบแบบสุ่มบนกราฟของตนเอง โดยคอยติดตามเส้นทางจากจุดหนึ่งไปยังอีกจุดหนึ่ง แต่ละคนจะเผยแพร่ตำแหน่งสิ้นสุดของตน แต่เก็บเส้นทางของตนไว้เป็นความลับ

ตอนนี้พวกเขาสลับที่กัน: อลิซไปที่จุดสุดท้ายของบ็อบ และบ็อบกับของอลิซ แต่ละคนเดินซ้ำ ๆ อย่างลับๆ พวกเขาทำเช่นนี้ในลักษณะที่พวกเขาทั้งสองจะจบลงที่จุดเดียวกัน

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

แต่เพื่อให้ SIDH ทำงานได้ อลิซและบ็อบยังต้องแลกเปลี่ยนข้อมูลเพิ่มเติมเกี่ยวกับการเดินของพวกเขา ข้อมูลเพิ่มเติมนั้นคือสิ่งที่นำไปสู่ความหายนะของ SIDH

บิดใหม่บนคณิตศาสตร์เก่า

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

พวกเขาสะดุดกับบทความที่ตีพิมพ์โดยนักคณิตศาสตร์ เอิร์นส์ คานิ ในปี 1997 ในนั้นคือทฤษฎีบทที่ “ใช้ได้กับ SIDH เกือบจะในทันที” Castryck กล่าว “ฉันคิดว่าเมื่อเราตระหนักว่า … การโจมตีเกิดขึ้นเร็วมากในหนึ่งหรือสองวัน”

ในท้ายที่สุด ในการกู้คืนเส้นทางลับของอลิซ (และด้วยเหตุนี้จึงใช้กุญแจร่วมกัน) Castryck และ Decru ได้ตรวจสอบผลคูณของเส้นโค้งวงรีสองเส้น — เส้นโค้งเริ่มต้นของอลิซและเส้นโค้งที่เธอส่งไปยังบ๊อบต่อสาธารณะ การรวมกันนั้นทำให้เกิดพื้นผิวที่เรียกว่าพื้นผิวแบบอาเบเลียน จากนั้นพวกเขาก็ใช้พื้นผิวอาเบเลียนเหล่านี้ ทฤษฎีบทของคานี (ซึ่งเกี่ยวข้องกับพื้นผิวอาเบเลียนกับเส้นโค้งวงรี) และข้อมูลพิเศษที่อลิซให้บ็อบค้นพบแต่ละขั้นตอนที่อลิซทำ

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

"มันเป็นวิธีการที่ไม่คาดคิดมาก ไปที่วัตถุที่ซับซ้อนมากขึ้นเพื่อให้ได้ผลลัพธ์เกี่ยวกับวัตถุที่ง่ายกว่า" เจ้ากล่าว

“ฉันรู้สึกตื่นเต้นมากที่ได้เห็นเทคนิคนี้ถูกใช้” . กล่าว คริสติน เลาเตอร์นักคณิตศาสตร์และนักเข้ารหัสที่ Meta AI Research ซึ่งไม่เพียงแต่ช่วยพัฒนาการเข้ารหัสตามไอโซเจนีเท่านั้น แต่ยังทำงานบนพื้นผิวของอาเบเลียนอีกด้วย “น่าเสียดายที่ฉันไม่คิดว่ามันเป็นวิธีทำลาย [มัน]”

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

“มันเป็นความรู้สึกที่พิเศษ” คาสทริคกล่าว แม้ว่าจะรู้สึกหวานอมขมกลืน “เราฆ่าหนึ่งในระบบที่เราโปรดปราน”

ช่วงเวลาแห่งลุ่มน้ำ

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

เหตุใดการแข่งขันอย่าง NIST จึงมีความสำคัญมาก ในรอบก่อนหน้าของการแข่งขัน NIST Ward Beullen นักเข้ารหัสที่ IBM ได้คิดค้นการโจมตีที่ ทำลายแผนการที่เรียกว่าเรนโบว์ ในช่วงสุดสัปดาห์ เช่นเดียวกับ Castryck และ Decru เขาสามารถโจมตีได้หลังจากที่เขามองปัญหาทางคณิตศาสตร์พื้นฐานจากมุมที่ต่างออกไป และเช่นเดียวกับการโจมตี SIDH ระบบนี้ทำลายระบบที่ใช้คณิตศาสตร์ที่แตกต่างจากโปรโตคอลหลังควอนตัมที่เสนอส่วนใหญ่

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