هجوم الاستيفاء

في علم التشفير ، يعتبر هجوم الاستيفاء نوعًا من أنواع الهجمات التحليلية المشفرة ضد التشفير الكتلي .

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

في هذا الهجوم، تُستخدم دالة جبرية لتمثيل صندوق الاستبدال (S-box) . قد تكون هذه الدالة تربيعية بسيطة ، أو متعددة الحدود ، أو كسرية على حقل غالوا . يمكن تحديد معاملات هذه الدالة باستخدام تقنيات استيفاء لاغرانج القياسية، وذلك باستخدام النصوص الأصلية المعروفة كنقاط بيانات. بدلاً من ذلك، يمكن استخدام نصوص أصلية مختارة لتبسيط المعادلات وتحسين الهجوم.

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

يمكن أيضًا استخدام هجوم الاستيفاء لاستعادة المفتاح السري.

من الأسهل وصف الطريقة بمثال.

لنفترض أن التشفير المتكرر معطى بواسطة

${\displaystyle c_{i}=(c_{i-1}\oplus k_{i})^{3},}$

أين${\displaystyle c_{0}}$هو النص الأصلي،${\displaystyle c_{i}}$مخرجات${\displaystyle i^{th}}$دائري،${\displaystyle k_{i}}$السر${\displaystyle i^{th}}$المفتاح الدائري (المشتق من المفتاح السري)${\displaystyle K}$(بحسب جدول زمني رئيسي معين )، ولـ${\displaystyle r}$التشفير المتكرر ذو الجولات،${\displaystyle c_{r}}$هذا هو النص المشفر.

لنفترض وجود تشفير من جولتين.${\displaystyle x}$يشير إلى الرسالة، و${\displaystyle c}$يشير إلى النص المشفر.

ثم يصبح ناتج الجولة الأولى

${\displaystyle c_{1}=(x+k_{1})^{3}=(x^{2}+k_{1}^{2})(x+k_{1})=x^{3}+k_{1}^{2}x+x^{2}k_{1}+k_{1}^{3},}$

وتصبح مخرجات الجولة الثانية

${\displaystyle c_{2}=c=(c_{1}+k_{2})^{3}=(x^{3}+k_{1}^{2}x+x^{2}k_{1}+k_{1}^{3}+k_{2})^{3}}$

${\displaystyle =x^{9}+x^{8}k_{1}+x^{6}k_{2}+x^{4}k_{1}^{2}k_{2}+x^{3}k_{2}^{2}+x^{2}(k_{1}k_{2}^{2}+k_{1}^{4}k_{2})+x(k_{1}^{2}k_{2}^{2}+k_{1}^{8})+k_{1}^{3}k_{2}^{2}+k_{1}^{9}+k_{2}^{3},}$

ينتج عن التعبير عن النص المشفر كمتعدد حدود للنص الأصلي

${\displaystyle p(x)=a_{1}x^{9}+a_{2}x^{8}+a_{3}x^{6}+a_{4}x^{4}+a_{5}x^{3}+a_{6}x^{2}+a_{7}x+a_{8},}$

حيث${\displaystyle a_{i}}$'s هي ثوابت تعتمد على المفاتيح.

استخدام عدد من أزواج النص العادي/النص المشفر يساوي عدد المعاملات المجهولة في متعددة الحدود${\displaystyle p(x)}$بعد ذلك، يمكننا بناء متعددة الحدود. يمكن القيام بذلك، على سبيل المثال، باستخدام استيفاء لاغرانج (انظر متعددة حدود لاغرانج ). عندما يتم تحديد المعاملات المجهولة، نحصل على تمثيل${\displaystyle p(x)}$التشفير، دون معرفة المفتاح السري${\displaystyle K}$.

بالنظر إلى${\displaystyle m}$ثم هناك تشفير الكتلة ذو البتات -${\displaystyle 2^{m}}$النصوص الأصلية المحتملة، وبالتالي${\displaystyle 2^{m}}$متميز${\displaystyle p/c}$أزواج. ليكن${\displaystyle n}$معاملات مجهولة في${\displaystyle p(x)}$بما أننا نحتاج إلى أكبر عدد ممكن${\displaystyle p/c}$إذا كان عدد الأزواج يساوي عدد المعاملات المجهولة في متعددة الحدود، فإن هجوم الاستيفاء لا يوجد إلا إذا${\displaystyle n\leq 2^{m}}$.

افترض أن الوقت اللازم لإنشاء متعددة الحدود${\displaystyle p(x)}$استخدام${\displaystyle p/c}$تكون الأزواج صغيرة مقارنةً بالوقت اللازم لتشفير النصوص الأصلية المطلوبة. لنفترض أن${\displaystyle n}$معاملات مجهولة في${\displaystyle p(x)}$إذن، فإن التعقيد الزمني لهذا الهجوم هو${\displaystyle n}$، مما يتطلب${\displaystyle n}$معروف ومتميز${\displaystyle p/c}$أزواج.

غالباً ما تكون هذه الطريقة أكثر فعالية. إليك كيفية القيام بذلك.

بالنظر إلى${\displaystyle r}$تشفير متكرر دائري بطول كتلة${\displaystyle m}$، يترك${\displaystyle z}$يكون ناتج التشفير بعد${\displaystyle s}$جولات مع${\displaystyle s<r}$سنعبر عن قيمة${\displaystyle z}$كدالة متعددة الحدود للنص الأصلي${\displaystyle x}$، وكدالة متعددة الحدود للنص المشفر${\displaystyle c}$. يترك${\displaystyle g(x)\in GF(2^{m})[x]}$كن تعبيرًا عن${\displaystyle z}$عبر${\displaystyle x}$ودع${\displaystyle h(c)\in GF(2^{m})[c]}$كن تعبيرًا عن${\displaystyle z}$عبر${\displaystyle c}$متعددة الحدود${\displaystyle g(x)}$يتم الحصول على ذلك عن طريق حساب الاتجاه الأمامي باستخدام الصيغة المتكررة للتشفير حتى الجولة${\displaystyle s}$، ومتعددة الحدود ${\displaystyle h(c)}$يتم الحصول على ذلك عن طريق الحساب العكسي من الصيغة المتكررة للتشفير بدءًا من الجولة${\displaystyle r}$حتى الجولة${\displaystyle s+1}$.

لذا ينبغي أن يكون هذا صحيحاً.

${\displaystyle g(x)=h(c),}$

وإذا كان كلاهما${\displaystyle g}$و${\displaystyle h}$إذا كانت كثيرات الحدود ذات عدد قليل من المعاملات، فيمكننا حل المعادلة لإيجاد المعاملات المجهولة.

يمكننا أيضًا استخدام هجوم الاستيفاء لاستعادة المفتاح السري${\displaystyle K}$.

إذا أزلنا الجولة الأخيرة من${\displaystyle r}$تشفير متكرر ذو طول كتلة${\displaystyle m}$، يصبح ناتج التشفير${\displaystyle {\tilde {y}}=c_{r-1}}$أطلق على هذه الشفرة اسم الشفرة المختزلة. الفكرة هي تخمين مفتاح الجولة الأخيرة.${\displaystyle k_{r}}$بحيث يمكننا فك التشفير في جولة واحدة للحصول على الناتج${\displaystyle {\tilde {y}}}$من الشفرة المُختزلة. ثم للتحقق من التخمين، نستخدم هجوم الاستيفاء على الشفرة المُختزلة إما بالطريقة العادية أو بطريقة "اللقاء في المنتصف". إليك كيفية القيام بذلك.

بالطريقة المعتادة نعبر عن الناتج${\displaystyle {\tilde {y}}}$من الشفرة المختزلة كمتعددة حدود للنص الأصلي${\displaystyle x}$. سمِّ هذه المعادلة متعددة الحدود${\displaystyle p(x)\in GF(2^{m})[x]}$ثم إذا استطعنا التعبير${\displaystyle p(x)}$مع${\displaystyle n}$المعاملات، ثم باستخدام${\displaystyle n}$معروف ومتميز${\displaystyle p/c}$باستخدام الأزواج، يمكننا بناء متعددة الحدود. للتحقق من تخمين مفتاح الجولة الأخيرة، ثم التحقق باستخدام مفتاح إضافي واحد.${\displaystyle p/c}$الزوج إذا كان ذلك صحيحًا

${\displaystyle p(x)={\tilde {y}}.}$

إذا كانت الإجابة بنعم، فمن المرجح أن يكون تخمين مفتاح الجولة الأخيرة صحيحًا. أما إذا كانت الإجابة بلا، فقم بتخمين المفتاح مرة أخرى.

باستخدام طريقة الالتقاء في المنتصف، نعبر عن الناتج${\displaystyle z}$من الجولة${\displaystyle s<r}$كدالة متعددة الحدود للنص الأصلي${\displaystyle x}$وكدالة متعددة الحدود لمخرجات التشفير المختزل${\displaystyle {\tilde {y}}}$. سمِّ كثيرات الحدود${\displaystyle g(x)}$و${\displaystyle h({\tilde {y}})}$وليكن التعبير عنها بواسطة${\displaystyle p}$و${\displaystyle q}$المعاملات، على التوالي. ثم مع${\displaystyle q+p-2}$معروف ومتميز${\displaystyle p/c}$يمكننا إيجاد المعاملات من خلال الأزواج. وللتحقق من صحة تخمين مفتاح الجولة الأخيرة، يتم التحقق منه باستخدام مفتاح إضافي.${\displaystyle p/c}$الزوج إذا كان ذلك صحيحًا

${\displaystyle g(x)=h({\tilde {y}}).}$

إذا كانت الإجابة بنعم، فمن المرجح أن يكون تخمين مفتاح الجولة الأخيرة صحيحًا. أما إذا كانت الإجابة بلا، فقم بتخمين المفتاح مرة أخرى.

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

يمكن استخدام هجوم "اللقاء في المنتصف" في شكل مختلف لمهاجمة صناديق الاستبدال (S-boxes)، والذي يستخدم الدالة العكسية، لأنه مع${\displaystyle m}$صندوق S-bit ثم${\displaystyle S:f(x)=x^{-1}=x^{2^{m}-2}}$في${\displaystyle GF(2^{m})}$.

تستخدم خوارزمية التشفير الكتلي SHARK شبكة SP مع صندوق S${\displaystyle S:f(x)=x^{-1}}$تُقاوم هذه الشفرة التحليلَ التفاضلي والخطي بعد عدد قليل من الجولات. مع ذلك، تم كسرها عام ١٩٩٦ على يد توماس جاكوبسن ولارس كنودسن باستخدام هجوم الاستيفاء. يُرمز لها بـ SHARK${\displaystyle (n,m,r)}$نسخة من برنامج SHARK بحجم كتلة${\displaystyle nm}$بتات باستخدام${\displaystyle n}$ موازي${\displaystyle m}$صناديق الاستبدال ذات البتات في${\displaystyle r}$جولات. وجد جاكوبسن وكنودسن أن هناك هجوم استيفاء على برنامج SHARK${\displaystyle (8,8,4)}$(تشفير الكتلة 64 بت) باستخدام حوالي${\displaystyle 2^{21}}$نصوص عادية مختارة، وهجوم استيفاء على برنامج SHARK${\displaystyle (8,16,7)}$(تشفير الكتلة 128 بت) باستخدام حوالي${\displaystyle 2^{61}}$النصوص الأصلية المختارة.

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

• توماس جاكوبسن ، لارس كنودسن (يناير 1997). هجوم الاستيفاء على تشفيرات الكتل ( ملف PDF / PostScript ) . ورشة العمل الدولية الرابعة حول التشفير السريع للبرمجيات (FSE '97)، سلسلة محاضرات في علوم الحاسوب 1267. حيفا : سبرينغر-فيرلاغ . الصفحات 28-40 . تاريخ الاسترجاع : 3 يوليو 2007 . 
• توماس جاكوبسن (25 أغسطس 1998). تحليل تشفير الكتل باستخدام العلاقات غير الخطية الاحتمالية منخفضة الدرجة (PDF/PostScript) . التطورات في علم التشفير - CRYPTO '98. سانتا باربرا، كاليفورنيا : سبرينغر-فيرلاغ. الصفحات 212-222 . تاريخ الاسترجاع: 6 يوليو 2007 . ( فيديو لعرض تقديمي على جوجل فيديو - يستخدم تقنية فلاش )
• شيهو مورياي؛ تاكيشي شيموياما؛ توشينوبو كانيكو (مارس 1999). هجمات الاستيفاء على تشفير الكتلة: سنيك (ملف PDF) . FSE '99. روما: سبرينغر-فيرلاغ. الصفحات 275-289 . doi : 10.1007/3-540-48519-8_20 . تاريخ الاسترجاع : 6 نوفمبر 2022 . 
• عمرو م. يوسف؛ غوانغ غونغ (أبريل 2000). حول هجمات الاستيفاء على تشفيرات الكتل (ملف PDF) . FSE 2000. مدينة نيويورك : سبرينغر-فيرلاغ. الصفحات 109-120 . تاريخ الاسترجاع : 6 يوليو 2007 . 
• كاورو كوروساوا؛ تيتسو إيواتا؛ فييت دوونغ كوانغ (أغسطس 2000). هجوم الاستيفاء لإيجاد الجذر (PDF/PostScript) . وقائع ورشة العمل الدولية السنوية السابعة حول مجالات مختارة في علم التشفير (SAC 2000). واترلو، أونتاريو : سبرينغر-فيرلاغ. الصفحات 303-314 . تاريخ الاسترجاع: 6 يوليو 2007 .