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

حمله ملاقات در میانه (به انگلیسی: Meet-in-the-middle attack یا به اختصار MITM) یک نوع حمله رمزنگاری است مقابل الگوریتم‌های رمزنگاری که متکی بر انجام جندین عملیات رمزنگاری متوالی هستند. این حمله دلیل اصلی استفاده نشدن دی‌ای‌اس دوگانه و شکسته شدن کلید دی‌ای‌اس سه‌گانه (۱۶۸ بیتی) به وسیله حمله کننده ای با 2⁵⁶ حافظه و 2¹¹² عملیات است.[1]

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

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

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

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

تاریخچه

ویتفیلد دیفی

مارتین هلمن

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

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

ملاقات در میانه ( یک بعدی )

فرض کنید شخصی بخواهد به طرح رمزگذاری با مشخصات زیر برای متن آشکار P و متن رمزگذاری شده C حمله کند.

{\begin{aligned}C&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(P))\\P&={\mathit {DEC}}_{k_{1}}({\mathit {DEC}}_{k_{2}}(C))\\\end{aligned}}

در اینجا ENC تابع رمزگذاری و DEC تابع رمزگشایی است که به صورت ENC^-1 تعریف میشود و k₁ و k₂ کلید ها هستند.

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

حمله ملاقات در میانه از یک روش به صرفه تر استفاده میکند. اگر C را با k₂ رمزگشایی کنیم به عبارت زیر میرسیم.

{\begin{aligned}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{aligned}}

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

حمله ملاقات در میانه یکی از دلایلی است که استاندارد رمزنگاری داده‌ها (Data Encryption Standard یا DES) به جای دی‌ای‌اس دوگانه با دی‌ای‌اس سه‌گانه جایگزین شد. یک حمله کننده میتواند ازین روش استفاده کند و دی‌ای‌اس دوگانه را با 2⁵⁷ عملیات و 2⁵⁶ حافظه بشکند که پیشرفت خیلی کمی نسبت به دی‌ای‌اس است. [3] دی‌ای‌اس سه‌گانه از کلید با طول سه برابر (168 بیت) استفاده میکند که با این حمله در 2¹¹² عملیات و 2⁵⁶ حافظه شکسته میشود. به همین دلیل این طرح رمزگذاری امن در نظر گرفته میشود. [4][1]

تصویر حمله ملاقات در میانه یک بعدی

تصویر حمله ملاقات در میانه دو بعدی

الگوریتم 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₁وk_b₁ را به عنوان یک جفت کلید کاندید در جدول T نگه میداریم. در نهایت همه جفت کلید های در جدول T را روی یک متن آشکار و رمزگذاری جدید (P, C) امتحان میکنیم، اگر کلید درست نبود الگوریتم MITM را روی (P, C) جدید تکرار میکنیم.

مرتبه زمانی و حافظه MITM

اگر اندازه هر کلید را k فرض کنیم، این حمله در 2^k+1 عملیات رمزگذاری و رمزگشایی و ( O(2 ^k حافظه برای نگهداری نتایج به اتمام میرسد. در مقابل حمله ساده (brute force) به 2^k×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 بعدی میتواند مدت زمان حمله را مقدار قابل توجهی کاهش دهد.

منابع

Blondeau, Céline. "Lecture 3: Block Ciphers" (PDF). CS-E4320 Cryptography and Data Security.
^ Diffie, Whitfield; Hellman, Martin E. (June 1977). "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" (PDF). Computer. 10 (6): 74–84. doi:10.1109/C-M.1977.217750.
Zhu, Bo; Guang Gong (2011). "MD-MITM Attack and Its Applications to GOST, KTANTAN and Hummingbird-2". eCrypt.
Moore, Stephane (November 16, 2010). "Meet-in-the-Middle Attacks" (PDF): 2.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[:1-1] Blondeau, Céline. "Lecture 3: Block Ciphers" (PDF). CS-E4320 Cryptography and Data Security.

[2] Diffie, Whitfield; Hellman, Martin E. (June 1977). "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" (PDF). Computer. 10 (6): 74–84. doi:10.1109/C-M.1977.217750.

[3] Zhu, Bo; Guang Gong (2011). "MD-MITM Attack and Its Applications to GOST, KTANTAN and Hummingbird-2". eCrypt.

[:0-4] Moore, Stephane (November 16, 2010). "Meet-in-the-Middle Attacks" (PDF): 2.