تحليل التعمية التفاضلي

تحليل التعمية التفاضلي Differential cryptanalysis هو أحد أهم التطورات التي طرأت على تحليل التعمية في السنوات الأخيرة. سنناقش في هذا المقطع هذه التقنية وتطبيقاتها على خوارزمية DES.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 تاريخ

لم يتم نشر أي شئ حول تحليل التعمية التفاضلي حتى عام 1990. وأول جهود تم نشرها كانت متعلقة بتحليل التعمية لخوارزمية التشفير المدعوة FEAL وذلك من قبل Murphy. بعد ذلك ظهرت سلسلة من النشرات لكل من Shamir , Biham والتي بينت هذا النوع من الهوم على عدد من خوارزميات التعمية وتوابع المزج والتوزيع (has function).

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

ومع أن تحليل التعمية التفضالي يعتبر أداة قوية، إلا أنه لم يؤثر بشكل جيد على خوارزمية DES ويعود السبب في ذلك، حسب ما أدلى به عضو فريق IBM الذي صمم هذه الخوارزمية، إلى أن تحليل التعمية التفاضلي عرف من قبل الفريق عام 1974، حيث لعبت الحاجة إلى تقوية خوارزمية DES ضد الكسر باستخدام التحليل التفاضلي دورا كبيرا في تصميم صناديق S وعملية تبديل المواضع P. وكدليل على هذا الدور سنطرح المقارنة التالية: يحتاج تحليل التعمية التفاضلي لخوارزمية LUCIFER ذات الثماني مراحل إلى 256 نص صريح مختار، بينما يتطلب الهجوم على نموذج من خوارزمية DES بثماني مراحل أيضا إلى 214 نص صريح مختار.

 الهجوم باستخدام تحليل التعمية التفاضلي

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

سنبدأ بتغيير الوصف الخاص بخوارزمية DES. اذا افترضنا أن كتلة النص الصريح هي m والمؤلفة من النصفين m0, m1، يجري في كل مرحلة نقل نصف الدخل الأيمن إلى نصف الخرج الأيسر، أما نصف الخرج الأيمن فيكون نتيجة تابع دخله نصف الدخل الأيسر والمفتاح الجزئي الخاص بهذه المرحلة. لذلك سيتم في كل مرحلة انتاج كتلة جديدة بطول 32 خانة فقط. اذا أعطينا كل كتلة جديدة الرمز m1 (حيث 7 ≥ i ≥ 2)، عندها سيكون أنصاف الرسالة المرحلية مرتبطين بالشكل:

Mi+1 = mi-1 ө F(mi, Ki I = 1, 2, 3, …. 16

نبدأ في تحليل التعمية التفاضلي بالرسالتين m1, m مع معرفة فارق XOR بينهما، أي ∆ m = m ө m1 ، وليكن الفارق بين أنصاف الرسالة المرحلية هو ∆ m = m ө m11، عندها يكون لدينا:

∆ mi-1 = mi+1 ө m1i-1 = [mi-1 ө F(mi, ki)] ө [mi-1 ө F(mi-, ki)] = ∆mi-1 ө [F(mi, ki) ө f(mi, ki)]

لنفترض الآن بأن عدة أزواج من الدخل التابع f وبنفس الفارق تعطي نفس الفارق في الخرج اذا تم استخدام نفس المفتاح الجزئي. ولطرح ذلك بشلك أدق سنقول بأن X يمكن أن تنتج Y باحتمال مقداره P اذا كان الكسر P يميز كل الأزواج التي يكون من أجلها دخل XOR هو X وخرج XOR هو Y. لنفترض ان هناك عددا من القيم X التي تعطي باحتمال كبير فرقا معينا في الخرج. لذلك، اذا علمنا ∆ mi-1, ∆ mi باحتمال كبير، عندها يمكن معرفة ∆ mi-1 باحتمال كبير أيضا. والأكثر من ذلك، اذا أمكن تحديد عدد هذه الفروق فمن المحتمل تحديد المفتاح الجزئي المستخدم كدخل للتابع f.

تعتمد الاستراتيجية العامة لتحليل التعمية التفاضلي على هذه الاعتبارات لمرحلة واحدة. وتتلخص الاجرائية بالبدء بنصين صريحين m, m1 وفرق معطى، ومتابعتهما خلال نموذج محتمل من الفروقات بعد كل مرحلة وذلك لانتاج فرق محتمل للنص المشفر. عمليا هناك فرقان محتملان للنصين المؤلفين من 32 خانة (∆ m17||∆ m16). نخضع بعد ذلك m1, m للتعمية من أجل تحديد الفرق الحقيقي تحت مفتاح غير معروف ونقارن النتيجة مع الفرق المحتمل . اذا كان هناك تطابق، أي:

Ek (m) ө Ek (m1) = ∆ m17||∆m16

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

يوضح الشكل 3-10 كيفية توليد الفروقات لثلاث مراحل من خوارزمية DES. تشير الاحتمالات الموضحة على اليمين إلى الاحتمالات التي يمكن أن تظهرها مجموعة معطاة من الفروقات كتابع لفروقات الدخل. أخيرا، كما هو مبين، فإن احتمال فرق الخرج بعد ثلاثة مراحل يساوي 0.25X1X0.25 = 0.0625.

الشكل 3-10: التوليد التفاضلي خلال ثلاث مراحل من خورازمية DES (الأرقام مكتوبة بالست عشري)

 الأنواع المتخصصة

• Higher order differential cryptanalysis
• Truncated differential cryptanalysis
• Impossible differential cryptanalysis
• Boomerang attack

 انظر أيضاً

• علم التعمية
• تحليل التعمية الخطي

 المراجع

د. م. سائد محمود الناظر، اعداد (2005). التعمية وأمن الشبكات – الجزء الأول (الطبعة الأولى ed.). سوريا: شعاع للنشر والعلوم.

• Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
• Biham, E. and A. Shamir. (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology — CRYPTO '90. Springer-Verlag. 2-21.
• Eli Biham, Adi Shamir,"Differential Cryptanalysis of the Full 16-Round DES," CS 708, Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, December 1991. (Postscript)
• Eli Biham, slides from "How to Make a Difference: Early History of Differential Cryptanalysis"PDF (850 KB), March 16, 2006, FSE 2006, Graz, Austria

 وصلات خارجية

• A tutorial on differential (and linear) cryptanalysis
• Helger Lipmaa's links on differential cryptanalysis
• A description of the attack applied to DES