ساختار مرکل–دمگارد
در رمزنگاری، تابع درهم ساز مرکل - دمگارد، روشی برای ایجاد توابع درهم ساز مقاوم در برابر برخورد، از طریق توابع فشرده‌سازی یک طرفه در برابر برخورد است[۱]: 145 . این ساختار در طراحی بسیاری از الگوریتم‌های درهم ساز معروف همچون MD5، SHA-1 و SHA -2 استفاده شده‌است.
ساخت مرکل - دمگارد در پایان‌نامه دکتری رالف مرکل در سال ۱۹۷۹ توصیف شد.[۲] رالف مرکل و ایوان دمگارد به‌طور مستقل ثابت کردند که: در صورتی اگر از طرح لایه گذاری مناسب استفاده شود و تابع فشرده‌سازی مقاوم باشد، تابع درهم سازی نیز مقاوم برخورد خواهد شد.[۳][۴]
تابع درهم ساز مرکل - دمگارد برای ایجاد یک ورودی شامل تعداد ثابتی از عدد ثابت (به عنوان مثال ۵۱۲ یا ۱۰۲۴) عمل می‌کند. این به این دلیل است که توابع فشرده‌سازی نمی‌توانند ورودی اندازه دل‌خواه را کنترل کنند. سپس تابع درهم ساز، نتیجه را به بلوک‌هایی با اندازه ثابت تقسیم می‌کند، و آنها را دریک زمان با تابع فشرده‌سازی پردازش می‌کنند، هر بار یک بلوک ورودی را با خروجی راند قبلی ترکیب کرد.
برای اطمینان از ساخت و ساز، مارکل و دمگارد پیشنهاد کردند که پیامها با لایه ای که طول پیام اصلی را رمزگذاری می‌کند، قرار بگیرند. به این حالت لایه گذاری طولی یا تقویت مرکل - دمگارد گفته می‌شود.
در نمودار، تابع فشرده‌سازی تک جهتی با f نشان داده می‌شود و دو ورودی طول ثابت را به خروجی همان اندازه به عنوان یکی از ورودی‌ها تبدیل می‌کند. الگوریتم با یک مقدار اولیه شروع می‌شود، بردار مقداردهی اولیه (IV. (IV یک مقدار ثابت است (الگوریتم یا پیاده‌سازی خاص) برای هر بلوک پیغام، تابع فشرده‌سازی (یا فشرده‌سازی) f نتیجه را تا اینجا می‌گیرد، آن را با بلوک پیغام ترکیب می‌کند و یک نتیجه میانی تولید می‌کند. بلوک آخر با صفر به صورت نیاز و بیت با نمایش طول کل پیام اضافه می‌شود. (برای مثال، به قسمت پایین مراجعه کنید)
برای مقاوم تر شدن بیشتر هش، نتیجه نهایی گاهی اوقات از طریق تابع نهایی تغذیه می‌شود. تابع نهایی می‌تواند چندین هدف از قبیل فشرده کردن یک حالت داخلی بزرگ‌تر را داشته باشد (آخرین نتیجه) به یک اندازه هش کوچک‌تر، یا تضمین یک اثر مخلوط سازی بهتر و اثر بهینه تری بر روی بیت‌های جمع هش باشد. تابع نهایی اغلب با استفاده از تابع فشرده‌سازی ساخته می‌شود؛ که در بعضی از اسناد اصطلاحات متفاوتی به کار رفته‌است: عمل لایه گذاری «نهایی کردن» نامیده می‌شود.
مشخصات امنیتی ویرایش
محبوبیت این ساخت و ساز به دلیل واقعیتی است که توسط مرکل و دمگارد ثابت شده‌است که اگر عملکرد یک طرفه فشرده سازی f در برابر برخورد مقاومت داشته باشد، بنابراین عملکرد هش با استفاده از آن نیز ساخته شده‌است. متأسفانه، این ساخت و ساز چندین ویژگی نامطلوب نیز دارد:
- دومین حمله مقدماتی علیه پیام‌های طولانی همیشه بسیار کارآمدتر از حمله جستجوی فراگیر است.[۵]
- مالتی‌کالیژن (پیامها زیادی با یک درهم ساز یکسان) را می‌توان تنها با کمی کار بیشتر از برخورد پیدا کرد.[۶]
- «حملات هردینگ»، که ترکیبی از ساخت و ساز آبشار برای یافتن مالتی‌کالیژن (مشابه موارد فوق) را با برخوردهای یافت شده برای یک پیشوند داده شده (برخورد پیشوند انتخاب شده) می‌باشد، این امر اجازه ساخت و ساخت اسناد و مدارک بسیار خاص را می‌دهد، و این کار را می‌توان برای کار بیشتر نسبت به پیدا کردن یک برخورد انجام داد.[۷][۸]
- «حمله گسترش طول»، (Length extension attack): با وجود هش H(x) با ورودی مجهول x، به راحتی می‌توان مقدار H(Pad(x)||Y) را بدست آورد، که Pad همان تابع لایه‌گذاری تابع هش می‌باشد![۹]حمله گسترش طول در واقع برای حمله به تعدادی از برنامه‌های اعتبار سنجی پیام وب مانند برنامه مورد استفاده توسط فلیکر مورد استفاده قرار گرفت.[۱۰]
ساخت لوله گسترده‌ای ویرایش
با توجه به ضعف ساختاری سازه‌های مرکل - دمگارد به خصوص مشکل گسترش طول و حملات مالتی‌کالیژنی، استفان لاکس استفاده از هش لوله گسترده را پیشنهاد کرد،[۱۱] به جای این که به ساختار مرکل دمگارد، درهم سازی لوله گسترده بسیار شبیه ساختار مرکل - دمگارد است اما دارای اندازه داخلی بزرگ‌تر است، به این معنی که طول بیتی که از داخل استفاده می‌شود بزرگ‌تر از طول بیت خروجی است. اگر یک هش از 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 و Souradyuti Paul نشان داده شده‌است که اگر حالت لوله گسترده را به صورت زیر تقسیم کنیم می‌توان عملکرد هش لوله گسترده را تقریباً دو برابر سریعتر انجام داد: نیمی از آن وارد عملکرد فشرده سازی موفق می‌شود و نیمی دیگر همراه با خروجی آن عملکرد فشرده سازی.[۱۲]
ایده اصلی ساخت هش این است که نیمی از مقدار زنجیره قبلی را جلو بکشید تا آن را به خروجی تابع فشرده‌سازی XOR کنید.
با استفاده از همان تابع f مانند قبل، مقادیر زنجیره n بیتی و n + m بیت پیام را می‌گیرد. با این حال هزینه اضافی ما حافظه اضافه شده برای جلو کشیدن زنجیره قبلی می‌باشد.
لایه گذاری مرکل - دمگارد ویرایش
همان‌طور که در مقدمه ذکر شد، طرح لایه گذاری مورد استفاده در ساخت‌وساز برای اطمینان از امنیت طرح باید به دقت انتخاب شود. لازم است ذکر شود که برای حصول اطمینان از ایمن بودن ساختمان مرکل - دمگارد، شرایط کافی برای طرح لایه گذاری وجود دارد:
- M یک پیشوند برای pad(M) می‌باشد.
- اگر |M1| =|M2| ⇐ Pad(M1) =Pad(M2)
- اگر |M1| |M2| ⇐ آخرین بلوک M1 با آخرین بلوک M2 متفاوت است.
با این شرایط، ما در تابع درهم سازی مرکل - دمگارد برخورد می‌یابیم درست زمانی که در تابع فشرده‌سازی اساسی برخورد برخورد می‌کنیم؛ بنابراین، در صورت ایمن بودن عملکرد فشرده سازی اساسی، ساخت و ساز مرکل - دامگارد به‌طور قابل ملاحظه ای ایمن است.
مثال‌های لایه‌گذاری عرضی ویرایش
به عنوان مثال، بیایید بگوییم پیامی که باید هش شود "HashInput" است و اندازه بلوک عملکرد فشرده سازی ۸ بایت (۶۴ بیت) است. بنابراین ما دو بلوک مانند این داریم:
- HashInpu t0000000
اما این کافی نیست زیرا این بدان معنی است که پیام‌های مجزا که با همان داده‌ها شروع می‌شوند و با صفر یا بیشتر بایت از داده‌های ثابت لنت ختم می‌شوند، با استفاده از همان بلوک‌های مشابه، تولید همان جمع نهایی نهایی را وارد تابع کاهش می‌کنند.
- برای مثال، در پیام ما، پیام اصلاح شده "HashInput00" همان پیام اصلی "HashInput" را ایجاد می‌کند.
برای جلوگیری از این امر، باید بیت اول داده‌های ثابت پر شده تغییر یابد. از آنجایی که لایه‌گذاری ثابت به‌طور کلی از صفر ساخته می‌شود، اولین بیت لنت به‌طور اجباری به "۱" تغییر می‌یابد.
- در مثال ما، چیزی شبیه به این می‌گیریم:
- HashInput 1000000
برای مقاوم شدن بیشتر هش، طول پیام را می‌توان در یک بلوک اضافی اضافه کرد.
- بنابراین در مثال ما، سه بلوک مانند این را بدست می‌آوریم:
- HashInput 1000000 00000009
برای جلوگیری از ابهام، مقدار طول پیام باید خود در برابر حملات پسوند طول مقاوم باشد. اکثر پیاده‌سازی‌های متداول از یک اندازه بیت ثابت (به‌طور کلی ۶۴ یا ۱۲۸ بیت در الگوریتم‌های مدرن) و یک موقعیت ثابت در انتهای آخرین بلوک برای رمزگذاری مقدار طول پیام استفاده می‌کنند (برای توضیحات، شبه کد SHA-1 را ببینید)، اگرچه این امر مطابق با منطق ارائه شده در این صفحه، از قرار دادن طول در ابتدای پیام، در جایی که خود مسئولیت حمله به پسوند ندارد، کمتر مؤثر است، اما قبل از شروع بررسی تعداد داده‌های در حال بررسی، یا قرار دادن چندین مقدار از این مقادیر، در جهت بلوک، در جریان بررسی، به دانش نیاز دارد. [ نیاز به استناد ] اکنون این مقدار کمی هدر رفته‌است زیرا به معنی ایجاد یک بلوک کامل برای یک مقدار طول است؛ بنابراین یک بهینه‌سازی سرعت جزئی وجود دارد که اکثر الگوریتم‌های هش از آن استفاده می‌کنند. اگر فضای کافی در بین صفرهای منتهی به آخرین بلوک وجود داشته باشد، در عوض می‌توان مقدار طول را در آنجا پر کرد.
- بیایید در اینجا بگوییم که، در مثال ما مقدار طول روی ۵ بایت (۴۰ بیت) کدگذاری می‌شود، بنابراین در بلوک نهایی به عنوان "۰۰۰۰۹" قرار می‌گیرد، نه فقط "۹" یا با صفرهای غیر ضروری بسیار زیاد. مثل این:
- HashInpu t1000009
توجه داشته باشید که ذخیره طول پیام به خارج از باند در ابرداده یا در غیر این صورت در آغاز پیام تعبیه شده‌است، یک کاهش مؤثر در مقابل حمله طولانی مدت می‌باشد. (تا زمانی که نادرستی طول پیام و عمل (checksum) هر دو مورد توجه واقع شوند)
منابع ویرایش
- کتاب راهنمای رمزنگاری کاربردی توسط منزز، ون اورشوت و وانستون (۲۰۰۱)، فصل ۹.
- مقدمه ای بر رمزنگاری مدرن، توسط جاناتان کاتز و یهودا لیندل. چاپمن و تالار / مطبوعات CRC، اوت ۲۰۰۷، صفحه ۱۳۴ (ساخت و ساز ۴٫۱۳).
- ↑ Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" بایگانی‌شده در ۲۱ آوریل ۲۰۱۲ توسط Wayback Machine. Summer course on cryptography, MIT, 1996-2001
- ↑ R.C. Merkle. Secrecy, authentication, and public key systems. بایگانی‌شده در ۱۴ اوت ۲۰۱۸ توسط Wayback Machine Stanford Ph.D. thesis 1979, pages 13-15.
- ↑ I. Damgård. A Design Principle for Hash Functions. In Advances in Cryptology – CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 416-427.
- ↑ R.C. Merkle. A Certified Digital Signature. In Advances in Cryptology - CRYPTO '89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard, ed, Springer-Verlag, 1989, pp. 218-238.
- ↑ Kelsey, John; Schneier, Bruce (2004). "Second Preimages on n-bit Hash Functions for Much Less than 2^n Work" (PDF) – via Cryptology ePrint Archive: Report 2004/304.
{{cite journal}}: Cite journal requires|journal=(help) - ↑ Antoine Joux.
- ↑ Stevens, Marc; Lenstra, Arjen; de Weger, Benne (2007-11-30). "Nostradamus". The HashClash Project. TU/e. Retrieved 2013-03-30.
- ↑ John Kelsey and Tadayoshi Kohno.
- ↑ Yevgeniy Dodis, Thomas Ristenpart, Thomas Shrimpton.
- ↑ Thai Duong, Juliano Rizzo, Flickr's API Signature Forgery Vulnerability بایگانی‌شده در ۹ آوریل ۲۰۲۱ توسط Wayback Machine, 2009
- ↑ Lucks, Stefan (2004). "Design Principles for Iterated Hash Functions" – via Cryptology ePrint Archive, Report 2004/253.
{{cite journal}}: Cite journal requires|journal=(help) - ↑ Mridul Nandi and Souradyuti Paul.