سه شنبه 2 آبان 1396 | Tuesday 24 th of October 2017 صفحه اصلی گروه الکترونیکی کامپیوتر
5-2-8-5 حمله همبستگی Ekdahlو Johnsson به A5/1 در سال 2003

در سال 2003 ،Ekdahlوjohnssonحمله همبستگی با تکیه بر خطی بودن فرایند اولیه سازی معرفی کردند  . در این حمله 20000 تا50000 فریم رمز شده با یک کلید جلسه نیاز است . شرح حمله بصورت زیر است:

فرض کنیم در زمان tهستیم و LFSRهای اول تا سوم به ترتیب  مرتبه انتقال یافته اند بنابراین مقدار  برابر با جمع XORسه مقدار از سه LFSRمی شود. هر کدام از این سه بیت خود از برایند خطی کلید kو شماره فریم   بصورت  حاصل شده است.

 یک مقدار معلوم و متفاوت برای هر فریم است وتابعی خطی از کلید با ضرایب معلوم باینری است که بصورت زیر نمایش داده می شود.

(5-23)                                                                 

که در ان به معنی جمع XORارگومانها است . هدف حمله یافتن 19 بیت متوالی خروجیLFSRاول به همراه 22و 23 بیت متوالی از خروجی دو LFSRدیگر است که در مجموع منجر به محاسبه 64 بیت کلید می شود . در صورتی که اطلاعات کلید اجرایی مربوط به mفریم را داشته باشیم ، این اطلاعات بصورت یک ماتریس     به صورت زیرقابل مشاهده است.

ایده اصلی این حمله همبستگی ، میزان اریبی( بایاس) رابطه زیر به ازای مقادیر انتخاب شده  است.در حقیقت مقدار احتمال pمطلوب است .

   (5-24)                                 

با توجه به اینکه در هر لحظه tاز انتقال کلی مولد ، حداقل دو LFSRانتقال می یابد ، پیشامدهای عدم انتقال هر کدام از LFSRها در یک زمان نسبت به هم جدا هستند . فرض کنیم tبین 101 تا 328 باشد انگاه می توان نشان داد که احتمال وجود  انتقال به ترتیب برای سه LFSRاز رابطه زیر بدست می اید.

      (5-25)

در صورتی که مقادیر انتخابی صحیح باشد ( با احتمال q) ، مقدار احتمال pبرابر بایک است و در غیر اینصورت ، با توجه به تصادفی بودن رابطه5-24 یعنی مقدار p، برابر است با :

                                                          (5-26)

رابطه (5-26) نشان می دهد که مقدار احتمال p  به اندازه 1/2qاریبی دارد که در حمله همبستگی مورد استفاده قرار می گیرد میدانیم مقادیر  و در هر لحظه  و به ازای هر فریم مشخص است ، به این ترتیب اگر مقدار را بنامیم ، احتمال یافتن از روی با نظر به رابطه5-24برابر با pاست. حال مشخصه  را تعریف می کنیم.

(5-27)

احتمال نهایی ptمقداری بزرگتر از ½است و بسته به تعداد فریم ها (m) تعیین می شود. در نمونه های قبل نتایج شبیه سازی حمله همبستگی به A5/1در حالات مختلف نمونه برداری از کلید اجرایی ذکر شده است .

لازم به ذکر است اینکه پیاده سازی حمله بر روی پردازش گر پنتیوم4 با سرعت 1.8 گیگا هرتز و مجهز به 512 مگابایت حافظه RAMانجام شده است.

از خصوصیات بارز این حمله تناسب خطی(ونه نمایی) پیچیدگی پردازش حمله نسبت به طول LFSRها و در عین حال عدم نیاز به حافظه زیاد است.

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26