ساختار مرکل–دمگارد
در رمزنگاری، تابع درهم ساز مرکل - دمگارد، روشی برای ایجاد توابع درهم ساز ، از طریق در برابر برخورد است. این ساختار در طراحی بسیاری از الگوریتم‌های درهم ساز معروف همچون MD5، SHA-1 و SHA -2 استفاده شده‌است.
ساخت مرکل - دمگارد در پایان‌نامه دکتری رالف مرکل در سال ۱۹۷۹ توصیف شد. رالف مرکل و ایوان دمگارد به‌طور مستقل ثابت کردند که: در صورتی اگر از طرح لایه گذاری مناسب استفاده شود و تابع فشرده‌سازی مقاوم باشد، تابع درهم سازی نیز مقاوم برخورد خواهد شد.
تابع درهم ساز مرکل - دمگارد برای ایجاد یک ورودی شامل تعداد ثابتی از عدد ثابت (به عنوان مثال ۵۱۲ یا ۱۰۲۴) عمل می‌کند. این به این دلیل است که توابع فشرده‌سازی نمی‌توانند ورودی اندازه دل‌خواه را کنترل کنند. سپس تابع درهم ساز، نتیجه را به بلوک‌هایی با اندازه ثابت تقسیم می‌کند، و آن‌ها را دریک زمان با تابع فشرده‌سازی پردازش می‌کنند، هر بار یک بلوک ورودی را با خروجی راند قبلی ترکیب کرد.
برای اطمینان از ساخت و ساز، مارکل و دمگارد پیشنهاد کردند که پیامها با لایه ای که طول پیام اصلی را رمزگذاری می‌کند، قرار بگیرند. به این حالت لایه گذاری طولی یا تقویت مرکل - دمگارد گفته می‌شود.
در نمودار، تابع فشرده‌سازی تک جهتی با f نشان داده می‌شود و دو ورودی طول ثابت را به خروجی همان اندازه به عنوان یکی از ورودی‌ها تبدیل می‌کند. الگوریتم با یک مقدار اولیه شروع می‌شود، بردار مقداردهی اولیه (IV. (IV یک مقدار ثابت است (الگوریتم یا پیاده‌سازی خاص) برای هر بلوک پیغام، تابع فشرده‌سازی (یا فشرده‌سازی) f نتیجه را تا اینجا می‌گیرد، آن را با بلوک پیغام ترکیب می‌کند و یک نتیجه میانی تولید می‌کند. بلوک آخر با صفر به صورت نیاز و بیت با نمایش طول کل پیام اضافه می‌شود. (برای مثال، به قسمت پایین مراجعه کنید)
برای مقاوم تر شدن بیشتر هش، نتیجه نهایی گاهی اوقات از طریق تابع نهایی تغذیه می‌شود. تابع نهایی می‌تواند چندین هدف از قبیل فشرده کردن یک حالت داخلی بزرگ‌تر را داشته باشد (آخرین نتیجه) به یک اندازه هش کوچک‌تر، یا تضمین یک اثر مخلوط سازی بهتر و ی بر روی بیت‌های جمع هش باشد. تابع نهایی اغلب با استفاده از تابع فشرده‌سازی ساخته می‌شود؛ که در بعضی از اسناد اصطلاحات متفاوتی به کار رفته‌است: عمل لایه گذاری «نهایی کردن» نامیده می‌شود.
محبوبیت این ساخت و ساز به دلیل واقعیتی است که توسط مرکل و دمگارد ثابت شده‌است که اگر عملکرد یک طرفه فشرده سازی "f" در برابر برخورد مقاومت داشته باشد، بنابراین عملکرد هش با استفاده از آن نیز ساخته شده‌است. متأسفانه، این ساخت و ساز چندین ویژگی نامطلوب نیز دارد:
با توجه به ضعف ساختاری سازه‌های مرکل - دمگارد به خصوص مشکل گسترش طول و حملات مالتی‌کالیژنی، استفان لاکس استفاده از هش لوله گسترده را پیشنهاد کرد، به جای این که به ساختار مرکل دمگارد، درهم سازی لوله گسترده بسیار شبیه ساختار مرکل - دمگارد است اما دارای اندازه داخلی بزرگ‌تر است، به این معنی که طول بیتی که از داخل استفاده می‌شود بزرگ‌تر از طول بیت خروجی است. اگر یک هش از n بیت مورد نظر باشد، تابع فشرده‌سازی f مقدار 2n بیت از ارزش زنجیره‌ای و m بیت پیام را می‌گیرد و این مقدار را به خروجی 2n بیت فشرده می‌کند.
بنابراین، در یک گام نهایی، یک تابع فشرده‌سازی ثانویه آخرین مقدار هش درونی (2n) را به مقدار هش نهایی (n بیت) فشرده می‌کند. این کار را می‌توان به سادگی با کنار گذاشتن نیمی از خروجی 2n بیتی انجام داد. SHA-512/224 و SHA-512/256 این شکل را می‌گیرند زیرا از نوع SHA-512 مشتق شده‌اند. SHA-384 و SHA-224 به ترتیب به ترتیب از SHA-512 و SHA-256 مشتق شده‌اند، اما عرض لوله آنها بسیار کمتر از "2n است".
توسط Mridul Nandi و نشان داده شده‌است که اگر حالت لوله گسترده را به صورت زیر تقسیم کنیم می‌توان عملکرد هش لوله گسترده را تقریباً دو برابر سریعتر انجام داد: نیمی از آن وارد عملکرد فشرده سازی موفق می‌شود و نیمی دیگر همراه با خروجی آن عملکرد فشرده سازی.
ایده اصلی ساخت هش این است که نیمی از مقدار زنجیره قبلی را جلو بکشید تا آن را به خروجی تابع فشرده‌سازی XOR کنید.
با استفاده از همان تابع f مانند قبل، مقادیر زنجیره n بیتی و n + m بیت پیام را می‌گیرد. با این حال هزینه اضافی ما حافظه اضافه شده برای جلو کشیدن زنجیره قبلی می‌باشد.
همان‌طور که در مقدمه ذکر شد، طرح لایه گذاری مورد استفاده در ساخت‌وساز برای اطمینان از امنیت طرح باید به دقت انتخاب شود. لازم است ذکر شود که برای حصول اطمینان از ایمن بودن ساختمان مرکل - دمگارد، شرایط کافی برای طرح لایه گذاری وجود دارد:
با این شرایط، ما در تابع درهم سازی مرکل - دمگارد برخورد می‌یابیم درست زمانی که در تابع فشرده‌سازی اساسی برخورد برخورد می‌کنیم؛ بنابراین، در صورت ایمن بودن عملکرد فشرده سازی اساسی، ساخت و ساز مرکل - دامگارد به‌طور قابل ملاحظه ای ایمن است.
"به عنوان مثال، بیایید بگوییم پیامی که باید هش شود "HashInput" است و اندازه بلوک عملکرد فشرده سازی ۸ بایت (۶۴ بیت) است." "بنابراین ما دو بلوک مانند این داریم:"
اما این کافی نیست زیرا این بدان معنی است که پیام‌های مجزا که با همان داده‌ها شروع می‌شوند و با صفر یا بیشتر بایت از داده‌های ثابت لنت ختم می‌شوند، با استفاده از همان بلوک‌های مشابه، تولید همان جمع نهایی نهایی را وارد تابع کاهش می‌کنند.
برای جلوگیری از این امر، باید بیت اول داده‌های ثابت پر شده تغییر یابد. از آنجایی که لایه‌گذاری ثابت به‌طور کلی از صفر ساخته می‌شود، اولین بیت لنت به‌طور اجباری به "۱" تغییر می‌یابد.
برای مقاوم شدن بیشتر هش، طول پیام را می‌توان در یک بلوک اضافی اضافه کرد.
برای جلوگیری از ابهام، مقدار طول پیام باید خود در برابر حملات پسوند طول مقاوم باشد. اکثر پیاده‌سازی‌های متداول از یک اندازه بیت ثابت (به‌طور کلی ۶۴ یا ۱۲۸ بیت در الگوریتم‌های مدرن) و یک موقعیت ثابت در انتهای آخرین بلوک برای رمزگذاری مقدار طول پیام استفاده می‌کنند (برای توضیحات، "شبه کد SHA-1 را ببینید")، اگرچه این امر مطابق با منطق ارائه شده در این صفحه، از قرار دادن طول در ابتدای پیام، در جایی که خود مسئولیت حمله به پسوند ندارد، کمتر مؤثر است، اما قبل از شروع بررسی تعداد داده‌های در حال بررسی، یا قرار دادن چندین مقدار از این مقادیر، در جهت بلوک، در جریان بررسی، به دانش نیاز دارد.
اکنون این مقدار کمی هدر رفته‌است زیرا به معنی ایجاد یک بلوک کامل برای یک مقدار طول است؛ بنابراین یک بهینه‌سازی سرعت جزئی وجود دارد که اکثر الگوریتم‌های هش از آن استفاده می‌کنند. اگر فضای کافی در بین صفرهای منتهی به آخرین بلوک وجود داشته باشد، در عوض می‌توان مقدار طول را در آنجا پر کرد.
توجه داشته باشید که ذخیره طول پیام به خارج از باند در ابرداده یا در غیر این صورت در آغاز پیام تعبیه شده‌است، یک کاهش مؤثر در مقابل حمله طولانی مدت می‌باشد. (تا زمانی که نادرستی طول پیام و عمل (checksum) هر دو مورد توجه واقع شوند)