حمله ملاقات در میانه

**حمله ملاقات در میانه** (به انگلیسی: Meet-in-the-middle attack یا به اختصار **MITM**) یک نوع حمله  رمزنگاری است مقابل الگوریتم‌های رمزنگاری که متکی بر انجام جندین عملیات رمزنگاری متوالی هستند. این حمله دلیل اصلی استفاده نشدن دی‌ای‌اس دوگانه و شکسته شدن کلید دی‌ای‌اس سه‌گانه (۱۶۸ بیتی) به وسیله حمله کننده ای با 256 حافظه و 2112 عملیات است.

یک ایده ساده برای افزایش امنیت رمزنگاری یک متن این است که به دفعات با کلید های مختلف رمزگذاری شود. در ابتدا به نظر میرسد که این عمل باعث چند برابر شدن امنیت اطلاعات میشود، با توجه به تعداد دفعاتی که داده رمزگذاری شده، به دلیل اینکه اگر اطلاعات n بار با کلید های k بیتی رمزگذاری شده باشند، جستجو برای پیدا کردن همه ترکیب های مخلف کلید ها 2k.n هزینه دارد.

MITM حمله‌ای است که به وسیله نگهداری متوسط مقدارها در عملیات های رمزگشایی و استفاده کردن از آنها زمان پیدا کردن کلید های رمزگشایی را کاهش میدهد. البته این کاهش زمان در ازای استفاده از حافظه‌ی بیشتر است.

این حمله برای پیدا کردن کلید ها از متن رمزگذاری شده و متن آشکار ترکیب تعداد زیادی تابع(یا قطعه رمزگذاری) استفاده میکند به طوری که حرکت از تابع اول مانند حرکت برعکس از تابع آخر است. برای مثال با اینکه دی‌ای‌اس دوگانه اطلاعات را با دو کلید 56 بیتی مختلف رمزگذاری میکند، میتواند با 257 عملیات رمزگذاری و رمزگشایی شکسته شود.

MITM چند بعدی (multidimensional MITM یا MD-MITM) از تعداد زیادی حمله MITM به صورت همزمان استفاده میکند به طوری که ملاقات در مکان های گوناگون تابع شکل میگیرد.

## تاریخچه

ویتفیلد دیفی و مارتین هلمن ابتدا این حمله را در سال 1977 پیشنهاد دادند.
آنها برای شکستن یک طرح رمزی با دو کلید مختلف ازین روش استفاده کرند تا قفل را تنها در دو برابر زمان لازم برای شکستن قفلی با یک کلید، بشکنند.

در سال 2011  Bo Zhu و  Guang Gong روی حمله ملاقات در میانه چند بعدی تحقیق کردند و به وسیله آن حمله های جدیدی روی رمزگذاری قطعه‌ای هایی از جمله GHOST ، KTANTAN و Hummingbird-2 پیشنهاد دادند.

## ملاقات در میانه ( یک بعدی )
فرض کنید شخصی بخواهد به طرح رمزگذاری با مشخصات زیر برای متن آشکار *P* و متن رمزگذاری شده *C* حمله کند.
:\begin{align}
                         C &= \mathit{ENC}_{k_2}(\mathit{ENC}_{k_1}(P)) \\
                         P &= \mathit{DEC}_{k_1}(\mathit{DEC}_{k_2}(C)) \\
\end{align}
در اینجا  *ENC* تابع رمزگذاری و  *DEC* تابع رمزگشایی است که به صورت *ENC* -1  تعریف میشود و *k*1 و *k*2 کلید ها هستند.

یک راه ساده ( brute force ) این است که برای هر *k*2 متن رمزگذاری شده را رمزگشایی کنیم و همه مقدار های جدید را با کلید *k*1 دوباره رمزگشایی کنیم که در کل 2*k*1 × 2*k*2 یا 2*k*1+*k*2 عملیات نیاز دارد.

حمله ملاقات در میانه از یک روش به صرفه تر استفاده میکند. اگر *C* را با *k<sub>2</sub>* رمزگشایی کنیم به عبارت زیر میرسیم.
:\begin{align}
                         C &= \mathit{ENC}_{k_2}(\mathit{ENC}_{k_1}(P)) \\
                         \mathit{DEC}_{k_2}(C) &= \mathit{DEC}_{k_2}(\mathit{ENC}_{k_2}[\mathit{ENC}_{k_1}(P)]) \\
                         \mathit{DEC}_{k_2}(C) &= \mathit{ENC}_{k_1}(P) \\
\end{align}

حمله کننده میتواند برای همه مقدار های ممکن کلید *k*1 مقدار (* ENC*k1(*P* و برای همه مقدار های ممکن کلید *k*2 مقدار  (* DEC**k*2(*C*  را حساب کند که این فرایند در کل  2*k*1 + 2*k*2 ( اگر اندازه دو کلید برابر باشد 2*k*1+1) عملیات نیاز دارد. اگر هر کدام از مقادیر (* ENC*k1(*P* مطابق با یکی از مقدار های (* DEC**k*2(*C* باشد، آنگاه جفت کلید *k*1 و *k*2 احتمالاً کلید های درست هستند. به کلید هایی که احتمالاً درست هستند کلید کانید گفته میشود. حمله کننده میتواند با امتحان کردن کلید های کاندید به وسیله یک جفت متن رمزگذاری شده و متن آشکار جدید کلید درست را پیدا کند.

حمله ملاقات در میانه یکی از دلایلی است که استاندارد رمزنگاری داده‌ها (Data Encryption Standard یا DES) به جای دی‌ای‌اس دوگانه با دی‌ای‌اس سه‌گانه جایگزین شد. یک حمله کننده میتواند ازین روش استفاده کند و دی‌ای‌اس دوگانه را با 257 عملیات و 256 حافظه بشکند که پیشرفت خیلی کمی نسبت به دی‌ای‌اس است.

دی‌ای‌اس سه‌گانه از کلید با طول سه برابر (168 بیت) استفاده میکند که با این حمله در 2112 عملیات و 256 حافظه شکسته میشود. به همین دلیل این طرح رمزگذاری امن در نظر گرفته میشود.

### الگوریتم MITM
ابتدا عبارات زیر را محاسبه میکنیم
*\mathit{SubCipher}_1=\mathit{ENC}_{f_1}(k_{f_1},P),\; \forall  k_{f_1} \in  K 
*: و همه \mathit{SubCipher}_{1}  ها را با   k_{f_1}  متناظر هرکدام در مجموعه A ذخیره میکنیم.
*\mathit{SubCipher}_1=\mathit{DEC}_{b_1}(k_{b_1},C),\; \forall k_{b_1} \in K 
*: و هر \mathit{SubCipher}_1  جدید را در مجموعه A جست و جو میکنیم.

در هر مرحله اگر یک جفت منطبق پیدا کردیم، *k**f*1و*k**b*1 را به عنوان یک جفت کلید کاندید در جدول T نگه میداریم. در نهایت همه جفت کلید های در جدول T را روی یک متن آشکار و رمزگذاری جدید (P, C) امتحان میکنیم، اگر کلید درست نبود الگوریتم MITM را روی (P, C) جدید تکرار میکنیم.

### مرتبه زمانی و حافظه MITM
اگر اندازه هر کلید را *k* فرض کنیم، این حمله در 2k+1 عملیات رمزگذاری و رمزگشایی و ( O(2 k حافظه برای نگهداری نتایج به اتمام میرسد. در مقابل حمله ساده (brute force) به 2k×2 عملیات و (O(1  حافظه نیاز دارد.

## حمله ملاقات در میانه چند بعدی
با وجود اینکه الگوریتم ملاقات در میانه یک بعدی میتواند به صرفه باشد ولی یک حمله پیچیده تری نیز طراحی شده است به نام حمله ملاقات در میانه چند بعدی ( multidimensional meet-in-the-middle attack یا **MD-MITM**). این حمله زمانی به صرفه تر است که اطلاعات با بیشتر از 2 کلید مختلف رمزگذاری شده باشند. این حمله به جای ملاقات در میانه (یک جا در میان دنباله) تلاش میکند تا با محاسبات رو به جلو و رو به عقب از مکان های مختلف رمز به تعداد بیشتری حالت میانی برسد.
تابع های رمزگذاری و رمزگشایی به شکل زیر هستند:

:  C=\mathit{ENC}_{k_n}(\mathit{ENC}_{k_{n-1}}(...(\mathit{ENC}_{k_1}(P))...)) 
:  P=\mathit{DEC}_{k_1}(\mathit{DEC}_{k_2}(...(\mathit{DEC}_{k_n}(C))...))
که متن آشکار P چندین بار رمزگذاری شده تا به متن C تبدیل شود.

حمله ملاقات در میانه چند بعدی برای رمزگشایی GHOST استفاده شده است و نشان داده شده که یک حمله 3 بعدی میتواند مدت زمان حمله را مقدار قابل توجهی کاهش دهد.

## منابع

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