الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.
قیمت
قیمت این مقاله: 48000 تومان
(ایران ترجمه - Irantarjomeh)
توضیح
بخش زیادی از این مقاله بصورت رایگان ذیلا قابل مطالعه می باشد.
Indian Institute of Science Education and Research, Pune, India
کشور
هندوستان
یک حمله حدس و تعیین جدید بر روی رمز دنباله ایA5/1
چکیده
در اروپا و آمریکای شمالی، A5/1 بعنوان گسترده ترین رمز دنباله ای استفاده شده جهت تضمین فرآیند محرمانگی و حفظ حریم خصوصی در مکالمات تلفن های سیار GSM می باشد. در این مقاله، ما نسبت به ارائه یک حمله جدید بر روی رمز دنباله ای A5/1، با میانگین پیچیدگی زمانی ۲۴۸٫۵، اقدام می نمائیم که بسیار کمتر از حمله کورکورانه با پیچیدگی ۲۶۴ می باشد. این حمله از موفقیت ۱۰۰% برخوردار می باشد و نیازمند حدوداً ۶۵/۵ گیگابایت فضای ذخیره سازی است. در این راستا ما توصیف تفصیلی حمله جدید خود، همراه با فرآیند اجرا و نتایج آن، را مورد بررسی قرار می دهیم.
کلمات کلیدی: A5/1، GSM، حمله حدس و تعیین، رمزهای دنباله ای
حمله حدس و تعیین رمز دنباله ای A5/1
۱- مقدمه
گسترده ترین رمز دنباله ای استفاده شده جهت تضمین حریم خصوصی و محرمانگی به هنگام تبادل اطلاعات یا مکالمه در تلفن های سیار GSM در اروپا و شمال آمریکا A5/1 می باشد. سیستم رمزنگاری A5/1 در سال ۱۹۸۷ ایجاد گردیده اما در آن زمان GSM برای استفاده در خارج از اروپا مدنظر نبوده است. ویژگیهای A5/1 در ابتدا به ساکن مخفی بوده، اما طراحی آن در سال ۱۹۹۹ از طریق مهندسی معکوس برملا شد [۶]. متعاقباً GSM (سیستم جهانی ارتباطات سیار) صحت این الگوریتم را تایید کرد [۵].
نگارش های متعددی در زمینه الگوریتم رمزنگاری یا مخفی سازی اطلاعات وجود دارند که متعلق به خانواده A5 می باشند: A5/0 به عنوان یک رمز مصنوعی بدون پنهان سازی به شمار می آید، A5/1 نیز به عنوان مبدا الگوریتم A5 محسوب می شود که از فرآیند برقراری ارتباط هوایی مطلوب با قابلیت حفظ حریم خصوصی و محرمانگی مکالمات در تلفن های سیار GSM بهره مند می باشد. A5/2 به صورت عامدانه به عنوان یک الگوریم رمزنگاری ضعیف تر صادراتی ساخته شده است. در حالی که A5/3 یک الگوریتم قدرتمند به رمز درآوری اطلاعات است که به عنوان بخشی از پروژه مشارکت نسل سوم (۳GPP) عرضه شده است و هم اکنون مسئول حفظ و توسعه مشخصه های فنی GSM در گوشه و کنار دنیا می باشد [۱۲].
Anderson [1]، Golic [11] و Babbage [2] به عنوان افراد پیشرو در زمینه کشف رمز الگوریتم مخفی سازی یا به رمزنگاری A5/1 می باشند آن هم به هنگامی که تنها یک چارچوب حداقلی از سیستم A5/1 به دنیای بیرون نشت کرده بود. پس از مهندسی معکوس A5/1، این سیستم به وسیله Biryukov، Shamir و Wagner [5]، Biham و Dunkelman [4]، Ekdahl و Johansson [8]، Maximov، Johansson و Babbage [15]، Barkan و Biham [3]، Keller و Seitz [13]، و چندین محقق دیگر مورد آنالیز قرار گرفت.
حمله حدس و تعیین رمز دنباله ای A5/1
۱-۱٫ تحقیقات جاری
در خلال ۲۰ سال گذشته حملات متعددی بر روی رمز دنباله ای A5/1 طراحی شده، اما تنها تعداد اندکی از آنها به مرحله پیاده سازی رسیده اند. حملات بر روی پروتکل GSM، حتی در صورتی که شبکه تنها قابلیت پشتیبانی از فرآیند رمزنگاری A5/1 یا A5/3 را داشته باشد، و تا زمانی که تلفن موبایل از سیستم رمزنگاری A5/2 پشتیبانی نماید، قابل اعمال خواهد بود. نقص اصلی این سیستم که اجازه پیاده سازی و اجرای چنین حملاتی را می دهد کاربرد کلید مشابهی، بدون توجه به استفاده از نوع الگوریتم کدگذاری A5/1، A5/2 یا A5/3، می باشد. بنابراین، فرد مهاجم قابلیت نصب حمله ای تحت عنوان «مردی در میان» (man-in-the-middle) را خواهد داشت که در آن فرد مهاجم اقدام به جعل هویت «موبایل به شبکه» و یا «شبکه به موبایل» (با استفاده از یک ایستگاه پایه جعلی) می نماید. فرد مهاجم می بایست برای برقراری ارتباط با شبکه از A5/1 استفاده نماید و از A5/2 نیز برای برقراری ارتباط با موبایل بهره جوید. اما بواسطه وجود نقیصه، هردوی الگوریتم ها با استفاده از کلید یکسانی رمزنگاری می شوند. فرد مهاجم قابلیت حاصل آوردن این کلید از طریق یک حمله انفعالی بر روی A5/2 را خواهد داشت. فرد مهاجم که هم اکنون در وسط سیستم قرار دارد قابلیت استراق سمع، تغییر مکالمه، انجام سرقت تلفنی و موارد دیگر را خواهد داشت. چنین حمله ای برای کل ترافیک شبکه شامل خدمات پیام کوتاه (SMS) نیز صادق خواهد بود [۳].
۱ـ۲٫ تعاملات ما در این زمینه
در این مقاله ما یک حمله حدس و تعیین جدید بر روی سیستم رمزنگاری دنباله ای A5/1 را تشریح می نمائیم. این حمله دارای میانگین پیچیدگی زمانی ۲۴۸٫۵ می باشد که بسیار کمتر از میانگین حمله کوکورانه به میزان ۲۶۴ خواهد بود. برای هر ۱۹ بیت محتمل رجیستر R1، ما نیازمند فضای ذخیره سازی ۱۰۰ مگابایتی جهت تعیین رجیسترهای R2 و R3 با توجه به استریم کلیدی شناخته شده KS می باشیم. این حمله را می توان به صورت مختصر به شرح ذیل توصیف نمود: ما در نظر می گیریم هر رجیستر R1 به هنگام بروز حمله به صورت کامل با ۱۹ بیت R2 و R3 به صورت پیوسته پر می شود. در هر مرحله این حمله، R1 به طور کامل پر گردیده و R2 و R3 به صورت نسبی پر می شوند. ما این وضعیت را به عنوان شرایط حالت می خوانیم. به هنگامی که کلیه رجیسترها کاملا پر گردیدند، ما آن کاندید حالت را یک کاندید حالت کامل خواهیم نامید. این حمله دارای نرخ موفقیت ۱۰۰% بوده و نیازمند فضای ذخیره سازی حدوداً ۶۵/۵ گیگا بایت می باشد. با توجه به این مورد تنها ۱۱ بیت استریم کلیدی شناخته شده اند، الگوریتم حمله را همچنین می توان به عنوان مجموعه ای از کاندیدهای حالت کامل ۶۴ بیتی در نظر گرفت که می توانند حاوی کلید باشند. با توجه به هر یک از موارد بیشتر این زمانبندی ساعت در حول چنین حمله ای، تعداد کاندیدهای حالت کامل افزایش می یابد. بنابراین، احتمال یافتن کلید در بین کلیه کاندیدهای حالت کامل با داشتن هر دور اضافه پس از ۱۱ دور زمانبندی ساعت افزایش خواهد یافت. ما تشریح کاملی را از حمله جدید خود، همراه با پیاده سازی و نتایج آن را در بخش های ۴ ، ۵ و ۶ ارائه خواهیم نمود.
حمله حدس و تعیین رمز دنباله ای A5/1
۲- تشریح رمزهای دنباله ای A5/1
رمز دنباله ای A5/1 از سه رجیستر تغییر مکان بازخوردی خطی کوتاه (LFSRs) با طول های ۱۹، ۲۲ و ۲۳ بیت ایجاد شده است که به وسیله R1، R2 و R3 به ترتیب نشان داده شده است. سمت راست ترین بیت در هر رجیستر تحت عنوان بیت صفر شناخته می شود. بیت های وسطی R1 در موقعیت های بیت ۱۳، ۱۶ ، ۱۷ و ۱۸ قرار دارند. بر همین منوال بیتهای R2 نیز در موقعیت های ۲۰ و ۲۱ و بیت های R3 در موقعیت های ۷، ۲۰، ۲۱ و ۲۲ هستند (جدول ۱).
حمله حدس و تعیین رمز دنباله ای A5/1
۳- حملات شناخته شده بر روی A5/1
ما در اینجا حملات حدس و تعیین مشخص در A5/1 را مورد بحث قرار می دهیم. یک حمله حدس و تعیین [۱۶] به عنوان حمله متن ساده ای در نظر است که بر روی رمزهای دنباله ای انجام شده و در آن مهاجم برخی از بیتهای چنین رمزی را حدس زده و بقیه بیت ها از بیتهای استریم کلیدی مشخص می گردند. حمله متن یا پیام عادی شناخته شده به عنوان مدل حمله ای به شمار می آید که در آن مهاجم دارای دسترسی به هر دوی پیام های عادی و پیام های به رمز درآمده می باشد. چنین موردی را می توان جهت مشخص سازی رمز کلید استفاده شده برای به رمز درآوری متن عادی در متن دارای رمز به کار گرفت. این موارد شامل حمله Anderson [1] ، حمله Golic، [۱۱]، حمله Biham-Dunkelman [4]، حمله Keller-Seitz [۱۳] و حمله Gendrullis-Novotny-Rupp (که همچنین تحت عنوان حمله اصلاح شده نیز شناخته می شود) [۱۰] می باشند. کلیه این حملات به نظر دارای ۶۴ بیت استریم کلیدی (KS) شناخته شده می باشند.
۳ـ۱٫ حملات حدس و تعیین
اولین حمله حدس و تعیین بر روی A5/1 به وسیله Anderson پیشنهاد شد [۱]. وی این موضوع را ارائه نمود که قابلیت پیش بینی کلیه بیت های رجیسترهای R1 و R2 و بخش پایینی رجیستر R3 (یعنی بیت های۱۹+۲۲+۱۱=۵۲ )، جهت تعیین بیتهای باقیمانده R3 به وسیله معادله ۱ را خواهد داشت. در بدترین حالت، هر کاندید حالت قطعی ۲۵۲ را می بایست در برابر استریم کلیدی شناخته شده مورد تصدیق قرار داد. این حمله به عنوان یک حمله Biham-Dunkelman اعمال نمی گردد و به علاوه حمله Keller-Seitz دارای پیچیدگی کمتری می باشد.
Golic حمله ای را ارائه نمود که از پیچیدگی مجموعه معادله خطی ۲۴۰ برخوردار می باشد [۱۱]. وی فرآیند حدس زدن نیمه پایینی کلیه سه رجیستر و مشخص سازی بیتهای باقیمانده رجیسترها با استریم کلیدی شناخته شده به وسیله معادله ۱ را ارائه نمود. با این وجود، هر عملیات در این حمله دارای پیچیدگی بیشتری خواهد بود چرا که بر مبنای راه حلهای سیستم معادلات خطی می باشد. در عمل، این الگوریتم بهتر از رویکرد آندرسون [۱] یا رویکرد Keller-Seitz [۱۳] نمی باشد. در ارتباط با حاصل آوردن راه حل سیستم معادلات، ما به طور اضافه نیازمند حل ۴۴ معادله خطی به وسیله روش حذف گاوسی می باشیم. چنین موردی سبب خواهد شد تا رویکرد Golic قابلیت اجرایی خود را از دست دهد.
حمله حدس و تعیین رمز دنباله ای A5/1
۴- یک حمله جدید بر روی A5/1
رویکرد ما بر مبنای حمله حدس و قطعیت به وسیله Anderson [1] ارائه شده است، اما این رویکرد دارای اصلاحات متعددی می باشد. با استفاده از ۶۴ بایت استریم کلیدی (KS)، کلیه بیت های رجیستر R1 حدس زده شده (مشخص گردیده) و کلیه بیت های رجیسترهای R2 و R3 نیز به طور قطعی تعیین می گردند. اما برخلاف رویکردهای Anderson [1]، Golic [11]، Biham-Dunkelman [4] و Keller-Seitz [13]، ما کلیه موارد محتمل را در نظر می گیریم یعنی آنکه هیچ موردی رد نمی شود. در انتها، ما دارای ۲۴۸٫۵ حالت کاندید محتمل هستیم که بسیار کمتر از جستجوی بیهوده می باشد که در آن از ۲۶۴ کاندید حالت برخوردار بوده ایم. بنابراین، این حمله بهتر از رویکرد جستجوی جامع است.
این حمله حاوی دو رویکرد می باشد، فاز تعیین و فاز پسا-پردازش. فاز تعیین مجدداً به دو فاز پردازش ـ فاز ۱ و پردازش فاز ۲ تقسیم می شود.
۴ـ۱٫ فاز تعیین
فاز تعیین قابلیت تولید کلیه کاندیدهای حالت محتمل، پس از آنکه فاز گرم شدن تکمیل شد، را خواهد داشت [۶]. حال اجازه دهید تا t2 و t3 معرف تعداد زمان هایی باشند که رجیسترهای R2 و R3 به ترتیب زمان سنجی می شوند. هر بار که یک رجیستر زمان سنجی می گردد، افزایش شمارنده برای آن رجیستر به میزان ۱ واحد رخ خواهد داد. با شروع این الگوریتم با مشخص نمودن ورودی بیتهای جریان کلید شناخته شده (KS) و حدس کلیه بیتهای کوچکترین رجیستر R1 مورد دنبال می گردد (شکل ۲).
پردازش ـ فاز ۱٫ محاسبه معنی دارترین یا پراهمیت ترین بیت های (MSBs) رجیستر R2 و رجیستر R3 با استفاده ای از MSB رجیستر R1 و KS از طریق معادله ۱٫ در صورتی که مقادیر سه مورد از این بیت ها شناخته شده باشند، مورد چهارمی را می توان به راحتی به وسیله معادله فوق محاسبه کرد. در صورتی که R2 [21] و R3 [22] ناشناخته باشند، متعاقباً چهار ترکیب محتمل برای بیت های ناشناخته موجود خواهند بود، یعنی ۰۰، ۰۱، ۱۰ و ۱۱٫ اما معادله فوق سبب تقلیل تعداد احتمالات به دو مورد می شود. دو ترکیب محتمل که قابلیت ارضای این معادله را دارند عبارتند از :
۴ـ۲٫ فاز پسا- پردازش
فاز پسا پردازش کنترل کننده کلید مربوطه از مجموعه ای از کاندیدهای حالت کامل حاصل آمده پس از فاز تشخیص می باشد. همانگونه که در بخش ۴ـ۱ بحث شد، تعداد حداقلی دورهای مورد نیاز جهت اعمال فاز پسا پردازش ۱۱ مورد می باشد. تعداد کاندیدهای حالت کامل با هر دور اضافه افزایش خواهد یافت. بنابراین، احتمال یافتن کلید با هر دور اضافه بیشتر خواهد شد.
در این فاز ما اقدام به تولید بیتهای خروجی از طریق اعمال کدگذاری نرمال A5/1 با کاندیدهای حالت کامل حاصل آمده از فاز تشخیص نمودیم. متعاقباً اقدام به تطبیق این بیتهای خروجی با بیتهای KS شناخته شده نمودیم. در صورتی که این بیتهای KS و بیتهای خروجی تطابق داشته باشند، فرآیند زمان سنجی و ایجاد بیتهای خروجی تا زمان مشخص سازی یک تطابق مرتبط با رفتار بیتی به صورت متناقض ادامه خواهد یافت. در صورتی که کلیه بیتهای خروجی در تطابق با ۶۴ بیت KS مشخص شده باشند، کاندید حالت کامل همانا کلید مشخص شده می باشد. بر این مبنا، ما قابلیت یافتن کلید در بین کلیه کاندیدهای حالت کامل را خواهیم داشت.
حمله حدس و تعیین رمز دنباله ای A5/1
۵- آنالیز حمله
ما هم اکنون هر فاز حمله را مرحله به مرحله مورد بحث قرار می دهیم. پس از آغاز، ما اولین مرحله رویه پیاده سازی یعنی فاز تشخیص را اجرا می نماییم. کاندید حالت دارای کلیه بیتهای رجیستر R1 و رجیسترهای خالی R2 و R3 می باشد. برحسب این پروتکل، فاز تشخیص مشخص کننده با اهمیت ترین بیتها (MSBs) مرتبط با رجیسترهای R2 و R3 در پردازش فاز ۱ می باشد. بیتهای زمان سنجی R2 و R3 (یعنی R2[10] و R3[10])، بیت R3[7] و در صورت ممکن بیتهای R2[20] و R3[21] نیز به وسیله پردازش فاز ۲ به کار گرفته می شوند.
هم اکنون ما اقدام به آنالیز مرحله اول فاز تشخیص یعنی پردازش فاز ۱ می نماییم. در صورت خالی بودن، MSBs رجیسترهای R2 و R3 را می بایست مشخص ساخت. تعداد ترکیبهای محتمل از چهار به دو مورد بر مبنای معادله ۱ کاهش می یابد. بنابراین قابلیت صرفه جویی دو ترکیب یعنی به میزان ۵۰% را خواهیم داشت. در طی پیاده سازی دورهای متعاقب، نوعی احتمال وجود دارد که در آن تنها یکی از MSBهای مرتبط با رجیسترهای R2 یا R3 به صورت خالی باشد. ما این بیتهای خالی را به وسیله معادله ۱ مشخص می سازیم.
حمله حدس و تعیین رمز دنباله ای A5/1
۶- مباحث
ما به تفصیل یک رویکرد احتمالی در خصوص تعیین پیچیدگی زمانی، ضروریات مربوط به ذخیره سازی و احتمال موفقیت حمله جدید خود را مورد بررسی قرار می دهیم. نتایج این رویکرد احتمالی همچنین دارای تعامل با داده های تجربی می باشد. بر مبنای این نتایج، تعداد میانگین دورهای مورد نیاز جهت حاصل آوردن کلید برابر با ۵/۱۵ می باشد و تعداد میانگین کاندیدهای حالت کامل که پس از ۵/۱۵ دور به دست می آید برابر با ۲۴۸٫۵ است.
ما این بخش را در ارتباط با مقایسه نتایج پیاده سازی حمله خود با رویه های حملات حدس و تعیین قبلی مورد بررسی قرار می دهیم.
۶ـ۱٫ پیچیدگی زمانی
هم اکنون که ما پیچیدگی دقیق زمان الگوریتم حمله خود را به خوبی شناخته ایم می توانیم مشخص سازیم که بر مبنای این الگوریتم چنین تحقیقی را می توان در طی موارد ذیل اعمال داشت:
کنترل جهت مشاهده آنکه آیا یک سلول در یک رجیستر به صورت خالی می باشد یا پر است.
تکثیر کاندیدهای حالت
پرکردن بیتهای خالی
بنابراین منطقی می باشدکه فرض کنیم که کنترل و پرکردن بیتها خود مقدار قابل توجهی زمان را طلب می نماید. بنابراین، ما می توانیم به طور ایمن در نظر بگیریم که واحد برآورد پیچدگی زمان ما می بایست به صورت تعداد تکرارهای مورد نیاز در نظر گرفته شود، که در آن یک واحد زمانی به عنوان یک تکرار محسوب می شود. این الگوریتم کار خود را با رجیسترهای R2 و R3 خالی و رجیستر R1 پر شده (حدسی) آغاز می نماید. در انتها، این الگوریتم قابلیت ایجاد ۲۴۸٫۵ کاندید حالت کامل ، یعنی برابر با ۲۴۸٫۵ تکرار را خواهد داشت.
۶ـ۲٫ ضروریات ذخیره سازی و احتمال موفقیت
همانگونه که در بخش ۴ـ۱ تشریح شد، تعداد حداقلی بیت های KS مورد نیاز جهت ایجاد مجموعه ای از کاندیدهای حالت کامل (با پر شدگی کلیه بیتها) برابر با ۱۱ می باشد. با هر دور اضافه زمانبندی، تعداد کاندیدهای حالت کامل افزایش می یابد. ما می توانیم فاز پسا پردازشی حمله را پس از ۱۱ دور به طور همزمان با فاز تعیین حمله آغاز نمائیم. بنابراین، احتمال یافتن کلید نیز در هر دور افزایش می یابد. اما ما حداقل به ۶۴ KS بیت برای فاز پسا پردازش حمله جهت کنترل کلید نیاز خواهیم داشت.
حمله حدس و تعیین رمز دنباله ای A5/1
۷- نتیجه گیری
حمله ما بر مبنای رویکرد حدس و تعیین ارائه شده به وسیله Anderson [1] می باشد، اما در عین حال چندین مورد اصلاح شده و تغییر یافته در این ارتباط مدنظر خواهد بود. در این حمله، کلیه بیتهای اولین رجیستر R1 به نظر شناخته شده بوده و کلیه بیتهای رجیسترهای R2 و R3 با ۶۴ بیت کلید دنباله ای شناخته شده (KS) مشخص می گردند.
این حمله دارای میانگین پیچیدگی زمانی ۲۴۸٫۵ می باشد، که بسیار کوچکتر از جستجوی گسترده و جامع است. میانگین تعداد دورهای مورد نیاز جهت حاصل آوردن کلید صحیح از مجموعه کاندیدهای حالت کامل برابر با ۵/۱۵ می باشد. با توجه به هر دور زمانبندی پس از ۱۱ دور، تعداد کاندیدهای حالت کامل افزایش خواهد یافت. بنابراین، احتمال یافتن کلید در هر دور زمانبندی بیشتر خواهد شد. بر این مبنا قابلیت انجام فاز پسا پردازشی برای یک دور به صورت همزمان با دور تعیین برای دور بعدی نیز وجود دارد و بنابراین می توان زمان قابل توجهی را صرفه جویی نمود. این حمله از احتمال موفقیت ۱۰۰% برخوردار می باشد و نیازمند حدوداً ۶۵/۵ گیگابایت فضای ذخیره سازی اطلاعات است. بر این مبنا ما به این نتیجه گیری می رسیم که حمله ما بهتر از کلیه حملات شناخته شده حدس و تعیین بر روی سیستم های رمزهای دنباله ای A5/1 می باشد.
لطفا به جای کپی مقالات با خرید آنها به قیمتی بسیار متناسب مشخص شده ما را در ارانه هر چه بیشتر مقالات و مضامین ترجمه شده علمی و بهبود محتویات سایت ایران ترجمه یاری دهید.
