التحليل التشفيري الخطي وجداول التقريب

التحليل الخطي (Matsui، 1993) هو هجوم بنصوص واضحة معروفة يعثر على تقريبات خطية (XOR لبتات محددة) للشيفرة تتحقق باحتمال p ≠ 1/2. وباستخدام عدد كبير من أزواج النصوص الواضحة والنصوص المشفّرة، يكشف الانحياز الإحصائي بتات المفتاح.

التقريب الخطي لصندوق S-box هو: مجموع بتات إدخال محددة XOR مجموع بتات إخراج محددة = 0 (mod 2) باحتمال p. ويُعبَّر عنه كما يلي: P[a·x XOR b·y = 0] = 1/2 + ε، حيث إن a وb قناعا بتات، وε هو الانحياز (ويُفضَّل أن يكون |ε| >> 0).

يحصي LAT: لكل قناع إدخال a وقناع إخراج b، عدد المدخلات x التي تحقق (a·x) XOR (b·S(x)) = 0. اطرح 2^{n-1} للحصول على الانحياز. يحتوي S-box الجيد على |max_bias| = 1 (باحتمال 1/2 ± 1/2^{n/2})، أي يكون مسطحًا قدر الإمكان.

في التقريبات الخطية المستقلة عبر جولات متعددة، تتضاعف الانحيازات: ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r. ويؤدي تقريب كل جولة إلى خفض الانحياز الفعّال إلى النصف. وبعد جولات كثيرة، يقترب الانحياز الكلي من 0، مما يتطلب عددًا أُسّيًا أكبر من الأزواج لاكتشافه.

لمهاجمة شيفرة من r جولة، ابحث عن مسار خطي ε عبر r-1 جولة. اجمع N = 1/ε^2 من النصوص الواضحة المعروفة. ولكل بايت مرشح من مفتاح الجولة الأخيرة k'، فك تشفير الجولة الأخيرة جزئيًا باستخدام XOR، وتحقق مما إذا كان التقريب الخطي يتحقق أكثر من N/2 مرة. يُظهر k' الصحيح الانحياز الصحيح.

هاجم Matsui شيفرة DES المكوّنة من 16 جولة في عام 1993 باستخدام تقريب خطي من 14 جولة بانحياز 2^{-21.4}. وتطلب ذلك 2^{43} من النصوص الواضحة المعروفة. استُعيدت 26 بتًا من المفتاح في المرحلة الأولى، واستُعيدت البتات الثلاثون المتبقية بالبحث الشامل. كان هذا أول هجوم عملي أسرع من القوة الغاشمة على DES بالكامل.

يمتلك AES S-box قيمة قصوى في LAT مقدارها |ε| = 4/256 = 1/64 لكل S-box. وتحد استراتيجية Wide Trail عدد S-box النشطة في أي مسار من 4 جولات ليكون ≥ 25. ويكون الانحياز الكلي ≤ (1/64)^{25/2} ≈ 2^{-75}. وهذا يتطلب 2^{150} من النصوص الواضحة المعروفة، وهو أمر غير قابل للتنفيذ عمليًا.

التفاضلي: أزواج من النصوص الواضحة المعروفة أو المختارة؛ يستغل فروق المخرجات. الخطي: نصوص واضحة معروفة؛ يستغل التقريبات الخطية الإحصائية. وكلاهما يعتمد على النصوص الواضحة المختارة في الهجمات العملية. كما أن كليهما من معايير التصميم: يجب أن تقاوم S-boxes كليهما (قيمة قصوى منخفضة في DDT وقيمة قصوى منخفضة في LAT).

استخدم تقريبات خطية متعددة في الوقت نفسه لتقليل تعقيد البيانات. وقد وسّع Nyberg وLeander أسلوب Matsui؛ إذ يؤدي دمج M من التقريبات إلى تقليل البيانات بعامل log(M). وقد طُبّق ذلك على PRESENT وSIMON وغيرها من الشيفرات خفيفة الوزن.

يُطبَّق التقريب الخطي على شيفرات التدفق للعثور على ارتباط بين keystream ودالة خطية لمخرج LFSR. ويتيح هذا الارتباط، إذا كان غير صفري، استعادة المفتاح بسرعة تفوق البحث الشامل. وقد ألهم ذلك تصميم دوال الدمج غير الخطية في شيفرات التدفق.

يتضمن تحليل Integral (Knudsen-Wagner) اختيار مجموعة من النصوص الواضحة، بحيث تأخذ بايتات معينة جميع القيم البالغ عددها 256، بينما تبقى البايتات الأخرى ثابتة. وبعد عدة جولات، يكون XOR لجميع المخرجات في مواضع معينة مساويًا لـ 0 (متوازنًا). ويستغل ذلك بنية AES، ويكسر AES ذا الجولات المخفّضة بكفاءة.

ماذا تنص لمّة التراكم بشأن دمج التقريبات الخطية؟

يعثر التحليل الخطي على تقريبات خطية منحازة لصناديق S-box. ويقاومه AES بفضل S-box المحسّن وفق LAT وتصميم Wide Trail. وقد كسر Matsui شيفرة DES باستخدام 2^43 من النصوص الواضحة المعروفة ومسار من 14 جولة. التالي: هجمات أعياد الميلاد والعثور على التصادمات.