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

صفحه 1:


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

صفحه 3:
* مفاهیم اولیه * رمزنگاري کلید خصوصي و كدهاي تشخیص خطا * کد های احراز تمامیت پیام * اصول توابع درهم ساز * توابع درهم ساز مهم (۸0 ۰ 

صفحه 4:
* اطمینان از: - تمامیت پیام؛ یعنی پیام دریافتی دستکاری نشده است: بدون تصحیح. TP ‏بدون‎ " 7 بدون حذف - پیام از جانب فرستنده ادعا شده ارسال شده است 

صفحه 5:
Adversary EVE gum | 

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

صفحه 7:
* رمزنگاري مرسوم (کلید خصوصي): - كدهاي احراز تمامیت پیام - احراز تماميت بيام * رمزنگاري کلید عمومي - امضاي دیجیتال - احراز تمامیت پیام ‎ISI pac‏ 

صفحه 8:
* طرفین یک کلید مخفی‌به اشتراک بگذارند. * ارسال هر پیام. به همراه یک برچسب که تابعي! = کلید مخفي و متقارن 7 پیام * به طوري که: 7 بدون دانستن کلید تولید این برچسب نا ممکن باشد. - با تغيير پیام. برچسب کاملاًتفییر کند. 

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

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

صفحه 11:
* بررسي مفهوم بودن محتوي‌همواره آسان نیست: - در حالت كلينوعي فزونگي یا ساختار دروني مورد انظار را جستجو میکنند. 7 بررسي قواعد زبان (فارسي انگليسي... ) دشواري خودكارسازي فرآیند چک کردن .. * هنگام ارسال داده - اكر داده ها خود تصادفي به نظر برسند. يعنياز ساختار دروني خاصي تبعیت ننمايند. بررسي مختوي ‎Seals Cait‏ الست * راه حل: استفاده از کدهاي تشخیص خطا - مثال: یک بیت به انتهاي پيام اضافه نماییم. به كونه ابى كه تعداد بيتهاي یک زوج شود. - يك كد متداول 036 

صفحه 12:
* تابع ]یک کد تشخیص خطا است - اضافه نمودن " دنباله بررسی‌قالب " ۳0/5 توسط تابع ظ - یک مثال از تابع ‎CRC a5 F‏ می‌باشد. * گيرنده بعد از رمز گشایی چک میکند که آیا " دنباله بررسي قالب " محاسبه شده توسط ‏ با برچسب پیام مطابقت دارد یا نه؟ + Source A» + Destination B —_» ‏ا‎ “> 35 Te مت ۳ 1 2 

صفحه 13:
* كدهاي تشخيص خطا مانند 1867 براي تشخیص خطاي حاصل از نویز در كاربردهاي مخابراتي طراحي شده اند. ‎epee‏ 0 sae Bz ‏أت غیر هوشمندانه و غیر عمدي‎ ات هوشمندانه و عمدي * حملات موفقي به الگوریتمهایی که از کدهاي تشخیص خطا استفاده میکردند. صورت پذیرفته است. - مثال: پروتکل 802.11 1۳8۳۳ 

صفحه 14:
* براي امنيت مخابرات سيار - الكوريتم رمزنكاري دنباله ايى .104 و كد تشخيص ‎CRC‏ 

صفحه 15:
yee * براي امنيت مخابرات سيار - الگو ریتم رمزنگاري 364 و کد تشخیص 00110 Gol be oh, SLI, CRC CRC(X @ Y) = CRC(X) @ CRC(Y) 04 نيز خاصيتهير را دارد: RC4(k,X @ Y) = RC4(k,X) @ Y حمله: RC4(k,CRC(X@Y)) = RC4(k,CRC(X)) @CRC(Y) 

صفحه 16:
4+ 101101110101............. 110111100001... 610000000000. 202 100111100061......... iy 3 ». | 11101 = RC#,(CRC(X)) OCRC(Y) 

صفحه 17:
* کد تشخیص خطا نمیتواند در حالت كلي از دستكاري بسته ها * راه حل: کد هاي احراز تمامیت پیام 

صفحه 18:
6 و 0 * تولید یک برچسب با طول ثابت: - وابسته به پیام - لزوماً برگشت پذیر نیست - نیازمند یک کلید مخفي‌مشترک بین طرفین - آنرا به اختصار 11/67 مینامند. نام ‎"Cryptographic Checksum" So‏ * اين برجسب را به ييام اضافه ميكنند * كيرنده خود برجسب يبيام را محاسبه نموده و با برجسب ارسالي مقايسه ميكند. * از تماميت بيام وهويت فرستنده اطمینان حاصل ميشود. . © 

صفحه 19:


صفحه 20:
محرمانگی و تمامیت M TIDE} ‏ام‎ ame M 5 2 Kr K, Compare Ky Fxal MICK)! 6 4 ۶ Message authentication and confidentiality; authentication tied to plaintext EK2IM] 5 ۶ 7 ٩۵۷ “Message authentication and confidentiality: authentication tied ‏موه ما‎ 

صفحه 21:
* آیا 11/62 همانند امضا غیر قابل انکار است؟ خير - امضا با يك كليد عمومي ثبت شده بررسى ميشود ولي كليد 40 خصوصي و مخفي است -بر خلاف امضاء دو طرف قادر به ایجاد ۷1/67[ میباشند. 

صفحه 22:
* ۷۸0 همواره پیامها را به یکط ول ابتمي نكارد. - يك به يك نيست - ييامهاي متفاوت 1/1/8100 يكسان دارند. * براي حمله ميتوان ييام هاي متمايزي يافت كه برجسب يكسان داشته * تصادم: - دو پیم با 11۸6 یکسان 

صفحه 23:
* ويژگيهاي یک 1۷1/۸67 مناسب : 7 با دانستن یک پیام و بر جسب آنء يافتن ييام متفاوتي با برچسب یکسان از لحاظ محاسباتی ناممکن باشد. ۱ - توزیع خروجي :1۷1/86 باید یکنواخت باشد تا احتمال اینکه دو پیام تصادفی 1۷167 یکسان داشته باشند. کمینه شود. * نکته: طول برچسب همانند طول کلید در امنیت 116 تاثیر دارد. (بنا به ( 

صفحه 24:
الس | 1 DAA (Data Authentication Algorithm) ¢ ANSI X9.17 , NIST ‏استاندارد‎ * * بر اساس رمز قطعه ايى 10185 و مد كاري ‎CBC‏ * همانند رمز نكاري 00 018). بيام را يردازش كرده و تنها آخرين قطعه را به عنوان برچسب استفاده میکنیم. 

صفحه 25:


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

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

صفحه 28:
* توابع درهم ساز باید یک طرفه باشند. - براي يك « داده شده, باید یافتن 5 به گونه ایی که (11626 = ‎bes th‏ محأسباتی ناممکن باشد. * مقاومت در برابر تصادم (ضعیف) - براي يك « داده شدهء بايد يافتن لا به كونه ايى كه ‎bed JA (y) = HX)‏ محاسباتى ناممكن باشد. * مقاومت در برابر تصادم (قوي» - يافتن * و الا به كونه ايى كه (11)36 > (11)387 از لحاظ محاسباتي ناممكن ‎BSL‏ 

صفحه 29:
* ممکن است ساختار تابع 3 طوري باشد که : - بتوان تعداد محدودي 5 و ۷ یافت به گونه اي که مقادیر تابع تصادم پیدا کنند. (تصادم قوي) - ولي‌براي یک : داده شده همواره نتوان يك لا پیدا کرد بطوریکه < (11)7 ‎potas) A(x)‏ 424( ۲ ارضاشدن شرط تصادم قوي براي یک تابع دشوار تر از ارضاشدن شرط تصالامشعيقمينافلته 7 5 © توابعى كه در برابر تصادم قوي مقاومت كنند امنيت بالاتري دارند 

صفحه 30:
tS ‏توابع درهم‎ : ne * توابع درهم ساز باید یک طرفه باشند. 7 پيچيدگي جستجوي کلمل (آزمون جامع) "2 میباشد. که « طول خروجي تابع است. *؟ مقاومت در برابر تصادم (ضعیف) 7 پيچيدگي جستجوي کلمل (آزمون جامع) "2میباشد * مقاومت در برابر تصادم (قوي) - پيچيدگي جستجوي کلمل (آزمون جامع) 20:5* "ميباشد - دقت كنيد آزمون جامع بيائكر حداكثر امنيت ممكن براي تابع است زيرا ممكن است ‎ay‏ دلیل ضعف طراحي حملات موثرتري نیز امکان پذیر باشد. ‎xD 

صفحه 31:
۲ ۸ let K Compare 7 a ۶ E«(HUD) 0 اگر پیام 1۷1" را بتوان یافت بطوریکه (]۳1)1۷ < (1۷1)] (تصادم ضعیف) را میتولنتوسط 1۷1" جعل مود ۵ 

صفحه 32:
<< Destination B——» <+—— Souree A wp ey 7 cot ۸ ۳ ‏یت‎ ۱ ۱۱۸۱ 7 

صفحه 33:
ف ضما 

صفحه 34:
روشهاي دیگر احراز ‎SS‏ * طرفین راز 5 را مخفیانه به اشتراک گذاشته ‎wil‏ ‏* بدون استفاده از رمزنگاري * كاربرد عملي زياد 4 42 “sD Ga ۷ st ® Hanis) 6 ‘Compare 

صفحه 35:
روشهاي دیگر احراز ‎SS‏ * روش قبل + محرمانگي * رمزتكاري صرفاً براي محرمانكي است. oe WSO, —— 1 | ‏لها‎ ۸ ۵۱۱۱۷۸۸۸۵ sat «01 0 " 4 

صفحه 36:
اعمال مکرر یک تابع فشرده ساز (2106و31 طملهط) اگر تابع فشرده ساز مقاوم در برابر تصادم باشد. تابع درهم ساز نیز همین گونه خواهد بود. توابع معروفي مانند ‎MD5: Message Digest 5‏ ‎SHA-1: Secure Hash Algorithm -1‏ از همین ایده استفاده میکنند. 

صفحه 37:
0 ساختار دروني توابع درهم ‎on‏ * ييام به قطعات * ۷ یک رشته ثابت میباشد. ‎CV,=IV‏ ‎CVi= £(CVi Yi)‏ ‎Hash = CV,‏ ,۷ تقسیم شده است. Initial value thaining Variable ‘th input block compression algorithm, umber of input blocks sngth of hash code -ngth of input block 

صفحه 38:
* برای مطالعه جزییات ساختار توابع به پیوست ها مراجعه فرمایید. 

صفحه 39:
‎So‏ م مايا ‎MD5: Message Digest 5 * ‏- طراحی 1992 توسط * " یکی از سه طراح ‎RSA‏ ۱ * استفاده گسترده در گذشته. اما از کاربرد ‎el‏ کاسته شده است. ‏* ویژگیها: 7 پیام به قطعات 512 بيتي تفسیم میشود ۱ 7 خروجي 128 بيتي 

صفحه 40:
* مقاومت در برابى تصادم (قوی ) تحت حمله آزمون جامع: ۲۳ 7 ام‌وزه امن محسوب نميشود. * حملات کارگ به این الگوریتم یافت شده اند: ‎Berson -‏ سا(1992: حمله تفاضلی به یکدور ا لگوییتم ‎Bosselaers, Boer -‏ ...)93 یافترت صادم هاي مجايي - 120061110 سلل[96: تصادم در تابع ف شرده ساز 

صفحه 41:
«a SHA-1: Secure Hash Algorithm - 1 151۰1995 ‏استانداره‎ - ‏طول ورودي < 254 بيت‎ - طول خروجي 160 بیت - استفاده شده در استاندارد امضاي دیجیتال ‎DSS‏ آمنیت: - مقاومت در براب تصادع (قوی) تحت حمله آزمون جامع: "2 * أمن محسوب میشود در برابر حملات شناخته شده مقاومت بالایی دارد 

صفحه 42:
0 كونه هاي ‎SHA-1‏ * براي سازگاری با ‎۸۸٩5‏ نسخه هاي زير نيز استاندارد شده اند: SHA -384 , SHA-512. SHA-256 - Seoul @Dbits 89 6۶ Sb block size wuxwessaye or or 999 989 ale ale 002 002 bu teasth (en) 2 car ale ماه 4ات CBs CAS 

صفحه 43:
توابع درهم ساز مهم: ‎1٩1۳171۷610‏ * طراحي در اروپا در سال 1997 ؟ مشخصات همانند 5۳۸-1 * قابل مقایسه با 8۳1-1 از لحاظ امنیت و سرعت ؟ سرعت هر ذو تقریباً نم ‎MD5‏ 

صفحه 44:
و ار ۱2/۱9/۰۰ MDS SHAT RIPEMD-160 sas 64 (4 rounds of 16) 80 (4 rounds of 20) 160 (5 paired rounds of 16) ] ۰ ‏لس لس‎ Digest length Basic unit of processing ‘Number of steps Maximum message size 

صفحه 45:
* ]۳1۷ یک گوریتملحراز هویتهیام لست * ,۲121۸6 ساسا روشي بولي ترکیبک ردن‌کلید مخفي‌با | لگوريتمهاي دوهم‌ساز فعلي میب‌اشد. * برای تولید چکیده پیغام از توابع درهم استفاده شده است - در مقابل استفاده از رمزهاي قطعه ای - بدلیل مزاياي عملي توابع درهم ساز 

صفحه 46:
* ۳1۷86 جزو مازوماتپیاده سازي 960 1۳ میب‌اشد. * 711۷۸0 به طور گسترده لستفادم میشود (مثلا89) 

صفحه 47:
11۷18)0]: لهدلفطرلحی استفاده از توابع درهم ساز بدون تغییر آنها پشتيباني از توابع درهم ساز متنوع * حفظ کارایی و سرعت تابع درهم ساز به کار گرفته شده * استفاده ساده از کلید * طراحي روشن و بدون ابهام 

صفحه 48:
‎A‏ : تابع‌درهم‌ساز به کار گرفته شده - : 24 ييام ورودى 7 ک: کلید مخفی - >1* : کلید مخفي كه يك دنبله صفر به لزإضافه شده لست - 1820 : تكرار يشته 00110110 - 0080 : تکرار پشته 01011010 ‎HMAC, = H[(K* © opad) || H[(K* © ipad) ||‏ [[ 1 

صفحه 49:
‎ash‏ لول« ‎9 ‏ده‎ ‎BLA @ pad) (11 ‏لسك‎ ‘pad to b bits: ¥ ¥ So ¥ ‏تس‎ ‎4 ‎ ‎H[(K* © ipad) || M ]] ‎ ‎ ‎ ‎ ‎H[(K* @ opad) | ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 50:
Precomputed Computed per message 1 ۳ ۳ Yo see Via WV att ot Hash ۳ ۳ ۱ opad Const dois ¥ + Se 3 5 sits : bits سح Figure 9.11 Efficient Implementation of HMAC. 

صفحه 51:
* ارتباط دقیق بین امنیت تابع در هم ساز با امنیت ‎FIMAC‏ ‏اثبات شده است. * مقاومت 111/800 در برابر حمله روز تولد از تابع در هم ساز به كار كرفته شدهء بيشتر است. - استفاده از ‎MD5‏ در هنكام نياز به سرعت بيشتر مجاز است. 

صفحه 52:


صفحه 53:
حداقل مقدار * چقدر است به نحوي که در يك گروه ‏ نفري احتمال اينکه دو نفر در يك روز به دنیا آمده باشند بیش از 5 باشد؟ 

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

صفحه 55:
70 60 50 40 30 20 10 08 07 06 04 03 02 0 4 

صفحه 56:
* در میان 23 نفر. احتمال یافتن دو نفر که در یک روز متولد شده اند بیش از 9050 میباشد. 

صفحه 57:
۴ تعمیم مسئله: حداقل 6 چقدر است به نحوي که با احتمال بیش از 5 يك تكرار در 6 عنصر داشته باشیم به نحوي که هر عنصر مقاديري در بازة 1 تا 2 بتواند اختيار كند؟ با تعميم حل قبلي مي توان به دست آورد كه ‎k=1.18 *n09 = n05‏ n= 365 > k=23 

صفحه 58:
° مبناي ریاضی ‎LH gb =‏ "2 خروجي ممکن را در نظر بگيريد(خروجي 1 بيتي) 1 را به 6 ورودي تصادفي اعمال کنیم و خروجي‌را مجموعه >( در نظر مي گيريم. به همین ترتیب مجموعه ۷ را تشکیل مي‌دهیم. ۱12 اگر ‎k‏ بزرکتر از 2 باشد. احتمال حداقل یک تصادم در بین اعضاي دو مجموعه > و ۷ بیش از 1- مي‌باشد 

صفحه 59:
ممکن است تصور کنید یک 1۸ يا 64 ‎Hash‏ بيتي امن است ام... با حمله روز تولد امنیت از بین میرود: - مهاجم :7پیام معتبر که اساساً هم معنا هستند تولید میکند. 0« طول خروجی 1851 است. — مهاجم همین تعداد پيامهايدلخواه خود را تولید میکند. ( که معناي ساختگي دارند) 1 ۱ ۲ - دودسته پیام مقایسه میشوند تا زوجی یافت شود كه 112511 يكسان داشته باشند. ۱ از کاربر میخواهیم تا ‎play‏ معتبر زوج را امضا نماید. و سپس پیام دلخواه دشمن را جایگزین میکنیم. 

صفحه 60:
Dear Dean Smith, This [ Jetter [ 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 ilson for [ about / almost ] six years. He is an [ outstanding | excellent | researcher of great [talent 1 ability ] known [ worldwide | internationally | for his [ brilliant / creative | insights into [many / a wide variety of | [difficult | challenging ] problems. 

صفحه 61:
Dear Dean South, This | r/ message | is to give my | /) st | 1 1 opinion of Prof Tom Wilson, who i is | Prof Wilson for | six years. He is an | poor / 1 1 not well known in his [| ۷ area |. His research | ha 1 1 5120175 ] 12151) [ key 

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

صفحه 63:
Message length Pada (og? bie (mod 264) $i hits — nic 32 i Si Message ۳ ۱ 4512 bits pet 512 bie ‏سو ديهم‎ Yo ۷ wee > 65 si S12 128, na CV, CVn ‏هك‎ ‎12-bit digest 

صفحه 64:
* Step 1.Appending padding bits - Congruent to 448 modulo 512 * Step 2.Appending length - Length modulo 64 - L*512-bit, N * 32 bit - Mf[i] : i,, word * Step 3.Initialize MD buffer - Four 32-bit register (A B C D), little endian ۰ ۸ - 1 = EFCDAB89 98BADCFE * D = 10325476 

صفحه 65:
* Step 4.Process message in 512-bit blocks - Four rounds ۰ Each round has a different primitive function, F, G, H andI * Use one-fourth of T[i] * Ti] = 2°°* abs(sin(i)) 

صفحه 66:
g(h,c,d) (b *c) * (-b* d) (b* d) * (c* =d) beced © © )5 " -0( Primitive function 9 F(b,c,d) G(b,c,d) H(b,c,d) I(b,c,d) 

صفحه 67:
CVvo =IV ‏)یرلاگ حر لا‎ ۷ 4 RELYg REuLYg REolYg RFAYg CV 4H) where IV = initial value of the ABCD buffer Y,= the qth 512-block of the message. 2 the number of blocks CV,- chaining variable processed with the the gth block of the message RE,= round function using primitive logical function X MD = final message digest value SUM,)~ Addition module 2? performed separatedly on each pair of words of the two inputs. 

صفحه 68:
MD5 Compression * X[i] is used once, during one step - p,(i) = (1 + 5i) mod 16 ۵ - P,(i) = (5 + 3i) mod 16 ‏ند‎ ‎- P,(i) = 7i mod 16 * Each step, only 4 bytes is updated 

صفحه 69:
SHA-1 

صفحه 70:
‎١555‏ اجاح ‎* Step 1. Appending padding bits ‎* Step 2. Append length ‎٠ Step 3. Initialize MD buffer - Five 32-bit registers, E = 0 - Big-endian 

صفحه 71:
SHA-1 Logic _ * Step 4. Process message in 512-bit blocks - Four rounds of 20 steps * Step 5. Output RED 

صفحه 72:
۳۵-1 ae K, is a additive constant varying across rounds 

صفحه 73:
0 ۴۰ ae ۱۱۹۵۵۵ 512 bits —_____» Were Wena Won We We Me Se Wo Mp Yq | | 0 ‏رن‎ (or) wa +e 3 + Wr ۲۷ ۷ ۰ Wi ‎Wes + Wes + Wes)‏ + و5۱0۷ ديللا ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 74:
RIPEMD 

صفحه 75:
_RIPEMD-160 Logic _ * Step 1. Appending padding bits ¢ Step 2. Append length ¢ Step 3. Initialize MD buffer - Same value is used in SHA-1 - Little-endian 

صفحه 76:
Ye * Step4. Processing message ee - 10 rounds of 16 steps 3 - Five primitive functions ۰ a * fy, fy fy fe f ci ~ Nine additive constant omy ~ Addition is involves a 53 rotation Se * Step5 .Output 

صفحه 77:
RIPEMD Compression fale. y.2) = (x foley. 7TPRPBEP EET Pema aa ‏هار ره‎ pe apps eC OT TC 201 ‏م | م | م‎ 7 Tight = 75 35 oe ‏چام‎ 1 (i) = 9i+ 5 (mod 16) Towa 1 [ Rene 7 | Wow 7 1 0 ws |e right ] 2۳-32 ] 2۳۰3 ] 2۳-5 

صفحه 78:
RIPEMD Design decision _ * Two parallel lines are used - Increase complexity of finding collisions between rounds * Two lines use same logic - Simplicity - Difference * Additive constants * Order of primitive functions * Order of processing of message block * Use five words, and rotation of the C word 

صفحه 79:
RIPEMD Design decision _ ¢ Permutations - Effect that two word that are close in one round are relatively far apart in the next * Circular left - Range from 5 to 15 - Different amounts for the five rounds - Not have special pattern (not be divisible by 32) - Not too many shift should be divisible by 4 

کدهاي احراز تماميت پيام و توابع درهم ساز بهروز تركالداني ‏ladani@eng.ui.ac.ir 1 پيش در آمد • در اين فصل روشهاي حفظ پيام در برابر تغييرات ناخواسته و شناسايي صحت محتواي پيامها مطالعه ميشوند. • ابزارها: – کدهاي احراز هويت پيام – توابع درهم ساز • چهارچوب مطالعاتي رمزنگاري کليد خصوصي ميباشد. 2 فهرست مطالب • مفاهيم اوليه • رمزنگاري کليد خصوصي و کدهاي تشخيص خطا • کد هاي احراز تماميت پيام • اصول توابع درهم ساز • توابع درهم ساز مهم • HMAC 3 احراز تماميت پيام چيست؟ • اطمينان از: – تماميت پيام؛ يعني پيام دريافتي دستکاري نشده است: – بدون تصحيح، – بدون درج، – بدون حذف – پيام از جانب فرستنده ادعا شده ارسال شده است 4 Adversary EVE Bob 01 10 1 .. 1 . محرمانگي Shared Network تماميت پيام Alice 5 اهميت تماميت پيام در بسياري از کاربرد ها ،مث ً ال تراکنشهاي بانکي ،اينکه ارتباطات مخفيانه باشند اهميت زيادي ندارد ولي اينکه محتواي آنها قابل اعتماد باشند از اهميت بسيار باالتري بر خوردار است. 6 يک نکته • رمزنگاري مرسوم (کليد خصوصي): – کدهاي احراز تماميت پيام – احراز تماميت پيام • رمزنگاري کليد عمومي: – امضاي ديجيتال – احراز تماميت پيام – عدم انکار 7 موضوع اين فصل ايده اساسي • طرفين يک کليد مخفي به اشتراک بگذارند. • ارسال هر پيام ،به همراه يک برچسب که تابعي است از: – کليد مخفي و متقارن – پيام • به طوري که: – بدون دانستن کليد توليد اين برچسب نا ممکن باشد. – با تغيير پيام ،برچسب کام ً ال تغيير کند. 8 راه کارهاي احراز تماميت پيام • رمزنگاري کليد خصوصي • استفاده از توابع درهم ساز براي احراز تماميت پيام • کد احراز تماميت پيام – همه ميتوانند پيام را بخوانند ،ولي تنها صاحب کليد مخفي ميتواند تماميت آن را بررسي کند. 9 رمزنگاري کليد خصوصي براي احراز تماميت پيام • فرستنده پيام را رمز ميکند. • اگر متن رمز شده دستکاري شود هنگام رمز گشايي به متن واضح نامفهوم (درهم و برهم) ميرسيم. • گيرنده ،بعد از رمز گشايي چک ميکند که آيا پيام مفهوم است يا نه؟ 10 مشکالت رمزنگاري • بررسي مفهوم بودن محتوي همواره آسان نيست: – در حالت کلي نوعي افزونگي يا ساختار دروني مورد انتظار را جستجو ميکنند. – بررسي قواعد زبان (فارسي ،انگليس ي) ...، – دشواري خودکارسازي فرآيند چک کردن .... • هنگام ارسال داده – اگر داده ها خود تصادفي به نظر برسند ،يعني از ساختار دروني خاصي تبعيت ننمايند ،بررسي محتوي تقريباً ناممکن است • راه حل :استفاده از کدهاي تشخيص خطا – مثال :يک بيت به انتهاي پيام اضافه نماييم ،به گونه ايي که تعداد بيتهاي يک زوج شود. – يک کد متداول CRC 11 کدهاي تشخ]يص خطا • تابع Fيک کد تشخيص خطا است – اضافه نمودن “ دنباله بررسي قالب ” ،FCS ،توسط تابع F – يک مثال از تابع ، Fکد CRCمي باشد. • گيرنده ،بعد از رمز گشايي چک ميکند که آيا “ دنباله بررسي قالب “ محاسبه شده توسط F با برچسب پيام مطابقت دارد يا نه؟ 12 نا امن بودن کدهاي تشخ]يص خطا1- • کدهاي تشخيص خطا مانند CRCبراي تشخيص خطاي حاصل از نويز در کاربردهاي مخابراتي طراحي شده اند. – نويز: – تغييرات غير هوشمندانه و غير عمدي – دشمن: – تغييرات هوشمندانه و عمدي • حمالت موفقي به الگوريتمهايي که از کدهاي تشخيص خطا استفاده ميکردند ،صورت پذيرفته است. – مثال :پروتکل IEEE 802.11 13 پروتکلIEEE 802.11 • براي امنيت مخابرات سيار – الگوريتم رمزنگاري دنباله ايي RC4و کد تشخيص CRC متن رمزشده C = متن واضح P ‏Checksum + )c(M 14 )RC4(iv,k پيام M ‏ = متن واضح P ‏Checksum + )F(M )RC4(iv,k ‏ پيام M متن رمز شده C ضعف پروتکلIEEE 802.11 • براي امنيت مخابرات سيار – الگو ريتم رمزنگاري RC4و کد تشخيص CRC ]ت • CRCيکا]]لگو ر]يتم خ]طي ا]س : • )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 15 تصحيح غير مجاز بسته ب]]رچ]سبCRC-32 …………10110 ‏XOR ‏XOR پيام ……………………………………011010010100 …………………………………………………………101101110101 …………11011 ……………………………………110111100001 …………00110 ……………………………………010000000000 …………11101 ……………………………………100111100001 بسته دستکاري شده 16 )RC4k(CRC(XY)) = RC4K(CRC(X)) CRC(Y ‏RC4 نتيجه گيري • کد تشخيص خطا نميتواند در حالت کلي از دستکاري بسته ها جلوگيري کند. • راه حل :کد هاي احراز تماميت پيام 17 کد هاي احراز تماميت پيام • توليد يک برچسب با طول ثابت: – – – – وابسته به پيام لزوماً برگشت پذير نيست نيازمند يک کليد مخفي مشترک بين طرفين آنرا به اختصار MACمينامند .نام ديگر “”Cryptographic Checksum • اين برچسب را به پيام اضافه ميکنند • گيرنده خود برچسب پيام را محاسبه نموده و با برچسب ارسالي مقايسه ميکند. • از تماميت پيام و هويت فرستنده اطمينان حاصل ميشود. 18 کد هاي احراز تماميت پيام تماميت 19 کد هاي احراز تماميت پيام محرمانگي و تماميت 20 !FAQ-MAC • آيا MACهمانند امضا غير قابل انکار است؟ – خ ير – امضا با يک کليد عمومي ثبت شده بررسي ميشود ولي کليد MACخصوصي و مخفي است – بر خالف امضاء ،دو طرف قادر به ايجاد MACميباشند. 21 امنيت MAC • MACهموار]ه] پ]]يام]ها را ب]]ه يکط]ولث]]اب]تم]ي ن]]گارد. – يک به يک نيست – پيامهاي متفاوت MACيکسان دارند. • براي حمله ميتوان پيام هاي متمايزي يافت که برچسب يکسان داشته باشند. • تصادم: – دو پيام با MACيکسان 22 ويژگيهاي MAC • ويژگيهاي يک MACمناسب : – با دانستن يک پيام و بر چسب آن ،يافتن پيام متفاوتي با برچسب يکسان از لحاظ محاسباتي ناممکن باشد. – توزيع خروجي MACبايد يکنواخت باشد تا احتمال اينکه دو پيام تصادفي MACيکسان داشته باشند ،کمينه شود. • نکته :طول برچسب همانند طول کليد در امنيت MACتاثير دارد( .بنا به حمله روز تولد) 23 کداحراز تماميت پيام DAA • )DAA (Data Authentication Algorithm • استاندارد NISTو ANSI X9.17 • بر اساس رمز قطعه ايي DESو مد کاري CBC • همانند رمز نگاري ،CBCپيام را پردازش کرده و تنها آخرين قطعه را به عنوان برچسب استفاده ميکنيم. 24 DAA )متن واضح (تقسيم شده به قطعات K P1 P2 P3 + + + DES DES K DES DES K DES DES PN … … K + DES DES MAC 25 توابع درهم ساز • تابع يك‌طرفه، • طول ورودي متغير • طول خروجي ثابت (نگاشت از فضاي بزرگتر به فضاي كوچكتر) • در حالت کلي ،کليد ي در کار نيست! 26 امنيت توابع درهم ساز-ايده کلي • نگاشت پيامهاي طوالني به رشته هاي کوتاه به گونه ايي که: – يافتن پيامهاي متفاوتي که به يک رشته يکسان نگاشته شوند دشوار باشد. – به اين رشته عصاره يا چکيده پيام ميگوييم. 27 امنيت توابع درهم ساز • توابع درهم ساز بايد يک طرفه باشند. – براي يک hداده شده ،بايد يافتن xبه گونه ايي که ) h = H(xاز لحاظ محاسباتي ناممکن باشد. • مقاومت در برابر تصادم (ضعيف) – براي يک xداده شده ،بايد يافتن yبه گونه ايي که ) H(y) = H(xاز لحاظ محاسباتي ناممکن باشد. • مقاومت در برابر تصادم (قوي) – يافتن xو yبه گونه ايي که ) H(y) = H(xاز لحاظ محاسباتي ناممکن باشد 28 مقايسه تصادم قوي و ضعيف • ممکن است ساختار تابع Hطوري باشد که : – بتوان تعداد محدودي xو yيافت به گونه اي که مقادير تابع تصادم پيدا کنند. (تصادم قوي) – ولي براي يک xداده شده همواره نتوان يک yپيدا کرد بطوريکه = )H(y )( H(xتصادم ضعيف) ‏ارضاشدن شرط تصادم قوي براي يک تابع دشوار تر از ارضاشدن شرط تصادم ضعيف ميباشد. ‏توابعي که در برابر تصادم قوي مقاومت کنند امنيت باالتري دارند 29 امنيت توابع درهم ساز :پيچيدگي حمله • توابع درهم ساز بايد يک طرفه باشند. – پيچيدگي جستجوي کا]مل (آزمون جامع) 2nميباشد ،که nطول خروجي تابع است. • مقاومت در برابر تصادم (ضعيف) – پيچيدگي جستجوي کا]مل (آزمون جامع) 2nم يباشد • مقاومت در برابر تصادم (قوي) با کمک حمله روز تولد – پيچيدگي جستجوي کا]مل (آزمون جامع) n *20.5م يباشد – دقت کنيد آزمون جامع بيانگر حداکثر امنيت ممکن براي تابع است زيرا ممکن است به دليل ضعف طراحي ،حمالت موثرتري نيز امکان پذير باشد. 30 توابع درهم ساز و رمز نگاري متقارن: تماميت اگر پيام ’Mرا بتوان يافت بطوريکه )’( H(M) = H(Mتصادم ضعيف) Mرا م]يت ]وا]نت]]وس]ط ’Mج]علن]]مود  31 توابع درهم ساز و رمز نگاري متقارن: محرمانگي و تماميت 32 توابع درهم ساز و رمز نگاري نا متقارن: امضاء 33 روشهاي ديگر احراز تماميت پيام • طرفين راز sرا مخفيانه به اشتراک گذاشته اند. • بدون استفاده از رمزنگاري • کاربرد عملي زياد 34 روشهاي ديگر احراز تماميت پيام • روش قبل +محرمانگي • رمزنگاري صرفاً براي محرمانگي است. 35 ساختار دروني تابع درهم ساز :ايده اساسي • اعمال مکرر يک تابع فشرده ساز • اگر تابع فشرده ساز مقاوم در برابر تصادم باشد ،تابع درهم ساز نيز همين گونه خواهد بود. • توابع معروفي مانند • MD5: Message Digest 5 • SHA-1: Secure Hash Algorithm -1 از همين ايده استفاده ميکنند. ()Ralph Merkle 36 ساختار دروني توابع درهم ساز2- پيام • پيام به قطعات Yiتقسيم شده است. • IVيک رشته ثابت ميباشد. ‏CV0=IV )CVi= f(CVi-1,Yi-1 ‏Hash = CVL 37 توجه • براي مطالعه جزييات ساختار توابع به پيوست ها مراجعه فرماييد. – MD5 – SHA-1 – RIPMED 38 توابع درهم ساز مهمMD5 : • MD5: Message Digest 5 – طراحي 1992توسط “وستيران ر” ،يک ي از سه طراح ‏RSA • استفاده گسترده در گذشته ،اما از کاربرد آن کاسته شده است. • ويژگيها: – پيام به قطعات 512بيت ي تقسيم ميشود – خروجي 128بيت ي 39 امنيت MD5 • مقاومت در برابر تصادم (قوي) تحت حمله آزمون جامع264 : – امروزه امن محسوب نميشود. • حمالت کارگر به اين الگوريتم يافت شده اند: – Bersonس]]ا]ل :1992ح]مله ت]]فاض]لي ب]]ه يکدور ا]]لگور]يت]]م – Boerو Bosselaersس]]ا]ل :93ياف]تنت]]صاد]م هاي م]جاز]ي – Dobbertinس]]ا]ل :96ت]]صاد]م در ت]]اب]ع ف]]شرد]ه] س]]از 40 توابع درهم ساز مهمSHA-1 : • SHA-1: Secure Hash Algorithm – 1 – – – – استاندارد NIST، 1995 طول ورودي < 264بيت طول خروجي 160بيت استفاده شده در استاندارد امضاي ديجيتال DSS • امنيت: – مقاومت در برابر تصادم (قوي) تحت حمله آزمون جامع280 : • امن محسوب ميشود – در برابر حمالت شناخته شده مقاومت بااليي دارد 41 SHA-1 گونه هاي : نسخه هاي زير نيز استاندارد شده اندAES • براي سازگاري با SHA -384 وSHA-512، SHA-256 – a l g o ri t h m SHA-1 SHA-256 SHA-384 SHA-512 bit length 160 256 384 512 b l o ck s i ze m a x m e s s a g e 512 2^64 512 2^64 1024 2^128 1024 2^128 s e cu ri t y 80b i t s 128b i t s 192b i t s 256b i t s 42 توابع درهم ساز مهمRIPEMD : • طراحي در اروپا در سال 1997 • مشخصات همانند SHA-1 • قابل مقايسه با SHA-1از لحاظ امنيت و سرعت • سرعت هر دو تقريباً نصف MD5 43 MD5،SHA-1، RIPEMD-1 مقايسه 44 HMAC-1 • HMACيکا]]لگور]ي]تما]حراز هويتپ]]يام ا]س]ت • HMACا]ساسًا رو]شي ب]]را]ي ت]]رک]يبک]]رد]نک]]ليد م]خفي ب]]ا ا]]لگوريتمهاي در]هم س]]از ف]]علي م]يب]]اشد. • براي توليد] چکيده پيغام ،از توابع درهم استفاده شده است – در مقابل استفاده از رمزهاي قطعه اي – بدليل مزاياي عملي توابع درهم ساز 45 HMAC-2 • HMACجزو م]لزو]ماتپ]]ياد]ه] س]]از]ي IPSecميب]]اشد. • HMACب]ه ط]ور گ]]سترد]ه] ا]س]تفاد]ه] م]يش]ود ً (م]ثال)SSL 46  :HMACا]هدا]فط]را]حي • • • • • 47 استفاده از توابع درهم ساز بدون تغيير آنها پشتيباني از توابع درهم ساز متنوع حفظ کارايي و سرعت تابع درهم ساز به کار گرفته شده استفاده ساده از کليد طراحي روشن و بدون ابهام  :HMACا]]لگوريت]]م : Hت]]اب]ع در]هم س]]از ب]]ه ک]]ار گ]]رف]ته ش]]ده] – M :پيام ورودي – :Kک]ليد م]خفي – : +Kک]ليد م]خفي ک]]ه يک د]ن]با]]له ص]]فر ب]]ه آ]نا]ضاف]ه ش]]ده] ا]س]ت – : ipadت]]کرار ر]ش]ته 00110110 – : opadت]]کرار ر]ش]ته 01011010 || )HMACK = H[(K+  opad) || H[(K+  ipad ]] M 48 پيام H[(K+  ipad) || M ] H[(K+  opad) || H[(K+  ipad) || M ]] 49 50  :HMACا]م]نيت • ارتباط دقيق بين امنيت تابع در هم ساز با امنيت HMAC اثبات شده است. • مقاومت HMACدر برابر حمله روز تولد از تابع در هم ساز به کار گرفته شده ،بيشتر است. – استفاده از MD5در هنگام نياز به سرعت بيشتر مجاز است. 51 پيوست ها 52 پارادکس روز تولد • حداقل مقدار kچقدر است به نحوي كه در يك گروه kنفري احتمال اينكه دو نفر در يك روز به دنيا آمده باشند بيش از 0.5باشد؟ 53 پارادکس روز تولد • تعداد حاالت ممكن به نحوي كه 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 54 پارادکس روز تولد 55 پارادکس روز تولد • در ميان 23نفر ،احتمال يافتن دو نفر که در يک روز متولد شده اند بيش از %50ميباشد. 56 پارادکس روز تولد • تعميم مسئله :حداقل kچقدر است به نحوي كه با احتمال بيش از 0.5يك تكرار در kعنصر داشته باشيم به نحوي كه هر عنصر مقاديري در بازة 1تا nبتواند اختيار كند؟ • با تعميم حل قبلي مي توان به دست آورد كه: ‏k=1.18 * n0.5 = n0.5 ‏n= 365  k=23 57 پارادکس روز تولد • مبناي رياضي – تابع Hبا ‏m 2 خروجي ممکن را در نظر بگيريد(خروجي mبيت ي) Hرا به kورودي تصادفي اعمال کنيم و خروجي را مجموعه Xدر نظر مي گيريم .به همين ترتيب مجموعه Yرا تشکيل مي دهيم. اگر kبزرگتر از 2m/ 2 باشد ،احتمال حداقل يک تصادم در بين اعضاي دو مجموعه Xو Yبيش از ½ مي باشد 58 حمله روز تولد • ممکن است تصور کنيد يک MACيا Hash 64بيت ي امن است اما... • با حمله روز تولد امنيت از بين ميرود: – – – – 59 ‏m تتت2پ يام معتبر که اساس]اً هم معنا هستند توليد ميکند m .طول مهاجم 2 خروجي Hashاست. مهاجم همين تعداد پ يامهاي دلخواه خود را توليد ميکند ( .که معناي ساختگي دارند) دو دسته پيام مقايسه ميشوند تا زوجي يافت شود که Hashيکسان داشته باشند. از کاربر ميخواهيم تا پيام معتبر زوج را امضا نمايد ،و سپس پيام دلخواه دشمن را جايگزين ميکنيم. )مثالي از حمله (نمونه معتبر 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. 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 [ 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. 61 ساختار داخلي توابع درهم ساز 62 MD5 63 MD5 Logic • Step 1.Appending padding bits – Congruent to 448 modulo 512 • Step 2.Appending length – Length modulo 64 – L * 512-bit, N * 32 bit – M[i] : ith word • Step 3.Initialize MD buffer – Four 32-bit register (A B C D), little endian • • • • A = 67482301 B = EFCDAB89 C = 98BADCFE D = 10325476 64 MD5 Logic • Step 4.Process message in 512-bit blocks – Four rounds • Each round has a different primitive function, F, G, H and I • Use one-fourth of T[i] • T[i] = 232 * abs(sin(i)) 65 MD5 درg تابع بولي Round Primitive function g(b,c,d) g (b  c)  (b  1 F(b,c,d) d) 2 G(b,c,d) (b  d)  (c  d) 3 4 H(b,c,d) I(b,c,d) bcd c  (b  d) 66 MD5 Logic • Step 5. Output 67 MD5 Compression Function • X[i] is used once, during one step – ρ2(i) = (1 + 5i) mod 16 – Ρ3(i) = (5 + 3i) mod 16 – Ρ4(i) = 7i mod 16 • Each step, only 4 bytes is updated 68 SHA-1 69 SHA-1 Logic • Step 1. Appending padding bits • Step 2. Append length • Step 3. Initialize MD buffer – Five 32-bit registers, E = C3D2E1F0 – Big-endian 70 SHA-1 Logic • Step 4. Process message in 512-bit blocks – Four rounds of 20 steps • Step 5. Output 71 SHA-1 Compression Function Kt is a additive constant varying across rounds 72 SHA-1 Compression Function Wt = S1(Wt-16 + Wt-14 + Wt-8 + Wt-3) 73 RIPEMD 74 RIPEMD-160 Logic • Step 1. Appending padding bits • Step 2. Append length • Step 3. Initialize MD buffer – Same value is used in SHA-1 – Little-endian 75 RIPEMD-160 Logic • Step4. Processing message – 10 rounds of 16 steps – Five primitive functions • f1, f2, f3, f4, f5 – Nine additive constant – Addition is involves a rotation • Step5 .Output 76 RIPEMD Compression function π (i) = 9i + 5 (mod 16) 77 RIPEMD Design decision • Two parallel lines are used – Increase complexity of finding collisions between rounds • Two lines use same logic – Simplicity – Difference • Additive constants • Order of primitive functions • Order of processing of message block • Use five words, and rotation of the C word 78 RIPEMD Design decision • Permutations – Effect that two word that are close in one round are relatively far apart in the next • Circular left – – – – Range from 5 to 15 Different amounts for the five rounds Not have special pattern (not be divisible by 32) Not too many shift should be divisible by 4 79