التحليل التشفيري الدوراني

في علم التشفير، يُعدّ التحليل التشفيري الدوراني هجومًا تشفيريًا عامًا يستهدف الخوارزميات التي تعتمد على ثلاث عمليات: الجمع المعياري ، والدوران، وعملية XOR ( أو ARX اختصارًا). تحظى الخوارزميات التي تعتمد على هذه العمليات بشعبية واسعة نظرًا لانخفاض تكلفتها نسبيًا من حيث المكونات المادية والبرمجية، فضلًا عن تشغيلها في وقت ثابت، مما يجعلها في مأمن من هجمات التوقيت في التطبيقات الشائعة.

تعتمد الفكرة الأساسية لتحليل التشفير الدوراني على أن كلاً من دوران البتات وعمليات XOR تحافظ على الارتباطات بين أزواج المدخلات التي خضعت لدوران البتات، وأن إضافة هذه المدخلات تحافظ جزئيًا على ارتباطات دوران البتات. وبالتالي، يمكن استخدام أزواج المدخلات الدورانية "لرؤية" عمليات ARX المتتالية في أنظمة التشفير بدرجة أكبر مما هو متوقع. ^{[ 1 ]} ويمكن استغلال هذه القدرة على "رؤية" الارتباطات عبر جولات المعالجة لكسر نظام التشفير بطريقة مشابهة لتحليل التشفير التفاضلي .

صاغ ديمتري خوفاتوفيتش وإيفيكا نيكوليتش ​​مصطلح "التحليل التشفيري الدوراني" في ورقة بحثية عام 2010 بعنوان "التحليل التشفيري الدوراني لـ ARX"، والتي عرضت أفضل الهجمات التحليلية التشفيرية في ذلك الوقت ضد تشفير Threefish ذي عدد جولات منخفض - وهو جزء من دالة التجزئة Skein ، المرشحة لمنافسة SHA-3 . ^{[ 1 ] [ 2 ]} وقد تمكن هجوم لاحق من نفس المؤلفين وكريستيان ريشبيرغر من كسر مقاومة التصادم لما يصل إلى 53 من أصل 72 جولة في Skein-256، و57 من أصل 72 جولة في Skein-512. ^{[ 3 ]} كما يؤثر هذا الهجوم على تشفير Threefish بما يصل إلى 39 جولة لمفاتيح 256 بت، و42 جولة لمفاتيح 512 بت، و43 جولة لمفاتيح 1024 بت بتعقيدات${\displaystyle 2^{252.4}}$،${\displaystyle 2^{507}}$، و${\displaystyle 2^{1014.4}}$على التوالي. ^{[ 1 ]}

يستفيد التحليل التشفيري الدوراني من حقيقة أن دالة XOR تحافظ على عمليات الدوران التي يتم إجراؤها على جزء من البيانات باحتمالية 1، وأنه على الرغم من أن الجمع المعياري لا يحافظ دائمًا على الدوران، إلا أن الاحتمالية يمكن أن تكون عالية بما يكفي (اعتمادًا على نظام التشفير) بحيث تصبح الإصدارات ذات الجولات المخفضة، أو أنظمة التشفير المعدلة مع إزالة الجمع المعياري، أو أنظمة تشفير ARX الضعيفة للغاية التي لا تستخدم عمليات جمع كافية عرضة للخطر بسهولة.

ليكن أي حرف متغيرًا معطى في النظام الثنائي، وليكن أي عملية أو بيانات بين قوسين "()" عبارة معطاة تتعلق بالبيانات التي تم إزاحتها بمقدار "r".

(x${\displaystyle \oplus }$y)=(x)${\displaystyle \oplus }$(y) و " (x)r" يساوي بشكل بديهي "(x مزاحة بواسطة r)" (حيث أن x و r هما الشيئان الوحيدان اللذان يحددان الناتج).

إضافة معيارية لـ${\displaystyle 2^{n}}$يُعدّ هذا الأمر أكثر تعقيدًا لأنه قد يكون غير خطي في معظم الحالات. احتمال بقاء سلسلة معينة بعد إزاحتها بعد عملية الجمع المعياري (أي "(س + ص) = (س) + (ص)") يساوي:

${\displaystyle (1/4)(1+2^{rn}+2^{-r}+2^{-n})}$^{[ 1 ]}

حيث "n" هو الأس في${\displaystyle 2^{n}}$، و r هي مقدار الدوران كما في السابق.

احتمالية بقاء جزء من نظام ثنائي مُدار بعد اجتيازه نظام تشفير ARX هي${\displaystyle (p{r})^{q}}$حيث "pr" هي احتمالية النجاة من عملية جمع نمطية منفردة وفقًا للصيغة المذكورة أعلاه، و"q" هي عدد عمليات الجمع ضمن مخطط ARX. ^{[ 1 ]} لكي يكون الهجوم ذا جدوى نظرية، يجب أن تكون احتمالية الحصول على المفتاح من الهجوم أقل من فرصة اكتشافه عشوائيًا (أي متوسط ​​تعقيد الحالة لـ${\displaystyle 2^{n}}$يجب أن يكون مستوى هجوم التحليل التشفيري الدوراني أقل من${\displaystyle 2^{n}}$(من القوة الغاشمة الخام). النسخ الكاملة لمعظم أنظمة تشفير ARX ليست عرضة للاختراق، ولكن جولاتها المخفضة تكون كذلك لأن احتمال استعادة المفتاح يكون أعلى في بداية عملية الخلط (الجولات) منه في النهاية.

من المهم أيضًا ملاحظة أن العديد من مخططات ARX تحتوي على حدود ثابتة تحتاج إلى عملية XOR وجمعها ضمن المخطط العادي. لا يمثل هذا مشكلة في الحالات التي يتم فيها تدوير الثوابت المستخدمة (كما ذُكر سابقًا، (x${\displaystyle \oplus }$y)=(x)${\displaystyle \oplus }$(y)، حيث يُحتمل أن يكون أحد المتغيرات ثابتًا، ولكن الثوابت التي لا تخضع للتدوير تُقلل من احتمالية بقاء عمليات التدوير. حاول مؤلفو ورقة الهجوم الأصلية معالجة هذا الأمر من خلال إدخال متغيرات "تصحيح الأخطاء" التي تم التوصل إليها باستخدام طريقة مونت كارلو ، والتي تهدف إلى زيادة فرصة إلغاء الثوابت خلال عملية الجولة. يمتلك ثابت تصحيح الأخطاء فرصة لإزالة التمويه الثابت لجولة معينة من نظام التشفير عن طريق إجراء عملية XOR بين ناتج الدالة وثابت الخطأ المُعطى.

على سبيل المثال، في Skein ، يكون لثابت الخطأ احتمال إنشاء التكافؤ التالي، مما يعكس دالة ضغط التجزئة إلى النقطة التي تسبق استخدام الثوابت:

${\displaystyle Skein((X)\oplus {E})=(Skein(X))}$^{[ 4 ]} حيث "e" هو ثابت الخطأ و"${\displaystyle (Skein(X))}$" هو ناتج دالة التقريب في الوقت المحدد بدون الثابت المعني.

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

بصرف النظر عن طبيعة التحليل التشفيري الدوراني ذي عدد الجولات المخفّض، والحظ اللازم لنجاح الهجوم، فإنّ أحد أهمّ وسائل التخفيف منه هو إضافة عدد من عمليات الجمع اللازمة لتناسب مستوى أمان التشفير. بالنسبة لتشفير ARX الذي يتطلب${\displaystyle 2^{128}}$فيما يتعلق بالأمان، يجب ألا يتجاوز عدد الإضافات المعيارية 128 إضافة تقريبًا وفقًا لما سبق.${\displaystyle (p{r})^{q}}$المعادلة، باستثناء القيود الأخرى.

تتطلب طريقة الهجوم الخاصة بـ Threefish حدوث هجوم نص عادي مختار ، وهو ما يأتي مع قيود مثل هذا الهجوم.

من القيود الأخرى أنه لا يوجد ضمان بأن تطبيق متغيرات تصحيح الأخطاء بنجاح سيؤدي إلى إلغاء الثوابت خلال الجولات. تشير الورقة البحثية الأصلية إلى أن احتمال إلغاء الثوابت عشوائيًا في جولة معينة يقل كلما زاد وزن هامينغ . ^{[ 1 ]} إن زيادة أوزان هامينغ للثوابت في جولات المفاتيح وجولات الضغط تزيد من هامش الأمان.