MD4 في RFC 1186: سرعة مقاسة وأمن قائم على التخمين

ملخص

سجل RFC 1186 معالجة 1,450,000 بايت في الثانية على Sun SPARC، ونحو 70,000 على DEC MicroVAX II، ونحو 32,000 على معالج 80286 بسرعة 20 ميغاهرتز. وقد وصف تقدير مقاومة التصادم بأنه تخمين.
حل RFC 1320 محل نص 1990 في 1992 ببرنامج مرجعي أسهل نقلاً. وفي 2011 نقل RFC 6150 MD4 إلى الحالة التاريخية بعد توثيق هجمات التصادم.

بدأ Ronald Rivest RFC 1186 عام 1990 بفكرة عملية: خذ ملفاً كبيراً، واحسب له بصمة قصيرة من 128 بت، ثم استخدمها في التوقيع بنظام RSA. سمّى الخوارزمية MD4. يستطيع المهندس قياس سرعة حساب هذه البصمة اليوم. أما قدرة خصم على صنع ملفين لهما البصمة نفسها فتحتاج إلى امتحان أطول بكثير.

للسرعة جدول واضح. على Sun SPARC بلغ الأداء 1,450,000 بايت في الثانية. على DEC MicroVAX II كان نحو 70,000. وعلى 80286 بتردد 20 ميغاهرتز، نحو 32,000. هذه نتائج لآلات محددة. وقدّم RFC الشيفرة بلغة C مع برنامج اختبار وتشغيل نموذجي. شرح أيضاً كلمات 32 بت وكتل 512 بت وطريقة الحشو وتسجيل طول الرسالة. كان بوسع القارئ تنفيذ الخوارزمية وفحص ما تفعله، من دون جداول استبدال كبيرة.

لأمن البصمة جدول من نوع آخر. قدّر Rivest أن صنع رسالتين تعطيان النتيجة نفسها يحتاج نحو 2^64 عملية. وقدّر أن العثور على رسالة تعطي بصمة محددة يحتاج نحو 2^128. سمّى ذلك تخميناً، وطلب المزيد من التحليل. سرعة البرنامج تقيس كلفة المحاولة الواحدة على جهاز معروف؛ لا تكشف الاختصار الذي قد يجده المهاجم في طريقة الحساب نفسها.

وُضعت MD4 في الملك العام للمراجعة والنظر في اعتمادها معياراً، وظلت وثيقة 1990 معلوماتية. إتاحة الشيفرة خدمت من ينفذ الخوارزمية ومن يبحث عن كسرها. في أبريل 1992، استبدل RFC 1320 الوثيقة الأولى، وسمّى قابلية نقل التنفيذ المرجعي أبرز تغيير. وأضاف معرّفاً للخوارزمية وقاعدة للمعاملات في تطبيقات OSI. صار حمل البرنامج إلى بيئات أخرى أسهل، فيما بقيت فرضية التصادم عرضة للتجربة المعاكسة.

سجل RFC 6150 نتيجة تلك التجربة بعد عقدين. أشار إلى هجوم عملي عام 1996 بكلفة تقارب 2^20 حساب MD4، ثم نتيجة من 2004 خفضت الكلفة إلى 2^8. انتقل تقدير 2^64 الأول من خطة أمنية إلى صفحة في تاريخ التصميم. وفي مارس 2011 نقل IETF وثيقة RFC 1320 إلى الحالة Historic، ودعا إلى الاستعاضة عن MD4 بخوارزميات موجودة مثل SHA-256.

أحصى RFC 6150 أيضاً استخدامات بقيت في البرمجيات، منها مسار توافق في منتجات Microsoft. سحب خوارزمية منشورة يستغرق سنوات. بعد تغيير حالة RFC، على فرق التشغيل العثور على الشيفرة التي ما زالت تستدعي MD4، وعلى الأنظمة التي تعتمد عليها. بدأت القصة بثلاث سرعات على طاولة اختبار؛ وانتهت بخريطة طويلة لمن يجب أن يغيّر برنامجه.