SIDH وSIKE: التصميم والتحليل التشفيري

يُعدّ SIDH ‏(تبادل مفاتيح Diffie-Hellman باستخدام الإيزوجيني الفائق التفرد)، الذي اقترحه Jao وDe Feo عام 2011، بروتوكولًا لتبادل المفاتيح العامة مشابهًا لـ Diffie-Hellman، لكنه يستخدم الإيزوجينيات على المنحنيات الإهليلجية فائقة التفرد. يبدأ الطرفان بالمنحنى الفائق التفرد نفسه E على Fp2. تحسب Alice إيزوجينيًا سريًا phi_A: E -> E_A (بنواة عشوائية ضمن 2^a-torsion)، وتنشر E_A وصور مولدات torsion الخاصة بـ Bob تحت تأثير phi_A. يحسب Bob ‏phi_B: E -> E_B (بنواة عشوائية ضمن 3^b-torsion)، وينشر E_B وصور مولدات torsion الخاصة بـ Alice تحت تأثير phi_B. تستخدم Alice البيانات التي نشرها Bob لحساب phi_A': E_B -> E_AB؛ ويحسب Bob ‏phi_B': E_A -> E_AB. ويتوصل كلاهما إلى j(E_AB) بوصفه السر المشترك.

تضمن صيغة العدد الأولي الخاصة بـ SIDH، وهي p = 2^a * 3^b * f - 1 ‏(حيث f معامل مشترك صغير للتحقق من الأولية)، أن يمتلك المنحنى E على Fp2 بنية torsion اللازمة. بالنسبة إلى SIKEp434 ‏(المستوى 1 من NIST، وأمان ما بعد الكم بمقدار 128 بتًا):‏ p = 2^216 * 3^137 - 1، وa = 216، وb = 137. وهذا يعني أن Alice تسلك مسارًا يتكون من 216 خطوة من إيزوجينيات 2، بينما يسلك Bob مسارًا يتكون من 137 خطوة من إيزوجينيات 3. أحجام المفاتيح: يتكون المفتاح العام لـ Alice من E_A ونقطتي Fp2 ‏(phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 bytes. يستهدف SIKEp751 أمانًا كلاسيكيًا بمقدار 192 بتًا وأمانًا كميًا بمقدار 128 بتًا، ويملك مفاتيح عامة بحجم 564 بايتًا. وهذه أصغر مفاتيح عامة بين جميع مرشحي NIST PQC، لكن ذلك يأتي على حساب سرعة أقل بمقدار 100-1000x.

يُعدّ SIKE ‏(تغليف المفاتيح باستخدام الإيزوجيني الفائق التفرد) مخطط KEM آمنًا وفق IND-CCA2، ومبنيًا على SIDH باستخدام تحويل Fujisaki-Okamoto. في SIKE.Encaps: اختر رسالة عشوائية m، واحسب ‏(c0 = SIDH public key with seed m, c1 = H2(m) XOR pk)، ثم أرسل ‏(c0, c1). في SIKE.Decaps: استعد m من c0 باستخدام المفتاح السري، وتحقق من c1، وأعد حساب ‏(c0, c1) للتحقق من الاتساق، ثم أخرج ‏K = H3(m, c0). يحوّل تحويل FO تبادل SIDH الآمن ضد CPA إلى KEM آمن ضد CCA2. شارك SIKE في الجولات الأربع جميعها من مسابقة NIST PQC ‏(2017-2022)، وصمد أمام تحليل تشفيري مكثف، إلى أن ظهر هجوم كلاسيكي مدمّر في يوليو 2022.

من عام 2011 إلى عام 2022، صمد SIDH أمام جهود كبيرة في التحليل التشفيري. وكانت أفضل الهجمات المعروفة ضد SIDH هي: (1) خوارزمية SSIP العامة: بتعقيد O(p^{1/4}) كلاسيكيًا، وO(p^{1/6}) كميًا باستخدام خوارزمية Tani. (2) هجوم الالتقاء من المنتصف على مسار الإيزوجيني: بتعقيد O(p^{1/4}) كلاسيكيًا، وهو التعقيد نفسه لخوارزمية SSIP. (3) خوارزميات متعددة الحدود لهجمات بنيوية محددة ‏(van Oorschot-Wiener): ولا تنطبق على SIDH. حللت عشرات الأبحاث أمان SIDH، ولم يُعثر خلال 11 عامًا على أي هجوم كلاسيكي أو كمي متعدد الحدود. جعل هذا السجل SIKE مرشحًا موثوقًا به في المرحلة النهائية من مسابقة NIST. ولم يأتِ الاختراق النهائي من هجوم مباشر على SSIP، بل من استغلال معلومات نقاط torsion المساعدة الخاصة بـ SIDH.

في 30 يوليو 2022، نشر Wouter Castryck وThomas Decru مسودة بحثية أظهرت هجومًا كلاسيكيًا متعدد الحدود على SIDH. يستغل الهجوم المعلومات الإضافية الموجودة في نقاط torsion المساعدة الخاصة بـ SIDH ‏phi_A(P_B), phi_A(Q_B): إذ تكشف هذه المعلومات عمليًا عن تأثير phi_A على مجموعة 3^b-torsion الجزئية. وبالاقتران مع منحنى الصورة E_A، يتيح ذلك إعادة بناء نواة phi_A ‏(ومن ثم phi_A نفسها) باستخدام تقنيات من نظرية المنحنيات الإهليلجية ذات الضرب المركب وإيزوجينيات Richelot. نُفذ الهجوم خلال 62 دقيقة على حاسوب محمول بالنسبة إلى SIKEp434، وهي مجموعة معلمات كان يُفترض أن توفر أمانًا من مستوى 128 بتًا بعد الكم. وخلال أيام، أكد باحثون مستقلون الهجوم ووسعوا نطاقه ليشمل جميع معلمات SIDH.

تطلب تصميم SIDH من الطرفين نشر صور نقاط أساس torsion الخاصة بالطرف الآخر تحت تأثير الإيزوجيني السري لكل منهما. وكان ذلك ضروريًا لعمل البروتوكول؛ فبدون ‏phi_A(P_B) وphi_A(Q_B)، لن يتمكن Bob من نقل إيزوجينيته إلى منحنى Alice لحساب السر المشترك. لكن هذه المعلومات الإضافية، التي تكشف تأثير phi_A المقيّد على 3^b-torsion، اتضح أنها تكشف معلومات أكثر بكثير مما كان متوقعًا، وبصورة كارثية. يستخدم هجوم Castryck-Decru منحنيات من الجنس 2 ‏(إيزوجينيات Richelot) لرفع المسألة إلى كائنات ذات جنس أعلى، حيث يحدد التأثير المقيّد phi_A تحديدًا كاملًا. وهذا التسرب متأصل في بنية SIDH، ولا يمكن إصلاحه من دون تغيير التصميم الأساسي للبروتوكول.

في 5 يوليو 2022 ‏(قبل هجوم Castryck-Decru)، أعلنت NIST خياراتها الأولية لتوحيد معايير PQC: ‏ML-KEM ‏(Kyber)، وML-DSA ‏(Dilithium)، وSLH-DSA ‏(SPHINCS+)، وFN-DSA ‏(Falcon)؛ ولم يكن SIKE من بينها، إذ كان ضمن جولة ثانية قيد الدراسة. وأدى هجوم Castryck-Decru في يوليو 2022 إلى استبعاد NIST لـ SIKE رسميًا من الدراسة نهائيًا. وذكرت NIST: «لم يعد SIKE قيد الدراسة للتوحيد القياسي». وكان هذا أكثر التطورات التحليلية التشفيرية إثارة في مسابقة NIST PQC، إذ أظهر أن مخططًا صمد أمام 11 عامًا من التحليل يمكن أن ينكسر بفضل بصيرة رياضية جديدة جذريًا.

خلال أسبوع من هجوم Castryck-Decru، نشر Thomas Decru وLuciano Maino، كلٌّ منهما على نحو مستقل، ثم Damien Robert لاحقًا، تحسينات إضافية. يستخدم إصدار Robert من الهجوم البصيرة نفسها، لكنه يحسب حلقة المؤثرات الذاتية للمنحنى E_A بدلًا من حساب نواة الإيزوجيني مباشرة، ويمكن القول إنه أبسط من الناحية الرياضية في الوصف. وأكدت عمليات إعادة الاكتشاف المستقلة السريعة هذه أن هجوم Castryck-Decru كشف ضعفًا بنيويًا جوهريًا، لا حيلة غامضة. كما عكست سرعة الأبحاث اللاحقة عدد الباحثين الذين كانوا يدرسون تسرب نقاط torsion في SIDH باعتباره مسارًا محتملًا للهجوم؛ فقد كانوا يدركون أن هذا الكشف غير المعتاد للمعلومات قد يشكل خطرًا، لكنهم لم يتمكنوا من استغلاله إلى أن وجد Castryck وDecru الجسر إلى منحنيات الجنس 2.

يُعدّ FESTA ‏(التشفير السريع من هجمات torsion الفائق التفرد، 2023) تصميم KEM مستوحى من SIDH، لكنه يتجنب بيانات torsion المساعدة. يستخدم FESTA بنية بروتوكول مختلفة؛ فلا يتضمن المفتاح العام صور أساس torsion للطرف المقابل، بل يُلتزم بالإيزوجيني السري عبر منحنى الصورة وحده ‏(من دون نقاط مساعدة). ويُجري FESTA التشفير باستخدام إيزوجينيات تكشف معلومات بنيوية أقل. وتشير التحليلات الأمنية الأولية إلى أن FESTA يتجنب بنية هجوم Castryck-Decru. ومع ذلك، فإن FESTA أحدث عهدًا وأقل خضوعًا للتدقيق من SIKE الذي يملك سجلًا يمتد 11 عامًا، ولذلك يتوخى مجتمع الإيزوجيني الحذر من نشر مخططات جديدة قبل إخضاعها لتحليل واسع.

يقدم اختراق SIKE دروسًا مهمة. (1) كشف المعلومات المساعدة خطر: فقد كانت بيانات نقاط torsion الإضافية في SIDH ضرورية للبروتوكول، لكنها سربت معلومات قاتلة. يجب على مصممي البروتوكولات تحليل كل جزء من البيانات العامة، لا القيم الأساسية وحدها. (2) السجل السابق ليس برهانًا على الأمان: إن مرور 11 عامًا من دون هجوم معروف أمر مطمئن، لكنه ليس ضمانًا. وتُعد البراهين التشفيرية، أي اختزال الأمان إلى مسألة صعبة محددة جيدًا، أكثر موثوقية من الاحتجاج بسلطة الخبراء أو بمجرد اجتياز التدقيق. (3) تنشئ الأدوات الرياضية الجديدة مخاطر: استخدم هجوم Castryck-Decru إيزوجينيات Richelot على منحنيات الجنس 2، وهي أداة رياضية لم تُطبّق من قبل على التحليل التشفيري للإيزوجينيات. ويجب على محللي التشفير، عند دراسة البدائيات الجديدة، مراعاة المجالات الرياضية الجديدة.

رغم اختراق SIKE، يواصل التشفير القائم على الإيزوجينيات تطوره كمجال بحثي. ولا تزال توقيعات SQISign ‏(177 بايتًا في المستوى 1) أصغر توقيعات PQC المعروفة، وهي تستخدم افتراض صعوبة مختلفًا، هو مسألة حلقة المؤثرات الذاتية، ولا يتأثر بهجوم SIDH. وتستخدم البروتوكولات القائمة على CSIDH بنية تأثير زمرة الأصناف ‏(الإيزوجينيات التبديلية) من دون تسرب نقاط torsion، مع أن CSIDH يواجه تحدياته الخاصة، فهو أبطأ مما كان عليه SIDH، ولا يزال تحليل أمانه الكمي جاريًا. وينظر مجتمع الإيزوجيني إلى اختراق SIKE باعتباره تجربة تعليمية حسّنت فهم المعلومات التي يجب إخفاؤها في بروتوكولات الإيزوجيني، وهي معرفة قيّمة لتصميم المخططات المستقبلية.

ما الجانب في تصميم SIDH الذي أتاح هجوم Castryck-Decru؟

يستخدم SIDH سلاسل إيزوجيني متناوبة من 2^a و3^b بين طرفين، مع مشاركة صور نقاط torsion المساعدة لتمكين تبادل المفاتيح. ويغلف SIKE بروتوكول SIDH بتحويل Fujisaki-Okamoto لتحقيق أمان CCA2. امتلك SIKE أصغر مفاتيح بين جميع مرشحي NIST PQC ‏(374 بايتًا)، لكنه كان أبطأ بمقدار 100-1000x. وبعد 11 عامًا من الأمان، اخترق Castryck-Decru نظام SIKE في يوليو 2022 باستخدام إيزوجينيات Richelot على منحنيات الجنس 2 لاستغلال تسرب نقاط torsion. واستبعدت NIST نظام SIKE. ويتجنب FESTA كشف نقاط torsion. وتواصل SQISign استخدام صعوبة حلقة المؤثرات الذاتية. يوضح اختراق SIKE ضرورة تحليل البيانات العامة المساعدة بعناية تضاهي العناية بتحليل قيم البروتوكول الأساسية.