कमजोर आरएसए कुंजी से घबराएं नहीं - बस अपने पी और क्यू का ख्याल रखें

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

एसएसएल के लिए वेबसाइटों द्वारा उपयोग की जाने वाली सभी सार्वजनिक कुंजियों का लगभग 0.4% हम दूर से समझौता करने में सक्षम थे। सभी समझौता किए गए कुंजी गलत तरीके से अनुमानित "यादृच्छिक" संख्याओं का उपयोग करके उत्पन्न किए गए थे, जिन्हें कभी-कभी दोहराया भी जाता था। कुल मिलाकर, हम दो प्रकार की समस्याओं को अलग कर सकते हैं: पूर्वानुमेय यादृच्छिकता के साथ उत्पन्न कुंजियाँ, और इन कुंजियों का एक सबसेट जिसके लिए यादृच्छिकता की कमी हमलावर को सार्वजनिक कुंजी को तुरंत कारक बनाने और एक गुप्त कुंजी प्राप्त करने की अनुमति देती है। एक गुप्त कुंजी होने पर, एक हमलावर एक वेबसाइट को स्थापित करने में सक्षम होगा और संभवतः इस वेबसाइट पर निर्देशित एन्क्रिप्ट किए गए ट्रैफ़िक को डिक्रिप्ट करने में सक्षम होगा। हमने एक कार्यक्रम विकसित किया है जो सार्वजनिक कुंजी को फ़ैसला कर सकता है और सभी मेजबानों के लिए गुप्त कुंजी जारी कर सकता है जो एक दो घंटे में इस हमले के प्रति संवेदनशील हो।

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

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

चिंता न करें, आपकी बैंक कुंजी सबसे अधिक सुरक्षित है।

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

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

हर कोई जानता है कि एम्बेडेड सिस्टम में एंट्रोपी के साथ समस्याएं हैं। हालांकि, अब तक यह स्पष्ट नहीं था कि इंटरनेट से जुड़े वास्तविक उपकरणों में ये समस्याएं आम कैसे थीं।

मुख्य पीढ़ी

वेब साइट और नेटवर्क वाले कंप्यूटर पहचान के लिए सार्वजनिक-कुंजी क्रिप्टो सिस्टम का उपयोग करते हैं। आगे हम उस प्रकार की पहचान के बारे में बात करेंगे जब क्लाइंट क्लाइंट को प्रमाणित करने के लिए प्रमाणपत्र के साथ प्रदान करता है कि वह वह है जिसे ग्राहक कनेक्ट करना चाहता है। यदि हमलावर को गुप्त कुंजी पता है, तो वह वास्तविक प्रणाली को लागू कर सकता है या ज्यादातर मामलों में क्लाइंट और सर्वर के बीच यातायात को डिक्रिप्ट कर सकता है।

आरएसए इन उद्देश्यों के लिए सबसे अधिक इस्तेमाल किया जाने वाला क्रिप्टो सिस्टम है। आरएसए क्रिप्टोसिस्टम सुरक्षा बड़ी संख्या के कारक पर बनाया गया है। RSA सार्वजनिक कुंजी में पूर्णांकों की एक जोड़ी होती है: खुला प्रतिपादक e और मॉड्यूल N , जो दो बड़े primes p और q का गुणनफल है। यदि विरोधी पी और क्यू के लिए एन वापस कर सकता है, तो वह सार्वजनिक कुंजी के साथ एन्क्रिप्ट किए गए किसी भी पाठ को भी डिक्रिप्ट कर सकता है। हालांकि, यहां तक ​​कि सबसे तेज फैक्टराइजेशन एल्गोरिदम का उपयोग करते हुए, कोई भी अभी तक 1024-बिट मॉड्यूल को फैक्ट करने में सक्षम नहीं है।

कुंजी सुरक्षा के लिए एक महत्वपूर्ण हिस्सा मुख्य पीढ़ी के चरण में यादृच्छिक इनपुट की उपस्थिति है। यदि इस इनपुट में पर्याप्त एन्ट्रापी नहीं है, तो हमलावर उन्हें अनुमान लगा सकता है, और इस प्रकार गुप्त कुंजी प्राप्त कर सकता है, बिना संख्या के दर्दनाक कारक के बिना ।

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

समस्या के दो संस्करण

यह समस्या कितनी सामान्य है, इसकी जांच करने के लिए, हमने सभी IPv4 पतों को स्कैन किया और प्रत्येक एसएसएल प्रमाणपत्र और एसएसएच कुंजी की प्रतियां एकत्र कीं। कुंजियों और प्रमाणपत्रों को एकत्रित करने में हमें एक दिन से भी कम समय लगा: सबसे पहले हमने मेजबान को खोजने के लिए मानक नैम्प का उपयोग किया, और फिर इन मेजबानों को चुनने के लिए हमने अपने अनुकूलित प्रोग्राम का उपयोग किया। कुल में, हमने 5.8 मिलियन एसएसएल सर्टिफिकेट और 10 मिलियन एसएसएच कुंजी एकत्र की।

जैसा कि हमने खोजा, एन्ट्रापी के साथ समस्याएं दो अलग-अलग प्रकार की कमजोरियों को जन्म देती हैं:

सार्वजनिक कुंजी डुप्लिकेट करें।

सभी आरएसए कुंजियों का लगभग 1% बार-बार पाया गया, सबसे अधिक संभावना है कि एंट्रोपी के साथ समस्याओं के कारण। यदि दो उपकरणों में एक ही सार्वजनिक कुंजी है, तो उनके पास भी एक ही निजी कुंजी है। वास्तव में, एक ही कुंजी वाले सभी उपकरण एक ही स्थिति में हैं - हमलावर इन उपकरणों में से सबसे कमजोर से समझौता कर सकता है और बाकी सभी को चाबी प्राप्त कर सकता है। इस समस्या के बारे में लंबे समय से जाना जाता है, लेकिन अब तक, किसी ने भी खुले साहित्य में प्रलेखित नहीं किया है कि यह कितना व्यापक है।

हमने मैन्युअल रूप से जाँच की है कि 59,000 कुंजियाँ एंट्रॉपी समस्याओं के कारण दोहराई गई थीं, जो सभी प्रमाण पत्रों में से 1% का प्रतिनिधित्व करती हैं, या सभी स्व-हस्ताक्षरित प्रमाणपत्रों का 2.6%। हमने यह भी पाया कि सभी उपकरणों के 4.6% (585,000 प्रमाणपत्र) डिफ़ॉल्ट रूप से स्थापित प्रमाण पत्र का उपयोग करते हैं। हालांकि ये उपकरण खराब एन्ट्रोपी के साथ उत्पन्न कुंजी का उपयोग नहीं करते थे, वे एक ही हमले के अधीन हैं, क्योंकि उनकी गुप्त चाबियाँ सभी मॉडलों पर समान हैं। हमने मैन्युअल रूप से इन सभी कुंजियों की जाँच की है, क्योंकि बड़ी संख्या में साइटें सही स्थितियों में डुप्लिकेट कुंजियों का उपयोग करती हैं और इसलिए उपयोगकर्ता के लिए कोई खतरा नहीं है।

महत्वपूर्ण सार्वजनिक कुंजी।

अधिक आश्चर्यजनक रूप से, हमने पाया कि एंट्रोपी समस्याएं इंटरनेट पर उपयोग किए जाने वाले सभी आरएसए कुंजियों के एक महत्वपूर्ण हिस्से को प्रभावित करने के लिए, विशेष पहुंच के बिना एक दूरस्थ हमलावर की अनुमति दे सकती हैं। हम SSL प्रमाणपत्रों में सभी RSA कुंजियों का 0.4% कारक बनाने में सक्षम थे। ऐसा करने के लिए, हमने इंटरनेट पर RSA सार्वजनिक कुंजियों के सभी युग्मों के लिए सबसे बड़े सामान्य कारक (gcd) की गणना की।

हमने 1724 सामान्य कारकों की पहचान की, जिससे हमें 24.8 एसएसएल कीज़ को फैक्टर करने की अनुमति मिली और 2422 एसएसएच कीज़ की फैक्टरिंग के लिए 301 कॉमन फैक्टर। इसका मतलब है कि हम एसएसएल के लिए उपयोग किए जाने वाले आरएसए कुंजी के लगभग 0.5% के लिए गुप्त कुंजी की गणना करने में सक्षम थे। आगे हम बताएंगे कि हमारी गणना कैसे काम करती है।

विशिष्ट संवेदनशील उपकरण

एंबेडेड सिस्टम अक्सर पहली बूट पर क्रिप्टोग्राफिक कुंजी उत्पन्न करते हैं, जब कारखाने में उनकी सभी स्थिति पूर्व निर्धारित की जा सकती है। इस अध्ययन में वर्णित एंट्रॉपी के साथ ऐसी समस्याएं क्या हो सकती हैं।

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

हम आपको सूचित करने से पहले डिवाइस के नामों को सूचीबद्ध नहीं करेंगे, लेकिन कुछ उदाहरण नीचे देखे जा सकते हैं:

फ़ायरवॉल X :
हमारे एसएसएल डेटा में 52.055 होस्ट
6.730 समान कुंजियों के साथ
12.880 फैक्टरेबल कुंजियों के साथ

उपयोगकर्ता स्तर राउटर Y :
26.952 हमारे SSL डेटा में होस्ट करता है
9.345 समान कुंजियों के साथ
4.792 फैक्टरेबल चाबियों के साथ

उद्यमों के लिए रिमोट एक्सेस समाधान जेड :
हमारे SSL डेटा में 1.648 होस्ट हैं
24 एक ही कुंजी के साथ
0 कारक कुंजी के साथ

यह कैसे हो सकता है?

यह पूरी तरह से स्पष्ट नहीं है कि एन्ट्रापी समस्याएं प्रमुख समस्याएं कैसे पैदा कर सकती हैं जो कारक के लिए आसान हैं। अब हम बताएंगे कि हमारे अधिक जिज्ञासु पाठकों के साथ ऐसा क्यों होता है।

यहाँ बताया गया है कि कैसे एक प्रोग्रामर RSA के लिए एक मॉड्यूल उत्पन्न कर सकता है:
prgn.seed(seed)
p = prgn.generate_random_prime()
q = generate_random_prime()
N = p*q
यदि एक छद्म यादृच्छिक संख्या जनरेटर के लिए अनाज का एक अनुमानित मूल्य है, तो कई अलग-अलग उपकरणों में एक ही एन मॉड्यूल हो सकता है, लेकिन हमें नहीं लगता कि एक अच्छा छद्म यादृच्छिक संख्या जनरेटर एक ही समान कारक के साथ दो अलग-अलग एन मॉड्यूल का उत्पादन कर सकता है।

हालांकि, कुछ कार्यान्वयन बढ़ती सुरक्षा के विचार के साथ, पी और पी की पीढ़ी के बीच अतिरिक्त यादृच्छिकता भी जोड़ते हैं:
prgn.seed(seed)
p = prgn.generate_random_prime()
prgn.add_randomness(bits)
q = generate_random_prime()
N = p*q
यदि पहला अनाज खराब एन्ट्रोपी के साथ उत्पन्न हुआ था, तो यह इस तथ्य को जन्म दे सकता है कि कई उपकरणों में अलग-अलग मॉड्यूल होंगे, जिसमें समान कारक p और विभिन्न कारक q शामिल होंगे । इसलिए, हम GCD: p = gcd (N1, N2) का उपयोग करके दोनों मॉड्यूल को कारक बना सकते हैं।

ओपनएसएसएल में आरएसए प्रमुख पीढ़ी निम्नानुसार काम करती है: प्राइम्स पी और क्यू उत्पन्न करने के लिए एंट्रोपी पूल से यादृच्छिक बिट्स के प्रत्येक उपयोग के बाद, सेकंड में वर्तमान समय पूल में जोड़ा जाता है। कई, लेकिन सभी नहीं, असुरक्षित कुंजियाँ OpenSSL और OpenSSH का उपयोग करके उत्पन्न की गईं, जो RSSS कुंजियाँ बनाने के लिए OpenSSL का उपयोग करती हैं।

सभी प्रमुख जोड़े के लिए जीसीडी गणना

यदि मॉड्यूल N1 और N2 के किसी भी आरएसए जोड़े में एक ही कारक है, तो आप बस दोनों मॉड्यूल को gcd का उपयोग कर सकते हैं। मेरे डेस्कटॉप कंप्यूटर पर, दो 1024 आरएसए मॉड्यूल के लिए एलसीडी गणना ऑपरेशन में लगभग 17 माइक्रो सेकंड लगते हैं।

गणित के लिए प्रवृत्त लोगों के लिए, अब मैं बताऊंगा कि कैसे हम इस विचार का उपयोग कर सकते हैं कि बड़ी संख्या में चाबियों का कारक है।

मुख्य कारक के लिए एक सरल दृष्टिकोण में आरएसए मॉड्यूल की प्रत्येक जोड़ी के लिए जीसीडी की गणना करना शामिल है। लेकिन अगर आप अनुमान लगाते हैं कि इन गणनाओं में कितना समय लगेगा, तो हमें मेरे डेस्कटॉप कंप्यूटर पर लगभग 24 साल मिलेंगे।

इसके बजाय, हम 2005 में जर्नल ऑफ़ अल्गोरिद्म में प्रकाशित डैन बुर्स्टीन के विचार का उपयोग करते हैं, जो हमें पूर्णांक संख्याओं में पूर्णांकों के एक समूह को जोड़ने की अनुमति देता है और जो हमें कुछ ही घंटों में पायथन में कुछ ही लाइनों के कार्यान्वयन के साथ हमारी गणना करने की अनुमति देगा। एल्गोरिथ्म एक बड़ा रहस्य नहीं है: बड़ी संख्या में प्रकाशित कार्यों ने एल्गोरिथ्म को बेहतर बनाने पर काम किया।

इस समस्या में मुख्य गणितीय समीक्षा यह है कि हम निम्नलिखित समीकरण का उपयोग करते हुए अन्य सभी मॉड्यूल के साथ मिलकर मॉड्यूल N1 के लिए gcd की गणना कर सकते हैं:
gcd(N1, N2 ... Nm) = gcd(N1, (N1 * N2 * ... Nm mod N1^2)/N1)
बड़ी समस्या यह है कि इस समीकरण का एक मिसकैरेज कैसे किया जाए - इस पर ध्यान दें कि इस गणना में पहला चरण 729 मिलियन अंकों वाले सभी कीज़, एक नंबर का उत्पाद खोजना है। हम एक सिंगल-कोर प्रोसेसर पर 18 घंटे में सभी एसएसएल डेटा को फैक्ट करने में सक्षम थे और चार-कोर प्रोसेसर पर 4 घंटे में एसएसएच डेटा को फैक्ट करते हैं।

निष्कर्ष

यह निश्चित रूप से एक समस्या है, लेकिन सामान्य उपयोगकर्ता की चिंता नहीं करनी चाहिए। हालांकि, एम्बेडेड सिस्टम के निर्माताओं को बहुत काम करना है, और कुछ सिस्टम एडमिनिस्ट्रेटर को चिंतित होना चाहिए। यह सुरक्षा क्षेत्र में लोगों के लिए एक जागरण कॉल के रूप में कार्य करना चाहिए, और हम सभी को याद दिलाता है कि कमजोरियां कभी-कभी सभी के सामने कैसे छिपी होती हैं।