चूंकि आर्माडिलो केजेनिक था, पीएसपी को हैक कर लिया गया था और डेबियन में सभी डीएसए कीज़ से समझौता किया गया था। या फिर कमजोर PRNG और (EC) DSA के बारे में

लगभग सात साल पहले, आर्मडिलो नामक एक ट्रेडर के लिए एक प्रमुख जनरेटर के साथ एक संग्रह पटाखे के हाथों में गिर गया। उत्पाद के कुछ आभारी उपयोगकर्ताओं ने इसे स्थायित्व के लिए परीक्षण करना चाहा। और जहां आपको पटाखा मंच पर नहीं तो ऐसे दिलचस्प कोड का मुफ्त ऑडिट मिलेगा।

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

तो, यह यहाँ है , टाइटैनिक प्रयासों के माध्यम से प्राप्त एक मूल संग्रह। (सी में स्रोत)

भेद्यता क्या छिपी है, इसे समझने के लिए बिना सुराग के प्रयास करें। हालाँकि बहुत कोड है, लेकिन यह अच्छी तरह से पढ़ा जाता है। क्या काम नहीं कर रहा है? और अगर आप 528 लाइन को देखते हैं?

ठीक है, सबसे पहले कुंजी के कई प्रकार हैं। पुराने, नए, आदि। हम सबसे अच्छे लोगों में रुचि रखते हैं, तथाकथित शॉर्ट लेवल V10 ECC ने कुंजियों पर हस्ताक्षर किए हैं, जिसके लिए बड़ी संख्या के गणित और दीर्घवृत्त के साथ कक्षा का एक अच्छा आधा आरक्षित है। तो, हम ECDSA को तोड़ देंगे!

वक्र 112 बिट्स है, गुप्त कुंजी ( x ) भी 112 बिट्स है। ब्रूट फोर्स के लिए यह थोड़ा बहुत है।

लेकिन!

गुप्त मान PRNG से लिया जाता है, जिसे इनिशियलाइज़ किया जाता है ... टाडा! 32 बिट संख्या !

Matan

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

कुंजी में पैरामीटर ईसीडीएसए पैरामीटर एच, आर, एस हैं । एच - संदेश हैश, आर, एस - हस्ताक्षर पैरामीटर।

उन्हें वहां से कैसे प्राप्त किया जा सकता है, आप एक तरह से देख सकते हैं, केवल एक चीज यह है कि आर और एस को सी और डी में बुलाया जाता है।

तो, हमारे दो त्रैमासिक (आर, एस) एच और (आर ', एस') एच हैं '

(ईसी) डीएसए

मैं एक उदाहरण के रूप में डीएसए का उपयोग करके सूत्र दिखाऊंगा। भेद्यता का सार समान है और सूत्रों का सार समान है, वे बस अधिक पठनीय हैं।

(EC) DSA में गुप्त कुंजी यादृच्छिक संख्या x है । इसके अलावा (केवल पहले से ही डीएसए में), दो बड़े अपराधों का चयन किया जाता है:
q , जिसका आकार बिट्स में हैश फ़ंक्शन के आकार से मेल खाता है।
p ऐसा (p-1) q से विभाज्य है।
हम एक संख्या g को भी चुनते हैं जैसे कि इसका गुणन क्रम modulo p q (विकी लेख देखें)। लेकिन, हमें इसमें कोई दिलचस्पी नहीं है, बस यह संख्या सूत्रों में मिलेगी।

डिजिटल हस्ताक्षर बनाने के लिए, हम निम्नलिखित क्रियाएं करते हैं:

1. यादृच्छिक कश्मीर उत्पन्न करें
2. compute r = g ^k mod p mod q
3. s = k ^-1 (H ( m ) + x * r) mod q की गणना करें

जहां H ( m ) उस संदेश का हैश है जिसे हम साइन कर रहे हैं।

भेद्यता

मान लीजिए कि हम दो हस्ताक्षर दो समान आर के साथ मिले। s उन्हें निम्नानुसार माना जाता है:
s = k ^-1 (H (m) + x * r) mod q
s '= k ^-1 (H (m') + x * r) mod q

एक को दूसरे से घटाएँ (सभी ऑपरेशन मोडुलो किए जाते हैं)
s - s '= k ^-1 (h + x * r) - k ^-1 (h' + x * r)

अब, k को ब्रैकेट किया जा सकता है, क्योंकि यह समान है
s- s '= k ^-1 (h + x * r - h'– x * r)

एक्स * आर हटना
s- s '= k ^-1 (h- h')

लेफ्ट k को छोड़ दिया
k = (h- h ') / (s - s')

और, जैसा कि हम याद करते हैं, r = g ^k mod p mod q ।
यहाँ पूरी समस्या k में है । यदि यह ज्ञात है, तो आप सूत्र द्वारा गुप्त कुंजी x की गणना कर सकते हैं
x = (s * k) - h) * r ^-1 mod q

जो 2010 में fail0verflow द्वारा किया गया था, जैसा कि सोनी से zhoporukye एनकोडर केवल एक बार कश्मीर उत्पन्न करने के बारे में सोचा

अर्माडिलो के साथ, चीजें इतनी सरल नहीं थीं। आर हमेशा अलग थे, लेकिन इस तथ्य के कारण कि जनरेटर को 32-बिट संख्या के साथ आरंभीकृत किया गया था, कुल विकल्पों की संख्या 2 ^{32 थी} , जिसने गणना को कई घंटों का मामला बना दिया था।

खोज एल्गोरिथ्म (सभी ऑपरेशन मोडुलो):

1. ज ’= -ह
2. r '= r ^-1
3. s '= s * r'
4. h '= h' * r '
5. हम चक्र को 0 से 2 ³² -1 तक और उसमें शुरू करते हैं:
6. हम आरएनजी काउंटर शुरू करते हैं
7. संख्या k उत्पन्न करें
8. गणना एक्स = ((एस * के) - एच) * आर ^-1 मॉड क्यू
9. इस x को बचाओ

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

उसी तरह, डेबियन में किसी भी प्रमुख जोड़ी की गणना करना संभव था, जब 2008 में यह पता चला कि ओपनएसएसएल में एक बग के कारण, PRNG को 0-2 ¹⁵ की सीमा में एक संख्या के साथ आरंभीकृत किया गया था। यह आयुध के साथ की तुलना में भी आसान है। और 2006 से 2008 तक समावेशी से डेबियन द्वारा उत्पन्न सभी डीएसए कुंजियों में समझौता किया गया था ।

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

मुझे उम्मीद है कि यह दिलचस्प था। अपने PRNG का ख्याल रखें।

पुनश्च

यहाँ एक ही आर्मडिला और मेरे नाम की दो वैध कुंजियों के साथ एक संग्रह है। आप घर के काम के रूप में अपने लिए एक कुंजी बनाने की कोशिश कर सकते हैं।
80 lvl के लिए: एक कुंजी करें। और क्या, काफी एक olympiad समस्या