Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields

إليك ملخص تقني مفصل لورقة البحث "تحليل كسر دالة ليجاندر شبه العشوائية فوق حقول التوسعة" (Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields) للباحث داكش باندي.

1. بيان المشكلة

تُعد دالة ليجاندر شبه العشوائية (Legendre PRF) من الأدوات التشفيرية ذات القيمة العالية نظراً لتعقيدها الضربي المنخفض، مما يجعلها فعالة للغاية في الحوسبة متعددة الأطراف (MPC) وإثباتات المعرفة الصفرية (ZKP). وبينما تمت دراسة أمنها على الحقول الأولية ($\mathbb{F}_p$) بشكل جيد، فقد انتقلت التطبيقات الحديثة إلى حقول التوسعة ($\mathbb{F}_{p^r}$) لتحسين معدل الإنتاجية.

المشكلة الجوهرية التي تتناولها الورقة هي أمن دالة ليجاندر (PRF) من الدرجة الأولى ($d=1$) فوق حقول التوسعة.

• السياق: في $\mathbb{F}_{p^r}$، يتم ترميز المدخلات كمتعددات حدود. وبخلاف الحسابات الصحيحة، تعمل عملية الجمع في $\mathbb{F}_{p^r}$ على مستوى المعاملات دون وجود "تأثير الحمل" (carry-over) إلى الدرجات الأعلى.
• الفرضية: كان يُعتقد سابقاً أن خاصية "عدم وجود الحمل" هذه ستؤدي إلى تعطيل التدرجات الجمعية المستمرة المطلوبة لهجمات النافذة المنزلقة (sliding-window) الكلاسيكية، مما يؤمن الدالة (PRF) ضد المهاجمين السلبيين.
• الهدف: تتحدى هذه الورقة هذا الافتراض، حيث تهدف إلى تحديد ما إذا كان "الكسر الهيكلي" الناتج عن غياب الحمل يمكن استغلاله لاستعادة المفتاح السري، سواء في الهجمات السلبية أو النشطة.

2. المنهجية

تستخدم الورقة مزيجاً من التحليل الجبري، والحدود الإحصائية، والتحليل التشفيري الخوارزمي تحت نموذجين للتهديد:

أ. الأسس الرياضية

• الترميز: يتم تعيين الأعداد الصحيحة $n$ إلى متعددات حدود $X_n(x)$ عبر التوسع بأساس $p$.
• "كسر عدم وجود الحمل" (The No-Carry Fracture): يحلل المؤلفون الفرق التفاضلي $\Delta_n = X_{n+1} \oplus X_n$. في الأعداد الصحيحة القياسية، يكون هذا الفرق دائماً 1. أما في $\mathbb{F}_{p^r}$، ونظراً لغياب انتشار الحمل، فإن الفرق ليس ثابتاً بل يأخذ قيماً من المجموعة $\{x^k + 1\}$، مما يخلق تسلسلاً "مكسوراً" من الكتل الحسابية الفرعية.
• الحدود الإحصائية: تستخدم الورقة حد هاسي-ويل (Hasse-Weil bound) لإثبات أن تدفق المفاتيح (keystream) غير قابل للتمييز إحصائياً عن التوزيع المنتظم. وهذا يثبت أن الهجمات لا يمكن أن تعتمد على الانحياز الإحصائي، بل يجب أن تستغل البنية الجبرية.

ب. نموذج التهديد السلبي (الاستعلامات المتتالية)

• النهج: يراقب المهاجم تدفق مفاتيح يتم توليده عبر زيادة العداد المدخل بشكل متتالٍ.
• التقنية: يقدم المؤلفون تقنية "تجميع التوقيع التفاضلي" (Differential Signature bucketing).
  • يعرّفون التوقيع $\delta_n$ كتسلسل من الفروقات متعددة الحدود التراكمية بالنسبة لنقطة بداية.
  • رغم "الكسر"، فإن تسلسل الفروقات هو دوري حتمي.
  • يقوم المهاجم بتجميع نوافذ تدفق المفاتيح المرصودة في فئات تكافؤ بناءً على "شكلها" الهيكلي (التوقيع).
  • من خلال مطابقة هذه الأشكال مع جدول هاش (hash table) مُعد مسبقاً، يمكن للمهاجم تجاوز "الكسر" واستعادة المفتاح.

ج. نموذج التهديد النشط (الاستعلام المختار)

• النهج: يمكن للمهاجم اختيار مدخلات محددة للاستعلام عنها من الدالة (PRF).
• التقنية: يتخلى المهاجم عن التسلسلات الجمعية ويقوم بالاستعلام عبر تسلسل هندسي يتم توليده بواسطة عنصر أولي $g(x)$ من المجموعة الضربية $\mathbb{F}_{p^r}^*$.
• الاختزال الجبري:
  • رمز ليجاندر هو ضربي بالكامل.
  • يمكن تحليل التقييم $L(g^i + K)$ إلى $L(K) \cdot L(g^{i+j} + 1)$، حيث $j$ هو إزاحة اللوغاريتم المنفصل.
  • يحول هذا العملية إلى البحث عن إزاحة $j$ في تسلسل مرجعي عالمي، مما يؤدي فعلياً إلى تحييد "الكسر الجمعي" تماماً.

3. المساهمات الرئيسية

1. أول تحليل شامل: هذه هي أول ورقة تقدم تحليلاً كاملاً لكسر دالة ليجاندر (PRF) من الدرجة الأولى ($d=1$) فوق حقول التوسعة ($\mathbb{F}_{p^r}$).
2. الهجوم السلبي (تجميع الأشكال): تثبت أن "كسر عدم وجود الحمل" ليس دفاعاً بل هو دورية حتمية. يقترح المؤلفون طريقة "التوقيع التفاضلي" المبتكرة لتجميع التسلسلات المكسورة، مما يسمح باستعادة المفتاح سلبياً.
3. الهجوم النشط (التسلسلات الهندسية): تثبت الورقة أن المهاجم النشط يمكنه الالتفاف تماماً على القيود الجمعية باستخدام الاستعلامات الهندسية. هذا يستدعي التماثل الضربي الصارم، مما يقلل المشكلة إلى مجرد بحث عن إزاحة (shift search).
4. تفصيل التعقيد:
   • التعقيد السلبي: $O(U \cdot p^r / M)$، حيث $U$ هي مسافة الوحدة و $M$ هو عدد البتات المرصودة.
   • التعقيد النشط: $O(p^r / M)$. وهذا يطابق الحد الأدنى النظري لهجمات تصادم الجداول، مما يثبت أن نسخة الدرجة الأولى قد كُسرت.
5. الحدود الأمنية: توضح الورقة أن متغيرات الدرجة الأعلى ($d \ge 2$) ضرورية. وتجادل الورقة بأنه بينما تقاوم الدرجة $d=2$ التفكيك الضربي، إلا أنها قد تظل عرضة لهجمات "الالتقاء في المنتصف" (Meet-in-the-Middle) المحسنة، مما يشير إلى ضرورة استخدام $d \ge 3$ أو $4$ لضمان أمن قوي.

4. النتائج

• كسر $d=1$: دالة ليجاندر (PRF) من الدرجة الأولى فوق $\mathbb{F}_{p^r}$ غير آمنة تماماً في كلا النموذجين السلبي والنشط. خاصية "عدم وجود الحمل" تفشل في توفير الأمن ضد التحليل الهيكلي.
• الكفاءة: يقلل الهجوم الهندسي النشط من أمن الدالة (PRF) إلى تعقيد هجوم تصادم الجدول القياسي، حيث يتطلب $O(p^r/M)$ عملية فقط.
• السلامة الإحصائية: تؤكد الورقة أن الدالة تظل عشوائية إحصائياً (لا يوجد انحياز)، مما يعني أن الهجمات هي هجمات جبرية وهيكلية بحتة، وليست إحصائية.
• التخفيف من حدة الهجوم: يؤكد المؤلفون أن زيادة درجة متعدد الحدود ($d \ge 2$) يمنع التفكيك الضربي المستخدم في الهجوم النشط. ومع ذلك، يحذرون من أن $d=2$ قد تظل عرضة لهجمات بقوة $O(p^r)$، ويوصون باستخدام $d \ge 3$ للحصول على هوامش أمن أسية.

5. الأهمية

• أمن البروتوكولات: لهذا العمل آثار فورية على بروتوكولات MPC و ZKP التي تستخدم حالياً أو تفكر في استخدام دالة ليجاندر (Legendre PRF) فوق حقول التوسعة من أجل الكفاءة. فهو يبطل أمن النسخة القياسية $d=1$ في هذه السياقات.
• إرشادات التصميم: توفر الورقة إرشادات تصميمية حرجة: حقول التوسعة لا تزيد الأمن تلقائياً للمتعددات الحدود الخطية؛ بل إنها تقدم هياكل جبرية محددة (مثل غياب الحمل) يمكن استغلالها إذا لم يتم رفع درجة متعدد الحدود.
• الأبحاث المستقبلية: تضع الورقة معياراً جديداً للتحليل التشفيري في حقول التوسعة، مما يسلط الضال على الحاجة إلى متعددات حدود ذات درجات أعلى ($d \ge 3$) ويقترح اتجاهات بحثية جديدة في تحويلات "تشيرنهاوس" (Tschirnhaus) والاختزالات الجبرية للنسخ ذات الدرجات الأعلى.
• قابلية التكرار: جعل المؤلفون تطبيقاتهم بلغة بايثون (بما في ذلك تصادم الجدول الهندسي وتجميع الأشكال السلبي) مفتوحة المصدر، مما يسهل التحقق الفوري والمزيد من البحث.

الخلاصة: تثبت الورقة بفعالية أن الانتقال من الحقول الأولية إلى حقول التوسعة لدالة ليجاندر (Legendre PRF) ليس ترقية أمنية لنسخة الدرجة الأولى، بل هو ثغرة تسمح باستعادة المفتاح بكفاءة. وهذا يفرض التحول إلى بناء متعددات حدود ذات درجات أعلى للحفاظ على السلامة التشفيرية.