Differential cryptanalysis की मूल बातें

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

XOR-आधारित सिफर के लिए: अंतर ΔX = X XOR X'। जोड़-आधारित सिफर के लिए: अंतर ΔX = X - X' mod 2^n। XOR अंतर सबसे सामान्य होते हैं, क्योंकि XOR-कुंजीकरण के साथ XOR क्रमविनिमेय होता है (विभेदी युग्मों में कुंजी अनुसूची के प्रभाव निरस्त हो जाते हैं)।

एक विभेदी युग्म (P, P') का इनपुट अंतर ΔP = P XOR P' होता है। एन्क्रिप्शन के बाद: (C, C') और आउटपुट अंतर ΔC = C XOR C' होता है। उपयोगी विभेदी संबंध ΔP → ΔC वह है जिसकी प्रायिकता p अधिक हो—अर्थात् ΔP अंतर वाले कई (P, P') युग्म ΔC आउटपुट अंतर उत्पन्न करते हैं।

DDT (विभेदी वितरण तालिका) यह गिनती करती है कि प्रत्येक इनपुट अंतर Δx और आउटपुट अंतर Δy के लिए कितने इनपुट x, S(x) XOR S(x XOR Δx) = Δy को संतुष्ट करते हैं। इसे 2^n से भाग देने पर प्रायिकता मिलती है। एक अच्छे S-बॉक्स का अधिकतम DDT मान 2 होता है (प्रायिकता 1/2^{n-1})—अर्थात् कोई प्रबल विभेदी संबंध नहीं होता।

r राउंड वाले ब्लॉक सिफर के लिए, ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1} का ऐसा क्रम खोजें जिसमें प्रत्येक राउंड-परिवर्तन की प्रायिकता ज्ञात हो। राउंडों की प्रायिकताओं को गुणा करें: कुल प्रायिकता p = p1 * p2 * ... * p_{r-1}। आक्रमण में अंतिम राउंड की कुंजी पुनर्प्राप्त करने के लिए 2/p युग्मों का उपयोग किया जाता है।

उच्च-प्रायिकता वाले r-1 राउंड के विभेदी संबंध के साथ, N = 2/p सादा-पाठ युग्म एकत्र करें। अंतिम राउंड की प्रत्येक संभावित कुंजी K' के लिए, दोनों सिफर-पाठों को एक राउंड पीछे विकूटित करें, परिणामों पर XOR लगाएँ और जाँचें कि अंतर ΔU_{r-1} से मेल खाता है या नहीं। सही K' लगभग N/2 बार मेल खाती है; गलत कुंजियाँ लगभग N/2^{bit_size} बार मेल खाती हैं।

एईएस S-बॉक्स GF(2^8) पर गुणनात्मक प्रतिलोम के बाद एक एफ़ाइन रूपांतरण से बनता है। इसका अधिकतम DDT मान 256 में से 4 है, जिससे प्रत्येक S-बॉक्स के लिए विभेदी प्रायिकता ≤ 4/256 = 1/64 होती है। एईएस में प्रत्येक राउंड में 4 S-बॉक्स होते हैं, लेकिन वाइड ट्रेल अभिकल्प सुनिश्चित करता है कि पूर्ण विभेदी पथों की प्रायिकता 2^{-100} से कम रहे।

Joan Daemen का वाइड ट्रेल अभिकल्प (एईएस/राइन्डेल में प्रयुक्त): MixColumns की शाखा संख्या B निर्धारित करें। एक राउंड से गुजरने वाले किसी भी गैर-तुच्छ विभेदी पथ में कम-से-कम B सक्रिय S-बॉक्स होते हैं। 4 राउंड × प्रत्येक राउंड में 4 S-बॉक्स से कम-से-कम 25 सक्रिय S-बॉक्स सुनिश्चित होते हैं → प्रायिकता < 2^{-100}।

संक्षिप्त विभेदी संबंध अंतर के केवल एक हिस्से को निर्दिष्ट करते हैं (जैसे, सटीक अंतर मानों के बजाय केवल यह बताना कि कौन-से कॉलम सक्रिय हैं)। इससे उन अधिक राउंडों पर आक्रमण संभव होते हैं जहाँ पूर्ण विभेदी संबंध बहुत कमजोर होते हैं। इनका उपयोग कम-राउंड वाले एईएस, SERPENT और अन्य SPN सिफरों के विरुद्ध किया जाता है।

असंभव विभेदी संबंध ऐसा (ΔP, ΔC) युग्म है जो किसी भी कुंजी के लिए कभी उत्पन्न नहीं हो सकता। इस अंतर वाले देखे गए युग्म (P, P') को उत्पन्न करने वाली किसी भी कुंजी को हटा दिया जाता है। पर्याप्त युग्म एकत्र करने पर सभी गलत कुंजियाँ हट जाती हैं और सही कुंजी बचती है।

बूमरैंग आक्रमण (Wagner, 1999) दो छोटे विभेदी संबंधों को मिलाकर एक अनुकूलनीय चयनित-सादा-पाठ/सिफर-पाठ आक्रमण बनाता है। यह सिफर को दो हिस्सों में बाँटता है, जिनमें से प्रत्येक में उच्च-प्रायिकता वाला छोटा विभेदी संबंध होता है। इस प्रकार ऐसा आक्रमण संभव होता है जो किसी एक विभेदी संबंध से अकेले संभव होने वाले आक्रमण से अधिक राउंड तक पहुँचता है।

विभेदी क्रिप्टविश्लेषण उच्च-प्रायिकता वाले इनपुट से आउटपुट तक अंतर के प्रसार का लाभ उठाता है। एईएस अपने DDT-अनुकूलित S-बॉक्स और वाइड ट्रेल अभिकल्प के माध्यम से इसका प्रतिरोध करता है। अगला विषय: रैखिक क्रिप्टविश्लेषण और सन्निकटन तालिकाएँ।