شبكات Feistel: لبنات بناء الشفرات الحديثة

في أوائل سبعينيات القرن العشرين، كان Horst Feistel يعمل في IBM Research على شيفرة Lucifer عندما توصّل إلى فكرة أساسية: يمكن بناء شيفرة قابلة للعكس باستخدام دالة جولة غير قابلة للعكس.

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

في شيفرة Feistel، تُقسَّم كتلة الإدخال إلى نصفين متساويين: L، وهو النصف الأيسر، وR، وهو النصف الأيمن. وتطبّق كل جولة دالة الجولة F على R، ثم تُجري XOR للناتج مع L، وبعد ذلك تبدّل النصفين.

بعد n جولة، يُعاد دمج النصفين لإنتاج النص المشفر. ويضمن التبديل معالجة النصفين في جولات متناوبة، مما يخلطهما بصورة شاملة.

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

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

يستخدم فك التشفير في شيفرة Feistel البنية نفسها تمامًا المستخدمة في التشفير، لكنه يطبّق مفاتيح الجولات الفرعية بترتيب عكسي. وهذا ممكن لأن XOR معكوس ذاتيًا: إذا كان A XOR B = C، فإن C XOR B = A.

وبما أن فك التشفير لا يستدعي أبدًا F^-1، أي معكوس F، فيمكن أن تكون دالة الجولة تجزئة غير قابلة للعكس أو جدول بحث أو أي عملية معقدة، من دون أن يؤثر ذلك في قابلية الشيفرة للعكس.

تكمن الأناقة الرياضية لشبكات Feistel في أن بنية XOR تضمن قابلية العكس بغض النظر عما تفعله F. وحتى إذا كانت F دالة أحادية الاتجاه مثل SHA-256، تظل شيفرة Feistel الكلية قابلة للعكس.

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

معيار تشفير البيانات (DES)، المنشور عام 1977، هو شيفرة Feistel من 16 جولة تعمل على كتل بحجم 64 بت باستخدام مفتاح بحجم 56 بت. وتستخدم كل جولة مفتاحًا فرعيًا مختلفًا بحجم 48 بت، مشتقًا من المفتاح الرئيسي.

تتضمن دالة الجولة في DES تبديل التوسعة، وإجراء XOR مع المفتاح الفرعي، وثمانية S-boxes توفر اللاخطية، وتبديلًا باستخدام P-box. ويوفر هذا المزيج كلًا من الإرباك والانتشار، وفقًا لمبادئ Shannon في تصميم الشفرات.

صمّم Bruce Schneier شيفرة Blowfish عام 1993، وهي شيفرة Feistel ذات طول مفتاح متغير من 32 إلى 448 بتًا وتتكون من 16 جولة. وتستخدم S-boxes تعتمد على المفتاح، مما يجعل الهجمات التي تعتمد على حسابات مسبقة غير عملية.

أما Twofish، وهو أحد المتأهلين للتصفيات النهائية في مسابقة AES، فيطوّر أفكار Blowfish باستخدام كتل بحجم 128 بت و16 جولة. ولا تزال كلتا الشيفرتين دون كسر، وتُستخدمان في تطبيقات مثل تجزئة كلمات المرور bcrypt، التي تستخدم إصدارًا معدلًا من Blowfish.

تقسّم شيفرة Feistel المتوازنة الكتلة إلى نصفين متساويين. أما Feistel غير المتوازنة فتستخدم نصفين غير متساويين، مثل تقسيم بنسبة 3/4 و1/4.

يمكن لشبكات Feistel غير المتوازنة أن توفر مزايا أمنية في سياقات معينة، وتُستخدم في بعض الشفرات المتخصصة. وتستخدم عائلة شفرات CAST بنية Feistel متوازنة بكتل حجمها 64 بت.

أثبت Michael Luby وCharles Rackoff عام 1988 أن شبكة Feistel من 3 جولات تستخدم دوال جولة شبه عشوائية تُعد تبديلًا شبه عشوائيًا آمنًا (PRP)، وأن إصدارًا من 4 جولات يُعد PRP قويًا.

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

تطبّق شبكة الاستبدال والتبديل (SPN) المستخدمة في AES الاستبدال والتبديل على الكتلة بأكملها في الوقت نفسه، بدلًا من تطبيقهما على نصف الكتلة في كل جولة. ويوفر ذلك انتشارًا أسرع.

يحقق AES انتشارًا كاملًا في 4 جولات فقط، بينما تحتاج بنية Feistel في DES إلى جولات أكثر لتحقيق انتشار مماثل. كما تتوافق بنية SPN في AES بصورة أفضل مع معماريات المعالجات الحديثة التي تتضمن تعليمات SIMD.

تتعامل مبرهنة Luby-Rackoff مع دالة الجولة F بوصفها دالة عشوائية حقيقية. أما عمليًا، فإن F هي دالة شبه عشوائية، مثل شيفرة أو تجزئة تعتمد على مفتاح، وليست عرّافة عشوائية حقيقية.

تُعد الفجوة بين البراهين النظرية والتطبيقات العملية موضوعًا متكررًا في علم التشفير. فالبراهين توفر الثقة، لكنها تعتمد على نماذج مثالية. ويعتمد الأمان في العالم الحقيقي أيضًا على تطبيقات آمنة خالية من ثغرات القنوات الجانبية.

اختبروا فهمكم لتصميم شبكة Feistel.

شبكات Feistel هي بنيات لشفرات الكتل تستخدم دالة جولة لا تحتاج إلى أن تكون قابلة للعكس. ويعمل فك التشفير بتشغيل البنية نفسها بالعكس، مع استخدام المفاتيح الفرعية بترتيب معكوس.

تُعد DES وBlowfish وTwofish جميعها شفرات Feistel. وتوفر مبرهنة Luby-Rackoff ضمانات نظرية للأمان. أما AES فيستخدم بنية SPN بدلًا من ذلك، مما يوفر انتشارًا أفضل في كل جولة.