एक प्रश्न जिसका अर्थ है कि मैंने लंबे समय से उत्तर दिया है - एक संकलित बाइनरी के MD5sum को खोजने की समय जटिलता क्या होगी जिसमें उसी एमडी 5 को स्थिर रूप से एम्बेडेड किया गया हो , एक स्ट्रिंग के रूप में कहते हैं?एक ब्रूट-फोर्स एम्बेडेड MD5sum की समय जटिलता
संपादित करें: यदि यह पहले से स्पष्ट नहीं था। मैं समय जटिलता और स्पष्टीकरण के साथ उत्तर की तलाश में हूं।
ब्रूट फोर्स के समान ही बहुत कुछ: एक md5sum कंप्यूटिंग छोटा है, लेकिन एक ज्ञात md5sum से मेल खाने के लिए फ़ाइल बनाना मुश्किल है।
आप सबसे अच्छे मामले में, एक ऐसे अनुमान की तलाश में हैं जो आपको एक ज्ञात हैश (संभवतः बाइनरी में डेटा जोड़कर) देगा।
एमडी 5 का अच्छा वितरण होने के बाद यह वास्तव में कठिन है। ब्रूटफोर्सिंग द्वारा आपकी सबसे अच्छी शर्त आपकी फ़ाइल में कुछ हैश जोड़ रही है और बाइनरी के अंत तक अर्थहीन डेटा जोड़ रही है जब तक कि बाइनरी के पास एक ही हैश जैसा ही एम्बेड न हो।
दूसरी तरफ यदि आप यह जांचना चाहते हैं कि आपकी बाइनरी बरकरार है और असम्बद्ध है तो आप अपने बाइनरी को 3 भागों में विभाजित करके बेहतर हो जाएंगे: हैश से पहले बाइनरी का हिस्सा, हैश स्वयं और बाद में हिस्सा हैश पहले और अंतिम भाग को संयोजित करें, md5 हैश की गणना करें और इसे बाइनरी में एम्बेड करें।
इस (उदाहरण) की तरह:
foo098f6bcd4621d373cade4e832627b4f6bar
foo | 098f6bcd4621d373cade4e832627b4f6 | bar
md5(foo+bar) = 3858f62230ac3c915f300c664312c63f
foo3858f62230ac3c915f300c664312c63fbar
आप हैश एल्गोरिथ्म में एक दोष की आवश्यकता होगी आपकी क्या अपेक्षाएं हैं। और वास्तव में, MD5 isn't very secure, तो यह संभव हो सकता है। लेकिन मुझे नहीं पता कि ज्ञात कमजोरियों में से कोई भी आप जो करना चाहते हैं उसमें मदद कर सकता है। यहां तक कि एक प्रीमेज हमले भी मदद नहीं करेगा, इसे 'चुने गए प्रीफिक्स प्रीमेज अटैक' की आवश्यकता होगी।
तो मुझे लगता है कि केवल एकमात्र व्यवहार्य तरीका (आज) ब्रूट फोर्स का उपयोग करना होगा।
यदि आप बाइनरी में 'सुरक्षा जोड़ें' का तरीका ढूंढ रहे हैं, हैश को ट्रंकेट करें और फिर ब्रूट फोर्स का उपयोग करें।
यह गलत है। – rook
@Rook: वास्तव में क्या गलत है, और क्यों? –
यह परिस्थितियों पर भी निर्भर करता है। यदि बाइनरी दी जाती है, और केवल एमडी 5 को किसी स्थान पर डाला जाना चाहिए, तो जवाब हो सकता है: 0. क्योंकि यह संभव हो सकता है (और मुझे लगता है कि यह लगभग इस तरह के सभी मामलों में हो सकता है) कि कोई एमडी 5 नहीं डाला गया है एक ही एमडी 5 पैदा करता है।
यदि आपके पास अधिक बाइनरी को संशोधित करने की संभावना है (उदाहरण के लिए पैडिंग स्पेस जो आप मनमानी संख्याओं से भर सकते हैं), केवल व्यवहार्य दृष्टिकोण ब्रूट फोर्स है।
इसे पूरा करने के लिए आपको collision मिलना होगा। यह the prefixing attack against md5 का उपयोग करके किया जा सकता है। ध्यान रखें यह केवल इसलिए संभव है क्योंकि एमडी 5 बहुत टूटा हुआ है। इस हमले में time complexity of 2^24.1 है, जो एक आधुनिक डेस्कटॉप की पहुंच के भीतर है।
आपको टकराव ढूंढना होगा, लेकिन एक सामान्य टक्कर (समान एमडी 5 हैश) नहीं, लेकिन संदेश के हैश कोड और (चुने गए) भाग की टक्कर है। यह बहुत कठिन है। –
इसे निरंतर समय में हल किया जा सकता है।
फ़ाइल जिसमें सभी संभावित MD5 digests शामिल हैं उस फ़ाइल का पाचन होता है।
हालांकि, यह मानते हुए कि एमडी 5 2^64 से बड़े संदेशों के लिए अच्छी तरह परिभाषित है, जो लंबाई पैडिंग का आकार है। –
आरएफसी 1321 एक सीमा का उल्लेख नहीं करता है। :) http://tools.ietf.org/html/rfc1321 –
मुझे लगता है कि यह ध्यान देने योग्य एक दिलचस्प बिंदु है, लेकिन मान लीजिए कि आपकी फ़ाइल में सभी संभावित MD5 हैंश शामिल नहीं हो सकते हैं? – atx
+1 अच्छा सवाल। – rook
संबंधित प्रश्न: http://stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x –