🙈 🏮 ⛸️ GOST के कोड, ग्रासहॉपर, इसके एसबॉक्स और खोए हुए बीजों के बारे में 💆🏿 🏍️ 🌵

हाय% उपयोगकर्ता नाम%!

हम हाल ही में EuroCrypt 2019 सम्मेलन से लौटे, जहां हम बेहद स्मार्ट लोगों से मिले और उसी समय GOST SBox के बारे में नए, बेहद आक्रामक तथ्य सीखे।

तो, यह प्रक्षेप्य के लिए दूसरा दृष्टिकोण है। ठीक किया और पूरक किया।

इस बार कोई लाल-नीली स्लाइड नहीं होगी, लेकिन ग्रासहॉपर के लेखकों के स्पष्टीकरण के साथ आईएसओ समिति के मूल दस्तावेज होंगे।

और अंत में चुनौती भी!

चलो चलते हैं।

पहला शैक्षिक कार्यक्रम। पिछले लेख में यह नहीं था, इस बार मैंने सही किया।

चुना हुआ प्लेनटेक्स्ट अटैक (CPA)

हम ब्लॉक सिफर पर बुनियादी हमले के मॉडल के साथ शुरू करते हैं।

इस मॉडल में, हमलावर को एन्क्रिप्शन कुंजी को छोड़कर क्रिप्टोकरेंसी के बारे में सब कुछ पता है। वह कोई भी प्लेटेक्स्ट बना सकता है, उसे संबंधित सिफरटेक् ट प्राप्त कर सकता है और उसका कार्य कुंजी की गणना करना है, क्योंकि यह एकमात्र चर है।

इस स्थिति में ब्लॉक सिफर को छद्म यादृच्छिक प्रतिस्थापन माना जा सकता है। एक फ़ंक्शन जो एक प्लेनटेक्स्ट ब्लॉक को एक सिफरटेक्स्ट ब्लॉक से इस तरह से मेल खाता है कि उनके बीच के रिश्ते को निर्धारित करना असंभव है।

एक आदर्श ब्लॉक सिफर की कल्पना एक बड़ी तालिका के रूप में की जा सकती है, जहाँ क्षैतिज रूप से 000 से सभी संभव कुंजियाँ होंगी ... 000 से 111 ... 111, खड़ी - सभी संभव खुले ग्रंथ भी 000 से ... 000 से 111 ... 111 , और उनके चौराहे की जगह पर - बेतरतीब ढंग से उत्पन्न सिफरटेक्स जो कि "की-प्लेनटेक्स्ट" की जोड़ी को विशिष्ट रूप से जोड़ देगा। वास्तविक जीवन में ऐसी तालिका बनाने के लिए इसके आकार के कारण संभव नहीं है, इसलिए विभिन्न ब्लॉक एन्क्रिप्शन एल्गोरिदम का उपयोग करके इसका अनुकरण किया जाता है।

ब्लॉक सिफर पर हमले को सफल कहा जा सकता है अगर हम "यादृच्छिकता" निर्धारित कर सकते हैं जिसके साथ एल्गोरिथ्म सिफरटेक्ट्स का चयन करता है जो प्लेनटेक्स के अनुरूप है। यह यादृच्छिकता एन्क्रिप्शन कुंजी की गणना करने के लिए सबसे खराब मामलों में अनुमति देता है।

(गैर) रैखिकता

ब्लॉक सिफर में एन्क्रिप्शन प्रक्रिया को एक सरल सूत्र द्वारा दर्शाया जा सकता है
सी = एम एक्स के
जहां C सिफरटेक्स्ट है, M प्लेटेक्स्ट है, K एन्क्रिप्शन कुंजी है, और x ब्लॉक सिफर है।

यह सूत्र नेत्रहीन रेखीय समीकरण y = kx + b के स्कूल सूत्र के समान है, जिसका ग्राफ एक सीधी रेखा है।

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

एल्गोरिथ्म की सुरक्षा के लिए उनकी गुणवत्ता महत्वपूर्ण है।

SBox क्या है?

यह एक ही नॉनलाइनर लेयर है। एक फ़ंक्शन जो ग्रासहॉपर और कुछ अन्य सिफर के मामले में विशिष्ट रूप से एक बाइट से दूसरे बाइट को मैप करता है।

बहुत बार यह एक साधारण पत्राचार तालिका द्वारा निर्धारित किया जाता है, उदाहरण के लिए:

क्योंकि अन्यथा इसका वर्णन नहीं किया जा सकता है। पहली नज़र में।

SBox क्यों महत्वपूर्ण है?

क्योंकि यह पूरे सिफर में एकमात्र गैर-रेखीय कार्य है। इसके बिना, एक सिफर को तोड़ना आसान नहीं होगा, लेकिन बहुत सरल है, इसे रैखिक समीकरणों की एक प्रणाली के रूप में प्रस्तुत करना। इसलिए, प्रतिस्थापन समारोह का इतना ध्यान है। रैखिक एसबॉक्स के साथ एईएस को हैक करने के लिए यहां तक कि व्यावहारिक अभ्यास भी हैं।

आप एक सुरक्षित SBox क्यों नहीं बना सकते?

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

इसलिए विभिन्न "जादू स्थिरांक" और अन्य बिंदुओं के बारे में निरंतर व्यामोह कि एल्गोरिदम के लेखक सुरक्षित के रूप में मौजूद हैं, लेकिन इसे साबित नहीं कर सकते ।

SBox कैसे बनाये?

विभिन्न SBox वेरिएंट 256 हैं, जो लगभग 2 ^{1684 है} । पसंद बड़ी है और क्रिप्टोनालिसिस के वर्षों में, मेट्रिक्स और विशेषताओं को विकसित किया गया है जो SBox के पास होना चाहिए, आज के ज्ञात हमलों के लिए प्रतिरोधी। बेशक, टेबल के निर्माता आने वाले वर्षों के लिए सोचते हैं और 5-10 साल में आविष्कार किए गए हमलों के लिए भी प्रतिरोधक बनाने की कोशिश करेंगे। लेकिन यह जादू और शर्मिंदगी की श्रेणी से अधिक है।

SBox बनाने के लिए दो मूलभूत रूप से अलग-अलग दृष्टिकोण हैं।

पहली एक यादृच्छिक खोज है। डेवलपर्स यादृच्छिक तालिकाओं को उत्पन्न करते हैं, उनकी विशेषताओं को देखते हैं और उन लोगों को फ़िल्टर करते हैं जो उपयुक्त नहीं हैं। यह तब तक जारी रहता है जब तक कि डेवलपर्स ने जो कुछ भी पाया है उससे संतुष्ट नहीं होते हैं।

सभ्य दुनिया में, यह होता है, उदाहरण के लिए, निम्नानुसार है:

कुछ प्रारंभिक मूल्य लिया जाता है, उदाहरण के लिए, एक पुस्तक का एक उद्धरण या पाई के पहले कुछ अंक
एक हैश के माध्यम से चलाता है
हैश परिणाम को एसबॉक्स बनाने के लिए डेटा के रूप में उपयोग किया जाता है।
यदि SBox फिट नहीं था, तो वर्तमान हैश ले लें और चरण 2 पर लौटें

तो कोई भी इस प्रक्रिया को पुन: पेश कर सकता है और यह सुनिश्चित कर सकता है कि छद्म यादृच्छिक खोज के लिए कम से कम न्यूनतम आवश्यकताएं पूरी हों।

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

दूसरा तरीका एसबॉक्स को खुद बनाना है, जो उपलब्ध गणितीय तंत्र द्वारा निर्देशित है। एईएस के लेखकों ने यही किया है, और उन्होंने बहुत अच्छा किया है। यदि हम SBox AES, SM4 (चीनी मानक) और ग्रासहॉपर की गैर-शुद्धता की तुलना करते हैं (यह Stribog हैश के समान SBox का उपयोग करता है), तो परिणाम उत्तरार्द्ध के पक्ष में नहीं होगा।

एईएस गैर-रैखिकता (न्यूनतम, अधिकतम) = (112.0, 112.0)
SM4 गैर-रैखिकता (न्यूनतम, अधिकतम) = (112.0, 112.0)
Streebog गैर-रैखिकता (न्यूनतम, अधिकतम) = (102.0, 110.0)

नॉनलाइनरिटी गणना कोड वाल्श ट्रांसफॉर्म का उपयोग करता है और यहां उपलब्ध है।

दस्तावेजों

मुझे आईएसओ से दो दस्तावेज मिले। पहले में, ग्रासहॉपर डिजाइनर बताते हैं कि उन्होंने एसबॉक्स कैसे बनाया, दूसरे में, समिति उनके तर्कों पर चर्चा करती है।

पहले दस्तावेज़ से हम दो उद्धरणों में रुचि रखते हैं:

और

मुझे उम्मीद है कि "लियो पेरिन के साथ विषय खुद इस विचार के साथ आया था कि लेखकों ने एसबॉक्स की खोज बेतरतीब ढंग से की है" अब बंद है।

डिजाइनरों के स्पष्टीकरण से यह निम्नानुसार है

वे वास्तव में छद्म यादृच्छिक तरीके से SBox की तलाश करते थे (सुरक्षा मानदंड दिए गए)
इसमें कथित रूप से कोई छिपी हुई संरचना नहीं रखी गई थी।

और इस जगह में वे पूरी तरह से खराब हो गए।

एक संरचना क्या है?

लुकअप टेबल पर लागू एक संरचना एक एल्गोरिथ्म है जो इस तालिका का वर्णन करता है।

दस्तावेज़ में एईएस का उल्लेख किया गया है। लेकिन एईएस के लिए लुकअप टेबल मूल रूप से यादृच्छिक खोज द्वारा नहीं, बल्कि कई गणितीय तकनीकों की मदद से बनाई गई थी, जिसने हमें कई सूत्रों के साथ एक नॉनलाइनर परत का वर्णन करने की अनुमति दी थी। यह, संयोग से, एईएस की विशिष्टता है।

इसके विपरीत, यदि आप एसबॉक्स को यादृच्छिक रूप से देख रहे हैं, तो इसमें ऐसी संरचनाएं नहीं होनी चाहिए और ग्रासहॉपर एसबॉक्स के साथ समस्या यह है कि एल्गोरिथ्म डिजाइनरों के शब्द तथ्यों से बहुत अलग हैं। मैंने पिछले लेख में TKLog नामक टिड्डे की संरचना के बारे में लिखा था, इस बार सामान्य रूप से संरचनाओं के बारे में बात करते हैं।

कोलमोगोरोव जटिलता

यह ग्रासहॉपर के लियो पेरिन के नवीनतम लेख के शोध का परिणाम है।

ग्रासहॉपर SBox में संरचनाओं के बारे में लेखों का मुख्य प्रतिवाद यह है कि "लगभग किसी भी SBox में आप चाहें तो कुछ संरचना पा सकते हैं।" और "भले ही लियो ने पाया कि संरचना को खोजने की संभावना नगण्य है, अगर एक और एसबॉक्स थे, तो एक और होगा, एक तुच्छ संभावना के साथ भी।"

मान लेते हैं कि ऐसा है। लेकिन। जैसा कि यह निकला, एसबॉक्स की एक निश्चित "संरचितता की डिग्री" प्राप्त करना संभव है, जो एक या किसी अन्य संरचना में गिरने की संभावना पर निर्भर नहीं करता है।

लेकिन यह उस SBox को उत्पन्न करने के लिए आवश्यक एल्गोरिथ्म के आकार पर निर्भर करता है!

इसे कोलमोगोरोव जटिलता कहा जाता है।

यदि आप SBox को बाइट्स के एक स्ट्रिंग के रूप में कल्पना करते हैं, तो एक यादृच्छिक स्ट्रिंग के मामले में, एक एल्गोरिथ्म नहीं होना चाहिए जो इस स्ट्रिंग को उत्पन्न करता है और एक ही समय में इस स्ट्रिंग से छोटा होता है।

टिड्डे के लिए

तो, SBox का आकार 256 बाइट्स है। यहां लियो पेरिन के लेखक के कोड का एक पठनीय संस्करण है, जो ग्रासहॉपर टेबल को लागू करता है। इनपुट में मूल बाइट है, आउटपुट में ग्रासहॉपर SBox से संबंधित बाइट है। इस तरह के एल्गोरिथ्म के लिए मुख्य शर्त भाषा या मंच संरचनाओं के उपयोग पर प्रतिबंध है जो कार्यक्रम के आकार को कम करती है। उदाहरण के लिए, यदि मानक पुस्तकालय के अंदर कहीं एसबीओक्स का लगातार आधा हिस्सा है, तो आप इसका उपयोग नहीं कर सकते।

चुनौती - एक प्रोग्राम लिखें जो SBox से छोटा होगा।

unsigned char p(unsigned char x){
    unsigned char
        s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
        k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};    
    if(x) {
        unsigned char l=1, a=2;
        while(a!=x) {
            a=(a<<1)^(a>>7)*29;
            l++;
        }
        if (l%17) return 252^k[l%17]^s[l/17];
        else return 252^k[l/17];
    }
    else return 252;
}

, SBox «» , , SBox. 416 , .

, :

p(x){
  unsigned char
      *t="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",
      a=2,l=0,b=17;
  while(x && (l++,a^x)) a=2*a^a/128*29;
  return l%b ? t[l%b]^t[b+l/b]^b : t[l/b]^188;
}

196 , 23% SBox. . , :

p(x){char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8";int l=256,b=17;while(--l*x^l)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}

SBox :

int main() {
   for(int i = 0; i < 256; i++){
       if (i % 16 == 0){
           printf("\n");
       }
    printf("%d, ", (unsigned char)p(i));    
   }
}

, SBox .
153 . — ANSI, 7 , 8. 1071 ~134 . , .

, Cortex-M4 80 ( ).

, 64 .

, ?

, , .

, 4 Sbox, SBox , .

. , « » AES (60 , GolfScript), .

— . , — .

— SBox. , . , .

( ), , 4 , SBox. , — , . 4 , , , . , , , 11 , , . , side project ¯\_(ツ)_/¯.

ISO . . .

, , , SBox . . , , .

Curve25519 Daniel J. Bernstein Tanja Lange, ISO . , , , SBox. . .

, .

, . ISO, , EuroCrypt.

, ( SBox), RFC 7801, .

, SBox, (, ). , , , . V2 .

. , « , ».

, ? , AES - .

, , , , . .

Challenge!

SBox , , . , 256 . . . — , .

— 58 Stax. « » SBox.

.

GOST के कोड, ग्रासहॉपर, इसके एसबॉक्स और खोए हुए बीजों के बारे में