Analyzing Linear Layers in Related-Differential Cryptanalysis

ملخص تقني: تحليل الطبقات الخطية في تحليل التشفير التفاضلي المرتبط

بيان المشكلة
في التشفيرات القائمة على بنية الـ SPN (مثل AES)، يتم إنشاء طبقة الانتشار الخطي عادةً باستخدام مصفوفات MDS (القصوى من حيث المسافة) لضمان أرقام تفرع مثالية ومقاومة ضد هجمات التحليل التفاضلي والخطي الكلاسيكية. ومع ذلك، كشفت أعمال حديثة بواسطة Daemen و Rijmen (2009) و Bardeh و Rijmen (2022) أن مصفوفات MDS لا تزال يمكن أن تُظهر هياكل "تفاضلية مرتبطة". تسمح هذه الهياكل ببناء خصائص تفاضلية مرتبطة يمكن استغلالها في الهجمات، مثل هجوم استعادة المفتاح لـ 7 جولات في AES-128. وبينما حددت الدراسات السابقة وجود تفاضلات مرتبطة في حالات محددة (مثل المصفوفات الدورانية 4×4، والمصفوفات الارتدادية 3×3)، فإن الفهم المنهجي للطبقات الخطية التي تتجنب أو تقبل هذه التفاضلات بطبيعتها لا يزال غير مكتمل. يبحث هذا البحث في الشروط التي تتجنب بموجبها الطبقات الخطية التفاضلات المرتبطة، بهدف تحديد فئات المصفوفات المقاومة طبيعيًا لهذا النوع من المتجهات التشفيرية.

المنهجية
يستخدم المؤلفون نهجًا جبريًا نظريًا فوق الحقول المحدودة ذات الخصائص 2 ($\mathbb{F}_{2^m}$). وتتضمن المنهجية ما يلي:

1. تعريف التفاضلات المرتبطة: استخدام تعريفات Daemen و Rijmen، حيث تكون التفاضلات $(u, Mu)$ و $(v, Mv)$ "مرتبطة" إذا كان الزوج المدخل $(u, v)$ والزوج المخرج $(Mu, Mv)$ يحققان الشرط $x_i \cdot y_i \cdot (x_i \oplus y_i) = 0$ لجميع الإحداثيات.
2. التحليل الهيكلي: استقصاء العلاقة بين خصائص المصفوفة (حالة MDS، التماثل، الهيكل الدوري) ووجود أزواج تفاضلية مرتبطة غير بديهية.
3. التفكك متعدد الحدود: بالنسبة للمصفوفات الدورانية، يقوم المؤلفون بربط عمليات المصفوفة بضرب متعددات الحدود في حلقة القسمة $\mathbb{F}_{2^m}[X]/\langle X^n - 1 \rangle$. يقومون بتفكيك متعدد حدود التحويل بناءً على الحسابات النمطية للأسس (بمعاملات 2، 3، و 4) لبناء أزواج فروق مدخلات محددة تنتج فروق مخرجات مرتبطة.
4. الحصر حالة بحالة: بالنسبة لحالة $3 \times 3$، يستخدم المؤلفون تفكيك أي مصفوفة MDS إلى شكل ممثل $M = D_1 M_1 D_2$ (حيث $D_i$ مصفوفات قطرية و $M_1$ هو ممثل محدد). يقومون بتحليل جميع أنماط وزن هامينغ (Hamming weight) لثلاثيات فرق المدخلات $(u, v, u \oplus v)$ بشكل منهجي لاستخلاص الشروط الجبرية الضرورية والكافية لغياب التفاضلات المرتبطة.

المساهمات والنتائج الرئيسية

1. ضرورة خاصية MDS:
   يثبت البحث أن خاصية MDS هي شرط ضروري لتجنب التفاضلات المرتبطة. وتحديدًا، توضح النظرية 2 أن كل مصفوفة غير MDS تقبل على الأقل زوجًا واحدًا من التفاضلات المرتبطة غير البديهية. وهذا يضيق نطاق البحث عن الطبقات الخطية المقاومة ليقتصر حصريًا على فئة مصفوفات MDS.

2. هشاشة المصفوفات المتماثلة:
   يؤكد المؤلفون أن التماثل في الأبعاد الفردية يمثل ثغرة متأصلة. تثبت النظرية 4 أن كل مصفوفة MDS متماثلة ذات رتبة فردية تقبل تفاضلات مرتبطة. هذه النتيجة تستبعد عائلات واسعة من البناء، بما في ذلك مصفوفات Cauchy من النوع 2 والمصفوفات الدورانية اليسارية ذات الرتبة الفردية (الاستنتاجات 2 و 3)، لأنها متماثلة بطبيعتها وبالتالي فهي عرضة للهجوم.

3. هشاشة المصفوفات الدورانية:
   يقدم البحث توصيفًا شاملاً للمصفوفات الدورانية. من خلال تحليل الخصائص النمطية لرتبة المصفوفة $n$، يثبت المؤلفون في النظرية 5 أن مصفوفة MDS دورانية من الرتبة $n$ تقبل تفاضلات مرتبطة كلما كانت $n \not\equiv \pm 2 \pmod{12}$. هذا يعمم النتائج السابقة لحالات $3 \times 3$ و $4 \times 4$، ويحدد فئة واسعة من الرتب المعرضة للخطر.

4. التوصيف الكامل لمصفوفات $3 \times 3$:
   بإعادة النظر في حالة $3 \times 3$، يستنتج المؤلفون توصيفًا جبريًا كاملًا. توفر النظرية 7 مجموعة صريحة من 15 قيدًا متعدد الحدود ضروريًا وكافيًا لمعاملات مصفوفة $3 \times 3$ ممثلة. إذا تحقق أي من هذه القيود الـ 15، فإن المصفوفة تقبل تفاضلات مرتبطة؛ وإذا لم يتحقق أي منها، فإن المصفوفة تكون مقاومة.

• يشير البحث إلى أن التوصيفات السابقة (مثل Otal et al.) كانت غير مكتملة.
• باستخدام هذا التوصيف، قام المؤلفون بحساب العدد الدقيق لمصفوفات $3 \times 3$ MDS عبر حقول محدودة مختلفة ($\mathbb{F}_{2^m}$) التي لا تمتلك تفاضلات مرتبطة، مما يوضح أن مجموعة المصفوفات المقاومة هي مجموعة جزئية صارمة من جميع مصفوفات MDS (الجدول I).

الأهمية والادعاءات
يزعم البحث أنه يقدم تحقيقًا منهجيًا للمتطلبات الهيكلية لمقاومة تحليل التشفير التفاضلي المرتبط. تكمن أهميته الأساسية في:

• وضع الحدود: إثبات أن خاصية MDS وحدها غير كافية للمقاومة، وأن خصائص هيكلية معينة (التماثل ذو الرتبة الفردية، الرتب الدورية المحددة) تضمن الضعف.
• تحسين معايير التصميم: تقديم مجموعة ملموسة وقابلة للتحقق من 15 قيدًا جبريًا لمصفوفات $3 \times 3$، مما يسمح للمصممين بالتحقق الشامل أو بناء مصفوفات مقاومة في هذا البعد.
• توجيه البناء المستقبلي: من خلال تحديد أن المصفوفات غير الـ MDS معرضة للخطر بطبيعتها، وأن العديد من البناءات المتماثلة الشائعة تفشل، يوجه العمل الأبحاث المستقبلية نحو بناء مصفوفات MDS تكون غير متماثلة (أو متماثلة ذات رتب زوجية) وتحقق أيضًا القيود الجبرية المحددة للمقاومة.

يخلص المؤلفون إلى أنه بينما تم التوصيف الكامل لحالة $3 \times 3$، فإن توسيع هذه النتائج لتشمل مصفوفات $4 \times 4$ وبناء مصفوفات MDS خفيفة الوزن وفعالة بدون تفاضلات مرتبطة لا يزال يمثل تحديات مفتوحة. كما يشيرون إلى أن الحالات غير المحلولة للمصفوفات الدورانية (حيث $n \equiv \pm 2 \pmod{12}$) تمثل فرضية للبحث المستقبلي.