تصميم DES وتشفير Lucifer

في عام 1971، طوّر Horst Feistel في IBM Research شيفرة تُسمى Lucifer ضمن مشروع لأمن الخدمات المصرفية لصالح Lloyd's of London. وكانت Lucifer واحدة من أوائل شفرات الكتل الحديثة، إذ استخدمت مفتاحًا بطول 128 بتًا وكتلًا بطول 128 بتًا.

أثبتت Lucifer إمكانية بناء شيفرة كتل قوية باستخدام بنية Feistel، التي تتناوب فيها جولات الاستبدال والتبديل وتُطبَّق على أنصاف الكتل. وكانت السلف المباشر لـ DES.

يطبّق DES عدد 16 جولة من بنية Feistel على كتل بطول 64 بتًا. وفي كل جولة، تُقسَّم الكتلة ذات الطول 64 بتًا إلى نصفين بطول 32 بتًا. ويُوسَّع النصف الأيمن إلى 48 بتًا، ثم يُجرى له XOR مع مفتاح فرعي بطول 48 بتًا، ويُمرَّر عبر S-boxes، ويُبدَّل، ثم يُجرى له XOR مع النصف الأيسر.

بعد ذلك يُبدَّل النصفان وتتكرر العملية. وبعد 16 جولة، ينتج عن تبديل نهائي النص المشفّر بطول 64 بتًا. ويستخدم فك التشفير البنية نفسها مع المفاتيح الفرعية بترتيب عكسي.

يشفّر DES البيانات في كتل بطول 64 بتًا (8 بايتات). كان حجم الكتلة الثابت هذا مناسبًا لأجهزة عام 1977، لكنه أصبح يمثل خطرًا أمنيًا. فعند معالجة كمية كافية من البيانات، تصبح تصادمات مفارقة أعياد الميلاد محتملة.

عند استخدام كتل بطول 64 بتًا، تظهر أنماط إحصائية بعد نحو 2^32 كتلة (نحو 32GB من البيانات المشفّرة باستخدام المفتاح نفسه). وقد جعل هجوم Sweet32 استخدام 3DES غير آمن لحركة البيانات الكبيرة مثل HTTPS.

يستخدم DES مفتاحًا بطول 64 بتًا، لكن 8 من هذه البتات هي بتات تكافؤ تُستخدم لكشف الأخطاء، وليست للتشفير. ولذلك لا يتجاوز طول المفتاح الفعلي 56 بتًا.

يعني هذا وجود 2^56 مفتاحًا محتملًا فقط لـ DES (أي نحو 72 كوادريليون مفتاح). وبحسب معايير عام 1977، كان ذلك يُعد كافيًا. أما بحلول عام 1997، فقد أصبح كسر هذا المفتاح ممكنًا عمليًا أمام مهاجم مصمم.

يبدأ DES بتبديل ابتدائي (IP) يعيد ترتيب البتات الأربعة والستين في كتلة النص الصريح، وينتهي بتبديل نهائي (IP^-1) يمثل المعكوس التام للتبديل الابتدائي. ولا يضيف هذان التبديلان أي قوة تشفيرية.

صُمِّما لتحقيق كفاءة عتادية على معماريات شرائح محددة في سبعينيات القرن الماضي، مما أتاح تحميل البتات في السجلات بسرعة أكبر. ويؤكد التحليل الحديث أنهما لا يسهمان بأي شيء في الأمان.

تُعد صناديق S-boxes الثمانية (صناديق الاستبدال) جوهر اللاخطية في DES. يأخذ كل صندوق S-box عدد 6 بتات من الإدخال وينتج 4 بتات من الإخراج باستخدام جدول بحث ثابت. ويحدد البتان الخارجيان الصف، بينما تحدد البتات الأربع الداخلية العمود.

من دون اللاخطية التي توفرها صناديق S-boxes، ستكون DES شيفرة خطية بالكامل ويمكن كسرها بسهولة باستخدام الجبر الخطي. ويقاوم التصميم المحدد لصناديق S-boxes في DES التحليل التشفيري التفاضلي.

بعد صناديق S-boxes، يطبّق DES تبديل P-box يعيد ترتيب بتات الإخراج الاثنتين والثلاثين الناتجة عن صناديق S-boxes. ويوفر ذلك الانتشار، إذ يوزّع مخرج كل صندوق S-box بحيث يؤثر في عدة صناديق S-boxes في الجولة التالية.

صُمِّم P-box بعناية لتحقيق أقصى قدر من الانتشار: إذ يؤثر كل بت خرج من صندوق S-box واحد في صندوقي S-box مختلفين على الأقل في الجولة التالية، مما يضمن حدوث تأثير الانهيار الجليدي بسرعة.

تشتق خوارزمية DES‏ 16 مفتاحًا فرعيًا مختلفًا بطول 48 بتًا من المفتاح الرئيسي ذي الطول 56 بتًا، مفتاحًا واحدًا لكل جولة. يبدأ جدول المفاتيح بتطبيق عملية الاختيار بالتبديل (PC-1) لإزالة بتات التكافؤ وإعادة ترتيب بتات المفتاح.

تُقسَّم البتات الـ56 إلى نصفين، طول كل منهما 28 بتًا، ويُدوَّر كل نصف إلى اليسار بمقدار موضع واحد أو موضعين في كل جولة. ثم تختار عملية الاختيار بالتبديل (PC-2) عددًا قدره 48 بتًا من أصل 56 بتًا لتكوين المفتاح الفرعي لكل جولة.

عملت NSA مع IBM أثناء تطوير DES، فقلّصت طول المفتاح من 128 بتًا في Lucifer إلى 56 بتًا، وعدّلت تصميمات صناديق S. وأثار ذلك جدلًا استمر عقودًا حول احتمال إدخال أبواب خلفية.

في تسعينيات القرن العشرين، أكد مسؤولون في NSA أنهم عززوا صناديق S لمقاومة التحليل التشفيري التفاضلي، وهي تقنية اكتشفتها IBM عام 1974. وكانت NSA تعرف التحليل التشفيري التفاضلي قبل الأوساط الأكاديمية بسنوات، مما يشير إلى أنها جعلت DES أكثر مقاومة، لا أضعف.

اعتمدت DES بوصفها معيار معالجة المعلومات الفيدرالي 46 في يناير 1977 بعد عملية تقييم تنافسية. وأصبحت خوارزمية التشفير القياسية للبيانات الحكومية غير المصنفة، واعتمدتها المصارف والقطاعات الصناعية على نطاق واسع.

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

خوارزمية DES نفسها هي خوارزمية تشفير كتلية، وتشفّر 64 بت بالضبط في كل مرة. وبما أن الرسائل الفعلية أطول، تحدد أوضاع التشغيل كيفية تطبيق الخوارزمية على كتل متعددة. وتشمل الأوضاع الشائعة ECB (تشفير كل كتلة بصورة مستقلة)، وCBC (إجراء XOR لكل كتلة مع النص المشفر السابق قبل التشفير)، وCFB، وOFB، وCTR.

يُعد ECB أضعف الأوضاع؛ إذ تنتج كتل النص الصريح المتطابقة كتلًا مشفرة متطابقة، مما يُنشئ أنماطًا ظاهرة. ويزيل وضعا CBC وCTR هذا الضعف، ويُفضَّلان عند استخدام DES و3DES عمليًا.

اختبروا معرفتكم بمعلمات تصميم DES.

تطورت DES من خوارزمية Lucifer التي طورتها IBM إلى خوارزمية Feistel من 16 جولة، بكتل طولها 64 بت ومفاتيح فعالة طولها 56 بت. ويستمد أمانها من 8 صناديق S غير خطية توفر الإرباك، ومن صندوق P الذي يوفر الانتشار، ومن الجولات الـ16 التي تضخم تأثير الانهيار الجليدي.

كان تدخل NSA في تصميم صناديق S مثيرًا للجدل، لكنه حسّن في نهاية المطاف مقاومتها للتحليل التشفيري التفاضلي. وقد ثبت أن مفتاح DES ذي الطول 56 بتًا، المصمم لعتاد عام 1977، غير كافٍ بحلول أواخر تسعينيات القرن العشرين.