حمله تصادم

حمله تصادم در رمزنگاری، حمله تصادم روی یک رشته هش رمزنگاری، تلاش می‌کند برای پیدا کردن دو ورودی اختیاری که مقدار هش یکسانی را تولید می‌کنند، مانند یک حمله تصادم. برخلاف حمله preimage، نه مقدار هش و نه یکی از ورودی مشخص شده نیست.
دو نوع حمله تصادم وجود دارد:
حمله برخورد:
یافتن دو پیام‌های دلخواه و مختلف m1 و m2 به طوری که: (hash(m1) = hash(m2
حمله تصادم-پیشوند برگزیده:
با توجه به دو پیشوند P1 وp2، دو ضمائم M1 و M2 که:(hash(p1 ∥ m1) = hash(p2 ∥ m2)
(که در آن ∥ است عملگر الحاق است.)
حمله تصادم کلاسیک
از نظر ریاضیات یعنی ؛ یافتن دو پیام‌های دلخواه و مختلف m1 و m2 به طوری که: (hash(m1) = hash(m2 است.
در یک حمله تصادم کلاسیک، حمله کننده ؛ هیچ کنترلی بر محتوای هر کدام از پیامها ندارد. اما آنها بصورت خودسرانه توسط الگوریتم انتخاب شده‌اند. بسیار شبیه به کلید رمزهای متقارن، در معرض حملات آزمون جامع هستند.
هر تابع رمزنگاری هش، ذاتا در تصادم، با استفاده از یک حمله تولد آسیب پذیر است. با توجه به مسئله تولد، این حملات بسیار سریع‌تر از حملات آزمون جامع خواهد بود. هش n بیتی را می‌توان در زمان 2n/2 شکست (ارزیابی تابع هش). بیشتر حملات کارآمد با به کارگیری تحلیل به توابع هش خاصی امکان پذیر است. هنگامی که یک حمله تصادم کشف شده و سریع‌تر از حمله تولد یافت می‌شود تابع هش شکسته شده‌است. در NIST رقابت تابع هش تا حد زیادی ناشی از حملات تصادم منتشر شده در برابر دو تابع هشی که معمولا استفاده می‌شود MD51و SHA-1.
حملات تصادم علیه MD5 بهبود یافته‌است به حدی که، تنها چند ثانیه بر روی یک کامپیوتر به طور منظم طول می‌کشد. در تصادم هش ایجاد شده، معمولا طول ثابت و تا حد زیادی بدون ساختار هستند. بنابراین به طور مستقیم نمی‌تواند برای حمله به فرمت‌های سند گسترده یا پروتکل‌ها استفاده شود . با این حال، راه حل‌های سوء استفاده از ساختارهای پویایی که در حال حاضر در بسیاری از فرمت وجود دارد امکان پذیر است. به این ترتیب، دو سند ساخته می‌شود که ممکن است مقدار هش یکسانی داشته باشند.
حمله تصادم-پیشوند برگزیده
توسعه حمله -پیشوند برگزیده مربوط به تابع هش Merkle–Damgård است. در این حالت، مهاجم می‌تواند دو سند مختلف را انتخاب کند، و سپس ارزش محاسبه شده را که در نتیجه تمام اسناد مقدار هش یکسانی دارد را اضافه کند، این حمله بسیار قوی‌تر از یک حمله تصادم کلاسیک است.
از نظر ریاضیات، با توجه به دو پیشوند P1 وp2، دو ضمائم M1 و M2 که:(hash(p1 ∥ m1) = hash(p2 ∥ m2)
در سال ۲۰۰۷ حمله تصادم-پیشوند برگزیده در برابرMD5 کشف شد، نیاز به حدود ۲۵۰ ارزیابی از تابع MD5 داشت. این مقاله همچنین دو گواهی X.509 را برای دامنه‌های مختلف، با تصادم مقادیر هش نشان می‌دهد. این به این معنی است که صدور ی گواهی مرجع برای ثبت نام می‌تواند سند رسمی برای یک دامنه بخواهد؛ و پس از آن گواهی می‌تواند برای جعل هویت دیگر دامنه‌ها مورد استفاده قرار گیرد.
حمله تصادم در دنیای واقعی در دسامبر ۲۰۰۸ منتشر شد ؛ زمانی که یک گروه از محققان امنیتی، گواهی جعلی X.509 که می‌تواند به جعل هویت یک مرجع گواهی، با استفاده از یک حمله پیشوند تصادم علیه تابع هش MD5 مورد استفاده قرار گیرد را منتشر کردند. این بدان معنی است که مهاجم می‌تواند با به عنوان یک مرد میانی، در هر وب سایت SSL امن به جعل آن بپردازد و نتیجه آن، اخلال اعتبار گواهی ساخته شده در هر مرورگر وب برای محافظت از تجارت الکترونیکی است.
گواهی‌ها ی جعلی ممکن است از طرف مقامات مرجع لغو نشود ومی‌توانند زمان انقضا ی جعلی داشته باشند. حتی اگر MD5 شناخته شده بود در سال ۲۰۰۴ بسیار ضعیف می‌بود. مقامات صدور گواهینامه هنوز هم مایل به تایید MD5، گواهی امضا در دسامبر ۲۰۰۸ بودندو و دست کم کد امضای صدور گواهینامه مایکروسافت هنوز هم با استفاده از MD5 در ماه مه ۲۰۱۲ است.
نرم‌افزارهای مخرب شعله ؛ با استفاده از نوع جدیدی از تصادم انتخاب پیشوند؛ به کلاه برداری کد امضای تولید شده توسط یک گواهینامه مایکروسافت (که هنوز هم از الگوریتم MD5 استفاده می‌کند) پرداخت و موفق به حمله شد.
سناریوی حمله
بسیاری از برنامه‌های کاربردی cryptographic، متکی بر تصادم نیستند. در نتیجه حملات تصادم بر روی امنیت آنها تاثیر نمی‌گذارد. به عنوان مثال، هش کردن رمز عبور و HMACs آسیب پذیر نمی‌باشد. برای حمله موفق، مهاجم باید ورودی تابع هش را کنترل کند.
امضای دیجیتال:
از آنجا که الگوریتم‌های امضای دیجیتالی نمی‌توانند مقدار زیادی از داده‌ها را به شکل کارآمد امضا کنند. برای امضا اکثر پیاده سازی با استفاده از یک تابع هش (فشرده ساز)به منظور کاهش مقدار داده‌های تا یک حد ممکن به منظور رسیدن به یک سایز ثابت صورت می‌گیرد. برنامه‌های امضای دیجیتال، اغلب در معرض تصادم هش هستند، مگر اینکه از روش‌های مانند هش تصادفی استفاده شود. توجه داشته ب شید که همه گواهی‌های کلید عمومی، مانند گواهی SSL، بر امنیت امضای دیجیتال تکیه می‌کنند و توسط تصادم هش به خطر میوفتند.
معمولا سناریوی حمله به شکل زیر است:
1. مالوری دو سند مختلف A و B، که دارای مقدار هش یکسان هستند (تصادم) را ایجاد می‌کند.
2. مالوری سند A را باری الیس می‌فرستد وبه انچه به توافق رسیده‌اند سند می‌گویند، آن را امضا می‌کند و برای مالوری می‌فرستد.
3. مالوری امضای فرستاده شده توسط آلیس در سند A را برای سند B کپی می‌کند.
4. سپس مالوری سندB را به باب می‌فرستد، و ادعا می‌کند که آلیس سند متفاوتی را امضا کرده و از آنجا که امضای دیجیتالی، با سند هش مطابقت دارد، نرم‌افزار باب قادر به تشخیص تغییرنیست.
رمزنگاری تابع هش