هجوم XSL

الموسوعة الحرة

في علم التشفير ، يُعد هجوم التوسيع الخطي المتفرق (XSL) أسلوبًا لتحليل الشفرات المشفّرة . نُشر هذا الهجوم لأول مرة عام 2002 على يد الباحثين نيكولاس كورتوا وجوزيف بيبرزيك . وقد أثار جدلًا واسعًا، إذ زُعم أنه قادر على كسر معيار التشفير المتقدم (AES) ، المعروف أيضًا باسم Rijndael ، بسرعة تفوق سرعة البحث الشامل . ونظرًا لأن معيار التشفير المتقدم ( AES) يُستخدم على نطاق واسع في التجارة والحكومة لنقل المعلومات السرية، فإن إيجاد تقنية تُقلل الوقت اللازم لاسترجاع الرسالة السرية دون الحاجة إلى المفتاح قد يكون له آثار بالغة الأهمية.

تتطلب هذه الطريقة جهدًا كبيرًا، ما يعني، ما لم يتم تخفيفه، أن هذه التقنية لا تُقلل من الجهد المطلوب لكسر خوارزمية AES مقارنةً بالبحث الشامل. لذا، فهي لا تُؤثر على أمن تشفير الكتل في الواقع العملي في المستقبل القريب. مع ذلك، أثار هذا الهجوم قلق بعض الخبراء بشأن بساطة خوارزمية AES الحالية من الناحية الجبرية.

باختصار، يعتمد هجوم XSL على تحليل بنية التشفير الداخلية واستخلاص مجموعة من المعادلات التربيعية الآنية . عادةً ما تكون هذه الأنظمة من المعادلات ضخمة جدًا، على سبيل المثال 8000 معادلة مع 1600 متغير لخوارزمية AES ذات 128 بت. توجد عدة طرق لحل هذه الأنظمة. في هجوم XSL، تُطبَّق خوارزمية متخصصة تُسمى " التخطيط الخطي المتفرق الموسع" (eXtended Sparse Linearization ) لحل هذه المعادلات واستعادة المفتاح .

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

حل المعادلات التربيعية متعددة المتغيرات

يُعدّ حلّ المعادلات التربيعية متعددة المتغيرات (MQ) على مجموعة محدودة من الأعداد مسألةً صعبة الحل (NP-hard ) (في الحالة العامة)، ولها تطبيقات عديدة في علم التشفير. يتطلب هجوم XSL خوارزمية فعّالة لمعالجة هذه المعادلات. في عام ١٩٩٩، بيّن كيبنيس وشامير أن خوارزمية مفتاح عام محددة ، تُعرف باسم مخطط معادلات الحقل الخفي (HFE)، يُمكن اختزالها إلى نظام مُفرط التحديد من المعادلات التربيعية (عدد المعادلات يفوق عدد المجاهيل). إحدى تقنيات حلّ هذه الأنظمة هي التخطيط الخطي ، الذي يتضمن استبدال كل حد تربيعي بمتغير مستقل، ثم حلّ النظام الخطي الناتج باستخدام خوارزمية مثل الحذف الغاوسي . ولنجاح هذه التقنية، يتطلب التخطيط الخطي وجود عدد كافٍ من المعادلات المستقلة خطيًا (يُقارب عدد الحدود). مع ذلك، ونظرًا لقلة المعادلات اللازمة لتحليل تشفير HFE، اقترح كيبنيس وشامير إعادة التخطيط الخطي ، وهي تقنية تُضاف فيها معادلات غير خطية إضافية بعد التخطيط الخطي، ثم يُحل النظام الناتج بتطبيق ثانٍ للتخطيط الخطي. وقد أثبتت إعادة التخطيط الخطي عموميتها الكافية لتطبيقها على مخططات أخرى.

في عام 2000، اقترح كورتوا وآخرون خوارزمية محسّنة لـ MQ تُعرف باسم XL (اختصارًا لـ eXtended Linearization )، والتي تزيد عدد المعادلات بضربها بجميع أحاديات الحدود من درجة معينة . أظهرت تقديرات التعقيد أن هجوم XL لن ينجح ضد المعادلات المشتقة من تشفيرات الكتل مثل AES. مع ذلك، تميزت أنظمة المعادلات الناتجة ببنية خاصة، وطُوّرت خوارزمية XSL كتحسين لـ XL للاستفادة من هذه البنية. في XSL، تُضرب المعادلات فقط بأحاديات حدود مختارة بعناية، وقد اقتُرحت عدة متغيرات.

لا يزال البحث جارياً حول كفاءة XL والخوارزميات المشتقة منها (يانغ وتشين، 2004).

تطبيق على التشفير الكتلي

لاحظ كورتوا وبيبرزيك (2002) أن خوارزمية التشفير المتقدمة (AES ) (Rijndael)، وجزئيًا خوارزمية Serpent ، يمكن التعبير عنها كنظام من المعادلات التربيعية. لا تمثل المتغيرات النص الأصلي والنص المشفر وبتات المفتاح فحسب، بل تمثل أيضًا قيمًا وسيطة مختلفة داخل الخوارزمية. ويبدو أن صندوق الاستبدال (S-box) في خوارزمية AES عرضة بشكل خاص لهذا النوع من التحليل، نظرًا لاعتماده على دالة عكسية بسيطة جبريًا . لاحقًا، دُرست خوارزميات تشفير أخرى لمعرفة أنظمة المعادلات التي يمكن إنتاجها ( بيريوكوف ودي كانيير، 2003)، بما في ذلك Camellia و KHAZAD و MISTY1 و KASUMI . على عكس أشكال تحليل التشفير الأخرى، مثل التحليل التفاضلي والخطي ، لا يتطلب الأمر سوى نص أصلي واحد أو اثنين (في حالة حجم كتلة 128 بت وحجم مفتاح 256 بت) .

صُممت خوارزمية XSL خصيصًا لحل أنواع أنظمة المعادلات الناتجة. ويُقدّر كورتوا وبيبرزيك أن "تقييمًا متفائلًا يُشير إلى أن هجوم XSL قد يكون قادرًا على اختراق خوارزمية Rijndael ذات 256 بت، وخوارزمية Serpent ذات أطوال مفاتيح 192 و256 بت". مع ذلك، لا يحظى تحليلهما بقبول عالمي. على سبيل المثال:

أعتقد أن عمل كورتوا-بيبرزيك معيب. فهم يبالغون في حساب عدد المعادلات المستقلة خطيًا. والنتيجة هي أنهم لا يملكون في الواقع عددًا كافيًا من المعادلات الخطية لحل النظام، ولا تُخالف هذه الطريقة قواعد رينديل... للطريقة بعض المزايا، وتستحق البحث، لكنها لا تُخالف قواعد رينديل في وضعها الحالي.

في مؤتمر AES 4، بون 2004، علّق فينسنت ريجمان ، أحد مخترعي خوارزمية Rijndael ، قائلاً: "هجوم XSL ليس هجومًا، بل هو حلم". فأجابه كورتوا على الفور: "قد يكون XSL حلمًا، وقد يكون أيضًا حلمًا سيئًا للغاية يتحول إلى كابوس". [ 1 ] ومع ذلك، لم تُقدّم أي ورقة بحثية لاحقة أو أي إجراءات من وكالة الأمن القومي أو المعهد الوطني للمعايير والتكنولوجيا أي دعم لملاحظة كورتوا هذه.

في عام 2003، اكتشف مورفي وروبشو وصفًا بديلًا لخوارزمية التشفير المتقدمة (AES)، حيث قاما بتضمينها في خوارزمية تشفير أكبر تُسمى "BES"، والتي يمكن وصفها باستخدام عمليات بسيطة للغاية على حقل واحد ، GF (2^ 8 ). يُنتج هجوم XSL المُطبق على هذا النظام مجموعة معادلات أبسط من شأنها كسر خوارزمية AES بتعقيد يبلغ حوالي 2^ 100 ، إذا كان تحليل كورتوا وبيبرزيك صحيحًا. في عام 2005، قدم سيد ولورينت دليلًا على أن خوارزمية XSL، بصيغتها المقترحة، لا تُوفر طريقة فعالة لحل نظام معادلات AES؛ ومع ذلك، اعترض كورتوا على نتائجهم. في مؤتمر FSE 2007، أظهر تشو-وي ليم وخونغمينغ خو أن هجوم XSL كان أسوأ من استخدام القوة الغاشمة على خوارزمية BES.

حتى لو نجح هجوم XSL ضد بعض الخوارزميات الحديثة، فإنه لا يشكل خطراً كبيراً على الأمن العملي في الوقت الحالي. ومثل العديد من نتائج التحليل التشفيري الحديثة، يُعد هذا الهجوم ما يُعرف بـ"نقطة ضعف في عملية التحقق": فرغم أنه أسرع من هجوم القوة الغاشمة ، إلا أن الموارد المطلوبة لا تزال هائلة، ومن المستبعد جداً أن تتعرض الأنظمة الحقيقية للاختراق باستخدامه. مع ذلك، قد تُحسّن التحسينات المستقبلية من جدوى الهجوم. ولأن هذا النوع من الهجمات جديد وغير متوقع، فقد أعرب بعض خبراء التشفير عن قلقهم إزاء البساطة الجبرية لخوارزميات التشفير مثل Rijndael. كتب بروس شناير ونيلز فيرغسون : "لدينا انتقاد واحد لخوارزمية AES: فنحن لا نثق تماماً بأمانها... ما يُقلقنا أكثر بشأن AES هو بنيتها الجبرية البسيطة... لا توجد خوارزمية تشفير كتلية أخرى نعرفها تتمتع بمثل هذا التمثيل الجبري البسيط. ليس لدينا أدنى فكرة عما إذا كان هذا يؤدي إلى هجوم أم لا، ولكن عدم المعرفة سبب كافٍ للتشكيك في استخدام AES." ( التشفير العملي ، 2003، ص 56-57)

مراجع

  1. ↑ فينسنت ريجمان (18 ديسمبر 2002). "ردًا على: خوارزمية رينديل وغيرها من خوارزميات التشفير الكتلي" . مؤرشف من الأصل بتاريخ 3 أغسطس 2004. تم الاطلاع عليه بتاريخ 16 مارس 2015 .
  • بيريوكوف، أليكس؛ كانيير، كريستوف دي (2003). "التشفير الكتلي وأنظمة المعادلات التربيعية". في: يوهانسون، توماس (محرر). التشفير البرمجي السريع، ورشة العمل الدولية العاشرة، FSE 2003، لوند، السويد، 24-26 فبراير 2003، أوراق منقحة . سلسلة محاضرات في علوم الحاسوب. المجلد  2887. سبرينغر. الصفحات 274-289 . doi : 10.1007/978-3-540-39887-5_21 . ISBN  978-3-540-20449-7.
  • كورتوا، نيكولا ت.؛ كليموف، ألكسندر؛ باتارين، جاك؛ شامير، عدي (2000). "خوارزميات فعّالة لحل أنظمة المعادلات متعددة الحدود ذات المتغيرات المتعددة" (ملف PDF) . في: برينيل، بارت (محرر). التطورات في علم التشفير - يورو كريبت 2000، المؤتمر الدولي حول نظرية وتطبيق تقنيات التشفير، بروج، بلجيكا، 14-18 مايو 2000، وقائع المؤتمر. سلسلة محاضرات في علوم الحاسوب. المجلد  1807. سبرينغر. الصفحات 392-407 . doi : 10.1007/3-540-45539-6_27 . ISBN  978-3-540-67517-4.
  • كورتوا، نيكولاس ت.؛ بيبرزيك، جوزيف (2002). "تحليل تشفير الكتل باستخدام أنظمة المعادلات المُعرَّفة بشكل زائد" . في: تشنغ، يوليانغ (محرر). التطورات في علم التشفير - ASIACRYPT 2002، المؤتمر الدولي الثامن حول نظرية وتطبيق علم التشفير وأمن المعلومات، كوينزتاون، نيوزيلندا، 1-5 ديسمبر 2002، وقائع المؤتمر . سلسلة محاضرات في علوم الحاسوب. المجلد  2501. سبرينغر. الصفحات 267-287 . doi : 10.1007/3-540-36178-2_17 . ISBN  978-3-540-00171-3.
  • كيبنيس، أفياد؛ شامير، عدي (1999). "تحليل تشفير نظام المفتاح العام HFE عن طريق إعادة التخطيط الخطي". في: وينر، مايكل ج. (محرر). التطورات في علم التشفير - CRYPTO '99، المؤتمر الدولي السنوي التاسع عشر لعلم التشفير، سانتا باربرا، كاليفورنيا، الولايات المتحدة الأمريكية، 15-19 أغسطس 1999، وقائع المؤتمر . سلسلة محاضرات في علوم الحاسوب. المجلد  1666. سبرينغر. الصفحات 19-30 . doi : 10.1007/3-540-48405-1_2 . ISBN  978-3-540-66347-8.
  • ليم، تشو-وي؛ خو، خونغمينغ (2007). "تحليل XSL المطبق على BES". في: بيريوكوف، أليكس (محرر). التشفير البرمجي السريع، ورشة العمل الدولية الرابعة عشرة، FSE 2007، لوكسمبورغ، 26-28 مارس 2007، أوراق مختارة منقحة . سلسلة محاضرات في علوم الحاسوب. المجلد  4593. سبرينغر. الصفحات 242-253 . doi : 10.1007/978-3-540-74619-5_16 . ISBN  978-3-540-74617-1.
  • دانا ماكنزي (2003). "لعبة حظ". مجلة نيو ساينتست . 178 (2398): 36.
  • مورفي، شون؛ روبشو، ماثيو جيه بي (2002). "البنية الجبرية الأساسية ضمن معيار التشفير المتقدم". في: يونغ، موتي (محرر). التطورات في علم التشفير - CRYPTO 2002، المؤتمر الدولي السنوي الثاني والعشرون لعلم التشفير، سانتا باربرا، كاليفورنيا، الولايات المتحدة الأمريكية، 18-22 أغسطس 2002، وقائع المؤتمر . سلسلة محاضرات في علوم الحاسوب. المجلد  2442. سبرينغر. الصفحات 1-16 . doi : 10.1007/3-540-45708-9_1 . ISBN  978-3-540-44050-5.
  • إس. مورفي، إم. روبشو تعليقات حول أمان AES وتقنية XSL .
  • يانغ، بو-يين؛ تشين، جيون-مينغ (2004). "التحليل النظري لـ XL على الحقول الصغيرة". في: وانغ، هواكسيونغ؛ بيبرزيك، جوزيف؛ فاراداراجان، فيجاي (محررون). أمن المعلومات والخصوصية: المؤتمر الأسترالي التاسع، ACISP 2004، سيدني، أستراليا، 13-15 يوليو 2004. وقائع المؤتمر . سلسلة محاضرات في علوم الحاسوب. المجلد  3108. سبرينغر. الصفحات 277-288 . doi : 10.1007/978-3-540-27800-9_24 . ISBN  978-3-540-22379-5.
  • سيد، كارلوس؛ لورينت، غايتان (2005). "تحليل خوارزمية XSL". في روي، بيمال ك. (محرر). التطورات في علم التشفير - ASIACRYPT 2005، المؤتمر الدولي الحادي عشر حول نظرية وتطبيق علم التشفير وأمن المعلومات، تشيناي، الهند، 4-8 ديسمبر 2005، وقائع المؤتمر . سلسلة محاضرات في علوم الحاسوب. المجلد  3788. سبرينغر. الصفحات 333-352 . doi : 10.1007/11593447_18 . ISBN  978-3-540-30684-9.
  • ديم، كلاوس (2004). "خوارزمية XL وتخمين من الجبر التبادلي". في: لي، بيل جونغ (محرر). التطورات في علم التشفير - ASIACRYPT 2004، المؤتمر الدولي العاشر حول نظرية وتطبيق علم التشفير وأمن المعلومات، جزيرة جيجو، كوريا، 5-9 ديسمبر 2004، وقائع المؤتمر . سلسلة محاضرات في علوم الحاسوب. المجلد  3329. سبرينغر. الصفحات 323-337 . doi : 10.1007/978-3-540-30539-2_23 . ISBN  978-3-540-23975-8.