Correlation attack
सहसंबंध आक्रमण धारा साइफरों को तोड़ने के लिए क्रिप्टोग्राफिक ज्ञात-पाठ हमलों का एक वर्ग है जिनकी मुख्य धाराएं बूलियन फ़ंक्शन का उपयोग करके कई रैखिक-फीडबैक शिफ्ट रजिस्टरों (एल. एफ. एस. आर.) के आउटपुट को मिलाकर उत्पन्न की जाती हैं। सहसंबंध आक्रमण एक सांख्यिकीय कमजोरी का फायदा उठाते हैं जो मुख्य धारा के लिए चुने गए विशिष्ट बूलियन कार्य से उत्पन्न होती है। जबकि कुछ बूलियन कार्य सहसंबंध हमलों के प्रति संवेदनशील होते हैं, ऐसे कार्यों का उपयोग करके उत्पन्न स्ट्रीम साइफर स्वाभाविक रूप से असुरक्षित नहीं होते हैं। व्याख्या सहसंबंध आक्रमण तब संभव हो जाते हैं जब कीस्ट्रीम जनरेटर में एक व्यक्तिगत एल. एफ. एस. आर. की उत्पादन अवस्था और सभी एल. एफ. एस. आर. की उत्पादन अवस्थाओं को जोड़ने वाले बूलियन फलन के उत्पादन के बीच एक महत्वपूर्ण सहसंबंध मौजूद होता है। इन हमलों को मुख्य धारा के आंशिक ज्ञान के साथ संयोजन में नियोजित किया जाता है, जो सादे पाठ के आंशिक ज्ञान से प्राप्त होता है। फिर दोनों की तुलना एक एक्सओआर लॉजिक गेट का उपयोग करके की जाती है। यह भेद्यता एक हमलावर को व्यक्तिगत एल. एफ. एस. आर. और शेष प्रणाली के लिए अलग-अलग कुंजी को क्रूर-बल देने की अनुमति देती है। उदाहरण के लिए, एक कीस्ट्रीम जनरेटर में जहां चार 8-बिट एल. एफ. एस. आर. को कीस्ट्रीम का उत्पादन करने के लिए जोड़ा जाता है, और यदि रजिस्टरों में से एक बूलियन फ़ंक्शन आउटपुट से सहसंबद्ध है, तो पहले इसे क्रूर बल देना संभव हो जाता है, उसके बाद शेष तीन एल. एफ. एस. आर.। नतीजतन, कुल हमले की जटिलता 28 + 224 हो जाती है। जटिलता 232 के साथ, पूरी प्रणाली पर एक क्रूर-बल हमले को शुरू करने की लागत की तुलना में, यह 256 से कम के हमले के प्रयास बचत कारक का प्रतिनिधित्व करता है। यदि एक दूसरा रजिस्टर फ़ंक्शन के साथ सहसंबद्ध है, तो प्रक्रिया को दोहराया जा सकता है और 65028 से कम के प्रयास बचत कारक के लिए हमले की जटिलता को 28 + 28 + 216 तक कम किया जा सकता है। उदाहरण गेफ जनरेटर एक उदाहरण गेफ जनरेटर है, जिसमें तीन एल. एफ. एस. आर. होते हैंः एल. एफ. एस. आर.-1, एल. एफ. एस. आर.-2 और एल. एफ. एस. आर.-3। मान लीजिए कि इन रजिस्टरों को क्रमशःः,, और के रूप में दर्शाया जाए। फिर, जनरेटर आउटपुट प्रदान करने के लिए तीन रजिस्टरों को मिलाकर बूलियन फ़ंक्शन (यानी। (और) XOR (और नहीं))। तीन रजिस्टरों के आउटपुट के लिए 23 = 8 संभावित मान हैं, और उनमें से प्रत्येक के लिए इस संयोजन फ़ंक्शन का मूल्य नीचे दी गई तालिका में दिखाया गया हैः तीसरे रजिस्टर के आउटपुट पर विचार करें। ऊपर दी गई तालिका से पता चलता है कि 8 संभावित आउटपुट में से 6 जनरेटर आउटपुट के संबंधित मूल्य के बराबर हैं। सभी संभावित मामलों में से 75 प्रतिशत में, इस प्रकार एल. एफ. एस. आर.-3 जनरेटर के साथ 'सहसंबद्ध' है। यह एक कमजोरी है जिसका उपयोग निम्नानुसार किया जा सकता हैः एक सादे पाठ के सिफर पाठ पर एक अवरोधन किया जा सकता है जिसे एक स्ट्रीम सिफर द्वारा एन्क्रिप्ट किया गया है जिसमें एक गेफ जनरेटर का उपयोग अपने कीस्ट्रीम जनरेटर के रूप में किया गया है, अर्थात। के लिए, समय पर एल. एफ. एस. आर.-1 का उत्पादन कहाँ है, आदि। यह भी संभव है कि सादे पाठ का हिस्सा, जैसे। , प्लेनटेक्स्ट के पहले 32 बिट्स (पाठ के 4 ASCII वर्णों के अनुरूप)। यह पूरी तरह से असंभव नहीं है क्योंकि सादा पाठ एक वैध एक्स. एम. एल. फ़ाइल है, उदाहरण के लिए, पहले 4 ए. एस. सी. आई. आई. वर्ण "<एक्स. एम. एल". होने चाहिए। इसी तरह, कई फ़ाइल प्रारूपों या नेटवर्क प्रोटोकॉल में बहुत ही मानक हेडर या फुटर होते हैं। अवरोधित और हमारे ज्ञात/अनुमान को देखते हुए, हम आसानी से दोनों को एक साथ एक्सओआर-आईएनजी द्वारा पा सकते हैं। इससे जनरेटर आउटपुट के लगातार 32 बिट्स का निर्धारण करना आसान हो जाता है। यह एल. एफ. एस. आर.-3 के लिए संभावित कुंजी (प्रारंभिक मान) के स्थान की एक क्रूर-बल खोज को सक्षम बनाता है (यह मानते हुए कि हम एल. एफ. एस. आर.-3 के टैप किए गए बिट्स को जानते हैं, एक धारणा जो केर्कहॉफ्स के सिद्धांत के अनुरूप है)। कुंजी स्थान में दी गई किसी भी कुंजी के लिए, हम जल्दी से एल. एफ. एस. आर.-3 के आउटपुट के पहले 32 बिट्स उत्पन्न कर सकते हैं और इनकी तुलना पूरे जनरेटर के आउटपुट के हमारे पुनर्प्राप्त 32 बिट्स से कर सकते हैं। क्योंकि हमने पहले स्थापित किया है कि एल. एफ. एस. आर.-3 के उत्पादन और जनरेटर के बीच 75 प्रतिशत सहसंबंध है, हम जानते हैं कि हमने एल. एफ. एस. आर.-3 के लिए कुंजी का सही अनुमान लगाया है यदि एल. एफ. एस. आर.-3 उत्पादन के पहले 32 बिट्स में से लगभग 24 जनरेटर उत्पादन के संबंधित बिट्स के साथ मेल खाएंगे। यदि हमने गलत अनुमान लगाया है, तो हमें इन दो अनुक्रमों के पहले 32 बिट्स में से लगभग आधे या 16 के मिलान की उम्मीद करनी चाहिए। इस प्रकार हम एल. एफ. एस. आर.-3 की कुंजी को एल. एफ. एस. आर.-1 और एल. एफ. एस. आर.-2 की कुंजी से स्वतंत्र रूप से पुनर्प्राप्त कर सकते हैं। इस स्तर पर हमने एक एकल एल. एफ. एस. आर. और फिर 2 एल. एफ. एस. आर. की प्रणाली को मजबूर करने की समस्या के लिए 3 एल. एफ. एस. आर. की प्रणाली को मजबूर करने की समस्या को कम कर दिया है। यहाँ सहेजे गए प्रयास की मात्रा एल. एफ. एस. आर. की लंबाई पर निर्भर करती है। यथार्थवादी मूल्यों के लिए, यह एक बहुत बड़ी बचत है और ब्रूट-फोर्स हमलों को बहुत व्यावहारिक बना सकती है। ऊपर दी गई तालिका में देखें कि यह भी 8 में से 6 बार जनरेटर उत्पादन से सहमत है, फिर से जनरेटर उत्पादन और जनरेटर उत्पादन के बीच 75 प्रतिशत सहसंबंध का सहसंबंध है। हम एल. एफ. एस. आर.-1 और एल. एफ. एस. आर.-3 की कुंजी से स्वतंत्र रूप से एल. एफ. एस. आर.-2 के खिलाफ एक क्रूर बल हमला शुरू कर सकते हैं, जिससे केवल एल. एफ. एस. आर.-1 अखंड रह जाता है। इस प्रकार, हम 3 पूरी तरह से स्वतंत्र एल. एफ. एस. आर. को क्रूर बल देने के लिए आवश्यक प्रयास के साथ गेफ जनरेटर को तोड़ने में सक्षम हैं। इसका मतलब है कि गेफ जनरेटर एक बहुत ही कमजोर जनरेटर है और इसका उपयोग कभी भी स्ट्रीम सिफर कीस्ट्रीम उत्पन्न करने के लिए नहीं किया जाना चाहिए। ऊपर की तालिका से ध्यान दें कि जनरेटर आउटपुट 8 में से 4 गुना-50 प्रतिशत सहसंबंध से सहमत है। हम इसका उपयोग दूसरों से स्वतंत्र रूप से एल. एफ. एस. आर.-1 को क्रूर बल देने के लिए नहीं कर सकते हैंः सही कुंजी से आउटपुट प्राप्त होगा जो 50 प्रतिशत समय जनरेटर आउटपुट से सहमत होगा, लेकिन औसतन एक गलत कुंजी होगी। यह सुरक्षा के दृष्टिकोण से आदर्श स्थिति का प्रतिनिधित्व करता है-संयोजन कार्य को चुना जाना चाहिए ताकि प्रत्येक चर और संयोजन कार्य के उत्पादन के बीच सहसंबंध यथासंभव 50 प्रतिशत के करीब हो। व्यवहार में, एक ऐसे कार्य को खोजना मुश्किल हो सकता है जो अन्य डिज़ाइन मानदंडों, जैसे, अवधि की लंबाई का त्याग किए बिना इसे प्राप्त करता है, इसलिए एक समझौता आवश्यक हो सकता है। हमले की सांख्यिकीय प्रकृति को स्पष्ट करना जबकि उपरोक्त उदाहरण सहसंबंध हमलों के पीछे की अपेक्षाकृत सरल अवधारणाओं को अच्छी तरह से दर्शाता है, यह शायद इस व्याख्या को सरल बनाता है कि व्यक्तिगत एल. एफ. एस. आर. का क्रूर बल कैसे आगे बढ़ता है। गलत अनुमान लगाने वाली कुंजी एल. एफ. एस. आर. आउटपुट उत्पन्न करेगी जो जनरेटर आउटपुट से लगभग 50 प्रतिशत समय सहमत होती है क्योंकि, किसी दी गई लंबाई के दो यादृच्छिक बिट अनुक्रमों को देखते हुए, किसी विशेष बिट पर अनुक्रमों के बीच समझौते की संभावना 0.5 है। हालांकि, विशिष्ट व्यक्तिगत गलत कुंजी अच्छी तरह से एल. एफ. एस. आर. आउटपुट उत्पन्न कर सकती है जो जनरेटर आउटपुट के साथ लगभग 50 प्रतिशत से अधिक बार सहमत होती है। यह विशेष रूप से एल. एफ. एस. आर. के मामले में मुख्य है जिसका जनरेटर के साथ सहसंबंध विशेष रूप से मजबूत नहीं है; छोटे पर्याप्त सहसंबंधों के लिए, यह निश्चित रूप से संभावना के दायरे से बाहर नहीं है कि एक गलत अनुमान की गई कुंजी भी एल. एफ. एस. आर. आउटपुट की ओर ले जाएगी जो जनरेटर आउटपुट के बिट्स की वांछित संख्या से सहमत है। इस प्रकार, उस एल. एफ. एस. आर. की विशिष्ट कुंजी की पहचान करना संभव नहीं हो सकता है। हालाँकि, कई संभावित कुंजियों की पहचान करना संभव हो सकता है, जो अभी भी साइफर की सुरक्षा का एक महत्वपूर्ण उल्लंघन है। इसके अलावा, ज्ञात सादे पाठ के एक मेगाबाइट को देखते हुए, स्थिति काफी अलग होगी। एक गलत कुंजी एल. एफ. एस. आर. उत्पादन उत्पन्न कर सकती है जो जनरेटर उत्पादन के 512 किलोबाइट से अधिक के साथ सहमत है लेकिन उत्पादन उत्पन्न करने की संभावना नहीं है जो जनरेटर उत्पादन के 768 किलोबाइट के साथ सहमत है जैसा कि सही अनुमान लगाया गया है। एक नियम के रूप में, एक व्यक्तिगत रजिस्टर और जनरेटर आउटपुट के बीच संबंध जितना कमजोर होगा, उस रजिस्टर की कुंजी को उच्च स्तर के विश्वास के साथ खोजने के लिए उतना ही अधिक ज्ञात सादा पाठ की आवश्यकता होती है। किसी दिए गए सहसंबंध के लिए आवश्यक ज्ञात सादे पाठ की लंबाई के अनुमानों की गणना द्विपद वितरण का उपयोग करके की जा सकती है। उच्च क्रम सहसंबंध परिभाषा ज्योफ जनरेटर पर उदाहरण हमले में जिन सहसंबंधों का दोहन किया गया था, वे प्रथम क्रम सहसंबंधों के उदाहरण हैंः वे जनरेटर आउटपुट के मूल्य और एक व्यक्तिगत एल. एफ. एस. आर. के बीच सहसंबंध हैं। इनके अलावा उच्च-क्रम सहसंबंधों को परिभाषित करना संभव है। उदाहरण के लिए, यह संभव हो सकता है कि किसी दिए गए बूलियन फ़ंक्शन का किसी भी व्यक्तिगत रजिस्टर के साथ कोई मजबूत सहसंबंध न हो, लेकिन दो रजिस्टरों के कुछ बूलियन फ़ंक्शन के बीच एक महत्वपूर्ण सहसंबंध मौजूद हो सकता है, उदाहरण के लिए। यह दूसरे क्रम के सहसंबंध का एक उदाहरण होगा। तीसरे क्रम के सहसंबंधों और उच्चतर को इस तरह से परिभाषित किया जा सकता है। उच्च-क्रम सहसंबंध हमले एकल-क्रम सहसंबंध हमलों की तुलना में अधिक शक्तिशाली हो सकते हैं, हालांकि, यह प्रभाव "सीमित रिटर्न के कानून" के अधीन है। नीचे दी गई तालिका एक कीस्ट्रीम जनरेटर पर विभिन्न हमलों के लिए कम्प्यूटेशनल लागत का एक उपाय दिखाती है जिसमें आठ 8-बिट एल. एफ. एस. आर. एक एकल बूलियन फ़ंक्शन द्वारा संयुक्त होते हैं। लागत की गणना को समझना अपेक्षाकृत सीधा हैः राशि का सबसे बायां पद सहसंबद्ध जनरेटरों के लिए प्रमुख स्थान के आकार का प्रतिनिधित्व करता है, और सबसे दाहिना पद शेष जनरेटरों के लिए प्रमुख स्थान के आकार का प्रतिनिधित्व करता है। जबकि उच्च-क्रम सहसंबंध अधिक शक्तिशाली हमलों की ओर ले जाते हैं, उन्हें ढूंढना भी अधिक कठिन होता है, क्योंकि उपलब्ध बूलियन कार्यों का स्थान जनरेटर आउटपुट के खिलाफ सहसंबंध करने के लिए कार्य के लिए तर्कों की संख्या के रूप में बढ़ता है। शब्दावली चरों के एक बूलियन कार्य को "-th क्रम सहसंबंध प्रतिरक्षा" कहा जाता है, या कुछ पूर्णांक के लिए "th क्रम सहसंबंध प्रतिरक्षा" कहा जाता है, यदि कार्य के उत्पादन और इसके निवेश के किसी भी बूलियन कार्य के बीच कोई महत्वपूर्ण सहसंबंध मौजूद नहीं है। उदाहरण के लिए, एक बूलियन कार्य जिसमें कोई प्रथम-क्रम या द्वितीय-क्रम सहसंबंध नहीं है, लेकिन जिसमें तृतीय-क्रम सहसंबंध है, द्वितीय-क्रम सहसंबंध प्रतिरक्षा प्रदर्शित करता है। जाहिर है, उच्च सहसंबंध प्रतिरक्षा एक कार्य को एक कीस्ट्रीम जनरेटर में उपयोग के लिए अधिक उपयुक्त बनाती है (हालांकि यह एकमात्र ऐसी चीज नहीं है जिस पर विचार करने की आवश्यकता है)। सिगेनथेलर ने दिखाया कि चर की बीजगणितीय डिग्री के बूलियन फ़ंक्शन की सहसंबंध प्रतिरक्षा संतुष्ट करती है; इनपुट चर के दिए गए सेट के लिए, इसका मतलब है कि एक उच्च बीजगणितीय डिग्री अधिकतम संभव सहसंबंध प्रतिरक्षा को प्रतिबंधित करेगी। इसके अलावा, यदि कार्य संतुलित है तो। यह इस प्रकार है कि चरों के एक कार्य के लिए th क्रम सहसंबंध प्रतिरक्षित होना असंभव है। यह इस तथ्य से भी मिलता है कि इस तरह के किसी भी कार्य को इनपुट कार्यों के एक्सओआर के संयोजन के रूप में रीड-मुलर आधार का उपयोग करके लिखा जा सकता है। एक धारा साइफर की सुरक्षा पर एक सहसंबंध हमले के प्रभाव की संभावित चरम गंभीरता को देखते हुए, एक धारा साइफर में इसका उपयोग करने का निर्णय लेने से पहले सहसंबंध प्रतिरक्षा के लिए एक उम्मीदवार बूलियन संयोजन कार्य का परीक्षण करना आवश्यक होना चाहिए। हालांकि, यह ध्यान रखना महत्वपूर्ण है कि उच्च सहसंबंध प्रतिरक्षा एक आवश्यक है, लेकिन एक कीस्ट्रीम जनरेटर में उपयोग के लिए उपयुक्त होने के लिए बूलियन कार्य के लिए पर्याप्त स्थिति नहीं है। विचार करने के लिए अन्य मुद्दे हैं, उदाहरण के लिए, क्या फ़ंक्शन संतुलित है या नहीं-क्या यह उतने ही या मोटे तौर पर उतने ही 1 का आउटपुट देता है जितना कि यह 0 करता है जब सभी संभावित इनपुट पर विचार किया जाता है। किसी दिए गए आकार के बूलियन कार्यों को आसानी से उत्पन्न करने के तरीकों पर शोध किया गया है जो कम से कम सहसंबंध प्रतिरक्षा के कुछ विशेष क्रम की गारंटी देते हैं। इस शोध ने सहसंबंध प्रतिरक्षा बूलियन कार्यों और त्रुटि सुधार कोड के बीच संबंधों को उजागर किया है। क्रिप्टोग्राफी संदर्भ ब्रूस श्नायर में विषय भी देखें। अनुप्रयुक्त क्रिप्टोग्राफीः सी, द्वितीय संस्करण में प्रोटोकॉल, एल्गोरिदम और स्रोत कोड। जॉन विली एंड संस, इंक. 1996. धारा 16.4 का पृष्ठ 382: एल. एफ. एस. आर. का उपयोग करते हुए स्ट्रीम् साइफर। बाहरी लिंक बूलियन कार्यों का ऑनलाइन डेटाबेस आगंतुकों को सहसंबंध प्रतिरक्षा सहित कई तरीकों से बूलियन कारकों के डेटाबेस को खोजने की अनुमति देता है। क्रिप्टोग्राफिक हमले