باحثون يزيفون توقيعات RSA بطول 1024 بت دون تحليل المفتاح إلى عوامله

نفّذ باحثون من جامعة كاليفورنيا في سان دييغو ومركز Inria في نانسي هجومًا يتيح تزوير توقيعات RSA بأطوال 1024 بت من دون تحليل المفتاح إلى عوامله. نُشرت المسودة البحثية "Forging 1024-bit RSA signatures in nearly SNFS time" في أرشيف IACR ePrint في 20 سبتمبر، ومؤلفوها لورا شيا وميرو هالر وآدم سول وناديا هينينغر وإيمانويل توميه.

يعتمد العمل على خوارزمية تعود إلى عام 2007 لـ Joux وNaccache وThomé يصفها المؤلفون بأنها لم تحظَ بالاهتمام الكافي. زمن تنفيذها قريب من زمن غربال حقل الأعداد الخاص (SNFS)، وهو أقل بكثير من غربال حقل الأعداد العام (GNFS) الذي تُبنى عليه أحجام مفاتيح RSA.

ما الذي يتطلبه الهجوم

نموذج التهديد هو هجوم "فترة الغداء" (lunchtime)، أو رسميًا هجوم النص المشفّر المختار غير التكيّفي (IND-CCA1): يحصل المهاجم على وصول مؤقت إلى أداة توقيع أو فك تشفير RSA خام وغير مُبطَّن لمفتاح معيّن، ثم يفقد هذا الوصول. بعد ذلك يستطيع تزوير أي توقيع يريده دون اتصال، وتكرار ذلك لأي هدف من دون أي استعلامات إضافية.

استغرق الحساب الكلي 1380 سنة-نواة من وحدات المعالجة المركزية على مدى خمسة أشهر تقويمية، ونحو 2^32 استعلامًا. تستهلك الحسابات المسبقة، التي تعتمد على المعامل وحده، نحو 1200 سنة-نواة؛ أما التزوير الواحد فيكلّف بعدها نحو 180 سنة-نواة. للمقارنة، تقدّر الورقة تحليل معامل RSA بطول 1024 بت بما بين 500,000 و1,000,000 سنة-نواة.

وحدات HSM والتوقيعات العمياء

نفّذ المؤلفون استعلاماتهم عبر وحدة أمان مادية (HSM)، وأظهروا أن مهاجمًا يملك وصولًا إلى واجهة برمجية بلا معرفة داخلية يمكنه انتحال شخصية الوحدة من دون استخراج المفتاح. ويوفّر معيار PKCS #11، الذي تدعمه جميع وحدات HSM تقريبًا، عمليات RSA الخام التي يحتاجها الهجوم بالضبط. كما توفّر مخططات التوقيع الأعمى القائمة على RSA الأداة نفسها؛ وترى الورقة أن المفاتيح الشائعة بطول 2048 بت تمنح هامش أمان منخفضًا جدًا في هذه الحالة.

أمان أقل بمقدار 15 إلى 30 بت

باستقراء الأزمنة المقيسة، يخلص المؤلفون إلى أن الأمان الفعلي لـ RSA عند وجود أداة توقيع أقل بمقدار 15 إلى 30 بت من التقديرات المبنية على التحليل إلى العوامل، للمعاملات الشائعة بين 1024 و4096 بت. فلمفتاح 1024 بت، الذي يُنسب إليه عادة أمان بمقدار 80 بت، تقدّر الورقة زمنًا يقارب 2^65. وبالقياس، يبلغ الهجوم نحو 2^90 و2^43 استعلامًا لمفتاح 2048 بت (112 بت)، ونحو 2^119 و2^57 استعلامًا لمفتاح 4096 بت. أي أن حتى RSA بطول 4096 بت لا يبلغ مستوى أمان 128 بت في هذا النموذج.

ثغرة في افتراضات RSA

لا يزعم المؤلفون أن RSA مكسور في الاستخدام اليومي: فالهجوم عملي أكاديميًا وليس عمليًا لمهاجر عابر، ونموذج الأداة الخام قوي جدًا. لكنهم يرون أنه يكشف ثغرة: فافتراض one-more RSA لا يغطي هذا النوع من الهجمات ذات الحسابات المسبقة، ويقترحون تسمية هذا السياق "delayed-target RSA". وتعتزم NIST التخلي عن RSA بحلول عام 2030 وحظره بحلول عام 2035، ويرى المؤلفون في نتيجتهم حجة إضافية لتسريع الانتقال. نُشرت الشيفرة على GitHub.