Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes
यह शोध पत्र एक बहुपद-समय (polynomial-time) कुंजी-रिकवरी हमले को प्रस्तुत करता है जो कॉम्बिनेटरियल और बीजगणितीय तकनीकों को जोड़कर एक समकक्ष गुप्त कुंजी को रिकवर करके एन्हांस्ड गैबिडुलिन मैट्रिक्स कोड्स (EGMC) एन्क्रिप्शन स्कीम के सभी प्रस्तावित पैरामीटर सेट्स को तोड़ देता है, जिससे दावा किए गए 128-बिट सुरक्षा स्तर को घटाकर केवल 35 बिट कर दिया जाता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि इंटरनेट एक विशाल, हलचल भरे शहर की तरह है जहाँ हर कोई गुप्त संदेश भेजने की कोशिश कर रहा है। अपने संदेशों को दूसरों की नज़रों से सुरक्षित रखने के लिए, हम डिजिटल ताले जिनका उपयोग करते हैं जिन्हें 'एन्क्रिप्शन' कहा जाता है। लंबे समय से, वैज्ञानिक इन तालों को जटिल गणितीय पहेलियों का उपयोग करके बनाने की कोशिश कर रहे हैं जो बनाने में तो आसान हैं लेकिन बिना 'चाबी' के उन्हें सुलझाना बेहद कठिन है। हाल ही में, एक नया प्रकार का ताला प्रस्तावित किया गया जिसमें संख्याओं के ग्रिड और "रैंक" (जो कि केवल एक फैंसी तरीका है यह मापने का कि ग्रिड के अंदर वास्तव में कितनी जानकारी भरी हुई है) से संबंधित एक विशेष प्रकार के गणित का उपयोग किया गया है। इसके रचनाकारों ने सोचा कि उन्होंने इसमें एक प्रकार का "शोर" (noise)—जैसे रेडियो पर आने वाली खरखराहट—जोड़ दिया है ताकि ताले के असली आकार को छिपाया जा सके, जिससे यह किसी भी घुसपैठिये के लिए एक यादृच्छिक (random) कचरे जैसा दिखे। उन्होंने दावा किया कि यह नया डिज़ाइन इतना सुरक्षित था कि एक सुपर-फास्ट क्वांटम कंप्यूटर भी इसे नहीं तोड़ पाएगा, और उन्होंने वादा किया कि यह छोटा और कुशल होगा, जो भविष्य के सुरक्षित संचार के लिए एकदम सही है।
हालाँकि, ठीक वैसे ही जैसे एक जादूगर का खेल एक विशिष्ट हाथ की सफाई पर निर्भर करता है, इस नए ताले में एक छिपा हुआ दोष था। थाई हंग ले (Thai Hung Le) नामक एक शोधकर्ता ने पाया कि वह "शोर" वास्तव में उस गुप्त आकार को उतनी अच्छी तरह से नहीं छिपा पा रहा था जितना कि सबको लगता था। एक चतुर अनुमान और बीजगणितीय (algebraic) जासूसी के मिश्रण का उपयोग करके, शोधकर्ता ने उस शोर की परतों को हटाने और उसके नीचे छिपी मूल संरचना को प्रकट करने का तरीका खोज निकाला। यह बिल्कुल वैसा ही है जैसे किसी ने एक गुप्त ब्लूप्रिंट के साथ ताश का घर बनाया हो, उसे धुंध से ढक दिया हो, और फिर यह महसूस किया हो कि यदि आप धुंध को सही कोण से देखें, तो ब्लूप्रिंट अभी भी धुंधला दिखाई दे रहा है। यह खोज एक बड़ी बात है क्योंकि इसका मतलब है कि नए ताले उतने सुरक्षित नहीं हैं जितना विज्ञापन किया गया था, और जो लोग इनका उपयोग हमारे डेटा की सुरक्षा के लिए करने वाले हैं, उन्हें अपने ब्लूप्रिंट पर फिर से विचार करने की आवश्यकता है।
शोध पत्र की बड़ी खोज
इस शोध पत्र में, थाई हंग ले "एन्हांस्ड गैबुलिडिन मैट्रिक्स कोड" (EGMC) एन्क्रिप्शन स्कीम्स को तोड़ने का एक नया तरीका प्रस्तुत करते हैं। ये स्कीम्स हाल ही में एक तरीके के रूप में पेश की गई थीं जिससे बहुत छोटे, कुशल एन्क्रिप्शन कीज़ (keys) बनाई जा सकें जो भविष्य के क्वांटम कंप्यूटरों के हमलों से बच सकें। इन स्कीम्स की सुरक्षा इस विचार पर टिकी थी कि यदि आप संख्याओं के एक विशेष, संरचित ग्रिड को लें और उसमें यादृच्छिक पंक्तियाँ (rows) और कॉलम जोड़ दें (जिसे "शोर" कहा जाता है), तो यह पहचानना असंभव हो जाएगा कि वास्तविक कोड और पूरी तरह से यादृच्छिक कचरे के बीच क्या अंतर है।
लेखक दिखाते हैं कि यह धारणा गलत है। शोर को हटाने के हर संभव तरीके का अनुमान लगाने (जिसमें बहुत समय लगेगा) के बजाय, यह शोध पत्र एक "हाइब्रिड" हमले का परिचय देता है। कल्पना कीजिए कि आप एक विशाल, बिखरे हुए मोज़ेक (mosaic) में एक विशिष्ट पैटर्न खोजने की कोशिश कर रहे हैं। पुराना तरीका हर एक टाइल की स्थिति का अनुमान लगाना था। यह नया तरीका अधिक स्मार्ट है: यह केवल टाइल्स की एक पंक्ति की स्थिति का अनुमान लगाता है, और फिर गणित का उपयोग करके तुरंत पता लगा लेता है कि बाकी टाइल्स कहाँ होनी चाहिए।
शोध पत्र दो मुख्य तरीकों का विवरण देता है कि यह कैसे किया जाता है:
- कॉलम का अनुमान लगाना: हमलावर यह अनुमान लगाता है कि ग्रिड के कॉलम को कैसे बदला (shuffle) गया था और फिर बीजगणित (algebra) का उपयोग करके यह पता लगाता है कि पंक्तियों (rows) को कैसे बदला गया था।
- पंक्तियों का अनुमान लगाना: हमलावर यह अनुमान लगाता है कि पंक्तियों को कैसे बदला गया था और फिर कॉलम के बारे में हल निकालता है।
एक बार जब हमलावर बदलाव (shuffling) को समझ लेता है, तो वे यादृच्छिक शोर को हटा सकते हैं और मूल, छिपी हुई संरचना को प्रकट कर सकते हैं। यह शोध पत्र सिद्ध करता है कि यह संरचना एक "गैबुलिडिन कोड" (Gabidulin code) है, जो गणित की एक ऐसी पहेली है जिसे एक बार गुप्त पैटर्न पता चलने के बाद हल करना काफी आसान है।
यह शोध पत्र वास्तव में क्या तोड़ता है
लेखक केवल एक छोटी सी दरार नहीं ढूंढते; वे पूरी खिड़की ही तोड़ देते हैं। शोध पत्र प्रदर्शित करता है कि यह हमला EGMC एन्क्रिप्शन स्कीम्स के प्रस्तावित सभी 16 पैरामीटर सेटों के खिलाफ काम करता है। इसका मतलब है कि इस्तेमाल के लिए सुझाया गया हर संस्करण अब टूटा हुआ माना जाता है।
आपको इसकी प्रभावशीलता का अंदाजा देने के लिए, शोध पत्र संख्याओं के एक विशिष्ट सेट को देखता है जो 128-बिट सुरक्षा (सुरक्षा का एक मानक स्तर) प्रदान करने वाला था। लेखक दिखाते हैं कि उनका हमला इस सुरक्षा स्तर को घटाकर मात्र 35 बिट्स कर देता है। एन्क्रिप्शन की दुनिया में, यह एक मिलियन-अंकों वाले कॉम्बिनेशन वाले तिजोरी से एक ऐसे ताले तक जाने जैसा है जिसे एक बच्चा कुछ ही सेकंड में खोल सकता है।
शोध पत्र इस शक्ति का एक ठोस उदाहरण प्रदान करता है: अपने तरीके का उपयोग करके, शोधकर्ता उस 128-बिट सुरक्षा स्तर की गुप्त कुंजी (secret key) को 10 मिनट से भी कम समय में प्राप्त करने में सक्षम थे। यह केवल एक सैद्धांतिक विचार नहीं था; उन्होंने इसे करने के लिए वास्तव में एक कंप्यूटर प्रोग्राम बनाया।
यह शोध पत्र क्या खारिज करता है
यह ध्यान रखना महत्वपूर्ण है कि यह शोध पत्र क्या काम नहीं करता है। लेखक बताते हैं कि इन कोडों को तोड़ने के पिछले प्रयास "कॉम्बिनेटोरियल" (combinatorial) विधियों पर निर्भर थे, जिनमें एक ही समय में पंक्ति और कॉलम दोनों के बदलावों का अनुमान लगाया जाता था। शोध पत्र तर्क देता है कि उनका नया "हाइब्रिड" दृष्टिकोण की तुलना में पुराना तरीका बहुत धीमा और अक्षम है।
इसके अलावा, शोध पत्र इस विचार के विरुद्ध तर्क देता है कि केवल पैरामीटर्स को बड़ा बनाना (अधिक शोर जोड़ना) सभी मामलों में समस्या को ठीक कर देगा। लेखक दिखाते हैं कि इन कोडों के कुछ प्रकारों के लिए—विशेष रूप से जब शोर का एक कारक (या तो अतिरिक्त पंक्तियों की संख्या या अतिरिक्त कॉलम की संख्या) शून्य हो—तो हमला इतना तेज़ हो जाता है कि यह "पॉलीनोमियल टाइम" (polynomial time) में चलता है। इसका अर्थ यह है कि उन विशिष्ट मामलों में आप ताले का आकार चाहे कितना भी बढ़ा दें, हमला फिर भी इसे तोड़ने के लिए पर्याप्त तेज़ होगा। शोध पत्र सुझाव देता है कि इसे संभावित रूप से ठीक करने का एकमात्र तरीका मूल डिज़ाइन को बदलना होगा ताकि दोनों शोर कारक गैर-शून्य हों और हमले को रोकने के लिए पर्याप्त बड़े हों, लेकिन लेखक चेतावनी देते हैं कि इससे कीज़ और संदेश बहुत बड़े और अनुपयोगी हो सकते हैं।
वे कितने आश्वस्त हैं?
शोध पत्र अपने परिणामों में बहुत आश्वस्त है। लेखक ने केवल अनुमान नहीं लगाया; उन्होंने इस हमले के काम करने के तरीके का पूर्ण गणितीय प्रमाण प्रदान किया और इसे एक कामकाजी कंप्यूटर कार्यान्वयन (implementation) के साथ पुख्ता किया। वे स्पष्ट रूप से कहते हैं कि उनका हमला योजना के सभी प्रस्तावित संस्करणों को तोड़ देता है। वे अपने परिणामों की पिछले हमलों से भी तुलना करते हैं, जिससे पता चलता है कि उनका तरीका काफी तेज़ और अधिक शक्तिशाली है। शोध पत्र निष्कर्ष निकालता है कि EGMC एन्क्रिप्शन स्कीम्स अब उपयोग के लिए सुरक्षित नहीं हैं, और सुरक्षा समुदाय को अन्य डिज़ाइनों की ओर बढ़ना चाहिए।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।