📓 🧜 ✋🏾 75 गीगाबाइट तत्काल खोज 😔 🤲🏾 👏🏾

यह इस बारे में होगा कि इस पृष्ठ पर डेटा के बड़े संस्करणों पर एक त्वरित खोज कैसे लागू की गई थी। वहां आप PvPGN गेम सर्वर के लिए हैश पासवर्ड खोज सकते हैं और समान हैश जनरेट कर सकते हैं।
खोज शुद्ध PHP में, मॉड्यूल और एक तृतीय-पक्ष डेटाबेस के उपयोग के बिना लिखा गया है। सिद्धांत रूप में, इस तरह से आप कई टेराबाइट्स में वॉल्यूम बढ़ा सकते हैं, एक जगह होगी - गति को इससे अधिक नुकसान नहीं होगा।

इसके अलावा, शुरुआत से अंत तक, पूरी प्रक्रिया का वर्णन किया गया है, जिसमें क्रूर बल शामिल है, तालिका का एक हैश बनाना, इसे सॉर्ट करना, और वास्तव में, खोज करना।

bruteforce

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

मैं C # में bruteforce का सबसे सरल उदाहरण दूंगा, एमडी 5 हैश खोज के लिए पासवर्ड सॉर्ट कर रहा हूं। और एक अनसुलझी तालिका की पीढ़ी केवल एक सीएसवी फ़ाइल में उत्पन्न डेटा को जोड़ने के लिए नीचे आती है।

class Program { static bool _isFound = false; static string _findHash; static string _symbols; static int _pass_lenght; static void Main(string[] args) { _findHash = args[0]; //   _pass_lenght = int.Parse(args[1]); //    _symbols = args[2]; //     byte[] data = new byte[_symbols.Length]; Process(data, 0); Console.ReadLine(); } private static string hash; private static byte[] data_trim; private static string pass; //   static void Process(byte[] data, int index) { //     if (index == _pass_lenght) { data_trim = data.TakeWhile((v, idx) => data.Skip(idx).Any(w => w != 0x00)).ToArray(); //     pass = Encoding.ASCII.GetString(data_trim); hash = GetHash(pass); Console.Write("{0} ", pass); if (hash == _findHash) { _isFound = true; Console.WriteLine("\n\nPassword was found!\n\t{0} = {1}", hash, pass); } return; } //    foreach (byte c in _symbols) { if (_isFound) return; data[index] = c; Process(data, index + 1); } } //  md5 hash   static string GetHash(string value) { MD5 md5 = new MD5CryptoServiceProvider(); byte[] output = md5.ComputeHash(Encoding.ASCII.GetBytes(value)); return BitConverter.ToString(output).Replace("-", "").ToLower(); // hex string } }

स्रोत लिंक के साथ एक उदाहरण।
भागो: BruteForce.exe [search_hash] [password_length] [password_characters]

छंटाई

अब हैश द्वारा डेटा को सॉर्ट करना आवश्यक था, क्योंकि परिणाम एक द्विआधारी खोज होगी जो केवल सॉर्ट किए गए डेटा के साथ काम करता है।
दो बार सोचने के बिना, मैंने अपने कंप्यूटर पर MySQL में 5 जीबी डेटा का परीक्षण किया। सूचकांक नहीं बना, बस एक निर्यात सीएसवी के निर्यात के साथ छंटनी शुरू हुई:

 SELECT hash, pass INTO OUTFILE 'd:\\result.csv' FIELDS TERMINATED BY ',' OPTIONALLY ENCLOSED BY '' LINES TERMINATED BY '\n' FROM hashes ORDER BY hash

उसे 16 घंटे लग गए, और जब ऐसा किया गया, तो 2 फाइलें TEMP फ़ोल्डर में बनाई गईं: 16 और 25 गीगाबाइट।
लेकिन यहां तक कि सूचकांक के साथ (जो कुछ घंटों के लिए बनाया गया था), यह विकल्प अभी भी मुझे सूट नहीं करता था, कम से कम छंटाई के दौरान अवशोषित गीगाबाइट के कारण, क्योंकि जब तालिकाओं का आकार बढ़ता है, तो मेरी डिस्क पर बस पर्याप्त जगह नहीं होगी।

मैंने SQLite में एक तालिका बनाने की कोशिश की, लेकिन यह बड़े संस्करणों के लिए डिज़ाइन नहीं किया गया है, इसलिए इसने बहुत धीमी गति से काम किया (1 जीबी में हैश खोज में लगभग 6 सेकंड लगे)। MySQL तेज है, लेकिन दोनों ही मामलों में यह अंतिम आकार के अनुरूप नहीं था, जो मूल डेटा (सूचकांक के साथ) से लगभग 2 या अधिक बार था।

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

मैंने अन्य छंटाई के तरीकों की तलाश शुरू की, विलय और एक पिरामिड उपयुक्त निकला। मैंने उनके हाइब्रिड को लागू करना शुरू कर दिया, लेकिन गलती से सॉर्ट यूटिलिटी के बारे में जानकारी मिली, जो कि डिफ़ॉल्ट रूप से एक्सपी के साथ शुरू होकर विंडोज के साथ आती है। जैसा कि यह निकला, वह आदर्श रूप से मेरे कार्य के अनुकूल था! मुझे नहीं पता कि यह कैसे काम करता है, लेकिन विवरण कहता है कि यह फ़ाइल को एक पास में सॉर्ट करता है (5 जीबी आधे घंटे में सॉर्ट किया जाता है)। सॉर्टिंग प्रक्रिया के दौरान, उपयोगिता के लिए मूल फ़ाइल के वजन (एक अस्थायी फ़ाइल के लिए) के रूप में अतिरिक्त अतिरिक्त स्थान की आवश्यकता होती है।

लेकिन यहाँ सब कुछ सहज नहीं था। जब 190 जीबी फ़ाइल को सॉर्ट किया गया था, तो यह 3 गुना अधिक जगह ले गया, और मैंने डिस्क स्थान खाली करने के लिए कुछ खोजना और हटाना शुरू कर दिया। इसके अलावा, अंतिम फ़ाइल में अजीब "कलाकृतियां" दिखाई दीं:

वे फ़ाइल के यादृच्छिक भागों में लगभग 10 तक समाप्त हो गए। मैंने कई बार छांटना शुरू किया, हर बार 24 घंटे इंतजार किया, लेकिन कलाकृतियां फिर भी दिखाई दीं। मुझे समझ नहीं आया कि ऐसा क्यों हुआ, मेरे पास 12 जीबी रैम, विन 7 एक्स 64 है, उस समय कंप्यूटर ने एक सप्ताह तक बिना बंद किए काम किया। मैं मान सकता हूं कि इस समय के दौरान स्मृति "भरा हुआ" है, क्योंकि सिस्टम को रिबूट करने के बाद, पहली बार समान छंटाई सफल रही।

खोज

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

बाइनरी (उर्फ बाइनरी) खोज निम्न सिद्धांत द्वारा काम करती है:

सरणी को 2 हिस्सों में विभाजित किया गया है और पढ़ने की स्थिति मध्य में चलती है।
वर्तमान मूल्य, जो मध्य में पाया जाता है, की तुलना वांछित के साथ की जाती है
यदि वांछित> वर्तमान, तो सरणी का दूसरा आधा भाग लिया जाता है, यदि वांछित <वर्तमान - पहली छमाही।
हम इस सरणी के आधे हिस्से के साथ 1 से 3 चरण करते हैं।

और, ज़ाहिर है, बाइनरी खोज के लिए मुख्य शर्त यह है कि सरणी को खोज कुंजी द्वारा क्रमबद्ध किया जाना चाहिए।

किसी फ़ाइल में, बाइनरी खोज बिल्कुल उसी तरह काम करती है। हम fseek फ़ंक्शन के साथ फ़ाइल के मध्य में ऑफसेट स्थिति को स्थानांतरित करते हैं और स्थिति को लाइन की शुरुआत में समायोजित करते हैं (यदि हम रिकॉर्ड के बीच में हिट करते हैं), तो पूरी तरह से वहां स्थित रिकॉर्ड पढ़ें।

यह इस पर रोकना संभव होगा, अगर एक BUT के लिए नहीं ...

विभाजन

PHP_INT_MAX (2147483647 बाइट्स) के मान से अधिक फ़ाइलों के लिए एक खोज संभव नहीं थी। इसके अलावा, कभी-कभी fseek फ़ंक्शन -1 देता है, और कभी-कभी इसके साथ सब कुछ ठीक होता है, लेकिन ऑफसेट स्पष्ट नहीं है कि कहां है। नतीजतन, यह बिल्कुल भी नहीं है कि क्या आवश्यक है। बग स्पष्ट नहीं था, लेकिन समस्या को खोजने की प्रक्रिया में, मुझे बगट्रैक में जानकारी मिली। Fseek फ़ंक्शन के लिए PHP प्रलेखन साइट पर एक टिप्पणी भी है जो 2 जीबी (fseek64 फ़ंक्शन) से बड़ी फ़ाइलों की खोज करती है। यह फ़ाइल की शुरुआत से पढ़ने के लिए नीचे आता है, लेकिन वर्तमान ऑफसेट से वांछित स्थान पर, पुनरावृत्ति द्वारा। लेकिन मैंने जाँच की, यह भी काम नहीं करता है।

मुझे फाइलों को भागों में विभाजित करना पड़ा। मुझे फ़ाइल को तोड़ने के लिए एक उपयुक्त उपयोगिता नहीं मिली (मैंने संभवतः खराब खोज की, लेकिन खोज के पहले पृष्ठ पर केवल संदिग्ध स्थापनाएं थीं)। विंडोज के शस्त्रागार में, अजीब तरह से पर्याप्त, ऐसी कोई उपयोगिता नहीं है। कुल कमांडर में बाइट्स द्वारा तोड़ना असंभव है, लेकिन मुझे सटीकता की आवश्यकता थी।
मैंने C # में एक साधारण उपयोगिता लिखी है जो बाइट द्वारा स्रोत फ़ाइल को पढ़ता है और उन्हें दिए गए आकार की अलग-अलग फ़ाइलों में क्रमिक रूप से डालता है।

शायद किसी को इसकी आवश्यकता है, यहां स्रोत से डाउनलोड करें ।
चलाएँ: Split.exe [फ़ाइल] [in_bytes]

दबाव

शुरू करने के लिए, मैंने सॉर्ट किए गए डेटा को दो अलग-अलग फ़ाइलों में विभाजित किया है: .hash, .pass, जिसमें क्रमशः उनके लिए हैश और पासवर्ड संग्रहीत हैं। फिर, मैंने अभी सभी डेटा को एक हेक्स में "पैक" किया है। संख्याओं को 2 बार तक इस तरह आसानी से पैक किया जाता है, और चूंकि प्रत्येक मान की लंबाई तय की जाती है, इसलिए 0xF को लापता अंतराल में जोड़ा जाता है।

संपीड़न कैसे किया जाता है, और खोज कैसे की जाती है, निम्न उदाहरण में स्पष्ट रूप से दिखाई देता है (हम हैश के लिए पासवर्ड की तलाश कर रहे हैं 0dd5eac5b02376a456907c705c6f6fb0b5b67cf):

0D D5 EA - हैश के पहले 6 अक्षर। इस तरह डुप्लिकेट हैश होगा, लेकिन इतने सारे नहीं। और चूंकि पासवर्ड सभी सहेजे जाते हैं, यहां तक कि एक हजार पासवर्ड से भी, आप बहुत जल्दी मूल हैश को पुनर्स्थापित कर सकते हैं।

70 FF - 70 नंबर यहां पैक किया गया है, यह पासवर्ड की संख्या है जो 0dd5ea से शुरू होने वाले हैश के लिए डिजिटपास फ़ाइल में समाहित है

59 99 95 68 FF FF - संख्या 59999568 यहां पैक की गई है, यह डिजिटपास फ़ाइल में पासवर्ड पढ़ने की शुरुआत की स्थिति है

11a19a90 - वह स्थिति जिसमें से डिजिटलीपास फ़ाइल में 70 पासवर्ड का पढ़ना शुरू होता है; इसकी गणना इस प्रकार की जाती है: 59999568 * 5 (किसी भी पासवर्ड की लंबाई पहले से ही संकुचित, बाइट्स में) = 299997840 (हेक्स में अनुवाद)

84 04 05 38 8F - नंबर 840405388 यहां पैक किया गया है, यह वांछित हैश के अनुरूप पासवर्ड है

फिर मैंने भागों में .pass फ़ाइल को विभाजित किया ताकि पासवर्ड फ़ाइल के अंत में छोटा न हो, और PHP_INT_MAX: 2147483647 - (2147483647% पासवर्ड का आकार) बाइट्स से आगे न जाए।
.Hash फ़ाइल का अधिकतम आकार 185 एमबी था, और इसे तोड़ना नहीं था।

वास्तव में, अब खोज केवल .hash फ़ाइलों में की जाती है, और केवल पासवर्ड .pass (फ़ाइल में एक निश्चित स्थिति से) से लोड किए जाते हैं। लेकिन यह इस लेख के मुख्य विषय को नकारता नहीं है, मैंने कच्चे डेटा पर जांच की गति कम नहीं थी।

सभी कच्ची फ़ाइलों का वजन 260 जीबी था, और संपीड़न के बाद यह 70 जीबी निकला। इस आकार में अक्षरों के साथ संख्याओं के 1 से 6 अक्षर और 7 से 10 वर्णों के पासवर्ड शामिल हैं - केवल संख्याएँ, कुल लगभग 13.5 बिलियन पासवर्ड। बाद में मैंने एक और 100 मिलियन शब्दावली शब्द जोड़े। नतीजतन, एक असली PvPGN सर्वर से लगभग 90% पासवर्ड स्थित होना चाहिए (मेरे पूर्व PvPGN सर्वर से 93.5% पाया गया)।

थोड़ा अनुकूलन

एक अच्छे व्यक्ति ने PvPGN हैश फ़ंक्शन को PHP से जावास्क्रिप्ट में पोर्ट किया (उसने मुझे टेबल के लिए 250 जीबी स्पेस के साथ एक वर्चुअल सर्वर भी प्रदान किया)।

मैंने विभिन्न हैश कार्यान्वयन के प्रदर्शन माप लिए:

विभिन्न भाषाओं में कार्यान्वयन harpywar.pvpgn.pl/?do=hash डाउनलोड करने के लिए उपलब्ध हैं
जाहिर है, सी सबसे तेज है। सभी ब्राउज़रों में, गति लगभग समान है, हालांकि फ़ायरफ़ॉक्स स्क्रिप्ट की अवधि के लिए लटका हुआ है।

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

परिणाम

बड़े डेटा सेट, या यहां तक कि टर्नकी समाधान खोजने के लिए अन्य तरीके हैं। लेकिन एक विशिष्ट कार्य के लिए, मेरा कार्यान्वयन बहुत तेजी से हुआ, और जो बहुत महत्वपूर्ण है - काफी कॉम्पैक्ट। मैंने इस पर लगभग एक सप्ताह बिताया, जिसमें पृष्ठभूमि निर्माण और तालिकाओं की छंटाई शामिल है।

यह शायद कुछ बनाने का सबसे उपयुक्त उदाहरण नहीं है, क्योंकि बहुत सारे वर्णों वाले पासवर्ड को अपेक्षाकृत जल्दी से हल किया जाता है यदि ब्रूटफोर्स कोड को समानांतर और GPU के लिए पोर्ट किया जाता है।
लेकिन इस प्रक्रिया में मुझे बहुत ज्ञान और अनुभव मिला, जिसे मैं साझा करना चाहता था।

अद्यतन

- जो लोग रुचि रखते हैं, उनके लिए मैंने पीएचपी स्रोतों को रखा है, लेकिन टेबल फ़ाइलों के बिना, उनका अध्ययन दिलचस्प नहीं हो सकता है: index.php , hashcrack.class.php ।

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

- मैंने कुल कमांडर के साथ एक गलती की - इसकी मदद से, आप अभी भी फाइल को भागों में बाइट्स ( जोशुआ 5 द्वारा सुझाए गए) द्वारा विभाजित कर सकते हैं।

- मैं विभिन्न डेटाबेस की विशेषताओं से बहुत परिचित नहीं हूं, यही वजह है कि खोज लंबी थी।
एलेक्सी पेचनिकोव हमें बताते हैं कि SQLite पर, प्रदर्शन बहुत अधिक हो सकता है , लेकिन तालिका के लिए आपको "fts4" का उपयोग करना होगा। MySQL में शायद कुछ ऐसा ही है।

- नीचे दी गई टिप्पणियों में, डेटा और खोज को बेहतर ढंग से व्यवस्थित करने के बारे में विचार हैं।

- वेबस्टर से टिप्पणी पूरी तरह से दर्शाती है कि मैं इस विषय में क्या दिखाना चाहता था

75 गीगाबाइट तत्काल खोज