यादृच्छिक और छद्म यादृच्छिक संख्या जनरेटर के बारे में विस्तार से

यादृच्छिक संख्या जनरेटर की भेद्यता पर लेख अक्सर Habré और नेटवर्क पर दिखाई देने लगे। यह विषय अत्यंत व्यापक है और क्रिप्टोग्राफी में मुख्य में से एक है। कट के तहत ए से जेड तक यादृच्छिक संख्याओं का वर्णन है। लेख एक पश्चिमी ब्लॉग और लेखक के व्यक्तिगत परिवर्धन से लेखों की एक श्रृंखला के मुफ्त अनुवाद का परिणाम है। मुख्य लक्ष्य फीडबैक प्राप्त करना और ज्ञान साझा करना है।

परिचय

रैंडम नंबर जनरेटर वेब सुरक्षा का एक महत्वपूर्ण हिस्सा है। उपयोग की एक छोटी सूची:

• सत्र जनरेटर (PHPSESSID)
• कैप्चा टेक्स्ट जनरेशन
• एन्क्रिप्शन
• पासवर्ड भंडारण के लिए अपरिवर्तनीय नमक पीढ़ी
• पासवर्ड जनरेटर
• ऑनलाइन कैसीनो में कार्ड वितरित करने की प्रक्रिया

गैर-आयामी से संख्याओं के यादृच्छिक क्रम को कैसे अलग किया जाए?

संख्याओं का एक क्रम दें: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 । क्या वह यादृच्छिक है? यादृच्छिक चर के लिए एक सख्त परिभाषा है। एक यादृच्छिक चर एक मात्रा है जो एक प्रयोग के परिणामस्वरूप कई मूल्यों में से एक लेता है, और इस माप के एक या दूसरे मूल्य के प्रकट होने से पहले इसकी माप की सटीक भविष्यवाणी नहीं की जा सकती है। लेकिन यह हमारे सवाल का जवाब देने में मदद नहीं करता है, क्योंकि हमारे पास जवाब देने के लिए पर्याप्त जानकारी नहीं है। अब कहते हैं कि ये संख्याएँ कीबोर्ड की शीर्ष पंक्तियों में से एक का एक सेट बन गईं। "निश्चित रूप से आकस्मिक नहीं है" - आप का दावा करते हैं और तुरंत अगले नंबर को नाम देते हैं और आप बिल्कुल सही होंगे। वर्णों के बीच निर्भरता न होने पर ही क्रम यादृच्छिक होगा। उदाहरण के लिए, यदि ये प्रतीक बैरल को लोट्टो में खींचने के परिणामस्वरूप दिखाई देते हैं, तो अनुक्रम यादृच्छिक होगा।

थोड़ा और जटिल उदाहरण या पाई

संख्या पाई में अंकों का क्रम यादृच्छिक माना जाता है। जनरेटर को किसी अज्ञात बिंदु से शुरू होने वाले नंबर Pi का प्रतिनिधित्व करने वाले बिट्स की व्युत्पत्ति पर आधारित होने दें। ऐसा जनरेटर, शायद, "अगले बिट के लिए परीक्षण" पास करेगा, क्योंकि पीआई, जाहिरा तौर पर, एक यादृच्छिक अनुक्रम है। हालांकि, यह दृष्टिकोण आलोचनात्मक रूप से विश्वसनीय नहीं है - यदि क्रिप्टोकरंसी यह निर्धारित करती है कि वर्तमान में किस बिट नंबर का उपयोग किया जा रहा है, तो वह पिछले और बाद के सभी बिट्स की गणना करने में सक्षम होगा।
यह उदाहरण यादृच्छिक संख्या जनरेटर पर एक और प्रतिबंध लगाता है। एक क्रिप्टैनालिस्ट एक यादृच्छिक संख्या जनरेटर के संचालन की भविष्यवाणी करने में सक्षम नहीं होना चाहिए।

एक छद्म यादृच्छिक संख्या जनरेटर (PRNG) और एक यादृच्छिक संख्या जनरेटर (RNG) के बीच अंतर

एन्ट्रापी के स्रोतों का उपयोग एन्ट्रापी को संचित करने के लिए किया जाता है और फिर यादृच्छिक संख्या उत्पन्न करने के लिए यादृच्छिक संख्या जनरेटर (RNG) द्वारा आवश्यक प्रारंभिक मूल्य (प्रारंभिक मूल्य, बीज) प्राप्त करते हैं। PRNG एक एकल प्रारंभिक मूल्य का उपयोग करता है, जिसमें से इसका छद्म यादृच्छिकता अनुसरण करता है, और RNG हमेशा एक यादृच्छिक संख्या उत्पन्न करता है, शुरुआत में एन्ट्रापी के विभिन्न स्रोतों द्वारा प्रदान की जाने वाली उच्च गुणवत्ता वाला यादृच्छिक मूल्य होता है।
एन्ट्रॉपी विकार का एक उपाय है। सूचना एन्ट्रापी सूचना की अनिश्चितता या अप्रत्याशितता का एक उपाय है।
हम कह सकते हैं कि RNG = PRNG + एंट्रोपी का स्रोत।

PRSP कमजोरियाँ

• संख्याओं के बीच एक अनुमानित संबंध।
• जनरेटर का अनुमानित प्रारंभिक मूल्य।
• यादृच्छिक संख्याओं के उत्पन्न अनुक्रम की छोटी अवधि, जिसके बाद जनरेटर चक्र में जाता है।

रैखिक बधाई PRNG (LCPRNG)

छद्म यादृच्छिक संख्याएँ उत्पन्न करने के लिए एक सामान्य विधि जिसमें क्रिप्टोग्राफ़िक ताकत नहीं है। रैखिक सर्वांगसम विधि में एक रेखीय पुनरावृत्ति अनुक्रम के सदस्यों की गणना में कुछ प्राकृतिक संख्या मी होती है, जो निम्न सूत्र द्वारा दी गई हैं:



जहाँ (गुणक), c (योजक), m (मास्क) कुछ पूर्णांक गुणांक हैं। परिणामी अनुक्रम बीज X0 की पसंद पर निर्भर करता है, और इसके विभिन्न मूल्यों के लिए, यादृच्छिक संख्याओं के विभिन्न अनुक्रम प्राप्त होते हैं।

गुणांक का चयन करने के लिए, ऐसे गुण हैं जो आपको अवधि की अधिकतम अवधि (अधिकतम लंबाई मीटर है) की अनुमति देते हैं, अर्थात्, जिस क्षण से जनरेटर चक्र [1] में जाता है।

जनरेटर को कई यादृच्छिक संख्याएँ X0, X1, X2, X3 दें। यह समीकरणों की एक प्रणाली को बताता है



इस प्रणाली को हल करने के बाद, हम गुणांक a, c, m निर्धारित कर सकते हैं। विकिपीडिया [8] के अनुसार, इस प्रणाली का एक समाधान है, लेकिन स्वतंत्र रूप से हल करना या समाधान खोजना संभव नहीं था। मैं वास्तव में इस क्षेत्र में किसी भी मदद की सराहना करता हूं।

रैखिक सर्वांगसम विधि के परिणामों की भविष्यवाणी

रैखिक सर्वांगसम विधि के लिए संख्याओं की भविष्यवाणी के लिए मुख्य एल्गोरिथ्म प्लमस्टेड है - एक एल्गोरिथ्म जिसका कार्यान्वयन यहां पाया जा सकता है [4] (एक ऑनलाइन लॉन्च है) और यहां [5] । एल्गोरिथ्म का वर्णन [9] में पाया जा सकता है।
जावा में सर्वांगसम विधि का एक सरल कार्यान्वयन।

 public static int a = 45; public static int c = 21; public static int m = 67; public static int seed = 2; public static int getRand() { seed = (a * seed + c) % m; return seed; } public static void main(String[] args) { for(int i=0; i<30; i++) System.out.println(getRand()); } 

साइट [4] पर 20 नंबर भेजकर, आप संभवतः निम्नलिखित प्राप्त कर सकते हैं। जितनी अधिक संख्या, उतनी अधिक संभावना।

जावा में अंतर्निहित यादृच्छिक संख्या जनरेटर को हैक करना

कई प्रोग्रामिंग भाषाएं, जैसे C (रैंड), C ++ (रैंड), और Java LCPRNG का उपयोग करती हैं। आइए देखें कि आप java.utils का उपयोग करके कैसे हैक कर सकते हैं। एक उदाहरण के रूप में। इस वर्ग के स्रोत कोड (jdk1.7) में जाकर, आप उपयोग किए गए स्थिरांक देख सकते हैं

 private static final long multiplier = 0x5DEECE66DL; // 25214903917 private static final long addend = 0xBL; // 11 private static final long mask = (1L << 48) - 1; // 281474976710655 = 2^48 – 1 

Java.utils.Randon.nextInt () विधि इस तरह दिखती है (यहाँ बिट्स == 32)

 protected int next(int bits) { long oldseed, nextseed; AtomicLong seed = this.seed; do { oldseed = seed.get(); nextseed = (oldseed * multiplier + addend) & mask; } while (!seed.compareAndSet(oldseed, nextseed)); return (int)(nextseed >>> (48 - bits)); } 

परिणाम 48-32 = 16 बिट्स द्वारा दाईं ओर स्थानांतरित किया गया है। इस पद्धति को ट्रंकेटेड-बिट्स कहा जाता है, यह ब्लैक-बॉक्स के साथ विशेष रूप से अप्रिय है, आपको ब्रूट-बल में एक और लूप जोड़ना होगा। ब्रूट-बल का उपयोग करके हैकिंग होगी।

मान लीजिए कि हम लगातार दो उत्पन्न संख्याएँ X1 और x2 जानते हैं। फिर आपको 2 ^ 16 = 65536 से अधिक विकल्प चुनने की जरूरत है और सूत्र को X1 पर लागू करें:

 ((x1*multiplier + addend) & mask) << 16 

जब तक यह x2 के बराबर न हो जाए। जानवर बल के लिए कोड इस तरह लग सकता है

 import java.lang.reflect.Field; import java.util.Random; import java.util.concurrent.atomic.AtomicLong; public class PasswordCracking { public static final long multiplier = 0x5DEECE66DL; public static final long addend = 0xBL; public static final long mask = (1L << 48) - 1; public static void main(String[] args) { Random random = new Random(); long v1 = random.nextInt(); long v2 = random.nextInt(); long v3 = random.nextInt(); long v4 = random.nextInt(); System.out.println("v1=" + v1 + "\nv2=" + v2 + "\nv3=" + v3 + "\nv4=" + v4); // brute-force seed for (int i = 0; i < 65536; i++) { long seed = (((long) v1) << 16) + i; int nextInt = (int)(((seed * multiplier + addend) & mask) >>> 16); if (nextInt == v2) { System.out.println("Seed found: " + seed); Random crackingRandom = new Random(); try { /* set the seed for Random to be convinced that we have found the right seed because constructor Random (long seed) uses the private static long initialScramble (long seed) { return (seed ^ multiplier) & mask; } for simplicity will use Reflection */ Field privateSeedField = Random.class.getDeclaredField("seed"); privateSeedField.setAccessible(true); AtomicLong crackingSeed = (AtomicLong)privateSeedField.get(crackingRandom); crackingSeed.set(seed); }catch(Exception e) { System.out.println(e.toString()); System.exit(1); } long cv1 = crackingRandom.nextInt(); long cv2 = crackingRandom.nextInt(); long cv3 = crackingRandom.nextInt(); long cv4 = crackingRandom.nextInt(); System.out.println("Set fiend seed and generate random numbers"); System.out.println("cv1=" + cv1 + "\ncv2=" + cv2 + "\ncv3=" + cv3 + "\ncv4=" + cv4); break; } } } } 

इस कार्यक्रम का आउटपुट कुछ इस तरह होगा:

 v1 = -1184958941 v2 = 274285127 v3 = -1566774765 v4 = 30466408 Seed found: -77657469128792 Set fiend seed and generate random numbers cv1 = 274285127 cv2 = -1566774765 cv3 = 30466408 cv4 = -803980434 

यह समझना आसान है कि हमें बहुत पहले बीज नहीं मिला, लेकिन बीज दूसरी संख्या उत्पन्न करता था। मूल बीज को खोजने के लिए, आपको कई ऑपरेशन करने की आवश्यकता है जो कि जावा बीज को परिवर्तित करने के लिए, रिवर्स ऑर्डर में करता था।

 public static long getPreviousSeed(long prevSeed) { long seed = prevSeed; // reverse the addend from the seed seed -= addend; // reverse the addend long result = 0; // iterate through the seeds bits for (int i = 0; i < 48; i++) { long mask = 1L << i; // find the next bit long bit = seed & mask; // add it to the result result |= bit; if (bit == mask) { // if the bit was 1, subtract its effects from the seed seed -= multiplier << i; } } System.out.println("Previous seed: " + result); return result; } 

और अब सोर्स कोड में बदलें
crackingSeed.set (बीज);
पर
crackingSeed.set (getPrepretSeed (बीज));

और यह, हमने जावा में PRNG को सफलतापूर्वक क्रैक किया है।

PHP में PRNG Mersenne ट्विस्टर को हैक करना

Mersenne Twister छद्म आयामी संख्या पैदा करने के लिए एक और गैर-क्रिप्टोग्राफिक एल्गोरिथ्म पर विचार करें। एल्गोरिथ्म के मुख्य लाभ पीढ़ी की गति और 2 ^ 19937 - 1 की एक विशाल अवधि है, इस बार हम php स्रोत कोड संस्करण 5.4.6 में mt_srand () और mt_rand () एल्गोरिदम के कार्यान्वयन का विश्लेषण करेंगे।




आप देख सकते हैं कि php_mt_reload को आरंभीकरण के दौरान और php_mt_rand 624 बार कॉल करने के बाद कहा जाता है। चलो अंत से हैकिंग शुरू करते हैं, php_mt_rand () फ़ंक्शन के अंत में परिवर्तनों को उल्टा करते हैं। विचार करें (s1 ^ (s1 >> 18))। एक द्विआधारी प्रतिनिधित्व में, ऑपरेशन इस तरह दिखता है:

101101110101111001 11111001110010 s1
0000000000000000001011011101011110011111111001110010 s1 >> 18
101101110101111001 01001110100101 s1 ^ (s1 >> 18)
यह देखा जा सकता है कि पहले 18 बिट्स (बोल्ड में हाइलाइट किए गए) अपरिवर्तित रहे।
हम बिट शिफ्ट और xor को इन्वर्ट करने के लिए दो फ़ंक्शन लिखते हैं

 public static long unBitshiftRightXor(long value, long shift) { // we part of the value we are up to (with a width of shift bits) long i = 0; // we accumulate the result here long result = 0; // iterate until we've done the full 32 bits while (i * shift < 32) { // create a mask for this part long partMask = (-1 << (32 - shift)) >>> (shift * i); // obtain the part long part = value & partMask; // unapply the xor from the next part of the integer value ^= part >>> shift; // add the part to the result result |= part; i++; } return result; } public static long unBitshiftLeftXor(long value, long shift, long mask) { // we part of the value we are up to (with a width of shift bits) long i = 0; // we accumulate the result here long result = 0; // iterate until we've done the full 32 bits while (i * shift < 32) { // create a mask for this part long partMask = (-1 >>> (32 - shift)) << (shift * i); // obtain the part long part = value & partMask; // unapply the xor from the next part of the integer value ^= (part << shift) & mask; // add the part to the result result |= part; i++; } return result; } 

तब php_mt_rand () फ़ंक्शन की अंतिम पंक्तियों को उल्टा करने के लिए कोड इस तरह दिखाई देगा

 long value = output; value = unBitshiftRightXor(value, 18); value = unBitshiftLeftXor(value, 15, 0xefc60000); value = unBitshiftLeftXor(value, 7, 0x9d2c5680); value = unBitshiftRightXor(value, 11); 

अगर हमारे पास Mersenne Twister द्वारा 624 लगातार संख्याएं उत्पन्न होती हैं, तो इन एल्गोरिदम को इन लगातार संख्याओं के लिए लागू करने पर, हमें Mersenne Twister की पूर्ण स्थिति मिलती है, और हम मूल्यों के ज्ञात सेट के लिए php_mt_reload चलाकर प्रत्येक बाद के मूल्य को आसानी से निर्धारित कर सकते हैं।

हैकिंग एरिया

अगर आपको लगता है कि टूटने के लिए कुछ नहीं है, तो आप गहराई से गलत हैं। दिलचस्प क्षेत्रों में से एक एडोब फ्लैश यादृच्छिक संख्या जनरेटर (एक्शन स्क्रिप्ट 3.0) है। इसकी ख़ासियत बंद स्रोत कोड और बीज कार्य की कमी है। इसमें मुख्य रुचि कई ऑनलाइन कैसीनो और ऑनलाइन पोकर में उपयोग है।
संख्याओं के कई क्रम हैं, डॉलर के विनिमय दर से लेकर हर दिन यातायात में खर्च होने वाली राशि तक। और इस तरह के डेटा में एक पैटर्न खोजने के लिए एक सरल काम नहीं है।

एक छद्म यादृच्छिक संख्या जनरेटर के लिए एक वितरण की स्थापना

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

त्रिकोणीय वितरण

हम C99 की भाषा में त्रिकोणीय वितरण [7] के साथ एक यादृच्छिक चर उत्पन्न करने का एक उदाहरण देते हैं।

 double triangular(double a, double b, double c) { double U = rand() / (double) RAND_MAX; double F = (c - a) / (b - a); if (U <= F) return a + sqrt(U * (b - a) * (c - a)); else return b - sqrt((1 - U) * (b - a) * (b - c)); } 

इस मामले में, हम यादृच्छिक चर रैंड () लेते हैं और त्रिकोणीय वितरण फ़ंक्शन के आधार पर वितरण सेट करते हैं। मापदंडों के लिए a -40, b = 100, c = 50, 10,000,000 मापों का ग्राफ इस तरह दिखेगा

घातांक वितरण

मान लीजिए कि आप तेजी से वितरित यादृच्छिक चर का सेंसर प्राप्त करना चाहते हैं। इस स्थिति में, F (x) = 1 - exp (-lambda * x)। फिर समीकरण y = 1 - exp (-lambda * x) के समाधान से हमें x = -log (1-y) / lambda मिलता है।
आप देख सकते हैं कि अंतिम सूत्र में लघुगणक के तहत अभिव्यक्ति अंतराल पर एक समान वितरण है [0,1), जो हमें एक और प्राप्त करने की अनुमति देता है, लेकिन सूत्र के अनुसार अनुक्रम भी वितरित करता है: x = -log (y) / lambda, जहां y एक यादृच्छिक चर है (रैंड) ()।

PRNG परीक्षण

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

प्रसिद्ध परीक्षणों में से एक अगले बिट के लिए परीक्षण है - एक परीक्षण जो क्रिप्टोग्राफिक ताकत के लिए छद्म यादृच्छिक संख्या जनरेटर की जांच करने का कार्य करता है। परीक्षण में कहा गया है कि एक बहुपद एल्गोरिथ्म नहीं होना चाहिए, जो यादृच्छिक क्रम के पहले k बिट्स को जानकर a k + 1 बिट्स को bits से अधिक संभावना के साथ भविष्यवाणी कर सकता है।

क्रिप्टोग्राफी सिद्धांत में, एक अलग समस्या यह निर्धारित कर रही है कि जनरेटर द्वारा उत्पन्न संख्याओं या बिट्स का क्रम कितना यादृच्छिक है। आमतौर पर, इस उद्देश्य के लिए विभिन्न सांख्यिकीय परीक्षणों का उपयोग किया जाता है, जैसे कि DIEHARD या NIST। 1982 में एंड्रयू याओ ने साबित कर दिया कि "अगला बिट टेस्ट" पास करने वाला एक जनरेटर किसी भी अन्य यादृच्छिक यादृच्छिक सांख्यिकीय परीक्षणों को पारित करेगा जो कि बहुपद समय में पूरा किया जा सकता है।
इंटरनेट [10] पर, आप एल्गोरिथ्म के महत्वपूर्ण प्रतिरोध को निर्धारित करने के लिए डाईहार्ड परीक्षण और कई अन्य को पास कर सकते हैं।

ज्ञात यादृच्छिक संख्या जनरेटर हैक

• कम एन्ट्रॉपी [11] के साथ अर्ली नेटस्केप SSL एन्क्रिप्शन प्रोटोकॉल
• PHP सत्र भेद्यता habrahabr.ru/company/pt/blog/149746
• Microsoft CryptGenRandom [12]
• PRNG में कमजोरियों के माध्यम से कई ऑनलाइन कैसीनो को एक से अधिक बार लक्षित किया गया है

संदर्भ

[१] डोनाल्ड नुथ, द आर्ट ऑफ़ प्रोग्रामिंग (खंड २। व्युत्पन्न एल्गोरिदम)
[२] ब्रूस श्नेयर, एप्लाइड क्रिप्टोग्राफी (अध्याय १६)
[४] www.staff.uni-mainz.de/pommeren/Kryptologie/Bitstrom/2_Analyse/LCGcrack.html
[५] www.staff.uni-mainz.de/pommeren/Kryptologie99/English.html
[६] en.wikipedia.org/wiki/Mersenne_twister
[[] En.wikipedia.org/wiki/Triangular_distribution
[[] En.wikipedia.org/wiki/Linear_Congruent_Method
[९] zaic101.ru/files/728/using_linear_congruential_generators_for_cryptographic_purpose.pdf
[१०] www.cacert.at/random
[११] www.cs.berkeley.edu/~daw/papers/ddj-netscape.html
[१२] www.computerworld.com/s/article/9048438/Microsoft_confirms_that_XP_contains_random_number_generator_bug
[१३] md5 raz0r.name/articles/magiya-sluchajnyx-chisel-chast-2/comment-page-1 के माध्यम से पीढ़ी का एक दिलचस्प उदाहरण वर्णित है

मूल

jazzy.id.au/default/2010/09/20/cracking_random_number_generators_part_1.html
jazzy.id.au/default/2010/09/21/cracking_random_number_generators_part_2.html
jazzy.id.au/default/2010/09/22/cracking_random_number_generators_part_3.html
jazzy.id.au/default/2010/09/25/cracking_random_number_generators_part_4.html