👲🏿 🛌🏾 🐼 حول رمز GOST ، Grasshopper ، SBox والبذور المفقودة 👩🏾‍🤝‍👩🏼 🏝️ 💧

مرحبا ٪ اسم المستخدم ٪!

لقد عدنا مؤخرًا من مؤتمر EuroCrypt 2019 ، حيث التقينا بأشخاص أذكياء للغاية وتعلمنا في الوقت نفسه حقائق جديدة ومهينة للغاية حول GOST SBox.

لذلك ، هذا هو النهج الثاني للقذيفة. تصحيح واستكمال.

هذه المرة لن يكون هناك شرائح حمراء زرقاء غير مفهومة ، ولكن ستكون هناك مستندات أصلية من لجنة ISO مع شرح من مؤلفي Grasshopper.

وحتى التحدي في النهاية!

دعنا نذهب.

البرنامج التعليمي الأول. في المقال السابق لم يكن ، وهذه المرة أنا تصحيح.

هجوم اختيار النص العادي (CPA)

نبدأ مع نموذج الهجوم الأساسي على الأصفار كتلة.

في هذا النموذج ، يعرف المهاجم كل شيء عن نظام التشفير باستثناء مفتاح التشفير. يمكنه إنشاء أي نص غير عادي ، والحصول على النصوص المشفرة المقابلة ، ومهمته هي حساب المفتاح ، لأن هذا هو المتغير الوحيد.

يمكن اعتبار تشفير البلوك في هذه الحالة كبديل عشوائي شبه عشوائي. دالة تطابق كتلة نص عادي مع كتلة نص مشفر بطريقة تجعل من المستحيل تحديد العلاقة بينهما.

يمكن تخيل تشفير البلوك المثالي كجدول كبير ، حيث سيكون هناك أفقياً جميع المفاتيح الممكنة من 000 ... 000 إلى 111 ... 111 ، رأسياً - جميع النصوص المفتوحة الممكنة أيضًا من 000 ... 000 إلى 111 ... 111 وفي مكان تقاطعهم - نص مشفر تم إنشاؤه عشوائيًا من شأنه أن يربط بشكل فريد زوجًا من "النص الأساسي الأساسي". لإنشاء مثل هذا الجدول في الحياة الحقيقية غير ممكن بسبب حجمه ، لذلك يتم محاكاته باستخدام خوارزميات تشفير البلوك المختلفة.

يمكن اعتبار الهجوم على تشفير البلوك ناجحًا إذا تمكنا من تحديد "العشوائية" التي تحدد بها الخوارزمية النصوص المشفرة التي تتوافق مع النصوص المشفرة. تسمح هذه العشوائية في أسوأ الحالات بحساب مفتاح التشفير.

(غير) الخطي

يمكن تمثيل عملية التشفير في تشفير البلوك بصيغة بسيطة
ج = م × ك
حيث C عبارة عن نص مشفر ، M هو نص غير عادي ، K هو مفتاح التشفير ، و x هو تشفير الكتل.

تشبه هذه الصيغة بصريًا الصيغة المدرسية للمعادلة الخطية y = kx + b ، الرسم البياني الذي هو خط مستقيم.

يمكن استعادة أي خط مستقيم في نقطتين فقط. وفي الوقت نفسه ، لا نريد حقًا أن تتمكن من استعادة مفتاح التشفير في اثنين من أزواج النص المشفر. لهذا ، تتم إضافة طبقات خاصة إلى خوارزميات التشفير المسؤولة عن عدم الخطية. تم تصميم هذه الطبقات لمنع إمكانية حساب العلاقة بين النص العادي والنص المشفر والمفتاح.

جودتها أمر بالغ الأهمية لأمن الخوارزمية.

ما هو SBox؟

هذه هي نفس الطبقة غير الخطية. دالة تقوم ، في حالة Grasshopper وبعض الأصفار الأخرى ، بتعيين خريطة فريدة لبايتة أخرى.

في كثير من الأحيان يتم تعيينه بواسطة جدول مراسلات بسيط ، على سبيل المثال هذا:

لأنه خلاف ذلك لا يمكن وصفها. للوهلة الأولى.

لماذا هو SBox مهم؟

لأنها الوظيفة غير الخطية الوحيدة في الشفرة بأكملها. بدون ذلك ، لن يكون كسر الشفرات أمرًا سهلاً ، ولكنه بسيط جدًا ، حيث يقدمها كنظام من المعادلات الخطية. لذلك ، وظيفة الاستبدال لديها الكثير من الاهتمام. هناك حتى تمارين عملية لاختراق AES مع SBox الخطي.

لماذا لا يمكنك إنشاء SBox آمن واحد على الإطلاق؟

المشكلة هي أن التشفير ليس علمًا دقيقًا. خوارزمية التشفير القوية الوحيدة هي لوحة لمرة واحدة . كل ما تبقى هو محاولات خجولة لتتناسب مع مجموعة المعرفة المتاحة لنا ، والتي مجموعة ليست كبيرة جدا.
لا نعرف على وجه اليقين ما إذا كانت منحنيات RSA أو AES أو المنحنيات الإهليلجية مقاومة ، لكننا نعرف أن مثل هذه الأشياء ومثل هذه الأشياء غير ممكنة بالتأكيد . كل ما في الأمر هو الإبداع.

ومن هنا فإن جنون العظمة المستمر حول "الثوابت السحرية" المختلفة والنقاط الأخرى التي يقدمها مؤلفو الخوارزميات آمنة ، ولكن لا يمكنهم إثباتها .

كيفية إنشاء SBox؟

المتغيرات SBox المختلفة هي 256! ، وهو ما يقرب من 2 ¹⁶⁸⁴ . الاختيار كبير وعلى مدار سنوات من تحليل الشفرات ، تم تطوير المقاييس والخصائص التي يجب أن يكون لدى SBox ، مقاومة للهجمات المعروفة اليوم. بالطبع ، يفكر منشئو الجداول لسنوات قادمة ويحاولون إنشاء بدائل من شأنها أن تقاوم حتى الهجمات التي تم اختراعها خلال 5-10 سنوات. لكن هذا أكثر من فئة السحر والشامانية.

هناك طريقتان مختلفتان بشكل أساسي لإنشاء SBox.

الأول هو البحث العشوائي. يقوم المطورون بإنشاء جداول عشوائية وإلقاء نظرة على خصائصهم وتصفية تلك غير المناسبة. يستمر هذا حتى يكتفي المطورون بما وجدوه.

في العالم المتحضر ، يحدث هذا ، على سبيل المثال ، على النحو التالي:

يتم أخذ بعض القيمة الأولية ، على سبيل المثال ، اقتباس من كتاب أو الأرقام القليلة الأولى من Pi
يمتد من خلال التجزئة
يتم استخدام نتيجة التجزئة كبيانات لتكوين SBox.
إذا لم يكن SBox مناسبًا ، فاختر التجزئة الحالية ثم عد إلى الخطوة 2

بحيث يمكن لأي شخص إعادة إنتاج هذه العملية والتأكد من تلبية الحد الأدنى من المتطلبات للبحث العشوائي على الأقل.

هل تعرف أين تذهب البذور من الخوارزمية الرئيسية المتماثلة للبلد؟ فقدت ! اعتقدت أنهم لم يخبروهم بالتحديد ، السر موجود أو شيء ما ، لكن الزملاء الروس في EuroCrypt قالوا أنه خلال تطوير الخوارزمية في عام 2007 ، لسبب ما لم يكن أحد يعتقد أنه سيكون من الضروري تبرير تصميم جدول البحث ، والقيم التي خرج منها كانت إلى الأبد خسر. القصة جميلة ، فقط لا تنس أن الخوارزمية تم إنشاؤها ليس في المدرسة في استراحة ، ولكن في أحشاء FSB.

الطريقة الثانية هي إنشاء SBox بنفسك ، مع الاسترشاد بالجهاز الرياضي المتاح. هذا ما فعله مؤلفو AES ، وفعلوا جيدًا. إذا قارنا عدم خطية SBox AES و SM4 (المعيار الصيني) و Grasshopper (يستخدم نفس SBox مثل تجزئة Stribog) ، فإن النتيجة لن تكون في صالح الأخير

AES non-linearity (min، max) = (112.0، 112.0)
SM4 non-linearity (min، max) = (112.0، 112.0)
Streebog non-linearity (min، max) = (102.0، 110.0)

يستخدم رمز حساب اللاخطية تحويل Walsh وهو متاح هنا.

وثائق

حصلت على وثيقتين من ISO. في البداية ، يشرح مصممو Grasshopper كيف أنشأوا SBox ، في أخرى ، تناقش اللجنة حججهم.

من المستند الأول ، نحن مهتمون باقتباسين:

آمل أن يتم الآن إغلاق موضوع "Le Perrin بنفسه الذي طرح فكرة أن المؤلفين بحثوا عن SBox بشكل عشوائي".

من شروحات المصممين يتبع ذلك

لقد بحثوا حقًا عن SBox بطريقة عشوائية زائفة (وفقًا لمعايير الأمان)
لم يتم وضع هيكل خفي فيه.

وفي هذا المكان قاموا بتفكيكها بالكامل.

ما هو الهيكل؟

البنية المطبقة على جدول البحث هي خوارزمية تصف هذا الجدول.

الوثيقة المذكورة AES. لكن جدول البحث عن AES تم إنشاؤه في الأصل ليس عن طريق البحث العشوائي ، ولكن بمساعدة العديد من التقنيات الرياضية التي سمحت لنا بوصف طبقة غير خطية بها عدة صيغ . هذا ، بالمناسبة ، هو تفرد AES.

على العكس من ذلك ، إذا كنت تبحث عن SBox بشكل عشوائي ، فلا ينبغي أن يكون هناك مثل هذه الهياكل فيه والمشكلة مع Grasshopper SBox هي أن كلمات مصممي الخوارزمية مختلفة تمامًا عن الحقائق. كتبت عن هيكل جندب يسمى TKLog في مقال سابق ، هذه المرة دعونا نتحدث عن الهياكل بشكل عام.

Kolmogorov التعقيد

هذه هي نتيجة البحث الذي دار في مقال Leo Perrin الأخير عن الجندب.

تتمثل النظرة المضادة الرئيسية للمقالات حول الهياكل في Grasshopper SBox في أنه "في أي SBox تقريبًا ، يمكنك العثور على بنية ما إذا كنت ترغب في ذلك." و "على الرغم من أن احتمال العثور على الهيكل الذي وجده ليو لا يكاد يذكر ، إذا كان هناك SBox آخر ، فسيكون هناك آخر ، مع احتمال ضئيل للغاية."

دعنا نقول هذا هو هكذا. ولكن. كما اتضح ، من الممكن استنباط "درجة معينة من التنظيم" لـ SBox ، والتي لا تعتمد على احتمال الوقوع في هيكل أو آخر.

لكن ذلك يعتمد على حجم الخوارزمية اللازمة لإنشاء هذا SBox!

وهذا ما يسمى تعقيد Kolmogorov.

إذا كنت تتخيل SBox كسلسلة من البايتات ، في حالة وجود سلسلة عشوائية ، يجب ألا يكون هناك خوارزمية تنشئ هذه السلسلة وفي نفس الوقت تكون أصغر من هذه السلسلة.

للحصول على جندب

لذلك ، فإن حجم SBox هو 256 بايت. فيما يلي نسخة قابلة للقراءة من مدونة تأليف Leo Perrin ، التي تنفذ جدول Grasshopper. عند الإدخال ، يوجد بايت المصدر ، عند الإخراج البايت المقابل من Grasshopper SBox. الشرط الرئيسي لمثل هذه الخوارزمية هو فرض حظر على استخدام اللغة أو هياكل النظام الأساسي التي تقلل من حجم البرنامج. على سبيل المثال ، إذا كان يوجد في مكان ما داخل المكتبة القياسية ثابت يحتوي على نصف 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 ، Grasshopper ، SBox والبذور المفقودة