🤟 💚 👨🏽 केकेक इतना शांत क्यों है और उसे नए SHA-3 के रूप में क्यों चुना गया 📽️ ✌🏾 📹

हाय% उपयोगकर्ता नाम%!
मेरे लिए, जैसा कि यह एक पेशेवर गणितज्ञ या क्रिप्टोग्राफर के लिए कभी नहीं रहा है, यह शायद ही कभी स्पष्ट रूप से स्पष्ट है कि एक या अन्य एल्गोरिथ्म कैसे काम करता है। और विशेष रूप से वे उसे क्यों चुनते हैं।
तो नए SHA-3 मानक के साथ। हमने कुछ केकेक को चुना, कॉमरेड नेवरवॉकऑलर के लिए धन्यवाद, इसका विवरण दिया । लेकिन व्यक्तिगत रूप से, यह मेरे लिए स्पष्ट नहीं है कि वह कैसे काम करता है और उसकी चाल क्या है। चलो ठीक है।

लेख के अंत में SHA-2 के प्रतिरोध के बारे में सोचने के लिए जानकारी के रूप में लोगों को पागल करने के लिए एक छोटा सा बोनस होगा।

के साथ शुरू करने के लिए, मैं कहूंगा कि सभी हैश तथाकथित "रैंडम ओरेकल" के समान संभव हैं। इसलिए, शुरुआत के लिए, उसके बारे में थोड़ा।

एक यादृच्छिक ओरेकल अनंत स्मृति के साथ एक अमूर्त ब्लैक बॉक्स है और निम्नलिखित एल्गोरिदम के अनुसार काम करता है:

यह इनपुट पर एक स्ट्रिंग प्राप्त करता है और यह देखता है कि क्या इसके साथ पहले काम किया था।
यदि नहीं, तो यह वास्तव में यादृच्छिक संख्या उत्पन्न करता है और एक स्ट्रिंग-संख्या जोड़ी को संग्रहीत करता है।
यदि हाँ, तो इस लाइन के लिए पहले से संग्रहीत संख्या लौटाता है।

एक हैश की तरह लगता है, है ना? केवल मूल अंतर के साथ जो हैशेड स्ट्रिंग और परिणाम के बीच के रिश्ते को सिद्धांत में गणना नहीं की जा सकती है । आगे बढ़ो।

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

और यहाँ केकेक के लेखक एक अलग तरीके से चले गए। उन्होंने छद्म-यादृच्छिक क्रमपरिवर्तन का उपयोग करने का निर्णय लिया, जिसमें टकराव परिभाषा के अनुसार नहीं हो सकता है। आइए हम इस क्षण पर अधिक विस्तार से ध्यान दें।

याद रखें कि कोई भी ब्लॉक सिफर कैसे काम करता है।

वह एक निश्चित लंबाई, एक चाबी के प्लेनटेक्स्ट का ब्लॉक लेता है, और एक ही लंबाई के एक सिफरटेक्स्ट से उनका मिलान करता है। यह मानचित्रण अस्पष्ट है, अन्यथा हम ब्लॉक को वापस डिक्रिप्ट नहीं कर पाएंगे। इस प्रकार, एक आदर्श ब्लॉक सिफर (कहते हैं, 128 बिट्स के ब्लॉक आकार के साथ) को गैर-फैंसी आकार की तालिका के रूप में दर्शाया जा सकता है, जिसकी पहली पंक्ति में सभी संभव कुंजियाँ (2 ¹²⁸ ) होगी, पहले कॉलम में - सभी संभव प्लेरटेक्स्ट (2 ¹²⁸ भी), और सचमुच बेतरतीब ढंग से उत्पन्न सिफरब्लॉक पंक्तियों और स्तंभों के चौराहे पर होंगे, और खुले ब्लॉक-कुंजी-एन्क्रिप्टेड ब्लॉक संबंध अस्पष्ट होंगे।

गणित में, इस तरह के एक-से-एक संबंध को एक आपत्ति कहा जाता है ।

ध्यान दें कि किसी भी पंक्ति और किसी भी कॉलम में आप यादृच्छिक क्रम में बिट्स (लंबाई 2 ¹²⁸ हमारे मामले के लिए) के सभी संभावित संयोजन पा सकते हैं, और प्रत्येक संयोजन एक बार होगा। यह क्रमचय है । खैर, वास्तविक जीवन में, एल्गोरिदम द्वारा वर्णित छद्म-यादृच्छिक क्रमपरिवर्तन का उपयोग किया जाता है। क्योंकि ऐसी तालिका उत्पन्न करना अवास्तविक है।

मुझे लगता है कि अब गैर-विशेषज्ञों के लिए यह स्पष्ट है कि टक्कर से आने के लिए बस कहीं नहीं है। अन्यथा, एक ही खुले ब्लॉक को विभिन्न सिफरब्लॉक और इसके विपरीत मैप किया जा सकता है।

और क्या यहाँ हैश और केकेक है?

केकेक के लेखक एक सरल (यदि आप देखो) योजना के साथ आए, तथाकथित रूसी में स्पंज समारोह, या स्पंज।
इस "स्पंज" के अंदर एक राज्य है (SHA-3 के लिए आकार में 1600 बिट्स), जिसके लिए प्रत्येक दौर में एक ही फ़ंक्शन लागू किया जाता है, जो एक छद्म यादृच्छिक क्रमांकन लागू करता है।

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

एक स्ट्रिंग हैश करने के लिए, आपको पहले इसे एक निश्चित आकार के टुकड़ों में विभाजित करने की आवश्यकता होती है और हर बार उन्हें पूरे 1600 बिट राज्य में गोल (मिक्स) करने के लिए नहीं, बल्कि केवल इसके आकार आर की शुरुआत तक। फिर मैं वही चित्र सम्मिलित करूंगा, अब यह समझ में आता है।

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

यह तथाकथित "अवशोषण" चरण है। और अब यह स्पष्ट है कि इसे क्यों कहा जाता है आशा है आप भी बस थोड़ा सा बचा है!

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

इस तथ्य के कारण कि हम पूरे राज्य का उपयोग नहीं कर रहे हैं, लेकिन इसका केवल एक हिस्सा है, हम इनपुट और आउटपुट डेटा के संबंध के बारे में कुछ नहीं कह सकते हैं। और केकेक के लेखकों ने साबित कर दिया कि इस तरह के डिजाइन का स्थायित्व एक यादृच्छिक ओरेकल से एस / 2 के बराबर "उत्तर" के आकार के साथ अविभाज्य है (पूरे राज्य में सी + आर का आकार है), बशर्ते कि एफ एक आदर्श क्रमपरिवर्तन फ़ंक्शन है (एक आदर्श ब्लॉक सिफर से प्लेट, केवल दो कॉलम से, क्योंकि कोई कुंजी नहीं है)। यही है, 512 बिट्स की गणितीय रूप से सिद्ध स्थिरता के साथ हैश पाने के लिए, आपको पैरामीटर का आकार (राज्य का स्वतंत्र हिस्सा) 512 * 2 = 1024 बिट्स के साथ बनाना होगा। इस प्रकार, 512-बिट हैश के लिए आकार में 1600 बिट्स की स्थिति में, हम 1024 बिट्स को नहीं छूते हैं, और पहले 576 के लिए हम प्रत्येक दौर में हैशेड लाइन का हिस्सा मिलाते हैं।

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

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

बोनस

स्ट्रीमिंग एचसी -128 को उठाते समय, मैंने 2 दिलचस्प कार्यों को देखा, जो एक ही नंबर को ओवरशैड करते थे, इसे 2 बार बिट्स की एक अलग संख्या में घुमाया + एक और XOR इसके साथ दाईं ओर स्थानांतरित हो गया। 3 विभिन्न स्थिरांक (दोनों कार्यों के लिए 6)
जावा पर यह कुछ इस तरह दिखता है

int func(int x, int a, int b, int c)
{
return (ror(x, a) ^ ror(x, b) ^ (x >>> c));
}

फिर यह पता चला कि ये SHA-2 से sigma1 और sigma2 2 कार्य हैं।

और किसी कारण से मैं भ्रमित हो गया, क्योंकि वे सुंदर दिखते हैं, लेकिन वे कैसे काम करते हैं - एक्सएस।

SHA-2 और HC-128 से मूल a, b, c
{3, १ 3, ३} और {१ 3, १ ९, १०}

मैंने अनंत लूप f (f (f (f (f ... (1))) ले कर और पुनरावृत्ति की खोज करके मुश्किल अवधि की गणना करने का निर्णय लिया। यह पता चला है कि मूल स्थिरांक के साथ एक समारोह में 49146 की ऐसी "अवधि" थी, लेकिन मैं उन जोड़ों का एक गुच्छा खोजने में कामयाब रहा, जिनकी "अवधि" 131070 थी। और, मूल स्थिरांक की तरह, ऐसे चक्र के दौरान उत्पन्न होने वाले सेटों को प्रतिच्छेद नहीं किया गया था। उदाहरण के लिए

{२२, १३, ३} और {१ 3, ४, ९},
{२४, १५, २} और {१,, ३, ४}

तो, फंक फ़ंक्शन, यदि आप सामान्य रूप से अवधि की गणना करते हैं, तो 0 से 2 ³² -1 तक चलने पर 2 ^{32 की} अवधि होती है, अर्थात, फिर से, विशेषण।

Pgpru के साथ इस विषय का और उद्धरण:

खैर, यहां तक कि प्रसिद्ध क्रिप्टोग्राफर्स ने इस एनएसए ट्रिक की जांच करने की कोशिश की, लेकिन उन्हें कोई निश्चित राय नहीं मिली।

The0 और GF1 GF (2) - रैखिक मैपिंग एक से एक हैं (इस संपत्ति की जांच करने के लिए, हमने 32x32 GF (2) मेट्रिसेस की गणना σ0 और ,1 का प्रतिनिधित्व करते हुए की, और जाँच की कि इस मैट्रिक्स की कर्नेल नल तक सीमित है) वेक्टर)।

"क्रिप्टोग्राफी का मूल्यांकन रिपोर्ट सुरक्षा स्तर - SHA-256" © डॉ। हेलेना हेंडशू, डॉ। हेनरी गिल्बर्ट

σ0 और σ1 दोनों में कम वजन वाले इनपुट के हेमिंग वजन को बढ़ाने के लिए संपत्ति होती है। यह वृद्धि 3. के एक कारक द्वारा ऊपरी रूप से बंधी हुई है। कम वजन वाले इनपुट के लिए हेमिंग के वजन की औसत वृद्धि और भी अधिक है अगर दो घुमाव और एक बिट-शिफ्ट के बजाय तीन घुमाव का उपयोग किया जाता है। हालांकि, इस बिट-शिफ्ट का एक कारण अगले अवलोकन द्वारा दिया गया है। SH4-1 सहित MD4-परिवार के अन्य सभी सदस्यों के विपरीत, नए विस्तारित संदेश शब्दों को प्राप्त करने के लिए विस्तारित संदेश शब्दों को घुमाना अब (यहां तक कि एक्सओआर-लीनियर केस में भी) संभव नहीं है। यह बिटशिफ्ट का and0 और ift1 में इस्तेमाल होने के कारण है।

"SHA-256 संदेश विस्तार का प्रारंभिक विश्लेषण" © नॉर्बर्ट प्रैमस्टैलर, क्रिश्चियन रेचबर्गर, विंसेंट रिज्मेन

हम दिखाते हैं कि अशांति-सुधार की रणनीति SHA-256 वास्तुकला पर लागू होती है और हम यह साबित करते हैं कि फ़ंक्शन the, vital SHA-256 की सुरक्षा के लिए महत्वपूर्ण हैं जो यह दर्शाते हैं कि उनके बिना एक वेरिएंट के लिए 264 जटिलता के साथ nd कोलाज संभव है हैश ऑपरेशन

एस-बॉक्स and0 और σ1 एक समान भूमिका निभाते हैं: वे संदेश विस्तार के लिए गैर-प्रसार और बेहतर प्रसार प्रदान करते हैं।

"SHA-256 के सरलीकृत वेरिएंट का विश्लेषण" © क्रिस्टियन माटूसिविक्ज़, जोसेफ़ पाइप्रेज़क, नॉर्बर्ट प्रमस्टालर, क्रिश्चियन रीचबर्गर, विंसेंट रिजमेन।

सामान्य तौर पर, ये रैखिक या थोड़े गैर-रैखिक एस-ब्लॉक 32x32 आकार के होते हैं, जिन्हें संचालन के एक सरल संयोजन द्वारा वर्णित किया जाता है। उन्हें कैसे उठाया गया यह स्पष्ट नहीं है।

ये पिस रहे हैं। उन्होंने कुछ स्थिरांक भर दिए, अपने एल्गोरिथ्म को एक मानक के रूप में धकेल दिया और किसी को कुछ भी नहीं बताया। और क्या नरक मजाक नहीं है, शायद छद्म-अवधि जो मैंने पाया कि एनएसए लोगों को दो उंगलियों की तरह नकली हैश की अनुमति देता है। और शायद यह नहीं है।

केकेक इतना शांत क्यों है और उसे नए SHA-3 के रूप में क्यों चुना गया

याद रखें कि कोई भी ब्लॉक सिफर कैसे काम करता है।

More articles: