حمله تصادم

**حمله تصادم**  در رمزنگاری، حمله تداخل روی  یک رشته هش رمزنگاری، تلاش می‌کند برای پیدا کردن دو ورودی اختیاری که   مقدار هش  یکسانی را تولید می‌کنند، مانند یک حمله تصادم. برخلاف حمله preimage، نه مقدار هش و نه یکی از ورودی مشخص شده نیست.

دو نوع حمله  تصادم وجود دارد:

حمله برخورد:
یافتن دو پیام‌های دلخواه  و مختلف   m1 و m2 به طوری که: (hash(m1) = hash(m2

حمله تصادم-پیشوند برگزیده:
با توجه به دو پیشوند P1 وp2،  دو ضمائم M1 و M2 که:(hash(p1 ∥ m1) = hash(p2 ∥ m2)

(که در آن ∥ است عملگر الحاق است.)

## حمله تصادم کلاسیک
از نظر ریاضیات یعنی ؛ یافتن دو پیام‌ (رشته) دلخواه  و مختلف   m1 و m2 به طوری که: (hash(m1) = hash(m2 است.

در یک حمله تصادم کلاسیک، حمله‌کننده ؛ هیچ کنترلی بر محتوای هر کدام از پیامها ندارد. اما آن‌ها به صورت خودسرانه توسط الگوریتم انتخاب شده‌اند. بسیار شبیه به  کلید رمزهای متقارن، در معرض حملات  بروت فورس (به انگلیسی: brute force) هستند.

هر تابع رمزنگاری هش، ذاتاً در تصادم، با استفاده از یک حمله تولد آسیب‌پذیر است. با توجه به مساله تولد، این حملات بسیار سریع تر از حملات بروت فورس (به انگلیسی: brute force) خواهد بود. هش n بیتی  را می‌توان در زمان 2n/2  شکست (ارزیابی   تابع هش). بیشتر حملات کارآمد با به کارگیری تحلیل به توابع هش خاصی امکان‌پذیر است. هنگامی که یک حمله تصادم کشف شده و سریع تر از حمله تولد یافت می‌شود تابع هش شکسته شده‌است. در NIST رقابت تابع هش تا حد زیادی ناشی از حملات تصادم منتشر شده در برابر دو تابع هشی که  معمولاً استفاده می‌شود MD5[1]و 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  را به باب می‌فرستد، و ادعا می‌کند  که آلیس سند متفاوتی را امضا کرده و از آنجا که امضای دیجیتالی، با سند هش مطابقت دارد، نرم‌افزار باب   قادر به تشخیص تغییرنیست.

## جستارهای وابسته
* رمزنگاری تابع هش

## منابع

http://en.wikipedia.org/wiki/Collision_attack

رده:حمله‌های رمزنگاری
رده:درهم‌سازهای رمزنگارانه