اللقاء في المنتصف ومفاضلات الزمن والذاكرة

تقسم هجمات MITM الشيفرة إلى نصفين وتهاجم كل نصف على حدة. ينشئ المهاجم جدولًا من أحد الطرفين، ثم يبحث من الطرف الآخر عن تطابق. ويؤدي ذلك إلى خفض تعقيد الهجوم من O(2^{2n}) إلى O(2^n)، مقابل استخدام ذاكرة مقدارها O(2^n).

يطبق Double-DES خوارزمية DES مرتين: C = DES_{K2}(DES_{K1}(P)). مساحة المفاتيح: 2^{112}. هجوم MITM: بالنسبة إلى جميع قيم K1 البالغ عددها 2^{56}، احسب DES_{K1}(P) وخزّن الناتج. وبالنسبة إلى جميع قيم K2 البالغ عددها 2^{56}، احسب DES_{K2}^{-1}(C) وابحث عن الناتج في الجدول. التطابق → مرشح (K1, K2). لا يتطلب الأمر إجمالًا سوى 2^{57} من العمل.

الخطوة 1: شفّر النص الصريح P باستخدام جميع قيم K1 الممكنة → الجدول T[DES_{K1}(P)] = K1. الخطوة 2: لكل K2، فك تشفير النص المشفر C: v = DES^{-1}_{K2}(C). تحقق مما إذا كان v ∈ T. إذا كانت T[v] = K1 موجودة، فتحقق من (K1, K2) باستخدام زوج ثانٍ من النص الصريح والنص المشفر. من المتوقع وجود تطابق أو تطابقين زائفين؛ فتخلّص منهما.

يستخدم Triple-DES ‏(3DES) ثلاثة مفاتيح K1 وK2 وK3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). يظل MITM قابلًا للتطبيق، ولكن بفاعلية أقل: إذ يخفض 3DES ذو المفتاحين (K3=K1) العمل إلى 2^{112}. أما 3DES ذو المفاتيح الثلاثة، فتوجد له هجمة MITM تتطلب 2^{112} من العمل، وهو ما يفسر لماذا يوفر 3DES أمانًا فعليًا يبلغ نحو 112 بتًا فقط رغم أن مفتاحه يبلغ 168 بتًا.

اقترح Hellman (عام 1980) إجراء حساب مسبق لجدول من سلاسل (start_point, end_point) لتسريع البحث غير المتصل عن المفاتيح. عند إعطائك تجزئة مستهدفة أو نصًا مشفرًا، ابحث في جدول Hellman عن سلسلة تحتوي عليه. المقايضة: P = N (حاصل ضرب الزمن في الذاكرة = ثابت المساحة). وتشكل هذه الطريقة أساس جداول قوس قزح.

تحسن جداول قوس قزح (Oechslin، عام 2003) جداول Hellman باستخدام دوال اختزال مختلفة في كل موضع من السلسلة، مما يلغي الإنذارات الكاذبة (السلاسل المندمجة). وهي فعالة لكسر تجزئات كلمات المرور غير المملحة. ويستغرق البحث O(table_size/chain_length) من الزمن.

قيمة الملح هي قيمة عشوائية تُضاف إلى بداية كلمة المرور قبل تجزئتها: H(salt||password). وتنتج قيم الملح المختلفة قيم تجزئة مختلفة لكلمة المرور نفسها؛ لذلك تصبح جداول قوس قزح الخاصة بـ "password" عديمة الفائدة إذا استُخدمت قيمة ملح مختلفة. ويجب تخزين قيم الملح إلى جانب قيمة التجزئة.

تقسم هجمات MITM على AES-128 (10 جولات) الخوارزمية عند الجولة 5 — إذ تُشفّر الجولات الخمس الأولى إلى الأمام، وتُفك الجولات الخمس الأخيرة إلى الخلف، ثم يحدث الالتقاء في المنتصف. أفضل هجوم معروف هو هجوم biclique، الذي يخفض التعقيد من 2^{128} إلى 2^{126.1}؛ وهو غير عملي، لكنه يوضح أن AES لا يملك هامش أمان في مواجهة الأساليب الشبيهة بـ MITM.

بالنسبة إلى تجزئات Merkle-Damgard، يستطيع MITM العثور على صور سابقة أسرع من القوة الغاشمة في بعض البنى. ينشئ الهجوم جدولًا من كتل الرسائل بدءًا من IV، ثم يبحث إلى الخلف انطلاقًا من قيمة التجزئة المستهدفة. أما في مواجهة SHA-256 بجولاته الكاملة، فلا يزال التعقيد نحو 2^{255}، أي لا يوجد تحسن مقارنةً بالقوة الغاشمة.

يعمم هجوم التفكيك هجوم MITM ليشمل التقسيم إلى r أجزاء. في تقسيم الشيفرة إلى ثلاثة أجزاء، تُشفّر الثلث الأول من الجولات إلى الأمام، ويحدث الالتقاء في منتصف السلسلة، ثم تُفك الشيفرة إلى الخلف في الثلث الأخير. ويتطلب ذلك زمنًا قدره O(2^{n*2/3}) وذاكرة قدرها O(2^{n/3})، وهي مقايضة أكثر توازنًا.

يمكن منع هجمات MITM في البروتوكولات من خلال: استخدام مفاتيح طويلة مشتقة بواسطة KDF من كلمات مرور عالية الإنتروبيا (مما يقلل مساحة المفاتيح التي يمكن تعدادها)، أو استخدام رموز مادية (FIDO2) لا يغادر فيها المفتاح الجهاز، أو استخدام المصادقة بالمفتاح العام (إذ لا يوجد سر مشترك يمكن تعداده).

تقسم هجمات MITM الشيفرات إلى أنصاف، فتخفض الزمن من 2^{2n} إلى 2^n باستخدام ذاكرة قدرها 2^n. وهي تكسر Double-DES، بينما يخفف 3DES من أثرها لكنه يوفر أمانًا فعليًا قدره 112 بتًا. وتستخدم جداول قوس قزح منطق MITM لكسر كلمات المرور، ويمكن إحباطها باستخدام قيمة ملح. التالي: هجمات التوقيت وهجمات القنوات الجانبية.