تابع درهم‌ساز رمزنگارانه

یک تابع درهم‌سازی رمزنگارانه یا تابع هش کریپتوگرافیک نوعی تبدیل است که رشته‌ای طولانی را به عنوان ورودی دریافت می‌کند و رشته‌ای با طول ثابت را خروجی می‌دهد. مقدار هش حاصل، نمایشی از کل محتوای متن یا رشته ورودی است و می‌توان آن را نوعی «اثر انگشت دیجیتالی» برای آن متن به حساب آورد. از توابع درهم‌سازی کریپتوگرافیک برای بررسی صحت پیام‌ها و امضای دیجیتال متون در طیف گسترده‌ای از کاربردها، همچون تصدیق اصالت و تصدیق صحت پیام استفاده می‌شود.
یک تابع درهم‌سازی، یک رشته (یا پیام) را دریافت می‌کند و رشته‌ای با طول ثابت موسوم به خلاصه پیام (message digest) یا اثر انگشت دیجیتال (digital fingerprint) یا هش را تولید می‌نماید. این مقدار نوعی امضا برای جریانی از داده است که محتوای آن را نمایندگی می‌کند.
برای آن که بتوان یک تابع درهم‌سازی را «کریپتوگرافیک» نامید، باید خواص امنیتی مشخصی در آن به تایید برسند. مشخصا تابع درهم‌سازی باید تا حد امکان واجد خاصیت «تصادفی بودن» باشد و در عین حال برای یک متن خاص قطعی بوده و با کارایی بالایی قابل محاسبه باشد. چنانچه هر یک از این موارد از نظر محاسباتی قابل انجام باشد، تابع درهم‌سازی کریپتوگرافیک از امنیت کافی بر خوردار نیست:
یافتن پیام جدیدی که مقدار هش داده شده را تولید نماید
یافتن دو پیام که مقدار هش مساوی هم تولید نمایند (چنین موردی یک تصادم هش خوانده می‌شود)
حمله‌کننده‌ای که بتواند هریک از این دو کار را انجام دهد قادر خواهد بود از آن برای جایگزینی یک متن غیر اصیل به جای متن اصیل استفاده نماید.
توابع مختلفی وجود دارند که از بلوک‌های رمز برای ساخت توابع درهم‌ساز رمزنگارانه استفاده می‌کنند، مخصوصا تابع فشرده سازی یک طرفه.
توابعی که مشابه توابع نام برده شده عمل می‌کنند و غالبا برای رمزگذاری استفاده می‌شوند، همگی به عنوان توابع درهم ساز شناخته می‌شوند، شامل MD4، MD5، SHA-1 و SHA-2 که از بلوک‌های رمزی مانند درست شده‌اند.
یک بلوک رمزی استاندارد مانند AES می‌تواند در جایگاهی از این بلوک‌های رمزی اختیاری قرار بگیرند، که ممکن است زمانی که یک سیستم تعبیه شده نیاز دارد که هر دوی رمزگشایی و درهم‌سازی را با اندازه کد کم و حجم کم سخت‌افزاری انجام دهد، مفید باشد.
به هر حال آن هدف می‌تواند موثر و در ایجاد امنیت ارزشمند باشد. رمزهای موجود در توابع درهم ساز که برای درهم‌سازی استفاده می‌شوند:
آنها از کلیدها و بلوک‌های طولانی، استفاده می‌کنند، بلوک‌ها می‌توانند به‌طور موثر کلیدها را تغییر دهند و برای مقاومت در برابر حملات کلید مرتبط طراحی شده‌اند. رمزهای با اهداف عمومی تمایل دارند که برای اهداف متفاوتی طراحی شوند، مخصوصا AES اندازه‌های از بلوک‌ها و کلیدها را دارد که باعث می‌شود برای تولید ارقام درهم ساز بزرگ استفاده نشوند، زمانی که کلید هربلوک را تغییر می‌دهد اثر رمزگذاری AES کمتر می‌شود و نیز حملات کلید مرتبط باعث می‌شود امنیت آن برای استفاده از آن در تابع درهم ساز نسبت به رمزگذاری بسیار کاهش یابد.
تصادم هش
منظور از تصادم hash موقعیتی است که در آن دو مقدار ورودی مختلف به یک تابع درهم‌سازی خروجی یکسان تولید نمایند.
از آنجا که طول ورودی توابع درهم‌سازی کریپتوگرافیک نامحدود ولی طول خروجی آن‌ها ثابت است، فضای ورودی بسیار بزرگتر از فضای خروجی است و در نتیجه توابع درهم‌سازی کریپتوگرافیک همواره دارای (بی‌شمار) تصادم هستند.
خواص کریپتوگرافیک
تابع درهم‌ریزی hash داده شده‌است:
این تابع باید حداقل واجد این خصوصیات باشد:
مقاومت پیش پرونده: برای هر H داده شده، محاسبه M به گونه‌ای که باشد دشوار است.
مقاومت پیش‌تصویر دوم (مقاومت تصادم ضعیف): برای هر ورودی M1 داده شده، یافتن ورودی M2 به گونه‌ای که باشد دشوار است.
دقت کنید که شرط اول قوی‌تر است و در واقع شرط دوم را دربردارد.
مقاومت تصادم (قوی): یافتن هر زوج ورودی M1 و M2 به گونه‌ای که باشد دشوار است. از آنجا که امکان استفاده از پارادوکس روز تولد برای یافتن یک تصادم وجود دارد، طول مقدار hash باید در این مورد حداقل دو برابر مقدار لازم برای مقاومت پیش‌تصویر باشد.
ساختار مرکل-دمگارد
یک تابع درهم ساز باید بتواند پس از پردازش پیام‌هایی با طول متغیر را به خروجی با طول ثابت تبدیل کند. این کار می‌تواند با شکستن ورودی به بلوک‌هایی با اندازه یکسان و سپس استفاده از یک تابع فشرده ساز یکسان صورت گیرد.
این تابع فشرده ساز می‌تواند به‌طور خاص برای درهم‌سازی طراحی شود یا از یک بلوک رمزی ساخته شود.
تابع درهمسازی که با ساختار مرکل-دمگارد ساخته می‌شود در مقابله با تصادم مانند تابع فشرده سازش عمل می‌کند، هرگونه تصادم برای کل تابع درهم ساز می‌تواند تا رسیدن به یک تصادم در تابع فشرده‌سازی دنبال شود.
الحاق توابع درهم ساز رمزگذار
الحاق کردن خروجی‌های توابع درهم سازچندگانه باعث مقاومت در برابر تصادم به خوبی قوی‌ترین الگوریتم‌ها که در نتیجه الحاق موجود هستند، می‌شود. برای مثال نسخه‌های قدیمی‌تر TLS/SSL از مجموع الحاق شده MD5 و SHA-1 استفاده می‌کنند، که ما را مطمئن می‌کند که یک روش برای پیدا کردن تصادم در یکی از توابع امکان جعل ترافیک مربوط به هر دو تابع را از بین می‌رود.
برای توابع در هم ساز مرکل-دمگارد، تابع الحاق شده به اندازه قوی‌ترین مولفه آن و نه بیشتر، در برابر تصادم مقاومت می‌کند. جوکس اظهار می‌دارد که دومین تصادم به nامین تصادم منجر می‌شود: اگر پیدا کردن دو پیام با درهم ساز MD5 مشابه امکان‌پذیر باشد، پیدا کردن هر تعداد پیام با درهم ساز MD5 یکسان که حمله‌کننده بخواهد هم به همین ترتیب امکان‌پذیر است. در بین n پیام با درهم ساز MD5 یکسان، احتمالا در SHA-1 یک تصادم وجود خواهد داشت. کار اضافی لازم برای پیدا کردن تصادم SHA-1 پلی نومیال است. این بحث توسط فینی خلاصه شده‌است. مقاله جدیدتری با اثبات کامل‌تری را از امنیت چنین ساختار ترکیبی‌ای توضیح واضح‌تر و پیچیده‌تری را از مبحث بالا ارائه می‌دهد.
برای امنیت این ساختار این مسئله مهم است. این ساختار مرکل-دمگارد نام دارد. توابع درهم ساز پرکاربرد مانند SHA-1 و MD5 دارای این حالت هستند.
الگوریتم‌های درهم ساز رمزی
لیست بلندی از توابع درهم ساز رمزی وجود دارد، هم چنین برخی از آن‌ها آسیب‌پذیر هستند و نباید استفاده شوند. حتی اگر یک تابع درهم ساز هیچ‌گاه شکسته نشود، یک حمله موفق علیه یک متغیر تضعیف شده وابسته به آن ممکن است اعتماد کارشناسان را تضیف کرده و منجر به ترک آن شود.