موضوع مقاله: ساختار مرکل–دمگارد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ساختار مرکل–دمگارد | مقدمه: در رمزنگاری، تابع درهم ساز مرکل - دمگارد، روشی برای ایجاد توابع درهم ساز مقاوم در برابر برخورد، از طریق توابع فشرده‌سازی یک طرفه در برابر برخورد استGoldwasser, S. | ## بخش 1: ساختار مرکل–دمگارد | این ساختار در طراحی بسیاری از الگوریتم‌های درهم ساز معروف همچون MD5، SHA-1 و SHA -2 استفاده شده‌است. رالف مرکل و ایوان دمگارد به‌طور مستقل ثابت کردند که: در صورتی اگر از طرح لایه گذاری مناسب استفاده شود و تابع فشرده‌سازی مقاوم باشد، تابع درهم سازی نیز مقاوم برخورد خواهد شد.I. تابع درهم ساز مرکل - دمگارد برای ایجاد یک ورودی شامل تعداد ثابتی از عدد ثابت (به عنوان مثال ۵۱۲ یا ۱۰۲۴) عمل می‌کند. این به این دلیل است که توابع فشرده‌سازی نمی‌توانند ورودی اندازه دل‌خواه را کنترل کنند. سپس تابع درهم ساز، نتیجه را به بلوک‌هایی با اندازه ثابت تقسیم می‌کند، و آن‌ها را دریک زمان با تابع فشرده‌سازی پردازش می‌کنند، هر بار یک بلوک ورودی را با خروجی راند قبلی ترکیب کرد. برای اطمینان از ساخت و ساز، مارکل و دمگارد پیشنهاد کردند که پیامها با لایه ای که طول پیام اصلی را رمزگذاری می‌کند، قرار بگیرند. (IV یک مقدار ثابت است (الگوریتم یا پیاده‌سازی خاص) برای هر بلوک پیغام، تابع فشرده‌سازی (یا فشرده‌سازی) f نتیجه را تا اینجا می‌گیرد، آن را با بلوک پیغام ترکیب می‌کند و یک نتیجه میانی تولید می‌کند. (برای مثال، به قسمت پایین مراجعه کنید) برای مقاوم تر شدن بیشتر هش، نتیجه نهایی گاهی اوقات از طریق تابع نهایی تغذیه می‌شود. تابع نهایی می‌تواند چندین هدف از قبیل فشرده کردن یک حالت داخلی بزرگ‌تر را داشته باشد (آخرین نتیجه) به یک اندازه هش کوچک‌تر، یا تضمین یک اثر مخلوط سازی بهتر و اثر بهینه تری بر روی بیت‌های جمع هش باشد. تابع نهایی اغلب با استفاده از تابع فشرده‌سازی ساخته می‌شود؛ که در بعضی از اسناد اصطلاحات متفاوتی به کار رفته‌است: عمل لایه گذاری «نهایی کردن» نامیده می‌شود. | ## بخش 2: ساختار مرکل–دمگارد | مشخصات امنیتی محبوبیت این ساخت و ساز به دلیل واقعیتی است که توسط مرکل و دمگارد ثابت شده‌است که اگر عملکرد یک طرفه فشرده سازی f در برابر برخورد مقاومت داشته باشد، بنابراین عملکرد هش با استفاده از آن نیز ساخته شده‌است. متأسفانه، این ساخت و ساز چندین ویژگی نامطلوب نیز دارد: دومین حمله مقدماتی علیه پیام‌های طولانی همیشه بسیار کارآمدتر از حمله جستجوی فراگیر است. «حملات هردینگ»، که ترکیبی از ساخت و ساز آبشار برای یافتن مالتی‌کالیژن (مشابه موارد فوق) را با برخوردهای یافت شده برای یک پیشوند داده شده (برخورد پیشوند انتخاب شده) می‌باشد، این امر اجازه ساخت و ساخت اسناد و مدارک بسیار خاص را می‌دهد، و این کار را می‌توان برای کار بیشتر نسبت به پیدا کردن یک برخورد انجام داد.John Kelsey and Tadayoshi Kohno. با توجه به ضعف ساختاری سازه‌های مرکل - دمگارد به خصوص مشکل گسترش طول و حملات مالتی‌کالیژنی، استفان لاکس استفاده از هش لوله گسترده را پیشنهاد کرد، به جای این که به ساختار مرکل دمگارد، درهم سازی لوله گسترده بسیار شبیه ساختار مرکل - دمگارد است اما دارای اندازه داخلی بزرگ‌تر است، به این معنی که طول بیتی که از داخل استفاده می‌شود بزرگ‌تر از طول بیت خروجی است. اگر یک هش از n بیت مورد نظر باشد، تابع فشرده‌سازی f مقدار 2n بیت از ارزش زنجیره‌ای و m بیت پیام را می‌گیرد و این مقدار را به خروجی 2n بیت فشرده می‌کند. بنابراین، در یک گام نهایی، یک تابع فشرده‌سازی ثانویه آخرین مقدار هش درونی (2n) را به مقدار هش نهایی (n بیت) فشرده می‌کند. ایده اصلی ساخت هش این است که نیمی از مقدار زنجیره قبلی را جلو بکشید تا آن را به خروجی تابع فشرده‌سازی XOR کنید. با استفاده از همان تابع f مانند قبل، مقادیر زنجیره n بیتی و n + m بیت پیام را می‌گیرد. لایه گذاری مرکل - دمگارد همان‌طور که در مقدمه ذکر شد، طرح لایه گذاری مورد استفاده در ساخت‌وساز برای اطمینان از امنیت طرح باید به دقت انتخاب شود. لازم است ذکر شود که برای حصول اطمینان از ایمن بودن ساختمان مرکل - دمگارد، شرایط کافی برای طرح لایه گذاری وجود دارد: M یک پیشوند برای pad(M) می‌باشد. | ## بخش 3: ساختار مرکل–دمگارد | با این شرایط، ما در تابع درهم سازی مرکل - دمگارد برخورد می‌یابیم درست زمانی که در تابع فشرده‌سازی اساسی برخورد برخورد می‌کنیم؛ بنابراین، در صورت ایمن بودن عملکرد فشرده سازی اساسی، ساخت و ساز مرکل - دامگارد به‌طور قابل ملاحظه ای ایمن است. مثال‌های لایه‌گذاری عرضی به عنوان مثال، بیایید بگوییم پیامی که باید هش شود "HashInput" است و اندازه بلوک عملکرد فشرده سازی ۸ بایت (۶۴ بیت) است. بنابراین ما دو بلوک مانند این داریم: اما این کافی نیست زیرا این بدان معنی است که پیام‌های مجزا که با همان داده‌ها شروع می‌شوند و با صفر یا بیشتر بایت از داده‌های ثابت لنت ختم می‌شوند، با استفاده از همان بلوک‌های مشابه، تولید همان جمع نهایی نهایی را وارد تابع کاهش می‌کنند. از آنجایی که لایه‌گذاری ثابت به‌طور کلی از صفر ساخته می‌شود، اولین بیت لنت به‌طور اجباری به "۱" تغییر می‌یابد. در مثال ما، چیزی شبیه به این می‌گیریم: برای مقاوم شدن بیشتر هش، طول پیام را می‌توان در یک بلوک اضافی اضافه کرد. بنابراین در مثال ما، سه بلوک مانند این را بدست می‌آوریم: برای جلوگیری از ابهام، مقدار طول پیام باید خود در برابر حملات پسوند طول مقاوم باشد. اکثر پیاده‌سازی‌های متداول از یک اندازه بیت ثابت (به‌طور کلی ۶۴ یا ۱۲۸ بیت در الگوریتم‌های مدرن) و یک موقعیت ثابت در انتهای آخرین بلوک برای رمزگذاری مقدار طول پیام استفاده می‌کنند (برای توضیحات، شبه کد SHA-1 را ببینید)، اگرچه این امر مطابق با منطق ارائه شده در این صفحه، از قرار دادن طول در ابتدای پیام، در جایی که خود مسئولیت حمله به پسوند ندارد، کمتر مؤثر است، اما قبل از شروع بررسی تعداد داده‌های در حال بررسی، یا قرار دادن چندین مقدار از این مقادیر، در جهت بلوک، در جریان بررسی، به دانش نیاز دارد. [ نیاز به استناد ] اکنون این مقدار کمی هدر رفته‌است زیرا به معنی ایجاد یک بلوک کامل برای یک مقدار طول است؛ بنابراین یک بهینه‌سازی سرعت جزئی وجود دارد که اکثر الگوریتم‌های هش از آن استفاده می‌کنند. اگر فضای کافی در بین صفرهای منتهی به آخرین بلوک وجود داشته باشد، در عوض می‌توان مقدار طول را در آنجا پر کرد. بیایید در اینجا بگوییم که، در مثال ما مقدار طول روی ۵ بایت (۴۰ بیت) کدگذاری می‌شود، بنابراین در بلوک نهایی به عنوان "۰۰۰۰۹" قرار می‌گیرد، نه فقط "۹" یا با صفرهای غیر ضروری بسیار زیاد. | ## جمع‌بندی | مثل این: توجه داشته باشید که ذخیره طول پیام به خارج از باند در ابرداده یا در غیر این صورت در آغاز پیام تعبیه شده‌است، یک کاهش مؤثر در مقابل حمله طولانی مدت می‌باشد.