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

التحليل التعموي (الإنكليزية: Cryptanalysis) هو دراسة مناهج استنباط المعلومات المشفرة دون وجود إمكانية وصول إلى المعلومات السرية التي غالباً ما يتطلب الوصول إليها لتحقيق الاستنباط. يتضمن هذا النشاط معرفة أسلوب التعمية والمفتاح السري.

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

تحليل التعمية التفاضلي والخطي

التساؤل الأول، على طول حياة خوارزمية DES، هو حول مدى ضعف هذه الخوارزمية تجاه الهجوم الأعمى، وذلك نتيجة لقصر طول المفتاح (56 خانة). لكن كان هناك أيضا اهتمام في ايجاد طريقة الهجوم على خوارزمية DES باستخدام تحليل التعمية. ومع زيادة شعبية نظم التعمية الكتلية ذات المفاتيح الطويلة، بما في ذلك خوارزمية DES الثلاثية، أصبح الهجوم الأعمى غير فعال. لذلك ازداد التأكيد على ايجاد طرق هجوم على خوارزمية DES وعلى بقية أنظمة التعمية المتناظرة باستخدام تحليل التعمية. سنقدم في هذا المقطع نظرة مختصرة على أكثر طريقتين فعالتين وواعدتين: تحليل التعمية التفاضلي، وتحليل التعمية الخطي.

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

مقالة مفصلة: تحليل التعمية التفاضلي

يعتبر تحليل التعمية التفاضلي واحدا من أهم التطورات التي طرأت على تحليل التعمية في السنوات الأخيرة. سنناقش في هذا المقطع هذه التقنية وتطبيقاتها على خوارزمية 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 (الأرقام مكتوبة بالست عشري

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

مقالة مفصلة: تحليل التعمية الخطي

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

سنوضح فيما يلي باختصار المبادئ التي اعتمد علهيا تحليل التعمية الخطية. ليكن لدينا نظام تشفير ما، والذي يكون فيه طول النص الصريح هو n خانة، أما طول المفتاح فهو m خانة. ولنرمز لكتلة النص الصريح P[1] ..P [n] ، بينما نرمز لكتلة النص المشفر C [1]..C[n]، أما المفتاح فسيأخذ الرمز K[1]…K[m] ، لنعرف بعد ذلك ما يلي:

A[I, j…k] = A[i] ө A[j] ө …+ A[k]

يهدف تحليل التعمية الخطي إلى ايجاد معادلة خطية من الشكل:

P[α1, α2…. Αa] ө C[β1, β2….βb] = K[γ1, γ2 …γc]

(حيث X تساوي 0 أو 1، 1≤C≤m، وحيث الرموز α و β و γتمثل مواقع خانات منفردة وثابتة)، يجب أن تكون هذه المعادلة محققة بالاحتمال P والذي لا يساوي 0.5. كلما بعد P عن القيمة 0.5 كلما كانت المعادلة أكثر كفاءة.

فاذا تم تحديد العلاقة المقترحة، عندها ستصبح الاجرائية هي حساب نتائج الطرف اليساري للمعادلة السابقة وذلك من أجل عدد كبير من أزواج النص الصريح-النص المشفر. اذا كانت النتيجة مساوية للصفر لأكثر من النصف عندها نفترض أن K[γ1, γ2 .. γc] = 0. اذا كانت النتيجة مساوية للواحد معظم الوقت، عندها نفتراض أن K[γ1, γ2 … γc] = 1. مما يعطينا معادلة خطية لحساب خانات المفتاح.

انظر أيضاً

مواضيع ذات صلة

Information security, the overarching goal of most cryptography
Security vulnerability; vulnerabilities can include cryptographic or other flaws
Security engineering, the design of applications and protocols
Information assurance, a term for information security often used in government
اقتصاد الأمن

عام

شخصيات تاريخية

Conel Hugh O'Donel Alexander
تشارلز بابدج
Lambros D. Callimahos
Alastair Denniston
Agnes Meyer Driscoll
Elizebeth Friedman
William F. Friedman, the father of modern cryptology
Meredith Gardner
Friedrich Kasiski
الكندي
Dilly Knox
Solomon Kullback
Marian Rejewski
Joseph Rochefort, whose contributions affected the outcome of the معركة ميدواي
Frank Rowlett
Abraham Sinkov
Giovanni Soro, the Renaissance's first outstanding cryptanalyst
John Tiltman
ألان تورنگ
هربرت ياردلي

روابط خارجية

Basic Cryptanalysis (files contain 5 line header, that has to be removed first)
Distributed Computing Projects
Simon Singh's crypto corner
The National Museum of Computing
UltraAnvil tool for attacking simple substitution ciphers

مراجع

د. م. سائد محمود الناظر، اعداد (2005). التعمية وأمن الشبكات – الجزء الأول (الطبعة الأولى ed.). سوريا: شعاع للنشر والعلوم.
Ibrahim A. Al-Kadi ,"The origins of cryptology: The Arab contributions”, Cryptologia, 16(2) (April 1992) pp. 97–126.
Friedrich L. Bauer: "Decrypted Secrets". Springer 2002. ISBN 3-540-42674-4
Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. ISBN 0-486-20097-3
David Kahn, "The Codebreakers - The Story of Secret Writing", 1967. ISBN 0-684-83130-9
Lars R. Knudsen: Contemporary Block Ciphers. Lectures on Data Security 1998: 105-126
Bruce Schneier, "Self-Study Course in Block Cipher Cryptanalysis", Cryptologia, 24(1) (January 2000), pp. 18–34.
Abraham Sinkov, Elementary Cryptanalysis: A Mathematical Approach, Mathematical Association of America, 1966. ISBN 0-88385-622-0
Christopher Swenson, Modern Cryptanalysis: Techniques for Advanced Code Breaking, ISBN 978-0470135938
Friedman, William F., Military Cryptanalysis, Part I, ISBN 0-89412-044-1
Friedman, William F., Military Cryptanalysis, Part II, ISBN 0-89412-064-6
Friedman, William F., Military Cryptanalysis, Part III, Simpler Varieties of Aperiodic Substitution Systems, ISBN 0-89412-196-0
Friedman, William F., Military Cryptanalysis, Part IV, Transposition and Fractionating Systems, ISBN 0-89412-198-7
Friedman, William F. and Lambros D. Callimahos, Military Cryptanalytics, Part I, Volume 1, ISBN 0-89412-073-5
Friedman, William F. and Lambros D. Callimahos, Military Cryptanalytics, Part I, Volume 2, ISBN 0-89412-074-3
Friedman, William F. and Lambros D. Callimahos, Military Cryptanalytics, Part II, Volume 1, ISBN 0-89412-075-1
Friedman, William F. and Lambros D. Callimahos, Military Cryptanalytics, Part II, Volume 2, ISBN 0-89412-076-X
Singh, Simon (1999), The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, London: Fourth Estate, pp. 143–189, ISBN 1-85702-879-1

ٍٍ

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

الكلمات الدالة: