डेवलपर टूल · SHA हैश कैलकुलेटर
मर्कले-डैमगार्ड ने समझाया: SHA-1 और SHA-2 के पीछे का निर्माण
· पेजभूमि
शा-256 क्रिप्टोग्राफी ब्राउज़र-एपिस
एक निश्चित आकार का संपीड़न फ़ंक्शन अपने आप मनमाने ढंग से इनपुट को हैश नहीं कर सकता है। मर्कले-डैमगार्ड श्रृंखलाएँ इसे ब्लॉक दर ब्लॉक करती हैं; यह पोस्ट निर्माण, इसके प्रमाण विचार और इसमें मौजूद कमजोरियों के बारे में बताती है।
मनमाना इनपुट, निश्चित आउटपुट - वह समस्या जिसे प्रत्येक हैश फ़ंक्शन को पहले हल करना होता है
एक हैश फ़ंक्शन को मनमाने इनपुट को निश्चित आउटपुट पर मैप करना होगा। तीन बाइट्स का एक संदेश और तीन मेगाबाइट का एक संदेश दोनों को SHA-256 के लिए बिल्कुल 256 bits आउटपुट उत्पन्न करना चाहिए। हैश नियतात्मक होना चाहिए, इसलिए समान इनपुट हमेशा समान आउटपुट उत्पन्न करता है। आउटपुट यादृच्छिक दिखना चाहिए; इनपुट के एक बिट को बदलने से आउटपुट बिट्स का लगभग आधा हिस्सा बदल जाना चाहिए।
पहली नज़र में ये विरोधाभासी आवश्यकताएं हैं, क्योंकि एक एकल तेज़ एल्गोरिदम मनमानी लंबाई के संदेशों को संभाल नहीं सकता है और एक समान निश्चित-चौड़ाई आउटपुट का उत्पादन नहीं कर सकता है। मर्कल-डैमगार्ड निर्माण एक निश्चित आकार के संपीड़न फ़ंक्शन का बार-बार उपयोग करके, प्रत्येक एप्लिकेशन के आउटपुट को अगले के इनपुट में फीड करके इसे हल करता है। इस निर्माण का उपयोग SHA-1 और सभी SHA-2 (SHA-256, SHA-384 और SHA-512) द्वारा किया जाता है।
संपीड़न फ़ंक्शन - एक निश्चित आकार का मिक्सर जो एक राज्य और एक ब्लॉक लेता है और एक नया राज्य लौटाता है
एक संपीड़न फ़ंक्शन मुख्य क्रिप्टोग्राफ़िक आदिम है जो मर्कले-डैमगार्ड हैश को शक्ति प्रदान करता है। यह एक निश्चित आकार की स्थिति लेता है, आमतौर पर SHA-256 के लिए 256 bits या SHA-512 के लिए 512 bits, और इनपुट का एक निश्चित आकार का ब्लॉक, आमतौर पर SHA-256 के लिए 512 bits या SHA-512 के लिए 1024 bits। संपीड़न फ़ंक्शन बिटवाइज़ ऑपरेशंस, रोटेशन और टेबल लुकअप का उपयोग करके उन्हें एक साथ मिलाता है, जिससे समान आकार की एक नई स्थिति उत्पन्न होती है। यह फ़ंक्शन टकराव-प्रतिरोधी होना चाहिए: समान आउटपुट उत्पन्न करने वाले दो अलग-अलग (राज्य, ब्लॉक) जोड़े ढूंढना कठिन होना चाहिए।
संपीड़न फ़ंक्शन स्वयं एक पूर्ण हैश फ़ंक्शन नहीं है - यह मनमानी इनपुट लंबाई को संभाल नहीं पाता है, और यह पहले इनपुट को भी संभाल नहीं पाता है, जिसकी कोई पिछली स्थिति नहीं होती है। इसके बजाय, यह बिल्डिंग ब्लॉक है जिसके चारों ओर एक बड़ा निर्माण किया जाता है। कम्प्रेशन फ़ंक्शन एकमात्र क्रिप्टोग्राफ़िक ऑपरेशन है जो बार-बार चलता है; बाकी सब कुछ बहीखाता है जो इस फ़ंक्शन को पूर्ण हैश से जोड़ता है।
चेनिंग और इनिशियलाइज़ेशन वेक्टर - कैसे ब्लॉक एक निश्चित प्रारंभिक स्थिति से एक दूसरे में फ़ीड करते हैं
इनिशियलाइज़ेशन वेक्टर निश्चित प्रारंभिक अवस्था है, जिसे समरूपता या कमज़ोरियों से बचने के लिए सावधानीपूर्वक चुना जाता है। SHA-256 के लिए, IV आठ 32-बिट शब्द हैं जो पहले आठ अभाज्य संख्याओं के वर्गमूलों के आंशिक भागों से प्राप्त हुए हैं। ये मान मनमाने लेकिन नियतिवादी हैं, इसलिए प्रत्येक कार्यान्वयन एक ही परिणाम उत्पन्न करता है। पहले संदेश ब्लॉक को संपीड़न फ़ंक्शन का उपयोग करके IV के साथ मिलाया जाता है, जिससे एक नई स्थिति उत्पन्न होती है। दूसरा संदेश ब्लॉक उस स्थिति के साथ मिश्रित होता है, जिससे एक और नई स्थिति बनती है, और इसी तरह संदेश के प्रत्येक ब्लॉक के माध्यम से।
यह चेनिंग महत्वपूर्ण हिस्सा है: एक ब्लॉक का आउटपुट पिछले सभी ब्लॉकों पर निर्भर करता है, इसलिए किसी भी पिछले ब्लॉक के किसी भी बिट को बदलने से बाद के सभी ब्लॉक बदल जाते हैं। जब तक अंतिम ब्लॉक संसाधित होता है, तब तक राज्य में इनपुट के प्रत्येक बिट के बारे में जानकारी होती है। पैडिंग वह युक्ति है जो इस निर्माण को सुदृढ़ बनाती है। एक संदेश हमेशा ब्लॉकों में समान रूप से विभाजित नहीं होता है। मर्कले-डैमगार्ड निर्माण एमडी-मजबूत करने का उपयोग करता है: संदेश में एक बिट जोड़ें, फिर शून्य जोड़ें जब तक कि लगभग एक पूर्ण ब्लॉक न रह जाए, फिर मूल संदेश लंबाई जोड़ें।
संदेश की लंबाई के साथ पैडिंग - एमडी-मजबूतीकरण ही निर्माण को बेहतर बनाता है
मर्कले-डैमगार्ड के सुरक्षा तर्क में कहा गया है कि यदि संपीड़न फ़ंक्शन टकराव-प्रतिरोधी है, तो संपूर्ण हैश टकराव-प्रतिरोधी है। इसका प्रमाण एक कमी है: यदि आप हैश में टकराव पा सकते हैं, तो आप संपीड़न फ़ंक्शन में टकराव निकाल सकते हैं, जो इस धारणा का खंडन करता है कि संपीड़न फ़ंक्शन को टकराना कठिन है। अंतर्ज्ञान यह है कि हैश में किसी भी टकराव से अंततः संपीड़न फ़ंक्शन कॉल में से एक में टकराव उत्पन्न होना चाहिए, क्योंकि राज्य को पूरी तरह से आगे बढ़ाया जाता है।
मर्कले-डैमगार्ड में कमजोरियाँ समय के साथ खोजी गईं, भले ही बुनियादी निर्माण अच्छा हो। लंबाई विस्तार एक है: एक हमलावर जो किसी संदेश के डाइजेस्ट को देखता है वह संदेश का विस्तार कर सकता है और इनपुट के बारे में कुछ भी जाने बिना लंबे संदेश के लिए वैध डाइजेस्ट की गणना कर सकता है। दूसरा प्रीइमेज हमला दूसरा है: एक संदेश दिया गया है, उसी हैश के साथ एक अलग संदेश ढूंढना कुछ प्रकार के संदेशों की तुलना में आसान है। इन कमज़ोरियों ने SHA-3 के डिज़ाइन को प्रेरित किया, जो स्पंज निर्माण नामक एक अलग दृष्टिकोण का उपयोग करता है।
लंबाई-एन्कोडिंग पैडिंग पैडेड संदेशों को अलग करती है; एक पूर्ण सुरक्षा प्रमाण बाहरी भंडार साक्ष्य है
SHA-256 के लिए संपीड़न फ़ंक्शन एक 256-बिट स्थिति (आठ 32-बिट शब्द) और एक 512-बिट ब्लॉक लेता है। ऑपरेशन 64 राउंड का उपयोग करता है, प्रत्येक राज्य को एक स्थिरांक और ब्लॉक से एक शब्द के साथ मिलाता है। मिश्रण बिटवाइज़ संचालन का उपयोग करता है: XOR, AND, NOT। यह रोटेशन और शिफ्ट का उपयोग करता है जो बिट्स को सेट किए गए बिट्स को बदले बिना इधर-उधर ले जाता है। यह तालिका लुकअप का उपयोग करता है जो गैर-रेखीय मिश्रण प्रदान करता है जिसे XOR अकेले प्राप्त नहीं कर सकता है।
SHA-512 SHA-256 के समान निर्माण का उपयोग करता है लेकिन 32-बिट संचालन के बजाय 64-बिट संचालन के साथ। स्थिति 512 bits (आठ 64-बिट शब्द) है, और ब्लॉक का आकार 1024 bits है। संपीड़न फ़ंक्शन में 64 के बजाय 80 राउंड हैं, और स्थिरांक और तालिका लुकअप भिन्न हैं। SHA-384 के लिए, स्थिति और संपीड़न फ़ंक्शन SHA-512 के समान हैं, लेकिन अंतिम स्थिति का केवल पहला 384 bits ही आउटपुट है। अंतिम 128 bits को छोड़ दिया जाता है। इस काट-छाँट के कारण SHA-384 लंबाई विस्तार के प्रति प्रतिरोधी है।
लंबाई विस्तार सत्यापित निर्माण सीमा है; बहुटकराव और SHA-3 प्रेरणा दावे छोड़े गए हैं
मर्कल-डैमगार्ड हैश की सुरक्षा कई संपत्तियों पर निर्भर करती है। संपीड़न फ़ंक्शन टकराव-प्रतिरोधी होना चाहिए, इसलिए इस पर सीधे हमला करना संभव नहीं है। पैडिंग योजना को यह सुनिश्चित करना चाहिए कि अलग-अलग संदेश अलग-अलग पैडेड फॉर्म उत्पन्न करें, इसलिए हैश में प्रत्येक टकराव में एक संपीड़न फ़ंक्शन टकराव शामिल होना चाहिए। ब्लॉक का आकार और स्थिति का आकार इतना बड़ा होना चाहिए कि क्रूर बल लगाना संभव न हो। एक व्यापक स्थिति सामान्य खोज स्थान को बढ़ाती है, लेकिन यह आलेख इनलाइन व्युत्पत्ति और एक समीक्षा स्रोत के बिना एक ऑपरेशन गणना या व्यवहार्यता तिथि संलग्न नहीं करता है।
यदि किसी हमलावर को संपीड़न फ़ंक्शन में कमजोरी मिलती है, या यदि क्वांटम कंप्यूटर व्यावहारिक हो जाते हैं और 2^n समय के बजाय sqrt(2^n) समय में एक असंरचित स्थान खोज सकते हैं, तो सुरक्षा मार्जिन कम हो जाता है। जिस कमजोरी ने SHA-3 को प्रेरित किया वह संपीड़न फ़ंक्शन में रुकावट नहीं थी, बल्कि लंबाई विस्तार समस्या और अन्य संरचनात्मक कमजोरियां थीं। एक स्पंज निर्माण अपनी पूर्ण आंतरिक स्थिति को कभी भी प्रकाशित न करके इनसे बचता है।
इसमें क्या शामिल नहीं है - SHA-256 के विशिष्ट राउंड फ़ंक्शंस, एक अलग पोस्ट में कवर किए गए हैं
मर्कल-डैमगार्ड निर्माण प्रत्येक इनपुट आकार को कैसे संभालता है यह इसके डिजाइन का व्यावहारिक परिणाम है। संदेश को 512-बिट ब्लॉक में विभाजित करें, अंतिम ब्लॉक को पैड करें, अनुक्रम में संपीड़न फ़ंक्शन के माध्यम से प्रत्येक ब्लॉक को संसाधित करें, और अंतिम स्थिति को आउटपुट करें। एक-बाइट इनपुट के लिए, पैडिंग एक 512-बिट ब्लॉक (संदेश का एक बाइट, पैडिंग का एक बिट, शून्य का 447 bits और लंबाई के लिए 64 bits) उत्पन्न करता है। संपीड़न की संख्या 512-बिट ब्लॉक की संख्या है, जो संदेश की लंबाई के समानुपाती होती है।
प्रत्येक डाइजेस्ट ToolAcre SHA हैश कैलकुलेटर का उत्पादन इसी निर्माण से होता है। 64-वर्ण SHA-256 डाइजेस्ट हेक्साडेसिमल में मुद्रित अंतिम 256-बिट स्थिति है। 128-वर्ण SHA-512 डाइजेस्ट हेक्साडेसिमल में मुद्रित अंतिम 512-बिट स्थिति है। 96-वर्ण SHA-384 डाइजेस्ट अंतिम 512-बिट स्थिति का पहला 384 bits है। पर्दे के पीछे की पैडिंग यह सुनिश्चित करती है कि हर संभव संदेश बिल्कुल सही संख्या में ब्लॉक और सही डाइजेस्ट चौड़ाई उत्पन्न करता है। यह ब्राउज़र में चलने वाला मानक मर्कले-डैमगार्ड निर्माण है।
टेकअवे: चार एल्गोरिदम के पीछे एक ही ढांचा - प्रत्येक डाइजेस्ट ToolAcre SHA हैश कैलकुलेटर का उत्पादन इसी निर्माण से होता है
निर्माण को समझना यह जानने के लिए उपयोगी है कि डाइजेस्ट हमेशा एक ही चौड़ाई के क्यों होते हैं और इनपुट के एक बिट को बदलने से पूरा डाइजेस्ट क्यों बदल जाता है। चेनिंग प्रॉपर्टी का मतलब है कि इनपुट का प्रत्येक बिट मिश्रण संचालन की एक श्रृंखला के माध्यम से आउटपुट के प्रत्येक बिट को प्रभावित करता है। संदेश के आरंभ में एक-बिट परिवर्तन बाद के सभी संपीड़नों के माध्यम से प्रसारित होगा, इसलिए अंतिम डाइजेस्ट पूरी तरह से अलग है। इस गुण को हिमस्खलन प्रभाव कहा जाता है और यह ध्वनि हैश फ़ंक्शन का हस्ताक्षर है।
मर्कले-डैमगार्ड निर्माण दशकों से उपयोग में है और सबसे व्यापक रूप से तैनात हैश फ़ंक्शन की नींव बनाता है। SHA-1 और SHA-2 इस निर्माण पर बनाए गए हैं, और कई तैनात सिस्टम उनके आउटपुट पर निर्भर हैं। निर्माण प्रायोगिक के बजाय स्थापित है, लेकिन इतिहास हर उपयोग को सुरक्षित नहीं बनाता है; लंबाई विस्तार एक प्रलेखित सीमा है। इस निर्माण को समझने से डेवलपर्स को यह समझने में मदद मिलती है कि कुछ सुरक्षा गुण क्यों मौजूद हैं और कुछ आक्रमण वैक्टर क्यों मौजूद हैं।