تشفير ما بعد الكم - خوارزمية جديدة "اختفت في 60 دقيقة"

لقد كتبنا عن PQC ، باختصار تشفير ما بعد الكمعدة مرات من قبل.

في حال فاتتك كل الإثارة الإعلامية في السنوات القليلة الماضية حول ما يسمى بالحوسبة الكمومية ...

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

مع الكثير من العناية ، وربما القليل من الحظ ، هذا يعني أنه يمكنك إعادة كتابة بعض أنواع الخوارزمية لتصل إلى الإجابة الصحيحة ، أو على الأقل تجاهل مجموعة كاملة من الإجابات الخاطئة بشكل صحيح ، دون محاولة واختبار كل نتيجة ممكنة واحدا تلو الآخر.

يمكن إجراء عمليتي تسريع تحليليين رائعتين باستخدام جهاز الحوسبة الكمومية ، بافتراض إمكانية بناء جهاز قوي وموثوق بشكل مناسب:

• خوارزمية البحث الكمي لغروفر. عادة ، إذا كنت ترغب في البحث عن مجموعة من الإجابات مرتبة عشوائيًا لمعرفة ما إذا كانت إجابتك مدرجة في القائمة ، فمن المتوقع أن تتصفح القائمة بأكملها ، في أسوأ الأحوال ، قبل الحصول على إجابة نهائية. على سبيل المثال ، إذا أردت العثور على مفتاح فك تشفير 128 بت AES لفك رموز مستند ، فستحتاج إلى البحث في قائمة جميع المفاتيح الممكنة ، بدءًا من 000..001, ..2, ..3، وما إلى ذلك ، وصولاً إلى FFF..FFF (قيمتها 16 بايت FF) ، للتأكد من إكمال المشكلة. بمعنى آخر ، يجب عليك تخصيص ميزانية لتجربة كل 2¹²⁸ مفاتيح محتملة قبل العثور على المفتاح الصحيح ، أو تحديد عدم وجود مفتاح واحد. ومع ذلك ، فإن خوارزمية جروفر ، نظرًا لوجود كمبيوتر كمي كبير وقوي بدرجة كافية ، تدعي أنها قادرة على إكمال نفس العمل الفذ باستخدام الجذر التربيعي من الجهد المعتاد ، وبالتالي فك الشفرة ، من الناحية النظرية ، في 2 فقط⁶⁴ يحاول بدلا من ذلك.
• خوارزمية التحليل الكمي لشور. تعتمد العديد من خوارزميات التشفير المعاصرة على حقيقة أن ضرب عددين أوليين كبيرين معًا يمكن أن يتم بسرعة ، في حين أن تقسيم منتجهم مرة أخرى إلى الرقمين اللذين بدأت بهما أمر مستحيل. للتعرف على هذا ، حاول ضرب 59 × 87 باستخدام القلم والورق. قد يستغرق الأمر دقيقة أو نحو ذلك لإخراجها (5133 هي الإجابة) ، لكن الأمر ليس بهذه الصعوبة. الآن جرب الطريقة الأخرى. قسّم ، على سبيل المثال ، 4171 مرة أخرى إلى عامليها. أصعب بكثير! (إنها 43 × 97.) الآن تخيل أنك تفعل هذا برقم طوله 600 رقم. إذا تحدثنا بشكل فضفاض ، فأنت عالق في محاولة قسمة الرقم المكون من 600 رقم على كل رقم أولي ممكن مكون من 300 رقم حتى تصل إلى الفوز بالجائزة الكبرى ، أو تجد أنه لا توجد إجابة. ومع ذلك ، تعد خوارزمية شور بحل هذه المشكلة مع لوغاريتم من الجهد المعتاد. وبالتالي ، فإن أخذ 2048 رقمًا ثنائيًا في الاعتبار يجب أن يستغرق ضعف طول احتساب رقم 1024 بت ، وليس ضعف طول احتساب رقم 2047 بت ، وهو ما يمثل تسريعًا كبيرًا.

مواجهة التهديد

يمكن مواجهة التهديد من خوارزمية Grover ببساطة عن طريق زيادة حجم الأرقام التي تستخدمها عن طريق تربيعها ، مما يعني مضاعفة عدد البتات في تجزئة التشفير أو مفتاح التشفير المتماثل. (بمعنى آخر ، إذا كنت تعتقد أن SHA-256 جيد الآن ، فإن استخدام SHA-512 بدلاً من ذلك سيوفر بديلاً مقاومًا لـ PQC.)

لكن لا يمكن مواجهة خوارزمية شور بهذه السهولة.

سيحتاج المفتاح العام الذي يبلغ 2048 بت إلى زيادة حجمه بشكل كبير ، وليس فقط عن طريق التربيع ، بحيث بدلاً من مفتاح 2 × 2048 = 4096 بت ، إما أنك ستحتاج إلى مفتاح جديد بحجم مستحيل يبلغ 2²⁰⁴⁸ بت ...

... أو سيتعين عليك اعتماد نوع جديد تمامًا من نظام تشفير ما بعد الكم الذي لم تنطبق عليه خوارزمية شور.

حسنًا ، تقوم هيئة المعايير الأمريكية NIST بتشغيل ملف مسابقة "PQC" منذ أواخر عام 2017.

كانت العملية مفتوحة للجميع ، مع ترحيب جميع المشاركين ، ونشر جميع الخوارزميات علنًا ، ولم يكن التدقيق العام ممكنًا فحسب ، بل شجع بنشاط:

دعوة لتقديم العروض. [مغلق 2017-11-30]. [...] من المقرر أن تحدد معايير تشفير المفتاح العام الجديدة واحدًا أو أكثر من التوقيعات الرقمية غير المصنفة والمعلن عنها للجمهور وتشفير المفتاح العام وخوارزميات إنشاء المفاتيح المتوفرة في جميع أنحاء العالم ، وتكون قادرة على حماية المعلومات الحكومية الحساسة في المستقبل المنظور ، بما في ذلك بعد ظهور أجهزة الكمبيوتر الكمومية.

بعد ثلاث جولات من التقديمات والمناقشات ، أعلن NIST، في 2022-07-05 ، أنها اختارت أربع خوارزميات اعتبرتها "معايير" ذات تأثير فوري ، وكلها بأسماء تبدو رائعة: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONو SPHINCS+.

الاول (CRYSTALS-KYBER) يستخدم ما يسمى ب آلية الاتفاق الرئيسية (KEM) ، حيث يقوم طرفا قناة اتصال عامة بتلفيق مفتاح تشفير خاص لمرة واحدة بشكل آمن لتبادل بيانات الجلسة بسرية. (ببساطة: يحصل المتلصصون على ملفوف مقطّع ، لذا لا يمكنهم التنصت على المحادثة.)

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

هناك حاجة إلى المزيد من الخوارزميات

في نفس الوقت للإعلان عن المعايير الجديدة ، أعلنت NIST أيضًا عن الجولة الرابعة من منافستها ، ووضع أربع خوارزميات أخرى إلى الأمام كبديل محتمل لـ KEMs. (تذكر أنه في وقت كتابة هذا التقرير ، لدينا بالفعل ثلاث خوارزميات توقيع رقمي معتمدة للاختيار من بينها ، ولكن KEM رسمي واحد فقط.)

هذه كانت: BIKE, Classic McEliece, HQC و SIKE.

ومن المثير للاهتمام أن خوارزمية McEliece تم اختراعه في السبعينيات من قبل عالم التشفير الأمريكي روبرت ماك إليسي ، الذي توفي في عام 1970 ، بعد فترة طويلة من بدء مسابقة NIST بالفعل.

ومع ذلك ، لم يتم التقاطها أبدًا لأنها تطلبت كميات هائلة من المواد الأساسية مقارنة بالخوارزمية الشائعة في ذلك الوقت ، خوارزمية Diffie-Hellman-Merkle (DHM ، أو أحيانًا DH فقط).

لسوء الحظ ، واحدة من خوارزميات الجولة الرابعة الثلاثة ، وهي SIKE، يبدو أنه تم تصدعها.

في ورقة التواء الدماغ بعنوان هجوم استرجاع رئيسي فعال على SIDH (نسخة أولية)، يبدو أن مصممين التشفير البلجيكيين ووتر كاستريك وتوماس ديكرو قد وجهوا شيئًا من الضربة القاتلة إلى خوارزمية SIKE

في حال كنت تتساءل ، فإن SIKE قصيرة تغليف مفتاح متساوي التماثل الفائق، و SIDH تعني التناظر الفائق Diffie-Hellman، استخدام محدد لـ خوارزمية سيكي حيث يقوم طرفا قناة اتصال بتنفيذ "تشفير" يشبه DHM لتبادل مجموعة من البيانات العامة التي تسمح لكل طرف باشتقاق قيمة خاصة لاستخدامها كمفتاح تشفير سري لمرة واحدة.

لن نحاول شرح الهجوم هنا. سنكرر فقط ما تدعيه الصحيفة ، وهو:

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

لكن الناتج الذي يتم استخراجه (يشار إلى المعلومات باسم متساوي المنشأ φ أعلاه) هو الجزء الذي لم يتم الكشف عنه مطلقًا من العملية - ما يسمى بالمفتاح الخاص.

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

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

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

هذا ضد خوارزمية SIKE عند تكوينها لتلبية المستوى 1 ، الدرجة الأساسية لأمان التشفير من NIST.

ماذا ستفعلين.. إذًا؟

لا شيء!

(هذه هي الأخبار السارة).

كما يقترح مؤلفو الورقة ، بعد ملاحظة أن نتائجهم لا تزال أولية ، "مع الوضع الحالي ، يبدو أن SIDH معطلة تمامًا لأي منحنى قاعدة تم إنشاؤه بشكل عام."

(هذه هي الأخبار السيئة.)

ومع ذلك ، لنفترض أن خوارزمية SIKE لم تتم الموافقة عليها رسميًا حتى الآن ، فيمكن الآن إما تكييفها لإحباط هذا الهجوم بالذات (وهو أمر يعترف المؤلفون بأنه قد يكون ممكنًا) ، أو ببساطة إسقاطها تمامًا.

مهما حدث أخيرًا لـ SIKE ، فهذا تذكير ممتاز لماذا محاولة ابتكار خوارزميات التشفير الخاصة بك محفوفة بالمخاطر.

إنه أيضًا مثال واضح على سبب احتكاك أنظمة التشفير التي تعتمد على سرية الخوارزمية نفسها للحفاظ على أمنهم هو ببساطة غير مقبول في عام 2022.

إذا نجت خوارزمية PQC مثل SIKE من المثابرة والتحقيق من قبل خبراء من جميع أنحاء العالم لأكثر من خمس سنوات ، على الرغم من الكشف عنها على وجه التحديد بحيث يمكن أن تخضع للتدقيق العام ...

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

---