أساسيات التحليل التشفيري التفاضلي

تحليل التشفير التفاضلي (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-box الجيد على قيمة قصوى في 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} مرة.

إن AES S-box هو المعكوس الضربي فوق GF(2^8)، يليه تحويل أفيني. وتبلغ قيمته القصوى في DDT مقدار 4 (من أصل 256)، ما يعطي احتمالًا تفاضليًا ≤ 4/256 = 1/64 لكل S-box. يحتوي AES على 4 من S-box في كل جولة، لكن تصميم Wide Trail يضمن أن تكون المسارات التفاضلية الكاملة أقل من 2^{-100}.

يستخدم تصميم Wide Trail لجوان دايمن (المستخدم في AES/Rijndael) عدد التفرع B لـ MixColumns. ويؤدي أي مسار تفاضلي غير تافه عبر جولة واحدة إلى تفعيل ≥ B من S-box النشطة. وتضمن 4 جولات × 4 من S-box لكل جولة تفعيل ≥ 25 من S-box، وبالتالي احتمالًا < 2^{-100}.

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

الفرق التفاضلي المستحيل هو زوج (ΔP, ΔC) لا يمكن أن يحدث مع أي مفتاح. ويُستبعد أي مفتاح يحوّل زوجًا ملحوظًا (P, P') بهذا الفرق. وبجمع عدد كافٍ من الأزواج، تُستبعد جميع المفاتيح الخاطئة، ويبقى المفتاح الصحيح.

يجمع هجوم Boomerang (Wagner، 1999) بين فرقين تفاضليين قصيرين في هجوم تكيّفي بنصوص واضحة أو نصوص مشفّرة مختارة. ويقسّم الشيفرة إلى نصفين، لكل منهما فرق تفاضلي قصير وعالي الاحتمال، ما يتيح مهاجمة عدد من الجولات أكبر مما يسمح به أي فرق تفاضلي واحد.

ما الغرض من جدول التوزيع التفاضلي (DDT) في تحليل التشفير؟

يستغل تحليل التشفير التفاضلي انتشار الفروق من المدخلات إلى المخرجات باحتمال مرتفع. ويقاومه AES بفضل S-box المحسّن وفق DDT وتصميم Wide Trail. التالي: التحليل الخطي وجداول التقريب.