كيف تم كسر DES؟

لدى DES عدد قدره 2^56 من المفاتيح الممكنة، أي ما يقارب 72 كوادريليون مفتاح (72,057,594,037,927,936). ورغم أن هذا العدد يبدو هائلًا، فإنه فضاء محدود يمكن البحث فيه بصورة منهجية بقدرة حوسبية كافية.

يتطلب استنفاد فضاء المفاتيح (القوة الغاشمة)، في المتوسط، اختبار نصف فضاء المفاتيح قبل العثور على المفتاح الصحيح. وبالنسبة إلى DES، يعني ذلك إجراء نحو 2^55 عملية فك تشفير تجريبية، تستغرق كل منها بضع عمليات على العتاد الحديث.

في عام 1997، عرضت RSA Data Security جائزة قدرها $10,000 مقابل كسر رسالة مشفرة باستخدام DES. ونسّق Rocke Verser جهدًا للحوسبة الموزعة عبر عشرات الآلاف من أجهزة الكمبيوتر المتصلة بالإنترنت.

بعد 96 يومًا من البحث، عُثر على المفتاح. وكان النص الصريح هو "Strong cryptography makes the world a safer place." وقد أثبت هذا الجهد إمكانية كسر DES، لكنه تطلب أشهرًا وتنسيقًا هائلًا.

أنشأت Electronic Frontier Foundation جهاز Deep Crack بتكلفة $250,000 عام 1998. وكان يحتوي على 1,856 دائرة ASIC مخصصة، كل منها قادر على اختبار 2.5 مليون مفتاح DES في الثانية، مما منح Deep Crack معدلًا إجماليًا يتجاوز 90 مليار مفتاح في الثانية.

كان Deep Crack قادرًا على استنفاد فضاء مفاتيح DES بأكمله خلال نحو 9 أيام في المتوسط. وكان ذلك دليلًا على أن خصمًا مصممًا، باستثمار قدره $250,000، يستطيع كسر DES خلال أقل من أسبوعين.

في تحدي DES II-1 (فبراير 1998)، تعاون Deep Crack مع شبكة الحوسبة التطوعية distributed.net وتمكن من كسر DES خلال 39 يومًا فقط. أما تحدي II-2 (يوليو 1998) فسقط خلال 56 ساعة.

أظهر التحسن السريع من 96 يومًا إلى 56 ساعة خلال عام واحد مدى سرعة تسريع تحسينات العتاد والتنسيق الأفضل لهجمات القوة الغاشمة.

في يناير 1999، تعاون Deep Crack التابع لـEFF مع distributed.net وتمكن من كسر DES Challenge III خلال 22 ساعة و15 دقيقة فقط، وفاز بجائزة قدرها $10,000 من RSA Security.

أنهى هذا العرض الحاسم لإمكانية كسر DES خلال أقل من 24 ساعة فعليًا أي جدال حول أمان DES. وبعد ذلك بوقت قصير، بدأ NIST عملية اختيار بديل لـDES، فأصبحت AES هي البديل.

نظّمت distributed.net جهودًا للحوسبة التطوعية، تبرع فيها مستخدمو الإنترنت العاديون بدورات وحدة المعالجة المركزية الخاصة بهم لتحديات DES. وعند الذروة، شارك مئات الآلاف من أجهزة الكمبيوتر.

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

ينجح استنفاد المفاتيح لأن كل عملية فك تشفير لـDES سريعة (تستغرق ميكروثوانٍ على العتاد) ومستقلة. فلا يوجد اعتماد بين اختبار المفتاح N واختبار المفتاح N+1، ولذلك يمكن توزيع البحث بالتوازي بصورة مثالية على أي عدد من الأجهزة.

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

نشر Eli Biham وAdi Shamir التحليل التشفيري التفاضلي عام 1990، وهي تقنية تستغل كيفية انتشار الاختلافات في أزواج المدخلات عبر جولات خوارزمية التشفير. وبالنسبة إلى DES، تتطلب هذه التقنية نظريًا 2^47 نصًا صريحًا مختارًا.

كُشف لاحقًا أن صناديق S في DES صُممت مع مراعاة مقاومتها للتحليل التشفيري التفاضلي، مما يشير إلى أن NSA كانت تعرف هذه التقنية في سبعينيات القرن العشرين. والهجوم مثير للإعجاب نظريًا، لكنه يتضاءل عمليًا أمام القوة الغاشمة باستخدام العتاد.

نشر Mitsuru Matsui التحليل التشفيري الخطي عام 1993، وكان يتطلب 2^43 نصًا صريحًا معروفًا لمهاجمة DES. وقد نفذ الهجوم وتمكن تجريبيًا من كسر DES عام 1994، مؤكدًا التحليل النظري.

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

نُشر التحليل التشفيري التفاضلي عام 1990، لكنه يتطلب نصوصًا صريحة مختارة، وهو أمر غير عملي في معظم السيناريوهات الواقعية. ونُشر التحليل التشفيري الخطي عام 1993، ويعمل باستخدام نصوص صريحة معروفة، لكنه يتطلب 2^43 نصًا منها.

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

كانت لعملية كسر DES المعلنة والموثقة آثار فورية على سياسة الأمن. بدأ NIST عملية منافسة AES عام 1997، وهو العام نفسه الذي نجح فيه تحدي DES الأول. وصُممت المنافسة صراحةً لتجنب نقاط ضعف عملية توحيد DES.

بدأت المصارف والوكالات الحكومية الانتقال إلى 3DES كتدبير مؤقت أثناء تطوير AES. وقد حدد الجدول الزمني لكسر DES مباشرةً مدى إلحاح جهود اعتماد AES وجدولها الزمني.

كُسرت DES بوتيرة متسارعة: خلال 96 يومًا عام 1997، و56 ساعة عام 1998، و22 ساعة عام 1999. واستخدم Deep Crack التابع لـEFF، بتكلفة $250,000، دوائر ASIC مخصصة لاختبار 90 مليار مفتاح في الثانية.

يكسر كل من التحليل التشفيري التفاضلي (2^47 نصًا صريحًا مختارًا) والتحليل التشفيري الخطي (2^43 نصًا صريحًا معروفًا) خوارزمية DES نظريًا، لكن القوة الغاشمة باستخدام العتاد كانت العامل الحاسم عمليًا. وأنهى الكسر خلال 22 ساعة حياة DES بوصفها خوارزمية تشفير قابلة للاستخدام.