एप्लाइड क्रिप्टोग्राफी। हमने 300 हजार डॉलर के लिए बिटकॉइन को कैसे पुनर्स्थापित किया

मैं आपके साथ अपनी एक कहानी साझा करूंगा। लगभग बीस साल पहले, मैंने भौतिकी में एक डिग्री प्राप्त की, लेकिन रिवर्स इंजीनियरिंग और क्रिप्टानालिसिस में व्यस्त था। हमारी कंपनी AccessData 90 के दशक के अंत और 2000 के दशक की शुरुआत में काम करती थी। तब अमेरिकी सरकार ने धीरे-धीरे क्रिप्टोग्राफी के निर्यात पर प्रतिबंध हटा दिया, हालांकि, अधिकांश कार्यक्रमों में पासवर्ड सुरक्षा अभी भी बेकार थी। हमने कार्यालय कार्यक्रम लिया, मैंने रिवर्स इंजीनियरिंग का प्रदर्शन किया और एन्क्रिप्शन एल्गोरिथ्म का पता लगाया, और फिर क्रिप्टोग्राफिक सुरक्षा को तोड़ दिया।

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

मुझे विशेष रूप से दो प्रोजेक्ट याद हैं। पहला Microsoft Word 97 था। प्रकट होने से पहले, फाइलें XOR बाइट्स ऑफ क्लीयर टेक्स्ट और एक 16-बाइट स्ट्रिंग जो कि पासवर्ड से आउटपुट थी, का उपयोग करके एन्क्रिप्ट की गई थीं। एक वर्ड फ़ाइल में सबसे आम बाइट्स आमतौर पर 0x00, 0xFF, या 0x20 (स्थान) थे, इसलिए हमने प्रत्येक कॉलम में सबसे आम चरित्र को चुना और 3 से ¹⁶ विकल्पों की जांच की। प्रमुख वसूली आमतौर पर तुरंत हुई, लेकिन ताकि लोगों को यह न लगे कि उनके पास पैसा बर्बाद हो गया है, हमने हॉलीवुड हैकर के दृश्य के समान एक छोटा सा एनीमेशन डाला जिसमें बहुत सारे यादृच्छिक अक्षर हैं, जिससे सही पासवर्ड धीरे-धीरे उभरता है।

Microsoft Word 97 ने सब कुछ बदल दिया है। शायद MSDN ने एन्क्रिप्शन प्रारूप का भी खुलासा किया था, लेकिन हमारी छोटी कंपनी सदस्यता नहीं ले सकी। और इस तथ्य से नहीं कि हमें सूचना प्राप्त करने के बाद हैकिंग के लिए एक कार्यक्रम लिखने की अनुमति होगी। समझने के लिए, सॉफ्टि में मैंने पासवर्ड दर्ज करने के तुरंत बाद एक ब्रेकपॉइंट सेट किया, और फिर धीरे-धीरे स्टैक ऊपर ले गया जब तक कि मुझे एक एल्गोरिथ्म नहीं मिला। यह आईडीए प्रो की रिलीज़ से पहले था, इसलिए मेरे पास मेरी दीवार पर एक लाल मार्कर के साथ कोडांतरक कोड वाले दर्जनों प्रिंटआउट थे। मुझे बहुत खुशी हुई जब मैंने आखिरकार इसका पता लगा लिया। उस समय, Microsoft को केवल 40-बिट क्रिप्टोग्राफी निर्यात करने की अनुमति दी गई थी, इसलिए कंपनी ने कर्तव्यनिष्ठा से सख्ती से लागू क्रिप्टोग्राफी को लागू किया: उन्होंने "नमक" (फ़ाइल से बेतरतीब ढंग से चयनित बाइट्स) का उपयोग करते हुए एमडी 5 में पासवर्ड को दोहराया है।एक 40-बिट कुंजी प्राप्त करने के लिए, फिर उसमें नमक मिलाया गया और फिर से हैशेड किया गया। उस समय के कंप्यूटरों पर पासवर्ड की जाँच में लगभग आधा सेकंड लगता था। हमें एक शब्दकोश हमले का उपयोग करना पड़ा क्योंकि यह क्रूर बल के साथ पासवर्ड क्रैक करना लगभग असंभव था। नतीजतन, हमने बड़ी कंपनियों और एजेंसियों के लिए एक पासवर्ड क्रैकर लिखा। कार्यक्रम ने इन फैंसी MMX पेंटियम निर्देशों का उपयोग करके 40-बिट कुंजी स्थान के bruteforce को निष्पादित किया। मैंने सुना है कि एक बार उसने पासवर्ड उठाने से पहले नौ महीने तक काम किया।कार्यक्रम ने इन फैंसी MMX पेंटियम निर्देशों का उपयोग करके 40-बिट कुंजी स्थान के bruteforce को निष्पादित किया। मैंने सुना है कि एक बार उसने पासवर्ड उठाने से पहले नौ महीने तक काम किया।कार्यक्रम ने इन फैंसी MMX पेंटियम निर्देशों का उपयोग करके 40-बिट कुंजी स्थान के bruteforce को निष्पादित किया। मैंने सुना है कि एक बार उसने पासवर्ड उठाने से पहले नौ महीने तक काम किया।

एक और वास्तव में मजेदार परियोजना ज़िप अभिलेखागार है। PKZIP के निर्माता फिल काट्ज ने उस समय के लिए अपनी फ़ाइल प्रारूप का दस्तावेजीकरण करने और सॉफ़्टवेयर पैकेज में इस प्रलेखन को शामिल करने के लिए एक असामान्य निर्णय लिया, जिसने ज़िप को डेवलपर्स के लिए एक पसंदीदा प्रारूप बना दिया। रोजर स्कलाफली ने अभिलेखागार को एन्क्रिप्ट करने के लिए एक स्ट्रीम सिफर विकसित किया। ज़िप मानक जल्दी से विंडोज के तहत सबसे लोकप्रिय हो गया, और कई अन्य प्रारूप, जैसे कि .jar जावा फाइलें और ओपनऑफिस दस्तावेज, वास्तव में अंदर विशिष्ट निर्देशिका संरचना के साथ ज़िप फाइलें थीं। कार्यक्रम के ओपन सोर्स संस्करण को इन्फोज़िप कहा गया, यह लगभग सभी मालिकाना ज़िप अभिलेखागार का आधार था, जैसे कि विनज़िप। जब मैंने WinZip को हैक करना शुरू किया, तो इसने बाजार के 95% हिस्से पर कब्जा कर लिया।

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

ज़िप सिफर में आंतरिक बिट्स के 96 बिट्स होते हैं, जिन्हें तीन 32-बिट ब्लॉक में विभाजित किया जाता है key0, key1औरkey2। पहली और तीसरी CRC32 की दो प्रतियों की आंतरिक स्थिति है, प्रतिक्रिया के साथ एक रैखिक बदलाव रजिस्टर (एक सरल गणितीय मॉडल जो आपको छद्म आयामी अनुक्रम बनाने की अनुमति देता है)। संक्षेप में, डेटा की एक नई बाइट के साथ राज्य को अपडेट करने के लिए, आप सब कुछ एक बाइट (निचली बाइट को छोड़ते हुए) से नीचे स्थानांतरित करते हैं, और फिर XOR के साथ डेटा बाइट के बाद XOR को निचले बाइट के साथ अनुक्रमित करते हैं। key1एक काट-छाँट रैखिक रैखिक संघटक (टीएलसीजी) की आंतरिक स्थिति है। इसकी आंतरिक स्थिति को अपडेट करने के लिए, हम डेटा का एक बाइट जोड़ते हैं, एक स्थिर से गुणा करते हैं, जिसे हम कॉल करेंगेc, और एक जोड़ें। सिफर निम्नानुसार कार्य करता है: पहले CRC32 में डेटा बाइट दर्ज करें, फिर लो बाइट लें और इसे TLCG में दर्ज करें, फिर वहाँ से ऊपरी बाइट लें और इसे दूसरी CRC32 में दर्ज करें, फिर राज्य और वर्ग (लगभग) लें, और फिर दूसरा बाइट जारी करें। बाइट की एक धारा में परिणाम। आंतरिक स्थिति के 96 बिट्स को आरंभ करने के लिए, आप एक ज्ञात स्थिति से शुरू करते हैं और पासवर्ड को एन्क्रिप्ट करते हैं, और फिर नमक के दस बाइट्स को एन्क्रिप्ट करते हैं।

PKZIP अपने नमक बाइट्स को प्राप्त करता है, स्मृति को बिना इसे आबंटित किए, इसलिए इसमें अन्य चल रहे कार्यक्रमों या छवियों, या दस्तावेजों से सामग्री के बिट्स शामिल हैं, जो भी हो। यह विंडोज पर ठीक काम करता है, लेकिन कई यूनिक्स सिस्टम पर, मेमोरी आवंटित होने पर स्वचालित रूप से प्रारंभ हो जाती है। InfoZIP फ़ंक्शन का उपयोग करके नमक बाइट्स का चयन करता हैrandसी भाषा। उन्होंने प्रक्रिया आईडी पर XOR टाइमस्टैम्प बनाकर यादृच्छिक संख्या जनरेटर की स्थिति को आरंभ किया, और फिर प्रति फ़ाइल दस बाइट्स उत्पन्न किए। इस मामले में, टाइमस्टैम्प और प्रक्रिया पहचानकर्ता को जानना, यह संभव था, सैद्धांतिक रूप से, हेडर के बाइट्स को पुनर्प्राप्त करने के लिए, जो बदले में, बेहम और कोचर पर हमला करना संभव बनाता था। ऐसा लगता है कि InfoZIP लेखकों को इस हमले के बारे में पता था क्योंकि वे एक कदम आगे बढ़ गए थे - और पासवर्ड का उपयोग करके हेडर को एन्क्रिप्ट किया था। इस प्रकार, हमलावर के पास केवल दो बार एन्क्रिप्टेड प्लेनटेक्स्ट था, और हमले ने काम नहीं किया होगा।

मैंने इस पर ध्यान दिया, क्योंकि पासवर्ड दोनों पासों में समान है, धारा का पहला बाइट उनमें से प्रत्येक में समान है। उसी तरह से जब प्रकाश स्विच दो बार स्विच किया जाता है, तो यह वही रहता है जहां यह शुरुआत में था, जब बाइट को XOR को उसी स्ट्रीम बाइट के साथ दोहराया जाता है, तो यह अछूता रहता है। इसने मुझे केवल सिफरटेक्स्ट पर एक बहुत शक्तिशाली हमले को विकसित करने की अनुमति दी : संग्रह में पांच एन्क्रिप्टेड फाइलें प्राप्त कीं , मैं फ़ंक्शन की आंतरिक स्थिति का उत्पादन कर सकता था।randसमय की मोहर लगने या प्रक्रिया आईडी को जाने बिना। तब मैं मूल unencrypted हेडर उत्पन्न कर सकता था। चूंकि सिफर के प्रत्येक भाग में बस कुछ बिट्स अगले भाग को प्रभावित करते हैं, इसलिए मैं स्थिति के कुछ बिट्स का भी अनुमान लगा सकता हूं और जांच कर सकता हूं कि क्या अगले बाइट्स को दो बार डिकोड करने से वह उत्तर मिलता है जिसकी मुझे उम्मीद थी। जैसे-जैसे मैं आगे बढ़ा, मुझे चाबी के कम और कम टुकड़ों का अनुमान लगाना पड़ा। प्रत्येक अतिरिक्त फ़ाइल को अधिक संभावित प्रमुख सामग्रियों को बाहर करने की भी अनुमति है; उस समय, एक डेस्कटॉप पर कई घंटे लगते थे। मैंने इस बारे में एक लेख प्रकाशित किया और इसे 2001 के फास्ट सॉफ़्टवेयर एनक्रिप्शन में जापान में प्रस्तुत करने का अवसर मिला।

जल्द ही मैंने AccessData छोड़ दिया, एक साल के लिए न्यूरल नेटवर्क पर एक स्टार्टअप के लिए काम किया, तीन साल तक क्रिस कलौड के साथ ऑकलैंड विश्वविद्यालय में कंप्यूटर विज्ञान में मास्टर डिग्री की पढ़ाई की, कैलिफोर्निया यूनिवर्सिटी के रिवरसाइड में गणितीय भौतिक विज्ञानी जॉन बैज के साथ छह साल तक काम किया। Google की एप्लाइड सिक्योरिटी टीम के हिस्से के रूप में, उन्होंने अपनी डॉक्टरेट पूरी की और कुछ साल बाद नए स्टार्टअप के सीटीओ बन गए।

लगभग आधे साल पहले, मुझे काफी अप्रत्याशित रूप से एक रूसी व्यक्ति से लिंक्डइन पर एक संदेश मिला। उन्होंने वह लेख पढ़ा जो मैंने 19 साल पहले लिखा था और जानना चाहता था कि क्या हमला एक संग्रह पर काम करेगा जिसमें केवल दो फाइलें हों। एक त्वरित विश्लेषण से पता चला कि इसके लिए भारी मात्रा में कंप्यूटिंग शक्ति और धन की आवश्यकता है। चूंकि चयन के प्रत्येक चरण में केवल दो फाइलें हैं, इसलिए बहुत अधिक झूठी सकारात्मकताएं हैं। परीक्षण के लिए परिणाम ^2,773 संभावित कुंजी है, लगभग 10 sextillion। मैंने गणना की कि GPU पर एक बड़ा क्लस्टर एक वर्ष के लिए काम करेगा, और इसकी लागत लगभग 100 हजार डॉलर होगी। उसने मुझे मारा, यह कहते हुए कि वह कुंजी को बहाल करने के लिए इतने पैसे खर्च करने के लिए सहमत हो गया।

तथ्य यह है कि जनवरी 2016 में, उन्होंने लगभग 10-15 हजार डॉलर में बिटकॉइन खरीदे और इनक्रिप्टेड ज़िप फाइल में चाबियां रखीं। अब उनकी लागत $ 300 हजार से अधिक थी, और वह पासवर्ड याद नहीं रख सके। सौभाग्य से, उसके पास अभी भी मूल लैपटॉप था, और वह वास्तव में एन्क्रिप्शन समय जानता था। चूंकि InfoZip एक टाइमस्टैम्प के आधार पर एन्ट्रॉपी प्राप्त करता है, इसने संभावित कुंजी विकल्पों की संख्या को "केवल" 10 क्विंटल तक कम करने का वादा किया है - और औसतन GPU फार्म पर कुछ महीनों में हमले को काफी संभव बना दिया है। हमने एक अनुबंध पर हस्ताक्षर किए और मुझे काम मिला।

मैंने लेख में वर्णित हमले को ठीक करने में कुछ समय बिताया। मेरे चैरगिन के लिए, कुछ मुश्किल विवरण थे जो मैंने लेख में याद किए, लेकिन मैंने उन्हें फिर से काम किया। और फिर मुझे पता चला कि मैंने गणना की मात्रा का मूल्यांकन करने में एक भयानक गलती की थी!

अपने मूल हमले में, मैंने चाबियाँ की 1 के उच्च बाइट्स का अनुमान लगाया। कुंजी ¹ , सी, की 1 · सी ² , की 1 · सी ³ और की 1 · सी ⁴ । जब तक मैंने इस चौथे बाइट का अनुमान लगाया, तब तक मुझे बाकी के सिफर की पूरी स्थिति का पता था; मुझे बस इन चार बाइट्स को मूल key1 में बदलने की जरूरत है, और यह है। मैं key1 के लिए 32-बिट स्थिति पर जाऊंगा और प्रत्येक को यह देखने के लिए जांचूंगा कि क्या यह सही उच्च बाइट्स देता है। हालाँकि, यहाँ क्विंटिलियन कुंजियों की जाँच करनी होगी; यदि आपको प्रत्येक पर 2 ³² परीक्षण करने की आवश्यकता है , तो इसमें कई सौ साल लगेंगे।

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

कम से कम यही विचार है। एकमात्र सही परिणाम प्राप्त करने में पाँच बाइट्स लगे और उस समय मेरे पास केवल चार हमले थे। लेख में वर्णित प्रक्रिया ने शायद ही कभी सही उत्तर दिया। हालांकि, मुझे पता था कि उत्तर सही एक के करीब होना चाहिए, इसलिए मैं key1 के सभी संभावित मूल्यों पर जा सकता हूं और वास्तविक उत्तर और सच्चे एक के बीच अंतर की जांच कर सकता हूं। अंतर हमेशा 36 वैक्टर में से एक रहा है! इस अनुकूलन के साथ, मैं खोज को चार अरब के बजाय केवल 36 विकल्पों में कम कर सकता हूं। हम अभी भी व्यापार में हैं।

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

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

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

हमला दस दिनों तक चला और विफलता में समाप्त हुआ।

मेरा दिल टूट गया था। क्या हम संभावित चाबियों में से एक को याद कर रहे हैं? हम वापस गए और अपने लैपटॉप पर अधिकतम प्रक्रिया पहचानकर्ता को देखा और पाया कि यह हमारी अपेक्षा से कई बिट अधिक था, और इसलिए इसके लिए कुछ अधिक संभावित स्रोत बीज थे rand। मैंने हमारे सभी कोड को डबल-चेक किया। शायद हम कुछ याद किया? शायद सीपीयू पर संस्करण जीपीयू की तुलना में किसी तरह अलग तरीके से काम करता है? अंत में, मैंने पाया कि जब उम्मीदवार सूची में दूसरे स्थान पर था, तो GPU पर संस्करण सही कुंजी नहीं पा सकता था, लेकिन केवल पहले। कोड के माध्यम से अफवाह करते हुए, हमने पाया कि हमने डेटा संरचना में ऑफसेट की गणना करते समय ब्लॉक इंडेक्स को स्ट्रीम इंडेक्स के साथ भ्रमित किया था।

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

अब मुझे काम की तलाश है। यदि आपको तकनीकी विश्लेषण या अनुकूलन के साथ दिलचस्प समस्याएं हैं, तो मुझे बताएं।

---