Full-Key Recovery and Forgery from One MQOM v2.1 Signature

कल्पना कीजिए कि आप अपने एक मित्र को एक गुप्त संदेश भेजने की कोशिश कर रहे हैं, लेकिन आप एक ऐसी दुनिया में रहते हैं जहाँ भविष्य में सुपर-फास्ट कंप्यूटर (जिन्हें क्वांटम कंप्यूटर कहा जाता है) मौजूद हो सकते हैं। ये भविष्य की मशीनें उन अधिकांश तालों को तोड़ सकती हैं जिनका उपयोग आज हमारे रहस्यों को सुरक्षित रखने के लिए किया जाता है। इसकी तैयारी के लिए, वैज्ञानिक नए, अत्यंत मजबूत डिजिटल ताले बना रहे हैं जिन्हें "पोस्ट-क्वांटम सिग्नेचर" कहा जाता है। इसे ऐसे समझें जैसे कि यह एक पत्र पर लगाया गया एक विशेष प्रकार का मोम का सांचा (wax seal) है। भले ही किसी चोर के पास सामान्य तालों को तोड़ने वाला एक जादुई हथौड़ा हो, यह नया मोम का सांचा ऐसे पदार्थ से बना है जो टिके रहने के लिए डिज़ाइन किया गया है।

इस तकनीक के सबसे आशाजनक नए तालों में से एक है जिसे MQOM कहा जाता है। यह थोड़ा एक विशाल, जटिल पहेली की तरह काम करता है। एक पत्र पर हस्ताक्षर करने के लिए, भेजने वाला एक गुप्त "गवाह" (छिपी हुई कुंजी) का उपयोग करके कई चरों (variables) वाली एक गणितीय समस्या को हल करता है। यह साबित करने के लिए कि उसने पहेली को हल किया है, लेकिन रहस्य को दिखाए बिना, वह "MPC-in-the-head" नामक एक चतुर तकनीक का उपयोग करता है। कल्पना कीजिए कि भेजने वाला एक पूरी टीम होने का नाटक कर रहा है, जिसमें से प्रत्येक व्यक्ति के पास गुप्त जानकारी का एक छोटा सा हिस्सा है। वे एक खेल खेलते हैं जहाँ वे केवल इतना प्रकट करते हैं जिससे यह सिद्ध हो सके कि टीम ने मिलकर पहेली को हल किया है, लेकिन इतना नहीं कि गुप्त हिस्सों का वास्तविक पता चल सके। यदि गणित सही बैठता है, तो हस्ताक्षर वैध होता है। हमें इसकी परवाह है क्योंकि यदि इन नए तालों में कोई छिपा हुआ दरार निकलती है, तो हमारा भविष्य का डिजिटल सुरक्षा ढांचा वहां पहुँचने से पहले ही ढह सकता है।

अब, आइए इस शोध पत्र की कहानी पर बात करते हैं। जोस लुइस डेलगाडो नामक एक शोधकर्ता ने इस MQOM लॉक (वर्जन 2.1) के एक विशिष्ट संस्करण का बारीकी से अध्ययन किया और एक आश्चर्यजनक रूप से सरल तरीका खोज निकाला जिससे इसे तोड़ा जा सकता है। यह शोध पत्र तर्क देता है कि यदि किसी हमलावर को इस प्रणाली से केवल एक वैध हस्ताक्षर प्राप्त होता है, तो वह पूरी गुप्त कुंजी (secret key) का पता लगा सकता है और किसी भी संदेश के लिए नए हस्ताक्षर बना सकता है। यह बिल्कुल वैसा ही है जैसे यदि किसी चोर ने आपको एक बार अपना दरवाजा खोलते हुए देख लिया, और उस एक झलक मात्र से वह आपके घर के हर ताले को खोलने वाली मास्टर चाबी बना सकता है।

यहाँ बताया गया है कि यह "जादुвिक ट्रिक" कैसे काम करती है, एक कहानी के माध्यम से। कल्पना कीजिए कि गुप्त कुंजी एक लंबी, छिपी हुई खजाने की खोज का नक्शा (treasure map) है। MQOM प्रणाली इस नक्शे को शाखाओं से बने एक विशाल पेड़ के भीतर छिपा देती है। जब आप एक संदेश पर हस्ताक्षर करते हैं, तो प्रणाली आपको पेड़ के ऊपर एक विशिष्ट छिपे हुए पत्ते (नक्शे पर एक स्थान) तक जाने वाला रास्ता दिखाती है, लेकिन वह उस पत्ते को ढक कर रखती है। हालाँकि, यह आपको एक "सिबलिंग पाथ" (sibling path) भी देती है—यानी छिपे हुए पत्ते के बगल वाली शाखाओं की एक सूची। चूंकि यह पेड़ जिस तरह से बनाया गया है, यदि आप बगल की शाखाओं को जानते हैं, तो आप ठीक से पता लगा सकते हैं कि यदि आपको गुप्त नक्शे का एक छोटा सा 'प्रिफिक्स' (prefix) पता होता, तो वह छिपा हुआ पत्ता क्या होता।

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

एक बार जब वे इस प्रिफिक्स को पा लेते हैं, तो उनके पास पहले से मौजूद हस्ताक्षर एक "करेक्शन सफिक्स" (correction suffix) देते हैं—जो एक छोटी सी टिप्पणी है जो कहती है, "यहाँ वह शेष नक्शा है जो आपके द्वारा खोजे गए प्रिफिक्स के साथ लगेगा।" इस प्रिफिक्स और उस टिप्पणी को एक साथ जोड़कर, हमलावर पूरे गुप्त नक्शे (पूर्ण हस्ताक्षर कुंजी) को फिर से बना लेता है। इस कुंजी के साथ, वह किसी भी नए संदेश पर हस्ताक्षर कर सकता है, और सिस्टम उसे वास्तविक मानकर स्वीकार कर लेगा।

यह शोध पत्र केवल अनुमान नहीं लगाता कि यह काम करेगा; उन्होंने इस समीकरण को हल करने के लिए गणित और कंप्यूटर का काम किया ताकि यह सिद्ध हो सके। उन्होंने गणना की कि लॉक के विभिन्न शक्ति स्तरों (जिन्हें कैटेगरी I, III, और V कहा जाता है) के लिए इस समीकरण को हल करने के लिए कितनी कंप्यूटिंग शक्ति की आवश्यकता होगी। उन्होंने पाया कि तीनों श्रेणियों के लिए, आवश्यक प्रयास उस सुरक्षा सीमा से कम है जो NIST ने इन तालों के लिए निर्धारित की थी।

सबसे आसान स्तर (कैटेगरी I) के लिए, हमले में लगभग $2^{142.335112}$ ऑपरेशन लगते हैं। मध्यम स्तर (कैटेगरी III) के लिए, यह लगभग $2^{206.774558}$ या $2^{206.988685}$ ऑपरेशन लगता है, यह इस पर निर्भर करता है कि वे नक्शे के कितने हिस्से को स्कैन करते हैं। सबसे कठिन स्तर (कैटेगरी V) के लिए, इसमें लगभग $2^{271.794162}$ ऑपरेशन लगते हैं। हर मामले में, हमलावर को जितने चरणों की आवश्यकता होती है, वह संख्या उस चरणों की संख्या से कम है जो लॉक को सुरक्षित रहने के लिए आवश्यक थे।

शोधकर्ताओं ने केवल गणित तक ही सीमित नहीं रहे। उन्होंने एक कंप्यूटर प्रोग्राम बनाया जिसने वास्तव में इस हमले को चलाया। उन्होंने एक वास्तविक हस्ताक्षर लिया, समीकरण को हल किया, बाइट-दर-बाइट सटीक गुप्त कुंजी को पुनः प्राप्त किया, और फिर उस कुंजी का उपयोग करके एक नया संदेश हस्ताक्षरित किया। सिस्टम के सत्यापनकर्ता (verifier) ने नए हस्ताक्षर की जांच की और कहा, "हाँ, यह वैध है!" इसने सिद्ध कर दिया कि यह हमला वास्तविक दुनिया में काम करता है, न कि केवल कागज पर।

शोध पत्र ने यह भी देखा कि क्या कुछ सेटिंग्स को बदलने से यह समस्या ठीक हो सकती है। उन्होंने पाया कि प्रक्रिया में एक "साल्ट" (एक यादृच्छिक संख्या) जोड़ने से समीकरण में संख्याएं बदल जाती हैं लेकिन यह हमले को रोकता नहीं है। समीकरण अभी भी मौजूद है; यह बस थोड़ा अलग दिखता है। इसे वास्तव में ठीक करने के लिए, डिजाइनरों को यह बदलना होगा कि पेड़ का पथ (tree path) रहस्य से कैसे संबंधित है, पत्ते को कैसे कमिट किया जाता है, या करेक्शन नोट कैसे जेनरेट किया जाता है।

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