کدهای احراز تمامیت پیام و توابع درهم ساز

کدهای احراز تمامیت پیام و توابع درهم ساز

اسلاید 1: 1 کدهاي احراز تماميت پيام و توابع درهم سازبهروز ترك‏لاداني ladani@eng.ui.ac.ir

اسلاید 2: پيش در آمددر اين فصل روشهاي حفظ پيام در برابر تغييرات ناخواسته و شناسايي صحت محتواي پيامها مطالعه ميشوند.ابزارها:کدهاي احراز هويت پيام توابع درهم ساز چهارچوب مطالعاتي رمزنگاري کليد خصوصي ميباشد.

اسلاید 3: فهرست مطالبمفاهيم اوليه رمزنگاري کليد خصوصي و کدهاي تشخيص خطا کد هاي احراز تماميت پياماصول توابع درهم ساز توابع درهم ساز مهم HMAC

اسلاید 4: احراز تماميت پيام چيست؟اطمينان از:تماميت پيام؛ يعني پيام دريافتي دستکاري نشده است:بدون تصحيح،بدون درج،بدون حذف پيام از جانب فرستنده ادعا شده ارسال شده است

اسلاید 5: AliceBob0 1 1 0 1 ...Adversary EVEShared Network1محرمانگيتماميت پيام

اسلاید 6: اهميت تماميت پيامدر بسياري از کاربرد ها، مثلاً تراکنشهاي بانکي، اينکه ارتباطات مخفيانه باشند اهميت زيادي ندارد ولي اينکه محتواي آنها قابل اعتماد باشند از اهميت بسيار بالاتري بر خوردار است.

اسلاید 7: يک نکتهرمزنگاري مرسوم (کليد خصوصي):کدهاي احراز تماميت پيام احراز تماميت پيام رمزنگاري کليد عمومي: امضاي ديجيتال احراز تماميت پيام عدم انکارموضوع اين فصل

اسلاید 8: ايده اساسيطرفين يک کليد مخفي به اشتراک بگذارند.ارسال هر پيام، به همراه يک برچسب که تابعي است از: کليد مخفي و متقارنپيام به طوري که:بدون دانستن کليد توليد اين برچسب نا ممکن باشد.با تغيير پيام، برچسب کاملاً تغيير کند.

اسلاید 9: راه کارهاي احراز تماميت پيام رمزنگاري کليد خصوصي استفاده از توابع درهم ساز براي احراز تماميت پيامکد احراز تماميت پيام همه ميتوانند پيام را بخوانند، ولي تنها صاحب کليد مخفي ميتواند تماميت آن را بررسي کند.

اسلاید 10: رمزنگاري کليد خصوصي براي احراز تماميت پيام فرستنده پيام را رمز ميکند.اگر متن رمز شده دستکاري شود هنگام رمز گشايي به متن واضح نامفهوم (درهم و برهم) ميرسيم. گيرنده، بعد از رمز گشايي چک ميکند که آيا پيام مفهوم است يا نه؟

اسلاید 11: مشکلات رمزنگاريبررسي مفهوم بودن محتوي همواره آسان نيست:در حالت کلي نوعي افزونگي يا ساختار دروني مورد انتظار را جستجو ميکنند. بررسي قواعد زبان (فارسي، انگليسي،... )دشواري خودکارسازي فرآيند چک کردن ....هنگام ارسال داده اگر داده ها خود تصادفي به نظر برسند، يعني از ساختار دروني خاصي تبعيت ننمايند، بررسي محتوي تقريباً ناممکن استراه حل: استفاده از کدهاي تشخيص خطا مثال: يک بيت به انتهاي پيام اضافه نماييم، به گونه ايي که تعداد بيتهاي يک زوج شود.يک کد متداول CRC

اسلاید 12: کدهاي تشخيص خطاتابع F يک کد تشخيص خطا است اضافه نمودن “ دنباله بررسي قالب ”، FCS، توسط تابع Fيک مثال از تابع F ، کد CRC مي باشد.گيرنده، بعد از رمز گشايي چک ميکند که آيا “ دنباله بررسي قالب “ محاسبه شده توسط F با برچسب پيام مطابقت دارد يا نه؟

اسلاید 13: نا امن بودن کدهاي تشخيص خطا-1کدهاي تشخيص خطا مانند CRC براي تشخيص خطاي حاصل از نويز در کاربردهاي مخابراتي طراحي شده اند.نويز:تغييرات غير هوشمندانه و غير عمدي دشمن:تغييرات هوشمندانه و عمدي حملات موفقي به الگوريتمهايي که از کدهاي تشخيص خطا استفاده ميکردند، صورت پذيرفته است.مثال: پروتکل IEEE 802.11

اسلاید 14: پروتکلIEEE 802.11براي امنيت مخابرات سيارالگوريتم رمزنگاري دنباله ايي RC4 و کد تشخيص CRCمتن واضح Pپيام MChecksum F(M)+RC4(iv,k)متن رمزشده C=متن واضح Pپيام MChecksum c(M)+RC4(iv,k)متن رمز شده C=

اسلاید 15: ضعف پروتکلIEEE 802.11 براي امنيت مخابرات سيارالگو ريتم رمزنگاري RC4 و کد تشخيص CRCCRC يک الگو ريتم خطي است:CRC(X  Y) = CRC(X)  CRC(Y)RC4 نيز خاصيت زير را دارد: RC4(k,X  Y) = RC4(k,X)  Yحمله:RC4(k,CRC(XY)) = RC4(k,CRC(X)) CRC(Y)

اسلاید 16: تصحيح غير مجاز بسته011010010100……………………………………پيام10110…………CRC-32 برچسب RC4101101110101…………………………………………………………XOR110111100001……………………………………11011…………010000000000……………………………………00110…………XOR100111100001……………………………………11101…………بسته دستکاري شدهRC4k(CRC(XY)) = RC4K(CRC(X)) CRC(Y)

اسلاید 17: نتيجه گيريکد تشخيص خطا نميتواند در حالت کلي از دستکاري بسته ها جلوگيري کند. راه حل: کد هاي احراز تماميت پيام

اسلاید 18: کد هاي احراز تماميت پيامتوليد يک برچسب با طول ثابت: وابسته به پيام لزوماً برگشت پذير نيست نيازمند يک کليد مخفي مشترک بين طرفين آنرا به اختصار MAC مينامند. نام ديگر “Cryptographic Checksum”اين برچسب را به پيام اضافه ميکنند گيرنده خود برچسب پيام را محاسبه نموده و با برچسب ارسالي مقايسه ميکند. از تماميت پيام و هويت فرستنده اطمينان حاصل ميشود.

اسلاید 19: کد هاي احراز تماميت پيامتماميت

اسلاید 20: کد هاي احراز تماميت پياممحرمانگي و تماميت

اسلاید 21: FAQ-MAC!آيا MAC همانند امضا غير قابل انکار است؟خير امضا با يک کليد عمومي ثبت شده بررسي ميشود ولي کليد MAC خصوصي و مخفي است بر خلاف امضاء، دو طرف قادر به ايجاد MAC ميباشند.

اسلاید 22: امنيت MACMAC همواره پيامها را به يک طول ثابت مي نگارد.يک به يک نيست پيامهاي متفاوت MAC يکسان دارند.براي حمله ميتوان پيام هاي متمايزي يافت که برچسب يکسان داشته باشند.تصادم:دو پيام با MAC يکسان

اسلاید 23: ويژگيهاي MACويژگيهاي يک MAC مناسب :با دانستن يک پيام و بر چسب آن، يافتن پيام متفاوتي با برچسب يکسان از لحاظ محاسباتي ناممکن باشد.توزيع خروجي MAC بايد يکنواخت باشد تا احتمال اينکه دو پيام تصادفي MAC يکسان داشته باشند، کمينه شود.نکته: طول برچسب همانند طول کليد در امنيت MAC تاثير دارد. (بنا به حمله روز تولد)

اسلاید 24: کداحراز تماميت پيام DAA DAA (Data Authentication Algorithm)استاندارد NIST و ANSI X9.17 بر اساس رمز قطعه ايي DES و مد کاري CBCهمانند رمز نگاري CBC، پيام را پردازش کرده و تنها آخرين قطعه را به عنوان برچسب استفاده ميکنيم.

اسلاید 25: DAADESP1K+DESP2K+DESP3K+DESPNMACK+……متن واضح (تقسيم شده به قطعات)

اسلاید 26: توابع درهم سازتابع يك‌طرفه،طول ورودي متغير طول خروجي ثابت (نگاشت از فضاي بزرگتر به فضاي كوچكتر)در حالت کلي، کليدي در کار نيست!

اسلاید 27: امنيت توابع درهم ساز-ايده کلينگاشت پيامهاي طولاني به رشته هاي کوتاه به گونه ايي که:يافتن پيامهاي متفاوتي که به يک رشته يکسان نگاشته شوند دشوار باشد.به اين رشته عصاره يا چکيده پيام ميگوييم.

اسلاید 28: امنيت توابع درهم سازتوابع درهم ساز بايد يک طرفه باشند. براي يک h داده شده، بايد يافتن x به گونه ايي که h = H(x) از لحاظ محاسباتي ناممکن باشد.مقاومت در برابر تصادم (ضعيف)براي يک x داده شده، بايد يافتن y به گونه ايي که H(y) = H(x) از لحاظ محاسباتي ناممکن باشد.مقاومت در برابر تصادم (قوي)يافتن x و y به گونه ايي که H(y) = H(x) از لحاظ محاسباتي ناممکن باشد

اسلاید 29: مقايسه تصادم قوي و ضعيفممکن است ساختار تابع H طوري باشد که : بتوان تعداد محدودي x و y يافت به گونه اي که مقادير تابع تصادم پيدا کنند.(تصادم قوي)ولي براي يک x داده شده همواره نتوان يک y پيدا کرد بطوريکه H(y) = H(x) (تصادم ضعيف)ارضاشدن شرط تصادم قوي براي يک تابع دشوار تر از ارضاشدن شرط تصادم ضعيف ميباشد.توابعي که در برابر تصادم قوي مقاومت کنند امنيت بالاتري دارند

اسلاید 30: امنيت توابع درهم ساز: پيچيدگي حملهتوابع درهم ساز بايد يک طرفه باشند. پيچيدگي جستجوي کامل (آزمون جامع) 2n ميباشد، که n طول خروجي تابع است.مقاومت در برابر تصادم (ضعيف)پيچيدگي جستجوي کامل (آزمون جامع) 2nميباشدمقاومت در برابر تصادم (قوي)پيچيدگي جستجوي کامل (آزمون جامع) 20.5*nميباشد دقت کنيد آزمون جامع بيانگر حداکثر امنيت ممکن براي تابع است زيرا ممکن است به دليل ضعف طراحي، حملات موثرتري نيز امکان پذير باشد. با کمک حمله روز تولد

اسلاید 31: توابع درهم ساز و رمز نگاري متقارن: تماميتاگر پيام M’ را بتوان يافت بطوريکه H(M) = H(M’) (تصادم ضعيف)M را ميتوان توسط M’ جعل نمود خطر

اسلاید 32: توابع درهم ساز و رمز نگاري متقارن: محرمانگي و تماميت

اسلاید 33: توابع درهم ساز و رمز نگاري نا متقارن: امضاء

اسلاید 34: روشهاي ديگر احراز تماميت پيام طرفين راز s را مخفيانه به اشتراک گذاشته اند.بدون استفاده از رمزنگاري کاربرد عملي زياد

اسلاید 35: روشهاي ديگر احراز تماميت پيام روش قبل + محرمانگي رمزنگاري صرفاً براي محرمانگي است.

اسلاید 36: ساختار دروني تابع درهم ساز: ايده اساسياعمال مکرر يک تابع فشرده ساز (Ralph Merkle)اگر تابع فشرده ساز مقاوم در برابر تصادم باشد، تابع درهم ساز نيز همين گونه خواهد بود.توابع معروفي مانند5 MD5: Message DigestSHA-1: Secure Hash Algorithm -1 از همين ايده استفاده ميکنند.

اسلاید 37: ساختار دروني توابع درهم ساز-2 پيام به قطعات Yi تقسيم شده است. IV يک رشته ثابت ميباشد.CV0=IVCVi= f(CVi-1,Yi-1)Hash = CVLپيام

اسلاید 38: توجهبراي مطالعه جزييات ساختار توابع به پيوست ها مراجعه فرماييد.MD5SHA-1RIPMED

اسلاید 39: توابع درهم ساز مهم: MD5 MD5: Message Digest 5طراحي 1992 توسط “ران ريوست”، يکي از سه طراح RSAاستفاده گسترده در گذشته، اما از کاربرد آن کاسته شده است.ويژگيها:پيام به قطعات 512 بيتي تقسيم ميشودخروجي 128 بيتي

اسلاید 40: امنيت MD5مقاومت در برابر تصادم (قوي) تحت حمله آزمون جامع: 264امروزه امن محسوب نميشود. حملات کارگر به اين الگوريتم يافت شده اند:Berson سال 1992: حمله تفاضلي به يک دور الگوريتم Boer وBosselaers سال 93: يافتن تصادم هاي مجازي Dobbertin سال 96: تصادم در تابع فشرده ساز

اسلاید 41: توابع درهم ساز مهم: SHA-1 SHA-1: Secure Hash Algorithm – 1استاندارد NIST، 1995طول ورودي < 264 بيتطول خروجي 160 بيتاستفاده شده در استاندارد امضاي ديجيتال DSS امنيت:مقاومت در برابر تصادم (قوي) تحت حمله آزمون جامع: 280امن محسوب ميشوددر برابر حملات شناخته شده مقاومت بالايي دارد

اسلاید 42: گونه هاي SHA-1 براي سازگاري با AES نسخه هاي زير نيز استاندارد شده اند:SHA-512، SHA-256 و SHA -384

اسلاید 43: توابع درهم ساز مهم: RIPEMD طراحي در اروپا در سال 1997مشخصات همانند SHA-1قابل مقايسه با SHA-1 از لحاظ امنيت و سرعتسرعت هر دو تقريباً نصف MD5

اسلاید 44: مقايسه MD5،SHA-1، RIPEMD-1

اسلاید 45: HMAC-1HMAC يک الگوريتم احراز هويت پيام استHMAC اساساً روشي براي ترکيب کردن کليد مخفي با الگوريتمهاي درهم ساز فعلي ميباشد.براي توليد چکيده پيغام، از توابع درهم استفاده شده استدر مقابل استفاده از رمزهاي قطعه ايبدليل مزاياي عملي توابع درهم ساز

اسلاید 46: HMAC-2HMAC جزو ملزومات پياده سازي IPSec ميباشد.HMAC به طور گسترده استفاده ميشود (مثلاً SSL)

اسلاید 47: HMAC: اهداف طراحياستفاده از توابع درهم ساز بدون تغيير آنها پشتيباني از توابع درهم ساز متنوعحفظ کارايي و سرعت تابع درهم ساز به کار گرفته شده استفاده ساده از کليد طراحي روشن و بدون ابهام

اسلاید 48: HMAC: الگوريتمH : تابع درهم ساز به کار گرفته شده:M پيام وروديK: کليد مخفيK+ : کليد مخفي که يک دنباله صفر به آن اضافه شده است ipad : تکرار رشته 00110110opad : تکرار رشته 01011010HMACK = H[(K+  opad) || H[(K+  ipad) || M ]]

اسلاید 49: پيامH[(K+  ipad) || M ]H[(K+  opad) || H[(K+  ipad) || M ]]

اسلاید 50:

اسلاید 51: HMAC: امنيتارتباط دقيق بين امنيت تابع در هم ساز با امنيت HMAC اثبات شده است.مقاومت HMAC در برابر حمله روز تولد از تابع در هم ساز به کار گرفته شده، بيشتر است.استفاده از MD5 در هنگام نياز به سرعت بيشتر مجاز است.

اسلاید 52: پيوست ها

اسلاید 53: پارادکس روز تولدحداقل مقدار k چقدر است به نحوي كه در يك گروه k نفري احتمال اينكه دو نفر در يك روز به دنيا آمده باشند بيش از 0.5 باشد؟

اسلاید 54: پارادکس روز تولدتعداد حالات ممكن به نحوي كه k نفر روز تولد متقاوت داشته باشند:365*364*… *(365-k+1) = 365!/(365-k)!احتمال اينكه هر k نفر در يك جمع k نفره داراي روز تولد متفاوت باشند:P = (365!/(365-k)!)/(365)k احتمال اينكه حداقل دو نفر در يك جمع k نفره داراي روز تولد يكسان باشند:1-P = 1- 365!/((365-k)!)*(365)k )

اسلاید 55: پارادکس روز تولد

اسلاید 56: پارادکس روز تولددر ميان 23 نفر، احتمال يافتن دو نفر که در يک روز متولد شده اند بيش از 50% ميباشد.

اسلاید 57: پارادکس روز تولد تعميم مسئله: حداقل k چقدر است به نحوي كه با احتمال بيش از 0.5 يك تكرار در k عنصر داشته باشيم به نحوي كه هر عنصر مقاديري در بازة 1 تا n بتواند اختيار كند؟با تعميم حل قبلي مي توان به دست آورد كه:k=1.18 * n0.5 = n0.5n= 365  k=23

اسلاید 58: پارادکس روز تولدمبناي رياضيتابع H با خروجي ممکن را در نظر بگيريد(خروجي m بيتي) H را به k ورودي تصادفي اعمال کنيم و خروجي را مجموعه X در نظر مي گيريم. به همين ترتيب مجموعه Y را تشکيل مي دهيم. اگر k بزرگتر از باشد، احتمال حداقل يک تصادم در بين اعضاي دو مجموعه X و Y بيش از ½ مي باشد

اسلاید 59: حمله روز تولدممکن است تصور کنيد يک MAC يا Hash 64 بيتي امن است اما...با حمله روز تولد امنيت از بين ميرود:مهاجم تتت پيام معتبر که اساساً هم معنا هستند توليد ميکند. m طول خروجي Hash است.مهاجم همين تعداد پيامهاي دلخواه خود را توليد ميکند. ( که معناي ساختگي دارند)دو دسته پيام مقايسه ميشوند تا زوجي يافت شود که Hash يکسان داشته باشند.از کاربر ميخواهيم تا پيام معتبر زوج را امضا نمايد، و سپس پيام دلخواه دشمن را جايگزين ميکنيم.

اسلاید 60: مثالي از حمله (نمونه معتبر)Dear Dean Smith,This [ letter | message ] is to give my [ honest | frank ] opinion of Prof Tom Wilson, who is [ a candidate | up ] for tenure [ now | this year ]. I have [ known | worked with ] Prof Wilson for [ about | almost ] six years. He is an [ outstanding | excellent ] researcher of great [talent | ability ] known [ worldwide | internationally ] for his [ brilliant | creative ] insights into [ many | a wide variety of ] [difficult | challenging ] problems.

اسلاید 61: مثالي از حمله (پيام دشمن)Dear Dean Smith,This [ letter | message ] is to give my [ honest | frank ] opinion of Prof Tom Wilson, who is [ a candidate | up ] for tenure [ now | this year ]. I have [ known | worked with ] Prof Wilson for [ about | almost ] six years. He is an [ poor | weak ] researcher not well known in his [ field | area ]. His research [ hardly ever | rarely ] shows [ insight in | understanding of ] the [ key | major ] problems of [the | our ] day.

اسلاید 62: ساختار داخلي توابع درهم ساز

اسلاید 63: MD5

اسلاید 64: MD5 LogicStep 1.Appending padding bitsCongruent to 448 modulo 512Step 2.Appending lengthLength modulo 64L * 512-bit, N * 32 bitM[i] : ith wordStep 3.Initialize MD bufferFour 32-bit register (A B C D), little endianA = 67482301B = EFCDAB89C = 98BADCFED = 10325476

اسلاید 65: MD5 LogicStep 4.Process message in 512-bit blocksFour roundsEach round has a different primitive function, F, G, H and IUse one-fourth of T[i] T[i] = 232 * abs(sin(i))

اسلاید 66: تابع بولي gدر MD5RoundPrimitive function gg(b,c,d)1F(b,c,d)(b  c)  (b  d)2G(b,c,d)(b  d)  (c  d)3H(b,c,d)b  c  d4I(b,c,d)c  (b  d)

اسلاید 67: MD5 LogicStep 5. Output

اسلاید 68: MD5 Compression FunctionX[i] is used once, during one stepρ2(i) = (1 + 5i) mod 16Ρ3(i) = (5 + 3i) mod 16Ρ4(i) = 7i mod 16Each step, only 4 bytes is updated

اسلاید 69: SHA-1

اسلاید 70: SHA-1 LogicStep 1. Appending padding bitsStep 2. Append lengthStep 3. Initialize MD bufferFive 32-bit registers, E = C3D2E1F0Big-endian

اسلاید 71: SHA-1 LogicStep 4. Process message in 512-bit blocksFour rounds of 20 stepsStep 5. Output

اسلاید 72: SHA-1 Compression FunctionKt is a additive constant varying across rounds

اسلاید 73: SHA-1 Compression FunctionWt = S1(Wt-16 + Wt-14 + Wt-8 + Wt-3)

اسلاید 74: RIPEMD

اسلاید 75: RIPEMD-160 LogicStep 1. Appending padding bitsStep 2. Append lengthStep 3. Initialize MD bufferSame value is used in SHA-1Little-endian

اسلاید 76: RIPEMD-160 LogicStep4. Processing message10 rounds of 16 stepsFive primitive functions f1, f2, f3, f4, f5 Nine additive constantAddition is involves a rotationStep5 .Output

اسلاید 77: RIPEMD Compression functionπ (i) = 9i + 5 (mod 16)

اسلاید 78: RIPEMD Design decisionTwo parallel lines are usedIncrease complexity of finding collisions between roundsTwo lines use same logicSimplicityDifferenceAdditive constantsOrder of primitive functionsOrder of processing of message blockUse five words, and rotation of the C word

اسلاید 79: RIPEMD Design decisionPermutationsEffect that two word that are close in one round are relatively far apart in the nextCircular leftRange from 5 to 15Different amounts for the five roundsNot have special pattern (not be divisible by 32)Not too many shift should be divisible by 4