هجوم الالتقاء في المنتصف باستخدام 3 مجموعات فرعية

📅 آخر تحديث: ٢ أغسطس ٢٠٢٦
✍️ نُشر في: ٢ أغسطس ٢٠٢٦
📷 يحتوي على 17 صور
الموسوعة الحرة

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

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

تاريخ

طُرح هجوم الوسيط (MITM) لأول مرة في مقالٍ لديفي وهيلمان عام 1977 ، حيث ناقشا الخصائص التحليلية لخوارزمية DES. [ 1 ] جادلا بأن حجم مفتاح DES صغير جدًا، وأن إعادة تطبيق DES عدة مرات بمفاتيح مختلفة قد يكون حلاً لمشكلة حجم المفتاح؛ ومع ذلك، نصحا بعدم استخدام DES المزدوج واقترحا DES الثلاثي كحد أدنى، نظرًا لهجمات الوسيط (يُعد DES المزدوج عرضةً لهجوم الوسيط، حيث يمكن تقسيمه بسهولة إلى تشفيرين فرعيين (تشفير DES الأول والثاني) بمفاتيح مستقلة عن بعضها البعض، مما يسمح بهجوم وسيط أساسي يقلل من التعقيد الحسابي).2112(=22×56){\displaystyle 2^{112}(=2^{2\times 56})}ل257(=2×256){\displaystyle 2^{57}(=2\times 2^{56})}.

ظهرت العديد من التعديلات منذ أن اقترح ديفي وهيلمان هجمات الوسيط. هذه التعديلات إما تجعل هجمات الوسيط أكثر فعالية، أو تسمح باستخدامها في حالات لا يُمكن فيها استخدام النسخة الأساسية. وقد عرض بوغدانوف وريشبيرغر نسخة المجموعة الفرعية الثلاثية في عام 2011، [ 2 ] وأثبتت فعاليتها في تحليل التشفير، مثل عائلة تشفير الكتل الخفيفة KTANTAN.

إجراء

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

مرحلة تقليل المفاتيح

في مرحلة تقليل عدد المفاتيح، يتم تقسيم الشفرة المستهدفة إلى شفرتين فرعيتين.و{\displaystyle f}وز{\displaystyle g}لكلٍّ منهما بتات مفتاح مستقلة، كما هو معتاد في هجمات الوسيط. وبدلاً من التقيد بشرط استقلال بتات مفتاح التشفيرين الفرعيين، يسمح هجوم المجموعة الفرعية الثلاثية بتقسيم التشفير إلى تشفيرين فرعيين، حيث يُسمح باستخدام بعض البتات في كليهما.

ويتم ذلك عن طريق تقسيم المفتاح إلى ثلاث مجموعات فرعية بدلاً من ذلك، وهي:

  • أ0{\displaystyle A_{0}}= بتات المفتاح المشتركة بين التشفيرين الفرعيين.
  • أ1{\displaystyle A_{1}}= بتات المفتاح المميزة للتشفير الفرعي الأول،و.{\displaystyle f.}
  • أ2{\displaystyle A_{2}}= بتات المفتاح المميزة للتشفير الفرعي الثاني،ز{\displaystyle g}

لتنفيذ هجوم الوسيط الآن، يتم اختبار المجموعات الفرعية الثلاث بشكل فردي باستخدام أسلوب التجربة والخطأ، وفقًا للإجراء التالي:

  1. لكل تخمين منأ0{\displaystyle A_{0}}:
    1. احسب القيمة الوسيطةأنا{\displaystyle i}من النص الأصلي، لجميع تركيبات المفتاح والبت فيأ1{\displaystyle A_{1}}
    2. احسب القيمة الوسيطةج{\displaystyle j}، لجميع تركيبات المفتاح والبت فيأ2{\displaystyle A_{2}}
    3. يقارنأنا{\displaystyle i}وج{\displaystyle j}عند وجود تطابق، يتم تخزينه كمرشح رئيسي.

مرحلة اختبار المفاتيح

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

مثال

يستند المثال التالي إلى الهجوم الذي نفذه ريشبيرغر وبوغدانوف على عائلة تشفير KTANTAN. وتُستخدم اصطلاحات التسمية الواردة في بحثهما في هذا المثال أيضًا. يُقلل الهجوم من التعقيد الحسابي لـ KTANTAN32 إلى275.170{\displaystyle 2^{75.170}}، أسفل من280{\displaystyle 2^{80}}بالمقارنة مع هجوم القوة الغاشمة. التعقيد الحسابي هو275.170{\displaystyle 2^{75.170}}لا يزال اختراق خوارزمية KTANTAN48 وKTANTAN64، التي يعود تاريخها إلى عام 2014، غير عملي، وبالتالي فإن الهجوم غير ممكن حسابيًا في الوقت الحالي. وينطبق الأمر نفسه على KTANTAN48 وKTANTAN64، ويمكن الاطلاع على تعقيداتهما في نهاية المثال.

يُمكن تنفيذ هذا الهجوم نظرًا لاستغلال نقاط الضعف في جدولة المفاتيح الثنائية لخوارزمية KTANTAN. وينطبق هذا الهجوم على كلٍ من KTANTAN32 وKTANTAN48 وKTANTAN64، حيث تستخدم جميعها نفس جدولة المفاتيح. ولا ينطبق على عائلة خوارزميات التشفير الكتلية KANTAN ذات الصلة، نظرًا لاختلاف جدولة المفاتيح بين KTANTAN وKANTAN.

نظرة عامة على KTANTAN

KTANTAN هي خوارزمية تشفير كتلية خفيفة الوزن، مصممة خصيصًا للمنصات ذات الموارد المحدودة مثل بطاقات RFID ، حيث يكون استخدام خوارزمية تشفير أساسية مثل AES إما مستحيلاً (نظرًا لمحدودية إمكانيات الجهاز) أو مكلفًا للغاية. ابتكرها كانيير ودونكلمان وكنيزيفيتش عام 2009. [ 3 ] تعتمد الخوارزمية على حجم كتلة بيانات يتراوح بين 32 و48 و64 بت، وتقوم بتشفيرها باستخدام مفتاح طوله 80 بت على مدار 254 دورة. تستخدم كل دورة بتين من المفتاح (يتم اختيارهما وفقًا لجدول المفاتيح ) كمفتاح للدورة.

هجوم

تحضير

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

وبشكل أدق، وجد منفذو الهجوم ما يلي:

  • الجولات من 1 إلى 111 لا تستخدم بتات المفتاح أبدًا:ك32،ك39،ك44،ك61،ك66،ك75{\displaystyle k_{32},k_{39},k_{44},k_{61},k_{66},k_{75}}
  • لا تستخدم الجولات من 131 إلى 254 بتات المفتاح أبدًا:ك3،ك20،ك41،ك47،ك63،ك74{\displaystyle k_{3},k_{20},k_{41},k_{47},k_{63},k_{74}}

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

  • أ0{\displaystyle A_{0}}= البتات الرئيسية المستخدمة من قبل كلا الكتلتين (مما يعني البتات الـ 68 المتبقية غير المذكورة أعلاه)
  • أ1{\displaystyle A_{1}}= البتات الرئيسية المستخدمة فقط بواسطة الكتلة الأولى (المحددة بواسطة الجولة 1-111)
  • أ2{\displaystyle A_{2}}= البتات الرئيسية المستخدمة فقط بواسطة الكتلة الثانية (المحددة في الجولة 131-254)

مرحلة تقليل المفاتيح

قد يلاحظ المرء مشكلة في الخطوة 1.3 في مرحلة تقليل المفاتيح. لا يمكن مقارنة قيمأنا{\displaystyle i}وج{\displaystyle j}، مثلأنا{\displaystyle i}يتم حسابها في نهاية الجولة 111، وج{\displaystyle j}يتم حسابها في بداية الجولة 131. ويتم التخفيف من ذلك باستخدام تقنية أخرى من تقنيات MITM تسمى المطابقة الجزئية . وقد وجد المؤلفون ذلك من خلال الحساب الأمامي من القيمة الوسيطة.أنا{\displaystyle i}، وإلى الوراء من القيمة المتوسطةج{\displaystyle j}أنه في الجولة 127، ظلت 8 بتات دون تغيير في كليهماأنا{\displaystyle i}وج{\displaystyle j}باحتمالية واحد. لذا، قارنوا جزءًا فقط من الحالة، بمقارنة تلك البتات الثمانية (كانت 8 بتات في الجولة 127 لـ KTANTAN32، و10 بتات في الجولة 123 و47 بتًا في الجولة 131 لـ KTANTAN48 وKTANTAN64 على التوالي). ينتج عن ذلك المزيد من النتائج الإيجابية الخاطئة، لكن لا شيء يزيد من تعقيد الهجوم بشكل ملحوظ.

مرحلة اختبار المفاتيح

يتطلب برنامج KTANTAN32 حاليًا زوجين من البيانات في المتوسط ​​للعثور على المفتاح المرشح، وذلك بسبب النتائج الإيجابية الخاطئة الناتجة عن مطابقة جزء فقط من حالة القيم الوسيطة. بينما لا يزال برنامجا KTANTAN48 وKTANTAN64 يتطلبان في المتوسط ​​زوجًا واحدًا فقط من النص الأصلي/المشفر لاختبار المفاتيح المرشحة الصحيحة والعثور عليها.

نتائج

ل:

  • KTANTAN32، التعقيد الحسابي للهجوم المذكور أعلاه هو275.170{\displaystyle 2^{75.170}}، مقارنة ب280{\displaystyle 2^{80}}باستخدام بحث شامل عن المفتاح. يبلغ تعقيد البيانات 3 أزواج من النص العادي/المشفر.
  • KTANTAN48، التعقيد الحسابي هو275.044{\displaystyle 2^{75.044}}ويلزم وجود زوجين من النصوص العادية/المشفرة.
  • KTANTAN64 هو275.584{\displaystyle 2^{75.584}}ويلزم وجود زوجين من النصوص العادية/المشفرة.

تم استخلاص النتائج من مقالة ريشبيرغر وبوغدانوف.

لم يعد هذا أفضل هجوم على KTANTAN. أفضل هجوم حتى عام 2011 كان من إسهامات وي، وريشبيرغر، وغو، وو، ووانغ، ولينغ، والذي حسّن هجوم الوسيط على عائلة KTANTAN. [ 4 ] وقد توصلوا إلى تعقيد حسابي قدره272.9{\displaystyle 2^{72.9}}باستخدام 4 أزواج مختارة من النصوص العادية/المشفرة باستخدام تقنيات المطابقة الجزئية غير المباشرة وتقنيات القطع والوصل MITM.

ملحوظات