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

الموسوعة الحرة

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

تاريخ

يُعزى اكتشاف ونشر التحليل التفاضلي للتشفير عمومًا إلى إيلي بيهام وآدي شامير في أواخر ثمانينيات القرن الماضي، حيث نشرا عددًا من الهجمات على مختلف خوارزميات التشفير الكتلي ووظائف التجزئة، بما في ذلك ثغرة نظرية في معيار تشفير البيانات (DES). وقد لاحظ بيهام وشامير أن معيار تشفير البيانات (DES) كان مقاومًا بشكلٍ لافتٍ للتحليل التفاضلي للتشفير، إلا أن تعديلات طفيفة على الخوارزمية من شأنها أن تجعله أكثر عرضةً للاختراق. [ 1 ] : 8-9

في عام ١٩٩٤، نشر دون كوبرسميث ، أحد أعضاء فريق IBM DES الأصلي، ورقة بحثية ذكر فيها أن IBM كانت على دراية بتحليل التشفير التفاضلي منذ عام ١٩٧٤، وأن الدفاع ضد هذا التحليل كان هدفًا أساسيًا من أهداف التصميم. [ ٢ ] ووفقًا للمؤلف ستيفن ليفي ، اكتشفت IBM تحليل التشفير التفاضلي بنفسها، ويبدو أن وكالة الأمن القومي كانت على دراية تامة بهذه التقنية. [ ٣ ] احتفظت IBM ببعض الأسرار، كما يوضح كوبرسميث: "بعد مناقشات مع وكالة الأمن القومي، تقرر أن الكشف عن اعتبارات التصميم سيكشف تقنية تحليل التشفير التفاضلي، وهي تقنية قوية يمكن استخدامها ضد العديد من أنظمة التشفير. وهذا بدوره سيضعف الميزة التنافسية التي تتمتع بها الولايات المتحدة على الدول الأخرى في مجال التشفير." [ ٢ ] داخل IBM، كان تحليل التشفير التفاضلي يُعرف باسم "هجوم T" [ ٢ ] أو "هجوم الدغدغة". [ ٤ ]

رغم أن خوارزمية DES صُممت مع مراعاة مقاومتها للتحليل التفاضلي للشفرات، إلا أن خوارزميات تشفير أخرى معاصرة أثبتت قابليتها للاختراق. وكانت خوارزمية FEAL هدفًا مبكرًا للهجوم . إذ يمكن اختراق النسخة الأصلية المقترحة ذات الأربع جولات (FEAL-4) باستخدام ثمانية نصوص عادية مختارة فقط ، بل إن نسخة FEAL ذات 31 جولة معرضة للهجوم أيضًا. في المقابل، يمكن لهذا النظام تحليل خوارزمية DES بنجاح بجهد يصل إلى 2^ 47 نصًا عاديًا مختارًا.

آليات الهجوم

عادةً ما يكون التحليل التفاضلي للتشفير هجومًا يعتمد على نص صريح مُختار ، ما يعني أن المهاجم يجب أن يكون قادرًا على الحصول على نصوص مشفرة لمجموعة من النصوص الصريحة التي يختارها. ومع ذلك، توجد امتدادات تسمح باستخدام نص صريح معروف أو حتى هجوم يعتمد على النص المشفر فقط . تستخدم الطريقة الأساسية أزواجًا من النصوص الصريحة المرتبطة بفرق ثابت . يمكن تعريف الفرق بعدة طرق، ولكن عملية "أو الحصرية" (XOR) هي الأكثر شيوعًا. يقوم المهاجم بعد ذلك بحساب الفروق بين النصوص المشفرة المتناظرة، على أمل اكتشاف أنماط إحصائية في توزيعها. يُطلق على زوج الفروق الناتج اسم " التفاضل" . تعتمد خصائصها الإحصائية على طبيعة صناديق الاستبدال (S-boxes) المستخدمة في التشفير، لذلك يقوم المهاجم بتحليل التفاضلات.(Δx،Δy){\displaystyle (\Delta _{x},\Delta _{y})}أين Δy=S(x⊕Δx)⊕S(x){\displaystyle \Delta _{y}=S(x\oplus \Delta _{x})\oplus S(x)} (ويرمز ⊕ إلى عملية "أو الحصرية") لكل صندوق استبدال S. في الهجوم الأساسي، يُتوقع أن يكون أحد اختلافات النص المشفر متكررًا بشكل خاص. وبهذه الطريقة، يمكن تمييز النص المشفر عن النص العشوائي . تسمح الاختلافات الأكثر تعقيدًا باستعادة المفتاح بشكل أسرع من البحث الشامل .

في أبسط أشكال استعادة المفاتيح عبر التحليل التفاضلي للتشفير، يطلب المهاجم النصوص المشفرة لعدد كبير من أزواج النصوص الأصلية، ثم يفترض أن التحليل التفاضلي صالح لمدة لا تقل عن r − 1 جولة، حيث r هو العدد الإجمالي للجولات. بعد ذلك، يستنتج المهاجم مفاتيح الجولات (للجولة الأخيرة) الممكنة، بافتراض أن الفرق بين الكتل قبل الجولة الأخيرة ثابت. عندما تكون مفاتيح الجولات قصيرة، يمكن تحقيق ذلك ببساطة عن طريق فك تشفير أزواج النصوص المشفرة بشكل شامل في جولة واحدة باستخدام كل مفتاح جولة ممكن. عندما يُعتبر مفتاح جولة ما مفتاحًا محتملاً للجولة أكثر بكثير من أي مفتاح آخر، يُفترض أنه مفتاح الجولة الصحيح.

بالنسبة لأي خوارزمية تشفير معينة، يجب اختيار فرق الإدخال بعناية لضمان نجاح الهجوم. يتم إجراء تحليل لبنية الخوارزمية الداخلية؛ وتتمثل الطريقة القياسية في تتبع مسار من الفروق ذات الاحتمالية العالية عبر مختلف مراحل التشفير، وهو ما يُسمى بالخاصية التفاضلية .

منذ أن أصبحت تقنية التحليل التفاضلي للشفرات معروفة للعامة، أصبحت مصدر قلق أساسي لمصممي الشفرات. ومن المتوقع أن تُرفق التصاميم الجديدة بأدلة تثبت مقاومة الخوارزمية لهذا الهجوم، وقد ثبتت فعالية العديد من الخوارزميات، بما في ذلك معيار التشفير المتقدم (ASC) ، ضد هذا الهجوم. [ 5 ]

هجوم مفصل

يعتمد الهجوم بشكل أساسي على حقيقة أن نمطًا معينًا لاختلاف المدخلات/المخرجات لا يظهر إلا لقيم محددة من المدخلات. عادةً ما يُطبق الهجوم على المكونات غير الخطية كما لو كانت مكونًا ثابتًا (عادةً ما تكون في الواقع جداول بحث أو مربعات استبدال ). تشير ملاحظة فرق المخرجات المطلوب (بين مدخلين نصيين عاديين مُختارين أو معروفين) إلى قيم مفاتيح محتملة.

على سبيل المثال، إذا حدث فرق 1 => 1 (أي أن اختلاف البت الأقل أهمية (LSB) في المدخلات يؤدي إلى اختلاف في البت الأقل أهمية في المخرجات) باحتمالية 4/256 (وهو أمر ممكن مع الدالة غير الخطية في تشفير AES على سبيل المثال)، فإن هذا الفرق ممكن فقط لأربع قيم (أو زوجين) من المدخلات. لنفترض أن لدينا دالة غير خطية حيث يتم تطبيق عملية XOR على المفتاح قبل التقييم، وأن القيم التي تسمح بهذا الفرق هي {2، 3} و{4، 5}. إذا أرسل المهاجم القيم {6، 7} ولاحظ فرق المخرجات الصحيح، فهذا يعني أن المفتاح إما 6 ⊕ K = 2، أو 6 ⊕ K = 4، أي أن المفتاح K إما 2 أو 4.

باختصار، لحماية التشفير من الهجوم، بالنسبة لدالة غير خطية مكونة من n بت، يُفضّل السعي إلى الحصول على قيمة قريبة قدر الإمكان من 2 −( n − 1) لتحقيق التوحيد التفاضلي . عندئذٍ، يتطلب الهجوم التفاضلي نفس الجهد المطلوب لتحديد المفتاح كما هو الحال في تجربة جميع الاحتمالات الممكنة. [ 6 ]

تتمتع دالة AES غير الخطية باحتمالية تفاضلية قصوى تبلغ 4/256 (معظم المدخلات إما 0 أو 2). هذا يعني أنه نظريًا، يمكن تحديد المفتاح بنصف الجهد المطلوب للتجربة الشاملة، إلا أن الفرع العالي في AES يمنع وجود أي آثار احتمالية عالية على مدار جولات متعددة. في الواقع، ستكون خوارزمية AES محصنة ضد الهجمات التفاضلية والخطية بنفس القدر باستخدام دالة غير خطية أضعف بكثير . يعني الفرع العالي للغاية (عدد صناديق الاستبدال النشطة) البالغ 25/4R أنه على مدار 8 جولات، لا يتضمن أي هجوم أقل من 50 تحويلًا غير خطي، مما يعني أن احتمالية النجاح لا تتجاوز Pr[attack] ≤ Pr[best attack on S-box] 50 . على سبيل المثال، مع صندوق الاستبدال الحالي، لا يُصدر معيار التشفير المتقدم (AES) أي فرق ثابت باحتمالية أعلى من (4/256) 50 أو 2⁻³⁰⁰ ، وهي أقل بكثير من العتبة المطلوبة البالغة 2⁻¹²⁸ لتشفير كتلة 128 بت. كان من شأن ذلك أن يُتيح مجالًا لصندوق استبدال أكثر كفاءة، فحتى لو كان موحدًا 16 بت، لكانت احتمالية الهجوم ستظل 2⁻²⁰⁰ .

لا توجد دوال تقابلية للمدخلات/المخرجات ذات الحجم الزوجي مع خاصية التوحيد الثنائي. توجد هذه الدوال في الحقول الفردية (مثل GF(2 7 )) باستخدام التكعيب أو الانعكاس (مع وجود أسس أخرى يمكن استخدامها أيضًا). على سبيل المثال، الدالة S(x) = x³ في أي حقل ثنائي فردي محصنة ضد التحليل التفاضلي والخطي للتشفير. وهذا جزئيًا ما يفسر استخدام تصميمات MISTY لدوال 7 و9 بت في الدالة غير الخطية ذات 16 بت. ما تكسبه هذه الدوال من مناعة ضد الهجمات التفاضلية والخطي، تخسره أمام الهجمات الجبرية. أي أنه من الممكن وصفها وحلها باستخدام محلل SAT . وهذا جزئيًا ما يفسر وجود تحويل خطي بعد الانعكاس في AES (على سبيل المثال).

أنواع متخصصة

انظر أيضاً

مراجع

  1. ↑ بيهام إي، شامير أ (1993). التحليل التشفيري التفاضلي لمعيار تشفير البيانات . نيويورك: سبرينغر فيرلاغ. ISBN 978-0-387-97930-4.
  2. 1 2 3 كوبرسميث د (مايو 1994). "معيار تشفير البيانات (DES) وقوته ضد الهجمات" (ملف PDF) . مجلة IBM للبحوث والتطوير . 38 (3): 243-250 . doi : 10.1147/rd.383.0243 .(الاشتراك مطلوب)
  3. ↑ ليفي، س. (2001). التشفير: كيف تغلب متمردو التشفير على الحكومة - إنقاذ الخصوصية في العصر الرقمي . دار بنجوين للنشر . الصفحات 55-56 . ISBN  0-14-024432-8.
  4. ↑ بليز م (15 أغسطس 1996). "ردًا على: الهندسة العكسية وشريحة كليبر" . sci.crypt .
  5. ↑ نيشفاتال ج، باركر إي، باشام ل، بور و، دوركين م، فوتي ج، روباك إي (مايو-يونيو 2001). " تقرير عن تطوير معيار التشفير المتقدم (AES)" . مجلة البحوث للمعهد الوطني للمعايير والتكنولوجيا . 106 (3): 511-577 . doi : 10.6028/jres.106.023 . PMC 4863838. PMID 27500035. 3.2.1.3.  
  6. ↑ إنديستيج، سيباستيان؛ برينيل، بارت (2009). "التصادمات العملية لـ EnRUPT" . في: دانكلمان، أور (محرر). التشفير البرمجي السريع . سلسلة محاضرات في علوم الحاسوب. المجلد 5665. برلين، هايدلبرغ: سبرينغر. الصفحات 246-259 . doi : 10.1007/978-3-642-03317-9_15 . ISBN   978-3-642-03317-9.

للمزيد من القراءة

  • بيهام إي، شامير أ (يناير 1991). "التحليل التشفيري التفاضلي لأنظمة التشفير الشبيهة بـ DES". مجلة علم التشفير . 4 (1): 3-72 . doi : 10.1007/BF00630563 . S2CID 33202054 . 
  • بيهام إي، وشامير أ (أغسطس 1992). "التحليل التشفيري التفاضلي لخوارزمية DES الكاملة ذات الـ 16 جولة". المؤتمر الدولي السنوي لعلم التشفير . سلسلة محاضرات في علوم الحاسوب. المجلد  740. برلين، هايدلبرغ: سبرينغر. الصفحات 487-496 . doi : 10.1007/3-540-48071-4_34 . ISBN  978-3-540-57340-1. S2CID 6188138 . مؤرشف من الأصل بتاريخ 2005-04-05. 
  • كنودسن إل آر، روبشو إم (2011). "التحليل التشفيري التفاضلي: الفكرة". دليل التشفير الكتلي . أمن المعلومات والتشفير. سبرينغر. ص 109-126 . doi : 10.1007/978-3-642-17342-4 . ISBN  978-3-642-17341-7.