'पोस्ट-क्वांटम' क्रिप्टोग्राफी योजना एक लैपटॉप पर टूट गई है

यदि आज के क्रिप्टोग्राफी प्रोटोकॉल विफल हो जाते हैं, तो ऑनलाइन कनेक्शन सुरक्षित करना असंभव होगा - गोपनीय संदेश भेजना, सुरक्षित वित्तीय लेनदेन करना, या डेटा प्रमाणित करना। कोई भी कुछ भी एक्सेस कर सकता था; कोई भी किसी के होने का दिखावा कर सकता है। डिजिटल अर्थव्यवस्था चरमरा जाएगी।

कब (या if) एक पूरी तरह कार्यात्मक क्वांटम कंप्यूटर उपलब्ध हो जाता है, ठीक यही हो सकता है। नतीजतन, 2017 में अमेरिकी सरकार के राष्ट्रीय मानक और प्रौद्योगिकी संस्थान (एनआईएसटी) ने "पोस्ट-क्वांटम" क्रिप्टोग्राफी प्राप्त करने के सर्वोत्तम तरीकों को खोजने के लिए एक अंतरराष्ट्रीय प्रतियोगिता शुरू की।

पिछले महीने, एजेंसी ने विजेताओं के अपने पहले समूह का चयन किया: चार प्रोटोकॉल जिन्हें, कुछ संशोधन के साथ, क्वांटम शील्ड के रूप में तैनात किया जाएगा। इसने चार अतिरिक्त उम्मीदवारों की भी घोषणा की जो अभी भी विचाराधीन हैं।

फिर 30 जुलाई को, शोधकर्ताओं के एक जोड़े ने खुलासा किया कि उनके पास था उन उम्मीदवारों में से एक को तोड़ा एक घंटे में लैपटॉप पर। (तब से, अन्य लोगों ने कुछ ही मिनटों में प्रोटोकॉल को तोड़ते हुए, हमले को और भी तेज कर दिया है।) "एक हमला जो इतना नाटकीय और शक्तिशाली है ... काफी सदमा था," ने कहा स्टीवन गैलब्रेथ, न्यूजीलैंड में ऑकलैंड विश्वविद्यालय में गणितज्ञ और कंप्यूटर वैज्ञानिक। न केवल हमले में अंतर्निहित गणित आश्चर्यजनक था, बल्कि इसने पोस्ट-क्वांटम क्रिप्टोग्राफी की (अत्यधिक आवश्यक) विविधता को कम कर दिया - एक एन्क्रिप्शन प्रोटोकॉल को समाप्त कर दिया जो एनआईएसटी प्रतियोगिता में अधिकांश योजनाओं से बहुत अलग तरीके से काम करता था।

"यह एक bummer का एक सा है," ने कहा क्रिस्टोफर पेइकर्टो, मिशिगन विश्वविद्यालय में एक क्रिप्टोग्राफर।

परिणामों ने पोस्ट-क्वांटम क्रिप्टोग्राफी समुदाय को हिलाकर रख दिया है और प्रोत्साहित किया है। हिल गया, क्योंकि इस हमले (और प्रतियोगिता के पिछले दौर से एक और) ने अचानक एक डिजिटल स्टील के दरवाजे की तरह गीले अखबार में बदल दिया। "यह नीले रंग से निकला," ने कहा डस्टिन मूडी, NIST मानकीकरण प्रयास का नेतृत्व करने वाले गणितज्ञों में से एक। लेकिन अगर एक क्रिप्टोग्राफिक योजना टूटने वाली है, तो यह सबसे अच्छा है अगर यह जंगली में इस्तेमाल होने से पहले अच्छी तरह से हो। "कई भावनाएं हैं जो आपके माध्यम से जाती हैं," कहा डेविड जोओ, कनाडा में वाटरलू विश्वविद्यालय में एक गणितज्ञ, जो आईबीएम शोधकर्ता के साथ लुका डी फीओ, 2011 में प्रोटोकॉल का प्रस्ताव रखा। निश्चित रूप से आश्चर्य और निराशा उनमें से हैं। "लेकिन यह भी," जाओ ने कहा, "कम से कम अब यह टूट गया है।"

घटता के बीच गुप्त चलता है

Jao और De Feo ने एक क्रिप्टोग्राफ़िक प्रणाली के लिए एक अवसर देखा था जो प्रसिद्ध प्रोटोकॉल के समान और उपयुक्त रूप से अलग था। उनकी योजना, जिसे सुपरसिंगुलर आइसोजेनी डिफी-हेलमैन प्रोटोकॉल (एसआईडीएच) कहा जाता है, अण्डाकार वक्रों से निपटता है - वही गणितीय वस्तुएं जो आज तैनात सबसे व्यापक प्रकार की क्रिप्टोग्राफी में से एक में उपयोग की जाती हैं। लेकिन इसने उन्हें पूरी तरह से अलग तरीके से इस्तेमाल किया। यह सबसे कॉम्पैक्ट योजना भी थी जिस पर एनआईएसटी विचार कर रहा था (व्यापार के साथ कि यह अन्य उम्मीदवारों की तुलना में धीमी थी)।

और "गणितीय रूप से, यह वास्तव में सुरुचिपूर्ण है," जाओ ने कहा। "उस समय, यह एक सुंदर विचार की तरह लग रहा था।"

मान लीजिए दो पक्ष, ऐलिस और बॉब, एक संभावित हमलावर की चौकस निगाहों के तहत गुप्त रूप से एक संदेश का आदान-प्रदान करना चाहते हैं। वे किनारों से जुड़े बिंदुओं के संग्रह से शुरू होते हैं जिन्हें ग्राफ़ कहा जाता है। प्रत्येक बिंदु एक अलग अण्डाकार वक्र का प्रतिनिधित्व करता है। यदि आप एक विशेष तरीके से एक वक्र को दूसरे में बदल सकते हैं (एक आइसोजेनी नामक मानचित्र के माध्यम से), बिंदुओं की जोड़ी के बीच एक किनारा बनाएं। परिणामी ग्राफ बहुत बड़ा है और इसमें खो जाना आसान है: यदि आप इसके किनारों के साथ अपेक्षाकृत कम चलते हैं, तो आप कहीं ऐसा समाप्त हो जाएंगे जो पूरी तरह से यादृच्छिक दिखता है।

ऐलिस और बॉब के रेखांकन में सभी समान बिंदु हैं, लेकिन किनारे अलग-अलग हैं - वे अलग-अलग आइसोजेनी द्वारा परिभाषित हैं। ऐलिस और बॉब एक ​​ही बिंदु पर शुरू करते हैं, और वे प्रत्येक अपने स्वयं के ग्राफ पर यादृच्छिक किनारों के साथ कूदते हैं, एक बिंदु से दूसरे तक अपने पथ का ट्रैक रखते हैं। प्रत्येक तब अपना अंतिम स्थान प्रकाशित करता है लेकिन अपना रास्ता गुप्त रखता है।

अब वे स्थानों की अदला-बदली करते हैं: ऐलिस बॉब के अंतिम बिंदु पर जाता है, और बॉब से ऐलिस तक। प्रत्येक अपनी गुप्त चाल को दोहराता है। वे इसे इस तरह से करते हैं कि वे दोनों एक ही बिंदु पर समाप्त हो जाएंगे।

यह स्थान गुप्त रूप से पाया गया है, इसलिए ऐलिस और बॉब इसे अपनी गुप्त कुंजी के रूप में उपयोग कर सकते हैं - ऐसी जानकारी जो उन्हें एक दूसरे के संदेशों को सुरक्षित रूप से एन्क्रिप्ट और डिक्रिप्ट करने की अनुमति देती है। भले ही कोई हमलावर ऐलिस और बॉब द्वारा एक दूसरे को भेजे जाने वाले मध्यवर्ती बिंदुओं को देखता है, वे ऐलिस या बॉब की गुप्त चाल को नहीं जानते हैं, इसलिए वे उस अंतिम समापन बिंदु का पता नहीं लगा सकते हैं।

लेकिन SIDH को काम करने के लिए, ऐलिस और बॉब को अपने चलने के बारे में कुछ अतिरिक्त जानकारी का आदान-प्रदान करने की भी आवश्यकता है। वह अतिरिक्त जानकारी ही SIDH के पतन का कारण बनी।

पुराने गणित पर एक नया मोड़

थॉमस डेक्रूस SIDH को तोड़ने के लिए तैयार नहीं था। वह इस पर निर्माण करने की कोशिश कर रहा था - एक अन्य प्रकार की क्रिप्टोग्राफी को बढ़ाने के तरीके को सामान्य बनाने के लिए। यह काम नहीं किया, लेकिन इसने एक विचार को जन्म दिया: उनका दृष्टिकोण SIDH पर हमला करने के लिए उपयोगी हो सकता है। और इसलिए वह संपर्क किया राउटर कास्त्रीक, बेल्जियम में कैथोलिक यूनिवर्सिटी ऑफ़ ल्यूवेन में उनके सहयोगी और उनके पूर्व डॉक्टरेट सलाहकारों में से एक, और दोनों ने प्रासंगिक साहित्य में गोता लगाया।

वे गणितज्ञ द्वारा प्रकाशित एक पेपर में ठोकर खा गए अर्न्स्ट कनीक 1997 में। इसमें एक प्रमेय था कि "एसआईडीएच पर लगभग तुरंत लागू था," कैस्ट्रीक ने कहा। "मुझे लगता है कि एक बार जब हमने महसूस किया कि ... हमला एक या दो दिनों में बहुत जल्दी हो गया।"

अंततः, ऐलिस के गुप्त वॉक (और इसलिए साझा कुंजी) को पुनर्प्राप्त करने के लिए, कैस्ट्रीक और डेक्रू ने दो अण्डाकार वक्रों के उत्पाद की जांच की - ऐलिस का प्रारंभिक वक्र और वह वक्र जिसे उसने सार्वजनिक रूप से बॉब को भेजा था। वह संयोजन एक प्रकार की सतह का निर्माण करता है जिसे एबेलियन सतह कहा जाता है। फिर उन्होंने इन एबेलियन सतहों का उपयोग किया, कानी का प्रमेय (जो एबेलियन सतहों को अण्डाकार वक्रों से संबंधित करता है), और ऐलिस द्वारा उठाए गए प्रत्येक चरण को उजागर करने के लिए ऐलिस ने बॉब को अतिरिक्त जानकारी दी।

"यह लगभग एक होमिंग सिग्नल की तरह है जो आपको [कुछ एबेलियन सतहों] पर लॉक करने देता है," जाओ ने कहा। "और वह संकेत आपको बताता है कि सही [गुप्त चलना] खोजने के लिए आपको अगला कदम उठाने के लिए इस तरह से जाना चाहिए।" जो उन्हें सीधे ऐलिस और बॉब की साझा कुंजी तक ले गया।

"यह एक बहुत ही अप्रत्याशित दृष्टिकोण है, सरल वस्तु के बारे में परिणाम प्राप्त करने के लिए अधिक जटिल वस्तुओं पर जा रहा है," जाओ ने कहा।

"मैं इस तकनीक का उपयोग करते हुए देखने के लिए बहुत उत्साहित था," ने कहा क्रिस्टिन लॉटरमेटा एआई रिसर्च में गणितज्ञ और क्रिप्टोग्राफर, जिन्होंने न केवल आइसोजीनी-आधारित क्रिप्टोग्राफी विकसित करने में मदद की, बल्कि एबेलियन सतहों पर भी काम किया है। "इसे तोड़ने के तरीके के रूप में इसके बारे में नहीं सोचने के लिए मुझ पर शर्म आती है।"

कास्त्रिक और डेक्रू के हमले ने 62 मिनट में एसआईडीएच प्रोटोकॉल के सबसे कम सुरक्षा संस्करण को तोड़ दिया और केवल एक दिन के भीतर उच्चतम सुरक्षा स्तर को तोड़ दिया। फिर, कुछ ही समय बाद, एक अन्य विशेषज्ञ ने हमले में बदलाव किया ताकि कम सुरक्षा वाले संस्करण को तोड़ने में केवल 10 मिनट लगे और उच्च सुरक्षा वाले संस्करण को तोड़ने में कुछ घंटे लगे। अधिक सामान्य हमले पिछले कुछ हफ्तों में पोस्ट किया गया यह संभावना नहीं है कि SIDH को बचाया जा सकता है।

"यह एक विशेष एहसास था," कास्त्रिक ने कहा, हालांकि एक बिटरवेट। "हमने अपने पसंदीदा सिस्टम में से एक को मार डाला।"

एक वाटरशेड पल

यह गारंटी देना असंभव है कि कोई सिस्टम बिना शर्त सुरक्षित है। इसके बजाय, क्रिप्टोग्राफर पर्याप्त समय बीतने पर भरोसा करते हैं और पर्याप्त लोग आत्मविश्वास महसूस करने के लिए समस्या को तोड़ने की कोशिश कर रहे हैं। "इसका मतलब यह नहीं है कि आप कल नहीं उठेंगे और पाएंगे कि किसी ने इसे करने के लिए एक नया एल्गोरिदम ढूंढ लिया है," ने कहा जेफरी हॉफस्टीन, ब्राउन विश्वविद्यालय में गणितज्ञ।

इसलिए एनआईएसटी जैसी प्रतियोगिताएं इतनी महत्वपूर्ण क्यों हैं। एनआईएसटी प्रतियोगिता के पिछले दौर में, आईबीएम के एक क्रिप्टोग्राफर वार्ड बेउलेंस ने एक हमले की योजना बनाई थी इंद्रधनुष नामक एक योजना को तोड़ दिया एक सप्ताहांत में। कैस्त्रिक और डेक्रू की तरह, वह अंतर्निहित गणितीय समस्या को एक अलग कोण से देखने के बाद ही अपने हमले का मंचन करने में सक्षम था। और SIDH पर हमले की तरह, इसने एक ऐसी प्रणाली को तोड़ दिया जो अधिकांश प्रस्तावित पोस्ट-क्वांटम प्रोटोकॉल की तुलना में विभिन्न गणित पर निर्भर थी।

"हालिया हमले एक वाटरशेड क्षण थे," ने कहा थॉमस पर्स्टो, स्टार्टअप PQShield में एक क्रिप्टोग्राफर। वे इस बात पर प्रकाश डालते हैं कि पोस्ट-क्वांटम क्रिप्टोग्राफी कितनी कठिन है, और विभिन्न प्रणालियों की सुरक्षा का अध्ययन करने के लिए कितने विश्लेषण की आवश्यकता हो सकती है। "एक गणितीय वस्तु में एक परिप्रेक्ष्य में कोई स्पष्ट संरचना नहीं हो सकती है, और दूसरे में एक शोषक संरचना हो सकती है," उन्होंने कहा। "कठिन हिस्सा सही नए दृष्टिकोण की पहचान करना है।"