Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

تخيل الإنترنت كمدينة صاخبة وعملاقة حيث يحاول الجميع إرسال رسائل سرية. وللحفاظ على أمان هذه الرسائل من الأعين المتطفلة، نستخدم أقفالاً رقمية تسمى التشفير. لفترة طويلة، كان العلماء يبنون هذه الأقفال باستخدام ألغاز رياضية معقدة يسهل إنشاؤها ولكن يصعب حلها للغاية بدون المفتاح. مؤخراً، تم اقتراح نوع جديد من الأقفال باستخدام نوع خاص من الرياضيات يتضمن شبكات من الأرقام و"الرتبة" (وهي مجرد طريقة فنية لقياس مقدار المعلومات الفعلية المحشوة داخل الشبكة). زعم مبتكروا هذا القفل الجديد أنه أضاف طبقة من "الضجيج" — مثل التشويش في الراديو — لإخفاء الشكل الحقيقي للقفل، مما يجعله يبدو كفوضى عشوائية لأي شخص يحاول اختراقه. وزعموا أن هذا التصميم الجديد آمن للغاية لدرجة أن حتى حاسوباً كمياً فائق السرعة لا يمكنه كسر حمايته، ووعدوا بأنه سيكون صغيراً وفعالاً، ومثالياً لمستقبل الاتصالات الآمنة.

ومع ذلك، تماماً مثل خدعة ساحر تعتمد على حركة يد محددة، كان لهذا القفل الجديد ثغرة خفية. فقد اكتشف باحث يُدعى "تاي هونج لي" (Thai Hung Le) أن "الضجيج" لم يكن يخفي الشكل السري كما كان يُعتقد. فباستاستخدام مزيج ذكي من التخمين والعمل التحري الجبري، وجد الباحث طريقة لتقشير طبقات التشويش والكشف عن الهيكل الأصلي المخفي تحتها. الأمر يشبه بناء بيت من ورق يحتوي على مخطط سري مغطى بالضباب، ثم اكتشاف أنه إذا نظرت إلى الضباب من الزاوية الصحيحة، فإن المخطط لا يزال مرئياً بشكل باهت. هذا الاكتشاف أمر بالغ الأهمية لأن هذا يعني أن الأقفل الجديدة ليست آمنة كما هو مُعلن، وأن الأشخاص الذين صمموها بحاجة إلى إعادة التفكير في مخططاتهم قبل البدء في استخدامها لحماية بياناتنا.

الاكتشاف الكبير للورقة البحثية

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

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

تفصل الورقة طريقتين رئيسيتين للقيام بذلك:

1. تخمين الأعمدة: يخمن المهاجم كيف تم خلط الأعمدة في الشبكة، ثم يستخدم الجبر لحل كيفية خلط الصفوف.
2. تخمين الصفوف: يخمن المهاجم كيف تم خلط الصفوف، ثم يحل كيفية خلط الأعمدة.

بمجرد أن يكتشف المهاجم عملية الخلط، يمكنه نزع الضجيج العشوائي والكشف عن الهيكل الأصلي المخفي. وتثبت الورقة أن هذا الهيكل هو "كود غابيدولين" (Gabidulin code)، وهو نوع من الألغاز الرياضية التي تكون سهلة الحل جداً بمجرد معرفة النمط السري.

ما الذي تكسره الورقة بالفعل

المؤلف لا يجد مجرد صدع صغير؛ بل يحطم النافذة بأكملها. توضح الورقة أن هذا الهجوم يعمل ضد جميع مجموعات المعايير الـ 16 المقترحة لمخططات تشفير EGMC. وهذا يعني أن كل نسخة من القفل التي اقترح استخدامها أصبحت الآن تعتبر مكسورة.

لإعطائك تصوراً عن مدى فعالية ذلك، تنظر الورقة في مجموعة محددة من الأرقام التي كان من المفترض أن توفر أماناً بمستوى 128 بت (وهو مستوى قياسي من السلامة). يوضح المؤلف أن هجومه يقلل مستوى الأمان هذا إلى 35 بت فقط. وفي عالم التشفير، هذا يشبه الانتقال من خزنة ذات مزيج مكون من مليون رقم إلى قفل يمكن لطفل فتحه في ثوانٍ.

توفر الورقة مثالاً ملموساً على هذه القوة: باستخدام طريقتهم، تمكن الباحثون من استعادة المفتاح السري لذلك المستوى من الأمان (128 بت) في أقل من 10 دقائق. لم يكن هذا مجرد فكرة نظرية؛ بل قاموا بالفعل ببناء برنامج حاسوبي للقيام بذلك.

ما الذي تنفيه الورقة

من المهم ملاحظة ما تقول الورقة إنها لا تعمل عليه. يوضح المؤلف أن المحاولات السابقة لكسر هذه الأكواد اعتمدت على طرق "توافقية" (combinatorial)، والتي تتضمن تخمين خلط الصفوف والأعمدة في وقت واحد. وتجادل الورقة بأن هذه الطريقة القدية بطيئة وغير فعالة مقارنة بنهجهم "الهجين" الجديد.

علاً عن ذلك، تجادل الورقة ضد فكرة أن مجرد تكبير المعايير (إضافة المزيد من الضجيج) سيحل المشكلة في جميع الحالات. يوضح المؤلف أنه بالنسبة لأنواع معينة من هذه الأكود — وتحديداً عندما يكون أحد عوامل الضجيج (سواء كان عدد الصفوف الإضافية أو عدد الأعمدة الإضافية) يساوي صفراً — يصبح الهجوم سريعاً جداً لدرجة أنه يعمل في "زمن حدودي" (polynomial time). وهذا يعني أنه مهما زدت حجم القفل في تلك الحالات المحددة، فإن الهجوم سيظل سريعاً بما يكفي لكسره. والطريقة الوحيدة التي قد تصلح ذلك، كما تقترح الورقة، هي تغيير التصميم الأساسي بحيث يكون كلا عاملي الضجيج غير صفريين وكبيرين بما يكفي لإيقاف الهجوم، لكن المؤلف يحذر من أن هذا قد يجعل المفاتيح والرسائل كبيرة جداً لدرجة تجعلها غير مفيدة.

ما مدى تأكدهم؟

الورقة واثقة جداً في نتائجها. لم يكتفِ المؤلف بالتخمين؛ بل قدم برهاناً رياضياً كاملاً لكيفية عمل هجومه ودعم ذلك بتنفيذ حاسوبي عامل. ويصرح صراحة بأن هجومه يكسر جميع النسخ المقتر المقترحة للمخطط. كما قارن نتائجه بالهجمات السابقة، موضحاً أن طريقته أسرع وأقوى بكثير. وتخلص الورقة إلى أن مخططات تشفير EGMC لم تعد آمنة للاستخدام، وأن المجتمع الأمني بحاجة إلى الانتقال إلى تصميمات أخرى.