مقاله تحلیل خطی و تفاضلی S - Box الگوریتم AES و استخراج ضعیفترین مشخصه های تفاضلی و خطی

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

تحليل خطي و تفاضلي S-Box الگوريتم AES و استخراج ضعيفترين
مشخصه هاي تفاضلي و خطي

چکيده
در اين مقاله ، S-Box١الگوريتم AES٢، تحليل خطي و تفاضلي شده ومشخصه هاي تفاضلي و خطي آن در دو حالت بررسي و تفاضل هاي مناسب جهت حمله مشخص گرديده است .در حالت اول مقادير بردار انتخاب کننده ...(٢٥٥.........١)در خروجي S-Box به ازاي کليه مقادير بردار انتخاب کننده ...(٢٥٥.........١)در نظر گرفته شده است . درحالت دوم بردار انتخاب کننده خروجـي در S-Box،در رابطه ...=(...)S صدق مي کند.
واژگان کليدي
AES،S-Box ، تحليل خطي رمز، تحليل تفاضلي رمز، شاخص خطي، شاخص تفاضلي
١-مقدمه
در طراحـي الگــوريتم هـاي رمزنگــاري دو اصــل اساســي "درهــم پيچيدگي "٣و "انتشار"٤که ارائه آنها به شانون نسبت داده شده اسـت به عنوان فلسفه اساسي در ساختار بخش هاي مختلف الگوريتم به کار مي رود. "انتشار"اولين اصل از اصول شانون است که به تأثير بيتهاي متن رمز شده از متن اصلي و کليد بـر مـي گـردد. در يـک الگـوريتم رمزنگاري با خاصيت انتشار بالا، تغيير هر بيت از کليد يا مـتن اصـلي موجب تغيير بيتهاي زيادي از متن رمز شده مي گردد. به عبارت ديگر هر بيت از متن رمز شده به کليه بيت هاي متن اصلي و کليد وابسـته است . در اين الگوريتم ها با استفاده از ساختار هاي پس و پيش سازي بيت هاي داده ، خاصيت انتشار را در سيستم بالا مي برند[١]. دومـين اصل "درهم پيچيدگي "است که موجب افزايش خواص آماري تصادفي بين متن اصلي و متن رمز شده مي گردد. اين خاصيت باعث متعـادل شدن توزيع بيتهاي داده در لايه هاي مختلـف الگـوريتم مـي شـود و مقاومت الگوريتم را در مقابل حمله هاي آمـاري همچـون تفاضـلي و خطي بالا مي برد. اسـتفاده از جانشـين سـازي در طراحـي الگـوريتم رمزنگاري که در قالب جدول هاي جانشين سـازي بـه کـار مـي رود،
موجب افزايش خاصيت درهم پيچيدگي الگوريتم مي گردد.
براي به دست آوردن خاصيت درهم پيچيدگي بـالا، بهتـرين روش استفاده از S-Box است . اگر در الگوريتمي خاصيت درهم پيچيدگي به خوبي به کار رفته باشد، آن الگـوريتم داراي امنيـت بـالايي اسـت . در حقيقت خاصيت درهم پيچيدگي به تنهايي امنيت يک الگوريتم رمـز قطعه اي را به ميزان زيادي تضمين مي کند. در الگوريتم هايي کـه از ساختار فيستل استفاده مي کنند در مقايسـه بـا الگـوريتم هـايي ک ه داراي ساختار SP٥هستند، قدرت الگوريتم بسيار وابسـته بـه S-Box
هاي طراحي شده اسـت . همچنـين امنيـت يـک الگـوريتم در مقابـ حملات خطي و تفاضلي، به قدرت S-Box آن الگوريتم وابسته است .
يک S-Box در واقع يک نگاشت بين ورودي mبيتي و خروجي n
بيتي آن است . در اکثر الگوريتم ها تنها بخش غير خطي که آنها را در مقابل حملات آماري مقاوم مي کند، S-Box است که هر چه بزرگتر باشد داراي خواص بهتر و قدرت بيشتري است . محدوديتي که استفاده از S-Box هاي بزرگ را در الگوريتم ها محدود مي کند، حجم حافظه زيادي است که براي ذخيره آنها لازم مـي باشـد[١]. در يـک S-Box
اندازه ورودي از اندازه خروجي اهميت بيشتري دارد. اگر ورودي داراي

371

mبيت و خروجي nبيتي باشد، افـزايش nتـأثير تحليـل تفاضـلي ر کاهش داده اما به مقدار زيادي باعث بهبود تحليل خطي مي شود. در واقع اگر 2-m..n باشد، اثبات مي شود که يک رابطه خطي بين ورودي و خروجي S-Box وجود دارد و اگر 2m..n، بـين بيتهـاي خروجي S-Box يک رابطه خطي مي توان پيدا کرد[١].
S-Box ها را مي توان به دو صورت جدول هاي ذخيره شونده در حافظه و پياده سازي سخت افزاري يا نرم افزاري روابط جبري به کـار برد. در پياده سازي بسياري از الگوريتم هاي قطعـه اي، از جـدولهاي ذخيره شونده در حافظه به عنوان S-Box استفاده مي گردد. به عنوان مثال DES داراي ٨جدول ٤*٦بيت اسـت کـه هـر S-Box جـدولي شامل ٤سطر و ١٦ستون است که عناصر اين جدول اعداد صفر تا ١٥ است . مزيت اين روش اين است که رابطه جبري به خصوصـي را نمـي توان براي تقريب زدن S-Box به کار برد. اين ويژگـي الگـوريتم را در مقابل بسياري از حمله هاي آماري مقاوم مي کند. البته در ايـن روش از S-Box هاي بزرگ به دليل نيـاز داشـتن بـه حجـم حافظـه زيـاد، استفاده نمي شود. S-Box هايي کـه بـه صـورت يـک الگـوريتم و استفاده از يک سري رابطه جبري در حين اجراي عمل رمزنگـاري بـه کار مي روند، در کاربردهايي که حافظه به مقدار کافي در دست نيست ، مثلاً در کارتهاي اعتباري، بسيار مناسبند. ايـن S-Box هـا بـه دليـل داشتن ساختار جبري، معمولاً بسيار مورد علاقه تحليلگران رمـز واقـع مي شوند. در واقع روابط جبري که در اين S-Box ها به کار مـي رود بايد با هوشياري کامل انتخاب گردد. البته اکثر اين S-Box ها را مـي توان به صورت جدولهايي که در حافظه ذخيره شوند، پياده سازي کرد.
به عبارت ديگر اکثر S-Box هـاي جـدولي نيـز داراي سـاختار هـا رياضي هستند، ولي مزيت آنها اين است که فلسفه پشت آنهـا مـبهم است [٢].
روابط جبري که در طراحي S-Box ها به کـار مـي رود، خطـي و آفاين ٦نيستند. اگر ورودي يک S-Box را di و mبيتي و خروجي آن را do و nبيتي در نظر بگيريم ، اين S-Box در صورتي آفـاين ناميـده مي شود که بتوان ماتريس هاي T*m و 1*Bn راطوري يافت کـه بـه
ازاي هر d d رابطه (١)را داشته باشيم [١٣]:
iو o
doTnm diBn1 (1)
همچنين ساختار S-Box بايد به گونه اي باشد که هيچگونه همبستگي ٧بين بيت هاي خروجي آن وجود نداشته باشد. در طراحي يک S-Box بايد به داشتن خاصيت بهمني بالا نيز توجه گردد، يعني با تغيير يک يا چند بيت در ورودي S-Box بايد تعداد زيادي از بيت هاي خروجي ( به عبارت دقيقتر هر بيت با احتمال ١= p) تغيير
2
کند.
اطلاعات ،سما،همدان ، ايران ، ٢٨بهمن ١٣٨٩.
٢-تحليل خطي
تحليل خطي رمز که يک حملـه KPA٨اسـت توسـط "ميتسـورو ماتسويي "٩به منظور تحليل DES ابداع شد. اسـاس ايـن تحليـل بـ دست آوردن يک تقريب خطي ١٠از الگوريتم رمزنگاري مي باشد[١٠].
بردار nبيتي انتخاب کننده ...و بردار nبيتي متن اصلي Pرا در نظـر
مي گيريم :
‥:(‥n,‥n1,...,‥2,‥1) (2)
P:(pn ,pn1 ,...,p2 ,p1)
يک ترکيب خطي از بردار ...و بردار nبيتي متن اصلي Pبه صورت
رابطه (٣)تعريف مي شود:
P.=n.n…n 1.n 1…..…2.2…1.1 (3)

در رابطه بالا .بيانگر عمل AND در ميدان (٢)GF است . در واقع نتيجه ترکيب خطي ....P نيز عضو ميدان (٢)GF است . حال اگر مـتن اصلي، متن رمز شده و کليد يک الگوريتم را به ترتيـب بـا P،C و K
نمايش دهيم ، پيدا کردن يک تقريب خطي از الگوريتم ، معادل با پيدا کردن بردارهاي انتخاب کننده ...، ...و ...است کـه رابطـه (٤)برقـرار
باشد:
….P….C….K = (4)
براي يک متن اصلي و متن رمز شده نظير آن ، احتمال اينکه رابطه بالا را بتوان يافت برابر با p( ١..p)خواهد بـود. بايـاس احتمـال
2
خطي ١١طبق رابطه (٥)تعريف مي گردد:
1
- (5)
2
هر چه مقدار ...بزرگتر باشد، رابطه تقريب خطي از کارايي ١٢بهتري برخوردار است [٣]. در واقع در يک الگوريتم رمز نگاري اگر در تقريـب خطي،...بيشينه باشد نشـان دهنـده ايـن اسـت کـه الگـوريتم دارا خصلت کاملاً تصادفي نيست . همچنين بيشينه بودن ...باعـث کـاهش پيچيدگي تحليل خطي الگوريتم مي شود[٤].در تحليل خطي بعد از پيداکردن يک تقريب خطي مناسب از الگـوريتم بـا ...بـزرگ ، توسـط الگوريتم هاي ويژه اي مي توان تعدادي از بيت هـاي کليـد را بدسـت آورد که تعدادي از اين الگوريتم ها در مرجع [٤]بيان شده است .
از آنجاييکه در اکثر الگوريتم هاي رمزنگاري، بخش جانشيني و استفاده از S-Box به عنوان تنها ترين بخش غير خطي الگوريتم مي
372

باشد، در صورتي که بتوان تقريب خطي مناسبي از S-Box استفاده شده پيداکرد، الگوريتم در مقابل تحليل خطي به شدت آسيب پذير خواهد بود[٥].
٣-تحليل تفاضلي
اين تحليل در ابتداي دهه نودتوسط "بيهام "و "شـمير"١٣ابـداع شد و در گروه حملـه هـاي 14CPAو 15CCAقـرار دارد[٧]. در ايـن روش با استفاده ازجفت هايي از متن اصلي و متن رمز شده نظير آن که داراي تفاوت ثابتي هسـتند، رفتـار تفاضـلي١٦سيسـتم رمزنگـاري بررسي مي شود. به عنوان مثال تفـاوت دو قطعـه ورودي P1 و P2 در الگوريتم AES به صورت P١..P٢ تعريف مي گردد که البته مي توان تعريف هاي ديگري نيز براي تفاوت دو بردار در نظـر گرفـت . در ايـن حمله بـا يـک کليـد ثابـت ،رفتـار تفاضـلي الگـوريتم شـبه تصـادفي نيست [١].
در تحليل تفاضلي بايد رفتار تفاضلي قسمت هاي مختلف الگوريتم بررسي شود. با توجه به اينکه قسمت هاي خطي و پس و پيش سازي در رفتار تفاضلي الگوريتم تأثير زيادي ندارند، در بررسي اين رفتار قسمت هاي غير خطي الگوريتم همچون S-Box از اهميت بسيار بالايي برخوردار است .[٨]
٤- S-Box الگوريتم AES
در سال ٢٠٠٢، AES به عنوان استاندارد رمزنگاري جانشين استاندارد قبلي DES گرديد. AES يک الگوريتم رمز قطعه اي متقارن با طول قطعه ورودي ١٢٨بيت است . طول کليد نيز مستقل از طول قطعه ورودي ١٩٢،١٢٨يا ٢٥٦بيت مي باشد . الگوريتم بسته به طول قهالمب چنيدان د داورايطول ساخکلتايرديم بشراتيل سرط ٠ک١لي ،د ا٢س١ت ياک١٤ازدروريخکواليد ابصلدي.
بسته به تعداد دورها ، تعدادي زير کليد توليد ميکند که در هر دوربه قالب داده اضافه ميشوند . الگوريتم شامل سه تبديل مهم
()SubByte، (MixColumn) و ()ShiftRow است که اولي يک تابع جايگزيني غير خطي و تامين کننده امنيت سيستم و دومي وسومي توابعي خطي براي افزايش خاصيت انتشارالگوريتم اند . در اين رمز قطعه اي چون با افزايش طول کليد تعداد دورهاي الگوريتم افزايش مييابد، زمان اجرا و سرعت الگوريتم به طول کليد وابسته است .[١١و١٢]
تابع ()SubByte يک تابع غيرخطي است که به طور مسـتقل روي بايتهاي آرايه حالت عمل کرده و به جاي هر بايت به کمک جدول -S box يک بايت جديد قرار ميدهد. اين S-Box داراي توصيف جبـري
زير است :

3rd National Conference on Computer Engineering & Inf
s(x)=x 1… (6)

در اين ساختار همانگونه که مشاهده مي شـود از تـابع معکـوس و جمع و ضرب در ميدان (٢٨)GF با چنـد جملـه اي اول زيـر اسـتفاده
شده است :
q(x)=8 +4 +3 ++ (7)
در جـدول (١) S-Box ايــن الگــوريتم در يــک آرايــه ١٦*١٦و نمايش اعداد در مبناي ١٦نشان داده شده است .
جدول (١):S-Box الگوريتم AES

٥-تحليل آماري S-Box
٥-١- تحليل آماري مشخصه خطي
قضيه ١: در يک S-Box داراي ورودي nبيتي و خروجي mبيت ، تعداد تقريب هاي خطي که مي تواند وجود داشته باشد از رابطـه زيـر
بدست مي آيد:
(2m 1)(2n 1)
(8)
با توجه به اين قضيه در بدترين حالت بـراي nو mبرابـر ٨، -S Box داراي ٦٥٠٢٥تقريب خطي مي باشد.
تعريف ١: شاخص خطي بودن يک S-Box از رابطه زير محاسـبه
مي شود[٦و ٧] :
(9)
NS(‥,)|#{x 0x 2n,x.‥S(x).} 2n1 |
373

که در اين رابطه ...و ...به ترتيب دو بردار انتخاب کننده nبيتي و
mبيتي هسـتند و علامـت #بيـان کننـده تعـداد اسـت . در S-Box
الگوريتم AES مقادير nو mبرابر ٨هستند. با توجه به اين رابطه بـا توجه به الگوريتم هاي ارائه شده در تحليل خطي رمـز دو حالـت مـي
توان در نظر گرفت :
١- کليه مقادير بردار انتخاب کننده ...(٢٥٥.........١)در خروجي -S Box را به ازاي کليه مقادير بردار انتخاب کننده ...(٢٥٥.........١) در نظر گرفته شود.
٢- بردار انتخاب کننده خروجـي در S-Box را بـه شـکل ...=(...)S
لحاظ گردد.
قضيه ٢: افزايش درجه امنيت يک الگوريتم رمز قطعه اي در مقابل
تحليل خطي به دو ويژگي وابسته است [٣]:
١. بيشينه شاخص خطي S-Box الگوريتم يا هر قسـمت غيـر خطي استفاده شده در الگوريتم کمترين مقدار ممکن باشد.
٢. افزايش تعداد S-Box هاي فعال در يک مرحله از الگوريتم به ازاي تغيير در ورودي .
ويژگي اول به S-Box طراحي شده بسـتگي دارد. ويژگـي دوم بـه ميزان انتشار به کار رفته در طراحي الگوريتم وابسته اسـت کـه در آن قسمت هاي خطي و غيرخطي الگوريتم هر دو مؤثر هستند.
اين S-Box بعد از پياده سازي در نـرم افـزار MATLAB از نظـر شاخص خطي مورد بررسي قرار گرفت . نتايج حاصل از اين بررسي در شکل هاي (١) و(٢)ارائه شده است .در جدول (٢)نيـز جفـت (...,...)
هاي داراي شاخص خطي ١٦با درنظـر گـرفتن ...=(...)S، نشـان داده شده است .[٣]
14000
12000 2, 12240
6, 10200
10000
8000 4, 9180 8, 8670 12, 9180
6000 10, 6120
4000 0, 4335 14, 4080
2000
0 16, 1275
٢٠ ١٥ شاخ٠ص ١ خطي ٥ ٠ شکل (١): نمودار شاخص هاي خطي S-Box الگوريتم AES و تعداد جفت (...,...)در هر شاخص (مقادير بردار انتخاب کننده ...(٢٥٥.........١) در خروجي S-Box به ازاي کليه مقادير بردار انتخاب کننده ...
(٢٥٥.........١)در نظر گرفته شده است .)
اطلاعات ،سما،همدان ، ايران ، ٢٨بهمن ١٣٨٩.
46 2, 43
41
36 4, 35 8, 36 12, 35
31 6, 35
26