هجوم بيكليك

يحصل${\displaystyle 2^{d}}$^{[ 7 ]} حالات وسيطة ^{[ 8 ]} و${\displaystyle 2^{d}}$بعد ذلك، يتم حساب المفاتيح التي تربط قيمة وسيطة واحدة بجميع النصوص المشفرة ^{[ 9 ]} . ثم تُكرر عملية ربط المفاتيح "من واحد إلى متعدد" لجميع القيم الوسيطة.

تتطلب عملية رسم الخرائط هذه${\displaystyle (2^{d})_{\text{عدد الحالات الوسيطة}}\cdot (2^{d})_{\text{عدد النصوص المشفرة لكل حالة وسيطة}}=2^{d+d}=2^{2d}}$عمليات استعادة المفاتيح، حيث يجب ربط كل حالة وسيطة بجميع النصوص المشفرة (وليس بنص مشفر واحد فقط). ^{[ 10 ]}

(تم اقتراح هذه الطريقة من قبل بوغدانوف وخوفراتوفيتش وريشبيرغر في ورقتهم البحثية: تحليل التشفير الثنائي لخوارزمية AES الكاملة ^{[ 2 ]} )

تمهيد: تذكر أن وظيفة المجموعة الثنائية هي تعيين القيم الوسيطة،${\displaystyle S}$، إلى قيم النص المشفر،${\displaystyle C}$، بناءً على المفتاح${\displaystyle K[i,j]}$بحيث: ${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

الإجراء: الخطوة الأولى: حالة وسيطة (${\displaystyle S_{0}}$), نص مشفر(${\displaystyle C_{0}}$) ومفتاح(${\displaystyle K[0,0]}$يتم اختيار ) بحيث:${\displaystyle S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}}$، أين${\displaystyle f}$هي الدالة التي تربط حالة وسيطة بنص مشفر باستخدام مفتاح معين. ويُشار إلى هذا باسم الحساب الأساسي.

الخطوة الثانية: مجموعتان من المفاتيح ذات الصلة بحجم${\displaystyle 2^{d}}$يتم اختيارها. يتم اختيار المفاتيح بحيث:

• المجموعة الأولى من المفاتيح هي مفاتيح، والتي تفي بالمتطلبات التفاضلية التالية على${\displaystyle f}$فيما يتعلق بالحساب الأساسي:${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}}$
• أما المجموعة الثانية من المفاتيح فهي مفاتيح، والتي تفي بالمتطلبات التفاضلية التالية على${\displaystyle f}$فيما يتعلق بالحساب الأساسي:${\displaystyle \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0}$
• يتم اختيار المفاتيح بحيث تكون آثار ...${\displaystyle \Delta _{i}}$- و${\displaystyle \nabla _{j}}$-التفاضلات مستقلة - أي أنها لا تشترك في أي مكونات غير خطية نشطة.

بمعنى آخر: يجب أن يُقابل فرق الإدخال الذي يساوي صفرًا فرقًا في الإخراج يساوي${\displaystyle \Delta _{i}}$في ظل اختلاف رئيسي يتمثل في${\displaystyle \Delta _{i}^{K}}$جميع الفروقات تتعلق بالحساب الأساسي. فرق الإدخال هو${\displaystyle \nabla _{j}}$ينبغي أن يُقابل ذلك فرقًا في المخرجات يساوي صفرًا في ظل فرق رئيسي قدره${\displaystyle \nabla _{J}^{K}}$جميع الاختلافات تتعلق بالحساب الأساسي.

الخطوة الثالثة: بما أن المسارات لا تشترك في أي مكونات غير خطية (على سبيل المثال، المسارات التي لا تشترك في أي صناديق S )، يمكن دمج المسارات للحصول على: ${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}}$، وهو ما يتوافق مع تعريفات كلا التفاضلين من الخطوة 2. من السهل ملاحظة أن المجموعة ^{[ 11 ]}${\displaystyle (S_{0},C_{0},K[0,0])}$انطلاقًا من الحساب الأساسي، يتوافق أيضًا بحكم التعريف مع كلا التفاضلين، كما هو الحال بالنسبة للتفاضلين بالنسبة للحساب الأساسي. بالتعويض${\displaystyle S_{0},C_{0}}$${\displaystyle K[0,0]}$سيؤدي إدخال أي من التعريفين إلى${\displaystyle 0{\xrightarrow[{f}]{0}}0}$منذ${\displaystyle \Delta _{0}=0,\nabla _{0}=0}$و${\displaystyle \Delta _{0}^{K}=0}$وهذا يعني أنه يمكن أيضًا تطبيق عملية XOR على مجموعة البيانات الخاصة بالحساب الأساسي مع المسارات المدمجة :${\displaystyle S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}}$

الخطوة الرابعة: من السهل ملاحظة ما يلي: ${\displaystyle S_{j}=S_{0}\oplus \nabla _{j}}$${\displaystyle K[i,j]=K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}$${\displaystyle C_{i}=C_{0}\oplus \Delta _{i}}$ إذا تم استبدال هذا في مسارات التفاضل المجمعة أعلاه، فستكون النتيجة كالتالي: ${\displaystyle S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$وهو نفس التعريف الذي ورد سابقًا أعلاه للثنائية:${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

وبالتالي، من الممكن إنشاء مجموعة ثنائية من الحجم${\displaystyle 2^{2d}}$(${\displaystyle 2^{2d}}$منذ كل${\displaystyle 2^{d}}$يمكن دمج مفاتيح المجموعة الأولى من المفاتيح مع${\displaystyle 2^{d}}$(مفاتيح من المجموعة الثانية من المفاتيح). وهذا يعني مجموعة ثنائية من الحجم${\displaystyle 2^{2d}}$يمكن إنشاؤها باستخدام${\displaystyle 2*2^{d}}$حسابات التفاضلات${\displaystyle \Delta _{i}}$و${\displaystyle \nabla _{j}}$زيادة${\displaystyle f}$. لو${\displaystyle \Delta _{i}\neq \nabla _{j}}$ل${\displaystyle i+j>0}$ثم جميع المفاتيح${\displaystyle K[i,j]}$سيكون الأمر مختلفًا أيضًا في المجموعة الثنائية.

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

يصف بوغدانوف وخوفراتوفيتش وريشبيرغر أيضًا طريقة أخرى لإنشاء biclique، تسمى "التشابك بين المسارات التفاضلية ذات المفاتيح ذات الصلة" في المقالة: "تحليل التشفير Biclique لـ AES الكامل ^{[ 2 ]} ".

يتم تقسيم مساحة المفاتيح إلى${\displaystyle 2^{112}}$مجموعات من المفاتيح، حيث تتكون كل مجموعة من${\displaystyle 2^{16}}$المفاتيح. لكل منها${\displaystyle 2^{112}}$المجموعات، مفتاح أساسي فريد${\displaystyle K[0,0]}$يتم اختيار الحساب الأساسي. يحتوي المفتاح الأساسي على بايتين محددين مضبوطين على الصفر، كما هو موضح في الجدول أدناه (والذي يمثل المفتاح بنفس الطريقة التي يمثل بها AES المفتاح في مصفوفة 4x4 لـ AES128):

${\displaystyle {\begin{bmatrix}-&-&-&0\\0&-&-&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

ثم يتم تعداد الـ 14 بايت المتبقية (112 بت) من المفتاح. وهذا ينتج عنه${\displaystyle 2^{112}}$مفاتيح أساسية فريدة؛ مفتاح واحد لكل مجموعة مفاتيح. المفاتيح العادية${\displaystyle 2^{16}}$ثم يتم اختيار المفاتيح في كل مجموعة بناءً على مفتاحها الأساسي. ويتم اختيارها بحيث تكون متطابقة تقريبًا مع المفتاح الأساسي، ولا تختلف عنه إلا في بايتين فقط (إما${\displaystyle i}$'s أو الـ${\displaystyle j}$'s) من البايتات الأربعة الموضحة أدناه:

${\displaystyle {\begin{bmatrix}-&-&i&i\\j&-&j&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

هذا يعطي${\displaystyle 2^{8}K[i,0]}$و${\displaystyle 2^{8}K[0,j]}$، وهو ما يعطي مجتمعاً${\displaystyle 2^{16}}$مفاتيح مختلفة،${\displaystyle K[i,j]}$. هؤلاء${\displaystyle 2^{16}}$تشكل المفاتيح المفاتيح الموجودة في المجموعة لمفتاح أساسي معين.

${\displaystyle 2^{112}}$يتم بناء ثنائيات المفاتيح باستخدام تقنية "التفاضلات المستقلة ذات المفاتيح المرتبطة"، كما هو موضح في قسم "كيفية بناء ثنائيات المفاتيح". ويشترط لاستخدام هذه التقنية ألا تشترك مسارات التفاضل الأمامية والخلفية التي يجب دمجها في أي عناصر غير خطية فعالة. كيف يُعرف أن هذا هو الحال؟ نظرًا للطريقة التي يتم بها اختيار المفاتيح في الخطوة 1 بالنسبة للمفتاح الأساسي، فإن مسارات التفاضل${\displaystyle \Delta _{i}}$باستخدام المفاتيح${\displaystyle K[i,0]}$لا تشارك أبدًا أي صناديق S نشطة (وهي المكون غير الخطي الوحيد في AES)، مع المسارات التفاضلية${\displaystyle \nabla _{j}}$باستخدام المفتاح${\displaystyle K[0,j]}$وبالتالي، من الممكن إجراء عملية XOR على المسارات التفاضلية وإنشاء المجموعة الثنائية.

عند إنشاء المجموعات الثنائية، يمكن البدء تقريبًا في هجوم الوسيط. قبل تنفيذ هجوم الوسيط،${\displaystyle 2^{d}}$القيم الوسيطة من النص الأصلي: ${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$، ال${\displaystyle 2^{d}}$القيم الوسيطة من النص المشفر: ${\displaystyle {\xleftarrow[{v_{j}}]{}}{\xleftarrow[{}]{K[0,j]}}S_{j}}$والحالات الوسيطة والمفاتيح الفرعية المقابلة.${\displaystyle K[i,0]}$أو${\displaystyle K[0,j]}$ومع ذلك، يتم حسابها مسبقًا وتخزينها.

الآن يمكن تنفيذ هجوم الوسيط. لاختبار مفتاح${\displaystyle K[i,j]}$، من الضروري فقط إعادة حساب أجزاء الشفرة، وهو أمر معروف أنه سيختلف بين${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$و${\displaystyle P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}}$. للحساب العكسي من${\displaystyle S_{j}}$ل${\displaystyle {\xleftarrow[{v_{j}}]{}}}$هذا يعني وجود 4 صناديق استبدال (S-boxes) تحتاج إلى إعادة حساب. بالنسبة للحساب الأمامي من${\displaystyle P_{i}}$ل${\displaystyle {\xrightarrow[{v_{i}}]{}}}$، إنها مجرد 3 (يمكن العثور على شرح مفصل لمقدار إعادة الحساب المطلوبة في ورقة "Biclique Cryptanalysis of the full AES ^{[ 2 ]} "، حيث تم أخذ هذا المثال منها).

عندما تتطابق القيم الوسيطة، يصبح المرشح مفتاحًا رئيسيًا${\displaystyle K[i,j]}$بين${\displaystyle P_{i}}$و${\displaystyle S_{j}}$يتم العثور على المفتاح المرشح. ثم يتم اختباره على زوج آخر من النص العادي/المشفر.

يقلل هذا الهجوم من التعقيد الحسابي لخوارزمية AES128 إلى${\displaystyle 2^{126.18}}$وهو أسرع من أسلوب القوة الغاشمة بمقدار 3 إلى 5 مرات. أما تعقيد البيانات في الهجوم فهو${\displaystyle 2^{88}}$وتعقيد الذاكرة هو${\displaystyle 2^{8}}$.