🍺 🍄 🗯️ 1000 गुना पासवर्ड हैशिंग की क्रिप्टोग्राफिक ताकत 🛰️ 😓 👆🏿

एक पासवर्ड (बार-बार फिसलने, अन्य मंचों पर फिसलने) पर हैश के बार-बार उपयोग की क्रिप्टोग्राफिक ताकत के बारे में इस विषय में जो चर्चा हुई, उसने मुझे इस गणितीय विषय पर थोड़ा धक्का दिया। समस्या का सार बार-बार (1,000 या अधिक बार) किसी भी क्रिप्टोग्राफिक एल्गोरिथ्म (सबसे अक्सर एक हैश फ़ंक्शन) के साथ पासवर्ड को संसाधित करने के विचार से उत्पन्न होता है ताकि धीमी सत्यापन एल्गोरिथ्म प्राप्त किया जा सके, जिससे एक हमलावर द्वारा अवरोधन या चोरी होने की स्थिति में प्रभावी रूप से क्रूर बल का विरोध किया जा सके। मान। स्क्रैच के दाएं हाथ के उपयोगकर्ताओं (पहले लेख के लेखक) के रूप में, mrThe और IlyaPodkopaev ने कहा कि यह विचार नया नहीं है और इसका उपयोग सिस्को उपकरण, RAR अभिलेखागार और कई अन्य लोगों के डेवलपर्स द्वारा किया जाता है। लेकिन, चूंकि हैशिंग एक ऑपरेशन है जो मूल्यों की भीड़ को संकुचित करता है, एक पूरी तरह से तार्किक सवाल उठता है - क्या हम सिस्टम की स्थिरता को नुकसान पहुंचाएंगे? इस सवाल का जवाब देने की कोशिश कर रहा है

हम दो खतरे मॉडल में लचीलापन में कमी पर विचार करेंगे:

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

चलो पहले, अधिक सैद्धांतिक, प्रश्न से शुरू करते हैं: "आधुनिक हैश फ़ंक्शन के मानों का इतना बड़ा स्थान 2 ¹²⁸ (MD5), 2 ¹⁶⁰ (SHA-1), 2 ²⁵⁶ (GOST R 34.11, SHA-256) बार-बार उपयोग के परिणामस्वरूप संकीर्ण हो सकता है इस हद तक कि इसे एक साधारण यादृच्छिक खोज द्वारा उठाया जा सकता है? "

शुरुआत

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

आइए हम एन तत्वों का एक इनपुट सेट लेते हैं और इसकी प्रत्येक वस्तु की हम एन वस्तुओं के आउटपुट सेट में तुलना करते हैं एक यादृच्छिक तत्व (चित्र देखें।)। जाहिर है, कई मैपिंग एक ही तत्व दिखाएंगे, और, इसलिए, ऐसे तत्व बने रहेंगे जो एक तीर में फिट नहीं होते हैं:

संभावना है कि आउटपुट सेट का एक विशेष तत्व एक विशेष मैपिंग (तीर) द्वारा नहीं चुना जाएगा

तदनुसार, संभावना है कि वह किसी भी एन तीर द्वारा चयनित नहीं किया जाएगा

या जो है वही है

(क्रिप्टोग्राफिक हैश फ़ंक्शन की संपत्ति के कारण, सभी एन मैपिंग एक पहले सन्निकटन में स्वतंत्र घटना हैं)।

सीमा

दूसरी उल्लेखनीय सीमा का परिणाम है और इसके बराबर है

, यानी। लगभग 0.3679। यह संभावना है कि आउटपुट सेट में तत्व "ग्रे हो जाएगा।" जिस तरह से, हम ध्यान दें कि बड़े एन के लिए (2 से अधिक ³² ) "गिरावट" की डिग्री हैश फ़ंक्शन की क्षमता पर निर्भर नहीं करती है। नतीजतन, पहले हैश दोहराने के बाद, मूल्य अंतरिक्ष का लगभग 63% ही रहेगा। यदि सब कुछ आगे भी चलता है, तो यह एक आपदा होगी - केवल 150 पुनरावृत्तियों में हम आउटपुट स्पेस के 100 बिट्स "खाएंगे", उदाहरण के लिए, एमडी 5 केवल 2 ^128-100 = 2 ²⁸ विकल्पों के लिए। सौभाग्य से, ऐसा नहीं है।

विस्तार से

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

इनपुट सेट में केवल kN तत्व सक्रिय होने दें, जहाँ 0 <k <1 । फिर एक विशिष्ट तत्व को चुनने की संभावना नहीं है

, जो के बराबर है

, और इस पुनरावृत्ति पर सेट आउटपुट का संकुचन केवल होगा

। यहाँ पहले 6 पुनरावृत्तियों की एक तालिका है:

Iteration नंबर, i	मूल्यों के समुच्चय का अंश, के
1	1.0000
2	0.6321
3	0.4685
4	0.3740
5	0.3120
6	0.2680

बेशक, सक्रिय तत्वों का अनुपात प्रत्येक पुनरावृत्ति के साथ घटता-बढ़ता रहता है, लेकिन शुरुआत में उतना जल्दी और भयावह रूप से नहीं।

बड़ी संख्या में पुनरावृत्तियों के लिए प्रतिरोध में कमी की डिग्री का आकलन करने के लिए, संख्या के स्वयं का अध्ययन करना अधिक सुविधाजनक है, लेकिन इसके विपरीत - आधार 2 लघुगणक पैमाने में आउटपुट सेट को कितनी बार कम किया गया है, ताकि बिट्स इकाइयां बन सकें:

। यह वह संख्या है जो संपूर्ण खोज के प्रतिरोध में कमी की विशेषता होगी - इसे स्थिर हैश फ़ंक्शन के बराबर बिट गहराई प्राप्त करने के लिए चयनित हैश फ़ंक्शन की बिट गहराई से घटाया जाना चाहिए। 50,000 पुनरावृत्तियों तक का एक भूखंड चित्र में दिखाया गया है:

जिन बिंदुओं पर ग्राफ पूर्णांक आर मानों को अंकित करता है, उन्हें तालिका में संक्षेपित किया गया है:

स्थायित्व में कमी, आर (बिट)	पुनरावृत्तियों की संख्या, i
4	30
5	61
6	125
7	253
8	509
9	1.020
10	2,044
11	4.092
12	8.188
13	16,379
14	32,763
15	65,531
16	131,067
...	...
20	2,097,146
...	...
24	33,554,425

जैसा कि आप देख सकते हैं, एक निश्चित क्षण से प्रतिरोध में कमी बहुत धीरे-धीरे बढ़ती है। इसके अलावा, पुनरावृत्तियों की संख्या वास्तव में दो की शक्तियों का अनुसरण करती है:

। सभी मामलों में जब समान पैटर्न देखे जाते हैं, तो उन्हें विश्लेषणात्मक रूप से साबित किया जा सकता है, लेकिन मैंने इसे अपने लक्ष्य के रूप में निर्धारित नहीं किया। इस प्रकार, एल्गोरिथ्म की स्थिरता को कम किए बिना 16 से अधिक बिट्स (और 128-बिट हैश फ़ंक्शन के लिए मेरी दृढ़ राय में, यह अगले 25 वर्षों के लिए उनकी व्यावहारिक स्थिरता को प्रभावित नहीं करेगा), आप पासवर्ड हैशिंग के 130,000 पुनरावृत्तियों का प्रदर्शन कर सकते हैं। 256-बिट हैश फ़ंक्शन (SHA-256, GOST R 34.11, RIPEMD-256, आदि) के लिए, जाहिर है, यह बार कई गुना अधिक है।

मॉडल पर्याप्तता की जाँच करें

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

नियोजित प्रतिरोध में कमी, आर (बिट)	पुनरावृत्तियों की संख्या, i	सेट में तत्वों की अपेक्षित संख्या	सेट में तत्वों की देखी गई संख्या
4	30	2 ^16-4 = 4.096	3.819
6	125	2 ^16-6 = 1.024	831
8	509	2 ^16-8 = 256	244

बेशक, एन और विशेष रूप से केएन के इस तरह के एक छोटे से मूल्य के साथ, तथ्य यह है कि सीमा के लिए ऊपर दी गई सभी गणना तुरंत प्रभावित होती है ( एन तुलनीय और बड़े 2 ^{128 के लिए} - सब कुछ वहां ठीक है)। लेकिन यहां भी, सामान्य प्रवृत्ति का पता लगाया जा सकता है और ऊपर दिए गए सूत्रों में स्वीकार्य फिट बैठता है।

परिणाम - शब्दकोश हमले का प्रतिरोध

विश्लेषण का समय आ गया है , "उन मामलों में ध्यान देने योग्य मूल्यों की संकीर्णता है जब एक शब्दकोश या आसानी से निर्मित पासवर्ड को पासफ़्रेज़ के रूप में चुना जाता है?" जाहिर है, इस मामले में मूल्यों का "सक्रिय" इनपुट सेट पहले से ही बहुत संकुचित है - यह 2 ¹⁶ से 2 ⁴⁸ तक सीमा में चयन के तरीकों पर निर्भर करता है। इस प्रकार, हम तुरंत खुद को एक "डिस्चार्ज" स्थिति में पाते हैं - अनुसूची के दाईं ओर। यहां, एक ही आउटपुट में दो अलग-अलग इनपुट तत्वों को मैप करने की संभावना बेहद कम है। लाखों और लाखों ऑपरेशन शायद ही आउटपुट सेट में तत्वों की संख्या को बदलेंगे। इकाइयाँ / दर्जनों समाप्त हो जाती हैं - भाषण की स्थिरता में कोई व्यावहारिक कमी का कोई सवाल ही नहीं है।

निष्कर्ष

वर्णित ब्रूट फोर्स प्रोटेक्शन स्कीम को क्रिप्टोग्राफिक ताकत पर लगभग कोई प्रतिबंध नहीं होने के साथ स्वतंत्र रूप से लागू किया जा सकता है। पुनरावृत्तियों की संख्या की अनुशंसित ऊपरी सीमा (प्रतिरोध आर में अनुमत कमी को विषयगत रूप से हैश फ़ंक्शन ^के _1/8 बिट की मात्रा में चुना गया है) तालिका में दिए गए हैं:

बिट गहराई हैश फ़ंक्शन (बिट)	प्रतिरोध में कमी की अनुमति, आर (बिट)	पुनरावृत्तियों की अनुमत संख्या की ऊपरी सीमा, i
128	16	130.000
160	20	2.000.000
192	24	32000000
224	28	500,000,000
256	32	आठ अरब

1000 गुना पासवर्ड हैशिंग की क्रिप्टोग्राफिक ताकत

शुरुआत

विस्तार से

मॉडल पर्याप्तता की जाँच करें

परिणाम - शब्दकोश हमले का प्रतिरोध

निष्कर्ष

More articles: