Full-Key Recovery and Forgery from One MQOM v2.1 Signature

تخيل أنك تحاول إرسال رسالة سرية إلى صديق، لكنك تعيش في عالم قد توجد فيه يوماً ما حواسيب فائقة السرعة (تسمى الحواسيب الكمومية). يمكن لهذه الآلات المستقبلية كسر معظم الأقفال التي نستخدمها اليوم للحفاظ على أسرارنا آمنة. وللاستعداد لهذا، يبني العلماء أقفالاً رقمية جديدة فائقة القوة تسمى "التوقيعات ما بعد الكم" (post-quantum signatures). فكر في الأمر كنوع من أنواع الأختام الشمعية الخاصة على الرسالة؛ حتى لو كان لدى اللص مطرقة سحرية يمكنها تحطيم الأقفال العادية، فإن هذا الختم الشمعي الجديد مصنوع من مادة يُفترض أن تصمد أمامها.

واحدة من أكثر الأقفال الجديدة الواعدة التي يتم اختبارها هي MQOM. تعمل هذه التقنية بشكل يشبه أحجية ضخمة ومعقدة. لتوقيع رسالة، يستخدم المرسل "شاهداً" سرياً (مفتاحاً مخفياً) لحل مسألة رياضية تتضمن متغيرات عديدة. ولإثبات أنه حل المسألة دون إظهار السر، يستخدم خدعة ذكية تسمى "التحكم متعدد الأطراف في الرأس" (MPC-in-the-head). تخيل أن المرسل يتظاهر بأنه فريق كامل من الأشخاص، كل منهم يمسك بجزء صغير من السر. يلعبون لعبة حيث يكشفون فقط عن القدر الكافي لإثبات أن الفريق حل الأحجية معاً، ولكن ليس بما يكفي للكشف عن قطع السر الفعلية. إذا كانت الرياضيات صحيحة، يكون التوقيع صالحاً. نحن نهتم بهذا لأننا نخشى أنه إذا وجدت شقوق خفية في هذه الأقفال الجديدة، فإن سلامتنا الرقمية المستقبلية قد تنهار قبل أن نصل إليها حتى.

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

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

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

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

لم تكتفِ الورقة بمجرد التخمين بأن هذا يعمل، بل قاموا بالفعل بالحسابات الرياضية والعمل الحاسوبي لإثبات ذلك. لقد حسبوا بالضبط مقدار قوة الحوسبة التي ستتطلبها حل هذه المعادلة لمستويات القوة المختلفة للقفل (المعروفة بالفئات I و III و V). ووجدوا أنه لجميع الفئات، فإن الجهد المطلوب هو أقل من حد الأمان الذي وضعه معهد NIST لهذه الأقفال.

بالنسبة للمستوى الأسهل (الفئة I)، يستغرق الهجوم حوالي $2^{142.335112}$ عملية. وبالنسبة للمستوى المتوسط (الفئة III)، يستغرق حوالي $2^{206.774558}$ أو $2^{206.988685}$ عملية، اعتماداً على كيفية مسح الخريطة. وبالنسبة لأصعب مستوى (الفئة V)، يستغرق حوالي $2^{271.794162}$ عملية. في كل حالة، عدد الخطوات التي يحتاجها المهاجم أقل من عدد الخطوات التي كان من المفترض أن يتطلبها القفل ليكون آمناً.

لم يتوقف الباحثون عند الرياضيات فحسب، بل بنوا برنامجاً حاسوبياً قام بتنفيذ الهجوم فعلياً. لقد أخذوا توقيعاً حقيقياً، وحلوا المعادلة، واستعادوا المفتاح السري بدقة بايت تلو الآخر، ثم استخدموا هذا المفتاح لتوقيع رسالة جديدة تماماً. تحقق نظام التحقق من التوقيع من التوقيع الجديد وقال: "نعم، هذا التوقيع صالح!". أثبت هذا أن الهجوم يعمل في العالم الحقيقي، وليس فقط على الورق.

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

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