مروری بر الگوریتم MD5 و نقاط ضعف آن

الگوریتم (MD5 (Message Digest 5 یکی از معروف‌ترین روشهای تولید چکیده یک طرفه (One-Way hash) است که در سال 1992 توسط Ron Rivest ابداع شده است (RFC-1320-1321).
چنین الگوریتمی، با دریافت رشته دلخواه M (با طول رشته دلخواه)، نگاشت (H(M را به گونه‌ای محاسبه می‌نماید که به ازای تمام مقادیر M، خروجی دارای طول ثابتی ‌‌‌باشد.عموما در دنیای تکنولوژی نرم‌افزار، از خروجی تابع (H(M با نام چکیده پیام (Message Digest) نام برده می‌شود.

یک الگوریتم چکیده یک طرفه، دارای دو ویژگی اساسی است:

  1. با داشتن خروجی (H(M، نمی‌توان به سادگی رشته M را محاسبه نمود.
  2. با داشتن رشته مفروض M1، پیدا نمودن رشته دلخواه M2، به گونه‌ای که (H(M1)=H(M2 باشد، کار بسیار مشکلی است.
دو رکن اساسی فوق به این معنی هستند که یک الگوریتم چکیده پیام، بازگشت ناپذیر (یکطرفه) بوده و احتمال وجود تصادم در الگوریتم آن (یعنی وجود دو رشته متفاوت که چکیده مشابهی داشته باشند) بسیار پایین است.

هر چند که تا کنون ویژگی اول در مورد الگوریتمهای چکیده پیام نقض نشده است، اما در مورد ویژگی دوم، نقض مکرر آن در نسلهای مختلف الگوریتمهای تولید چکیده پیام، موجب ظهور مبحثی تحت عنوان Collision Detection شده است.

در مورد الگوریتم MD5، اولین بار در سال 1993 (یک سال پس از معرفی MD5 بوده) Bert Boer و Antoon Bosselaers روشی را برای محاسبه دو رشته متفاوت با چکیده پیام مشابه پیدا نمودند. لازم به ذکر است که در حال حاضر، الگوریتم‌های کشف تصادم در MD5 آنقدر پیشرفته هستند که در مدت زمان 1 ساعت، می‌توان چندین رشته متفاوت پیدا نمود که چکیده یکسانی داشته باشند.

البته ذکر مطالب فوق به این معنی نیست که این الگوریتم فاقد امنیت است، بلکه با توجه به میزان امنیت مورد نیاز در الگوریتمهای رمزنگاری مورد استفاده، امنیت آن کافی نیست. در حال حاضر هم هنوز وبسایتها و نرم‌افزارهای بسیاری همچنان از این روش در CA های خود استفاده می‌کنند، اما اگر قرار بر حفظ امنیت در حد اعلای خود باشد، به جای این الگوریتم از الگوریتمهای دیگری مانند SHA-512 و MD6 استفاده خواهد شد.

MD5 یک الگوریتم 128 بیتی است. یعنی که حداکثر تعداد رشته‌های متفاوتی که می‌توان بدون بروز تصادم در این الگوریتم بدست آورد، 2 به توان 128، حالت است. الگوریتمهایی مانند SHA-512 و MD6 نیز که نسخه ارتقاء یافته MD5 است، 512 بیتی هستند.

اما فکر می‌کنید چرا با وجود الگوریتمهای چکیده 512 بیتی و یا حتی بزرگتر از آن، همچنان از روش MD5 هم استفاده می‌شود.؟!
پاسخ ساده است، “هزینه اجرای الگوریتم”.

هر چقدر که میزان پیچیدگی عملیات نگاشت در الگوریتم مورد نظر افزایش یابد، هزینه اجرای آن نیز افزایش خواهد یافت.
با توجه به اینکه الگوریتمهای چکیده پیام، با توجه به کاربرد آنها معمولا به دفعات بسیار بسیار زیادی در طول پروسه یک نرم‌افزار اجرا خواهند شد، میزان بار اضافه آن بر کارایی برنامه باید قابل قبول باشد. در نتیجه با توجه به میزان اهمیت کدگذاری در برنامه و همچنین کارایی مورد انتظار از آن، در مورد انتخاب الگوریتم چکیده مناسب تصمیم‌گیری خواهد شد.

اما ساختار الگوریتم MD5 چگونه است:

  1. رشته ورودی M دریافت شده و به بیتهای تشکیل دهنده آن تجزیه می‌شود.
  2. با توجه به طول رشته (بیتی) در صورت نیاز عملیات لایه گذاری (Padding) بر روی آن انجام می‌شود. این عملیات به این صورت است که تا زمانی که باقیمانده تقسیم طول رشته بر 512 برابر با 448 گردد، به تعداد مورد نیاز، صفر به آن الحاق می‌گردد. (در نهایت پس از همه صفرها یک “1” هم اضافه می‌شود)
  3. طول واقعی رشته M، به صورت یک عدد 64 بیتی، به انتهای خروجی مرحله دوم الحاق می‌گردد.
  4. یک تابع Hash که به چهار تابع A تا D تقسیم شده است، بر روی بافر موجود اعمال شده و نتیجه آن در 128 بیت (چهار ثبات 32 بیتی) ذخیره می‌گردد.
  5. بافر خروجی، به صورت بلاکهای 512 بیتی، به بخش اصلی الگوریتم که یک تابع فشرده‌سازی (نگاشت) است ارسال می‌گردد.
  6. نتیجه تمام مراحل تابع فشرده سازی، به صورت یک رشته 128 بیتی محاسبه می‌گردد. این رشته همان خروجی الگوریتم MD5 است.

البته عملیات موجود در توابع Hash و نگاشت، پیچیده‌تر از چیزی است که ذکر شد، اما ساختار کلی این الگوریتم، دقیقا طبق مراحل ذکر شده است.

اکثر روشهای ایجاد تصادم در MD5، از نقاط ضعف مربوط به عملیات Padding و سادگی توابع Hash موجود در مرحله فشره سازی استفاده نموده و با تزریق بافر اضافی به بافر اولیه، بافر جدیدی بدست می‌آورند که چکیده آن ثابت باقی می‌‌ماند.
یکی از مثالهای معروفی که در زمینه تصادم در MD5 وجود دارد، دو رشته 128 بایتی زیر هستند:

d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70
d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70
همانطور که می‌بینید دو رشته فوق در کاراکترهای قرمز رنگ، با یکدیگر تفاوت دارند، اما اگر هر کدام از آنها را به صورت hex در یک فایل باینری جداگانه ذخیره نموده و چکیده MD5 هر کدام را محاسبه نمایید، خواهید دید که برای هر دو فایل، مقدار چکیده زیر بدست می‌آید.
“79054025255fb1a26e4bc422aef54eb4”
وقتی در چنین رشته‌های کوتاهی وجود تصادم در الگوریتم به اثبات می‌رسد، بروز آن در فایلهای بزرگتر ساده‌تر خواهد بود.

به عنوان نکته پایانی، لازم به ذکر است که در حال حاضر روشهایی برای ایجاد تصادم در MD5 ابداع شده‌اند که قادرند تا با دریافت دو فایل دلخواه، بافری را محاسبه کنند که با اضافه کردن آن به انتهای یکی از فایلها، خروجی Hash یکسانی برای هر دو فایل محاسبه شود. کاملا واضح است که می‌توان با استفاده از چنین روشهایی، فایلهای مختلفی را با file-checksum مشابهی تولید نمود.

About محمد شمس

برنامه‌نویس، طراح انیمیشن و علاقمند به هوش مصنوعی

9 Comments

  1. عالی بود. ممنونم ازت

  2. سلاام باز هم ممنووون واقعا عالی بود

    من همیشه به وبلاگ شما سر میزنم و استفاده میکنم

    موفق باشید

  3. سطح مطالب فوق العاده بالا و بسیار لذت بردم

  4. مطلب جالبی بود و به اطلاعاتم اضافه شد.
    موفق باشی

  5. مطلب خوبی بود
    بندهن یز در زمینه ی آسیب پذیری های md5 قبلا مطالعات زیادی انجام داده ام که با خواندن مطلب پربار شما بسیاری از آنها مرور شد

  6. خیلی عالی بود … ممنون (لبخند) … آیا در زمینهء امنیت در php هم مطلب دارید؟
    sahar_diamond11@yahoo.com

  7. خیر در این زمینه تجربه ندارم.

  8. ممنون عالی بود
    مرسی

  9. سلام
    ممنون از مطالب عالیتون
    با اجازتون بخشی از مطالبتون را باذکر لینک و نام شما در مقاله آورده ام.
    با سپاس فراوان

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *


× 6 = 54