هجوم الارتباط

أحد الأمثلة على ذلك هو مولد جيف، الذي يتكون من ثلاثة مسجلات إزاحة خطية ذات تغذية راجعة (LFSRs): LFSR-1 وLFSR-2 وLFSR-3. لنرمز لهذه المسجلات بالرموز التالية:${\displaystyle x_{1}}$،${\displaystyle x_{2}}$، و${\displaystyle x_{3}}$على التوالي. ثم، تُعطى الدالة المنطقية التي تجمع السجلات الثلاثة لتوفير خرج المولد بواسطة${\displaystyle F(x_{1},x_{2},x_{3})=(x_{1}\wedge x_{2})\oplus (\neg x_{1}\wedge x_{3})}$(أي (${\displaystyle x_{1}}$و${\displaystyle x_{2}}$XOR (ليس)${\displaystyle x_{1}}$و${\displaystyle x_{3}}$)). هناك 2 ³ = 8 قيم ممكنة لمخرجات السجلات الثلاثة، وقيمة دالة الدمج هذه لكل منها موضحة في الجدول أدناه:

جدول مخرجات الدالة المنطقية

${\displaystyle x_{1}}$	${\displaystyle x_{2}}$	${\displaystyle x_{3}}$	${\displaystyle F(x_{1},x_{2},x_{3})}$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

لننظر إلى مخرجات السجل الثالث،${\displaystyle x_{3}}$يوضح الجدول أعلاه أن من بين 8 مخرجات محتملة لـ${\displaystyle x_{3}}$، 6 تساوي القيمة المقابلة لمخرج المولد،${\displaystyle F(x_{1},x_{2},x_{3})}$في 75% من جميع الحالات الممكنة،${\displaystyle x_{3}=F(x_{1},x_{2},x_{3})}$وبالتالي، فإنّ LFSR-3 "مرتبط" بالمولد. وهذا يُعدّ نقطة ضعف يُمكن استغلالها على النحو التالي:

يمكن إجراء اعتراض على النص المشفر${\displaystyle c_{1},c_{2},c_{3},\ldots ,c_{n}}$نص عادي${\displaystyle p_{1},p_{2},p_{3},\ldots }$والتي تم تشفيرها بواسطة تشفير تدفقي باستخدام مولد جيف كمولد لتدفق المفاتيح، أي${\displaystyle c_{i}=p_{i}\oplus F(x_{1i},x_{2i},x_{3i})}$ل${\displaystyle i=1,2,3,\ldots ,n}$، أين${\displaystyle x_{1i}}$هو ناتج LFSR-1 في الوقت${\displaystyle i}$إلخ. من الممكن أيضًا أن يكون جزء من النص العادي، على سبيل المثال${\displaystyle p_{1},p_{2},p_{3},\ldots ,p_{32}}$، أول 32 بت من النص الأصلي (المقابلة لأربعة أحرف ASCII). وهذا ليس مستبعدًا تمامًا بالنظر إلى أن النص الأصلي هو ملف XML صالح، على سبيل المثال، يجب أن تكون الأحرف الأربعة الأولى من ASCII هي "<xml". وبالمثل، فإن العديد من تنسيقات الملفات أو بروتوكولات الشبكة لها رؤوس أو تذييلات قياسية للغاية. بالنظر إلى ما تم اعتراضه${\displaystyle c_{1},c_{2},c_{3},\ldots ,c_{32}}$ومعروف لدينا/متوقع${\displaystyle p_{1},p_{2},p_{3},\ldots ,p_{32}}$قد نجد بسهولة${\displaystyle F(x_{1i},x_{2i},x_{3i})}$ل${\displaystyle i=1,2,3,\ldots ,32}$عن طريق إجراء عملية XOR بينهما. هذا يجعل تحديد البتات الـ 32 المتتالية لمخرج المولد أمراً سهلاً.

يُمكّن هذا من إجراء بحث شامل في فضاء المفاتيح المحتملة (القيم الأولية) لـ LFSR-3 (بافتراض معرفتنا للبتات المُستخرجة من LFSR-3، وهو افتراض يتوافق مع مبدأ كيركوفس ). لأي مفتاح مُعطى في فضاء المفاتيح، يُمكننا توليد أول 32 بت من مُخرجات LFSR-3 بسرعة ومقارنتها بـ 32 بت التي استعدناها من مُخرجات المُولّد بالكامل. ولأننا أثبتنا سابقًا وجود ارتباط بنسبة 75% بين مُخرجات LFSR-3 والمُولّد، فإننا نعلم أننا خمنّا المفتاح بشكل صحيح لـ LFSR-3 إذا تطابقت 24 بت تقريبًا من أول 32 بت من مُخرجات LFSR-3 مع البتات المُقابلة لها من مُخرجات المُولّد. أما إذا كان تخميننا خاطئًا، فمن المُتوقع أن تتطابق نصف البتات تقريبًا، أي 16 بتًا، من أول 32 بت من هاتين السلسلتين. وبالتالي، يمكننا استعادة مفتاح LFSR-3 بشكل مستقل عن مفتاحي LFSR-1 وLFSR-2. في هذه المرحلة، نكون قد اختزلنا مشكلة البحث الشامل في نظام مكون من 3 LFSRs إلى مشكلة البحث الشامل في LFSR واحد، ثم في نظام مكون من 2 LFSRs. يعتمد مقدار الجهد المُوفَّر هنا على طول LFSRs. بالنسبة للقيم الواقعية، يُعد هذا توفيرًا كبيرًا جدًا، مما يجعل هجمات البحث الشامل عملية للغاية.

لاحظ في الجدول أعلاه أن${\displaystyle x_{2}}$كما يتوافق مع خرج المولد 6 مرات من أصل 8، وهو ما يمثل مرة أخرى ارتباطًا بنسبة 75% بين${\displaystyle x_{2}}$ومخرجات المولد. يمكننا بدء هجوم القوة الغاشمة على LFSR-2 بشكل مستقل عن مفاتيح LFSR-1 وLFSR-3، تاركين LFSR-1 فقط سليمًا. وبالتالي، نستطيع كسر مولد Geffe بنفس الجهد المطلوب لاختراق 3 LFSRs مستقلة تمامًا. هذا يعني أن مولد Geffe ضعيف جدًا، ولا ينبغي استخدامه أبدًا لتوليد سلاسل مفاتيح تشفير التدفق.

لاحظ من الجدول أعلاه أن${\displaystyle x_{1}}$يتطابق مع مخرج المولد 4 مرات من أصل 8 - أي بنسبة ارتباط 50%. لا يمكننا استخدام هذا لاختراق LFSR-1 بشكل مستقل عن البقية: فالمفتاح الصحيح سيعطي مخرجًا يتطابق مع مخرج المولد 50% من الوقت، ولكن في المتوسط، سيعطي المفتاح الخاطئ نفس النتيجة. يمثل هذا الوضع الأمثل من منظور أمني - دالة الدمج${\displaystyle F(x_{1},x_{2},x_{3})}$ينبغي اختيار الدالة بحيث يكون الارتباط بين كل متغير ومخرجات الدالة المركبة أقرب ما يمكن إلى 50%. عمليًا، قد يصعب إيجاد دالة تحقق ذلك دون التضحية بمعايير تصميم أخرى، مثل طول الفترة، لذا قد يكون من الضروري التوصل إلى حل وسط.

بينما يوضح المثال أعلاه جيدًا المفاهيم البسيطة نسبيًا وراء هجمات الارتباط، فإنه ربما يُبسّط شرح كيفية تنفيذ هجوم القوة الغاشمة على سجلات الإزاحة الخطية ذات التغذية الراجعة (LFSRs) الفردية. ستُنتج المفاتيح المُخمنة بشكل خاطئ مُخرجات LFSR تتوافق مع مُخرجات المُولّد بنسبة 50% تقريبًا، لأنه عند إعطاء سلسلتين عشوائيتين من البتات بطول مُحدد، فإن احتمال التوافق بين السلسلتين عند أي بت مُعين هو 0.5. مع ذلك، قد تُنتج مفاتيح فردية خاطئة مُحددة مُخرجات LFSR تتوافق مع مُخرجات المُولّد بنسبة تزيد أو تقل عن 50% بالضبط. يبرز هذا الأمر بشكل خاص في حالة سجلات الإزاحة الخطية ذات التغذية الراجعة التي لا يكون ارتباطها بالمُولّد قويًا جدًا؛ فبالنسبة للارتباطات الصغيرة بما يكفي، ليس من المستبعد أن يؤدي مفتاح مُخمن بشكل خاطئ إلى مُخرجات LFSR تتوافق مع عدد البتات المطلوب لمُخرجات المُولّد. وبالتالي، قد لا يكون من الممكن تحديد المفتاح الفريد لهذا السجل. قد يكون من الممكن تحديد عدد من المفاتيح المحتملة، إلا أن ذلك لا يزال يمثل ثغرة أمنية خطيرة في التشفير. علاوة على ذلك، إذا توفر ميغابايت واحد من النص الأصلي المعروف، فسيكون الوضع مختلفًا تمامًا. قد يُنتج مفتاح خاطئ مخرجات سجل الإزاحة ذي التغذية الراجعة الخطية (LFSR) تتوافق مع أكثر من 512 كيلوبايت من مخرجات المولد، ولكنه من غير المرجح أن يُنتج مخرجات تتوافق مع 768 كيلوبايت من مخرجات المولد كما يفعل المفتاح المُخمن بشكل صحيح. وكقاعدة عامة، كلما ضعف الارتباط بين سجل معين ومخرجات المولد، زادت كمية النص الأصلي المعروف المطلوبة للعثور على مفتاح ذلك السجل بدرجة عالية من الثقة. ويمكن حساب تقديرات طول النص الأصلي المعروف المطلوب لارتباط معين باستخدام التوزيع ذي الحدين .

تُعدّ الارتباطات التي استُغلت في الهجوم المذكور على مولد جيف أمثلةً لما يُسمى بالارتباطات من الدرجة الأولى : وهي ارتباطات بين قيمة خرج المولد ومسجل الإزاحة الخطي ذي التغذية الراجعة (LFSR) الفردي. ويمكن تعريف ارتباطات من درجات أعلى بالإضافة إلى هذه. على سبيل المثال، قد يكون من الممكن ألا يكون لدالة منطقية معينة ارتباطات قوية مع أي من المسجلات الفردية التي تجمعها، بينما قد يوجد ارتباط كبير بين دالة منطقية ما لمسجلين من هذه المسجلات، على سبيل المثال،${\displaystyle x_{1}\oplus x_{2}}$هذا مثال على ارتباط من الدرجة الثانية. ويمكن تعريف الارتباطات من الدرجة الثالثة وما فوقها بهذه الطريقة.

قد تكون هجمات الارتباط من الرتب العليا أكثر فعالية من هجمات الارتباط من الرتب الدنيا، إلا أن هذا التأثير يخضع لقانون "العائد المحدود". يوضح الجدول أدناه مقياسًا للتكلفة الحسابية لهجمات مختلفة على مولد دفق المفاتيح، والذي يتكون من ثمانية مسجلات إزاحة خطية خطية (LFSRs) ذات 8 بتات، مُدمجة بواسطة دالة منطقية واحدة. يُعد فهم حساب التكلفة أمرًا بسيطًا نسبيًا: يُمثل الحد الأيسر من المجموع حجم فضاء المفاتيح للمولدات المرتبطة، بينما يُمثل الحد الأيمن حجم فضاء المفاتيح للمولدات المتبقية.

جهد هجوم المولد

هجوم	الجهد (حجم مساحة المفاتيح)
القوة الغاشمة	${\displaystyle 2^{8\times 8}=18446744073709551616}$
هجوم الارتباط من الدرجة الأولى الفردي	${\displaystyle 2^{8}+2^{7\times 8}=72057594037928192}$
هجوم الارتباط من الدرجة الثانية الفردي	${\displaystyle 2^{2\times 8}+2^{6\times 8}=281474976776192}$
هجوم الارتباط من الدرجة الثالثة الفردي	${\displaystyle 2^{3\times 8}+2^{5\times 8}=1099528404992}$
هجوم الارتباط من الدرجة الرابعة الفردية	${\displaystyle 2^{4\times 8}+2^{4\times 8}=8589934592}$
هجوم الارتباط الفردي من الدرجة الخامسة	${\displaystyle 2^{5\times 8}+2^{3\times 8}=1099528404992}$
هجوم الارتباط من الدرجة السادسة	${\displaystyle 2^{6\times 8}+2^{2\times 8}=281474976776192}$
هجوم الارتباط الفردي من الدرجة السابعة	${\displaystyle 2^{7\times 8}+2^{8}=72057594037928192}$

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

دالة منطقية${\displaystyle F(x_{1},\ldots ,x_{n})}$يُقال إن دالة منطقية تتكون من n متغيرًا تتمتع بـ " مناعة ضد الارتباط من الرتبة m "، أو " مناعة ضد الارتباط من الرتبة m " لعدد صحيح m ، إذا لم يكن هناك ارتباط ذو دلالة إحصائية بين مخرجات الدالة وأي دالة منطقية أخرى تتكون من m من مدخلاتها. على سبيل المثال، الدالة المنطقية التي لا تحتوي على ارتباطات من الرتبة الأولى أو الثانية، ولكنها تحتوي على ارتباط من الرتبة الثالثة، تتمتع بمناعة ضد الارتباط من الرتبة الثانية. من الواضح أن ارتفاع مستوى المناعة ضد الارتباط يجعل الدالة أكثر ملاءمة للاستخدام في مولدات تدفق المفاتيح (مع أن هذا ليس العامل الوحيد الذي يجب مراعاته).

أظهر سيغينثالر أن مناعة الارتباط m لدالة منطقية من الدرجة الجبرية d ذات n متغيرًا تحقق${\displaystyle m+d\leq n}$بالنسبة لمجموعة معينة من متغيرات الإدخال، يعني هذا أن الدرجة الجبرية العالية ستحد من أقصى قدر ممكن من مناعة الارتباط. علاوة على ذلك، إذا كانت الدالة متوازنة، فإن${\displaystyle m\leq n-1}$[ ^{1 ]​}

يستنتج من ذلك أنه من المستحيل أن تكون دالة ذات n متغيرًا محصنة ضد الارتباط من الرتبة n . ويستنتج هذا أيضًا من حقيقة أنه يمكن كتابة أي دالة من هذا القبيل باستخدام أساس ريد-مولر كمزيج من عمليات XOR لدوال الإدخال.