توابع هش و اصالت داده ها (Hash Functions and Data Integrity)

مقدمهامروزه با توجه به گسترش خدمات الکترونیکی، اینترنت و شبکه های اجتماعی و نقش اساسی این ها در مراودات و مبادلات اجتماعی و با توجه به قرارگیری انواع اطلاعات شخصی و عمومی در این بستر، امنیت اطلاعات یکی از مسائل ضروری و مهم در این چرخه گردیده‌است. در این بستر، داده‌های سازمان‌ها در معرض دسترسی افراد و میزبان‌های خارجی قرار می‌گیرد. اطمینان از عدم دستیابی افراد غیرمجاز به اطلاعات حساس از مهم‌ترین چالش‌های امنیتی در رابطه با توزیع اطلاعات میباشد. در دنیای دیجیتال کنونی حفاظت از اطلاعات رکن اساسی و مهمی در تبادلات پیام‌ها و مبادلات تجاری ایفا می‌نماید.رمزنگاری (Cryptography) در عصر حاضر فرآیند تأمین امنیت اپلیکیشن‌ها و محافظت از دیتای مربوط به آن‌ها در برابر انواع حملات (در بستر اینترنت و یا غیر اینترنت) است و این مفهوم در تمامی حوزه‌های فضای مجازی به کار گرفته می‌شود. برای تأمین نیازهای امنیتی تراکنش های امن، از رمزنگاری استفاده می‌شود. با توجه به اهمیت این موضوع و گذار از مرحله سنتی به مرحله دیجیتال آشنایی با رمزنگاری بسیار مهم میباشد.توابع هش تاثیر اساسی و نقش مهمی در رمز نگاری دارد و از توابع هش برای کاهش میزان حافظه مورد نیاز برای ذخیره یا انتقال داده و برای شناسایی و identifier کردن استفاده میشود.با توجه به اهمیت موضوعات بیان شده و کاربرد بسیار زیاد آنها در عصر حاضر، در این نوشته به رمزنگاری و توابع هش و اصالت داده خواهیم پرداخت.تاریخچهمیتوان گفت رمزنگاری همراه با نوشتن و ایجاد قبایل و گروه ها و شکل گیری قدرت سیاسی در جامعه ایجاد شده است.این موضوع موجب ایجاد نگرش‌هایی مانند افزایش قدرت، پیروزی در نبردها و دستیابی به برتری شد و این موارد موجب افزایش گرایش انسان­ها به نیاز طبیعیِ ارتباط امن با گیرنده انتخابی توسط فرستنده شد. پیدایش این نوع شیوه‌های ارتباط در نوع خود موجب تکامل مداوم رمزنگاری شد.جایگزینی نماد، که به نوعی ساده‌ترین شکل رمزنگاری به حساب می‌آید، در نوشته‌های به جا مانده از مصریان و ساکنین بین‌النهرین، دیده می‌شود. در اینگونه از رمزنگاری به جای هر کدام از حروف یک نماد قرار می گرفته است.در یکی از شهرهای یونان باستان به نام اسپارتا، پیام‌ها از طریق نوشته شدن روی یک نوار کاغذی و پیچیدن آن دور یک استوانه‌ی با قطر مشخص رمزگذاری ‌می‌شدند. نوار کاغذی تا زمانی که توسط گیرنده آن، روی یک استوانه با همان قطر قرار نمی‌گرفت، به صورت ناخوانا باقی می‌ماند.به مرور زمان رمزنگاری بسیار کامل تر و دقیق تر شد. در جنگ جهانی دوم نمونه‌ای کامل از رمزنگاری با نام ماشین انیگما (Enigma) صورت میگرفته است. این دستگاه با بکارگیری نیروهای محور چرخ، از چرخ‌های در حال چرخیدن برای کدگذاری یک پیام استفاده می‌کند، که این نوع رمزنگاری تقریبا خواندن آن پیام توسط هر ماشین دیگری را غیرممکن می‌سازد. و در نهایت، تکنولوژی کامپیوترهای اولیه برای کمک به شکستن رمز ماشین انیگما مورد استفاده قرار گرفت و رمزگشایی پیام‌های انیگما، همچنان به عنوان یکی از مؤلفه‌های مهم در پیروزی نسل جدید رمزنگاری به حساب می‌آید.با پیدایش و افزایش استفاده از کامپیوترها، رمزنگاری به چیزی بسیار پیشرفته تر از آنچه در دوران قبل بود، تبدیل شد. این رمزنگاری ها با استفاده از سخت افزار ها، نرم افزارها و کد های نوشته شده(برنامه نویسی) بر روی کامپیوتر ها بسیار پیشرفته تر شد.توابع هش نوع خاصی از عملکرد برنامه نویسی است که برای mapping داده ها از اندازه دلخواه به داده هایی با اندازه ثابت استفاده می شود. توابع هش ناشی از نیاز به فشرده سازی داده ها به منظور کاهش میزان حافظه مورد نیاز برای ذخیره فایل های بزرگ است.بعد ها از توابع هش برای شناسایی (singularly-unique identifiers) به کار برده شد به صورتی که به طور مثال از تابع هش در ذخیره پسوردها و داکیومنت‌های مربوط به این پسوردها و دیتای کاربران از طریق فرآیند هَشینگ محافظت می‌شوند و یا در سیستم‌های بلاکچین به منظور تولید آدرس‌های بلاکچین، شناسۀ تراکنش و بسیاری از الگوریتم‌ها و پروتکل‌های دیگر استفاده می‌شود.از توابع هش برای یکپارچگی داده ها در مورد طرح های امضای دیجیتالی نیز استفاده می شود، به این صورت که که با توجه به موارد گفته شده این اعمال برای امنیت و محافظت از دیتا در برابر حملات استفاده میشود.کاربرد توابع هش و اصالت داده هادر توابع هش یک ورودی با طول های مختلف داده میشود و طی عملیاتی و الگوریتمی یک خروجی با طول ثابت داده میشود که شبیه به ورودی اولیه نمیباشد و با تغییر بسیار کوچک در ورودی، خروجی تغییر بسیاری خواهد کرد.از شروط تابع هش باید به این توجه نمود که تابع باید به صورت یکطرفه باشد و قابلیت decrypt شدن را نداشته باشد به صورتی که اگر یک تابع هش h یک مقدار هش z را تولید کرد، پیدا کردن یک مقدار x که هش آن با z یکی شود، بایستی فرآیند دشواری باشد.علاوه بر مطالب ذکر شده مهمترین و پر استفاده ترین استفاده از توابع هش برای حفظ Data Integrity (اصالت و تمامیت داده ها) میباشد.یکپارچگی و اصالت داده ها یک صفت خاص یا یک ویژگی از اطلاعات است که باید اطمینان حاصل کنیم که داده ها در طی هر عمل (مانند انتقال ، ذخیره سازی یا بازیابی) "نامتناقض"، "صحیح"، "کامل" هستند و برای استفاده بیشتر به صورت صحیح ذخیره شده اند.به این صورت که hash value پیام به طریق تابع هش محاسبه میشود و در طرف دیگر برای اینکه فهم اینکه پیام تغییر کرده یا نه، hashcode پیام به وسیله گیرنده پیام (کسی که پیام بعد از گذشت از راه به او رسیده است) محاسبه و درآورده میشود و اگر هر دو هش یکسان بود پیام تغییر نکرده است و تمامیت داده ها حفظ شده است. این نکته نیز مهم میباشد که عمل هشینگ فقط بر روی integrity پیام اعمال میشود نه بر روی خود پیام.در عکس زیر(تصویر یک) نحوه استفاده از تابع به طور مثال H نمایش داده شده است.تصویر یک - استفاده از مثال تصویری برای درک کار تابع Hتوابع هش به 2 دسته تقسیم میشوند: توابع هش کلید دار و توابع هش بدون کلید که در دسته اول مشخصات یک پیام را دیکته میکند و مینویسد و در دسته دوم 2 ورودی مستقیم و پیام و یک کلید مخفی (secret key).تابع هش سه ویژگی فشرده سازی که یک پیام به آن داده میشود و خروجی یک پیام دیگر با طول ثابت میباشد و دیگر ویژگی آن سهولت در محاسبه و تبدیل به hash value میباشد و سومی به این صورت است که هیچوقت نباید خروجی 2 ورودی متفاوت یکی بشود و حتما باید تفاوت داشته باشد.دو نوع تابع هش بسیار پرکاربرد تر و بهتر میباشد که عبارتند از:1- modiﬁcation detection codes (MDCs) : هدف از یک MDC ارائه هش یک پیام است و هدف نهایی تسهیل ، در ارتباط با سازوکارهای اضافی، اطمینان از یکپارچگی داده ها به عنوان برنامه های خاص مورد نیاز است. MDC ها زیر مجموعه ای از توابع هش بدون کلید هستند و خودشان ممکن است طبقه بندی شوند.2. message authentication codes (MACs) : هدف از MAC بدون استفاده از مکانیسم های اضافی ، اطمینان در مورد منبع پیام و یکپارچگی آن است . MAC ها دارای دو پارامتر کاملاً مجزا ، یک ورودی پیام و یک کلید مخفی هستند. آنها زیر مجموعه ای از توابع هش کلید دار هستند.تصویر زیر (تصویر دو) طبقه بندی ساده را نشان می دهد. برنامه های کاربردی اضافی از توابع هش کلید دار شامل استفاده از علامت گذاری به عنوان response که تابعی از یک کلید مخفی و یک پیام است ، می باشد. و برای تایید کلید. باید بین یک الگوریتم MAC و استفاده از MDC با یک کلید مخفی به عنوان بخشی از ورودی پیام آن تمایز قائل شد.تصویر دو - طبقه بندی ساده از 2 نوع تابع هش بسیار پرکاربردUnkeyed Hash Functions (MDCs)امروزه یک تحولی عمومی در ویژگی­ها و ساختاری که برای یکسری توابع هش شده در حال ایجاد است. در این بخش مجموعه ای از توابع درهم ساز بدون کلید به عنوان کد تشخیص اصلاح شناخته (MDCs) می شود در نظر گرفته شده است. از دیدگاه ساختاری, این موارد ممکن است براساس ماهیت عملیات شامل توابع فشرده سازی داخلی طبقه بندی شوند. از این دیدگاه, سه مقوله بزرگ توابع درهم ساز مطالعه شده تا به امروز توابع درهم سازی مبتنی بر رمزهای بلوکی, توابع درهم ساز سفارشی و توابع درهم ساز مبتنی بر محاسبات مدولار است. توابع هش کامل آنهایی هستند که به طور خاص برای درهم سازی, با سرعت در ذهن و مستقل از سیستم­های دیگر طراحی شده­اند (به عنوان مثال, رمز بلوکی یا ضرب مدولار که ممکن است در حال حاضر برای اهداف غیر از هش وجود داشته باشد). جدول 3-3 امنیت مورد حدس یک زیرمجموعه از MDC ها که متعاقبا در این بخش مورد بحث قرار گرفت را نشان میدهد. شبیه به مورد رمزهای بلوکی برای رمزنگاری (به عنوان مثال 8 یا 12 دور DES در مقابل 16 دور DES) سرعت را قربانی سرعت می کنیم. در موارد خاص مبتنی بر بلوک MDC ها به طور تقریبی طرحی امن از Merkley با نرخ 0.276 شناخته شده است اما کاربرد کمی دارد, در حال که MDC-2 به طور گسترده مطمئن است و نرخ 0.5 دارد و توجه بیشتری را به عمل جلب می کند.توابع هش براساس بلوک رمزنگارییک انگیزه عملی برای ایجاد توابع درهم سازی از رمزهای بلوکی این است که اگر یک پیاده سازی کارآمد از یک رمز بلوکی در یک سیستم وجود داشته باشد)چه در سخت افزار و چه در نرم افزار) سپس با استفاده از آن به عنوان جز مرکزی برای یک عملکرد هش می تواند عملکرد دومی را با هزینه اضافی کوچک فراهم کند. امید این است که یک رمز بلوک خوب می تواند به عنوان یک بلوک ساختمانی برای ایجاد یک تابع درهم سازی با خواص مناسب برای کاربردهای مختلف عمل کند.a همین قدرت برای توابع hash دیویس - مایر و Miyaguchi - Preneel پیش‌بینی شده‌است. b قدرت را می توان با استفاده از یک رمز با keylength برابر با رمز نگاری افزایش داد. جدول 9.3- مرزه‌ای بالایی بر مقاومت توابع درهم ساز منتخب. بلوک‌های پیغام n - بیتی برای تولید مقادیر هش کامل m پردازش می‌شوند. تعداد رمز و عملیات تابع فشرده‌سازی که در حال حاضر برای یافتن preimages و برخوردها ضروری است، با فرض اینکه هیچ ضعف اساسی برای رمزهای بلوکی وجود ندارد (ارقام برای MDC - ۲ و MDC - ۴ دارای ویژگی‌های کلید ضعیف هستند). با توجه به نرخ، تعریف ۹.۴۰ را ببینید.این کار با هزینه اضافی کمی انجام می‌شود. امید این است که یک رمز بلوکی خوب می‌تواند به عنوان یک بلوک ساختمانی برای ایجاد یک تابع درهم سازی با خواص مناسب برای کاربردهای مختلف عمل کند. ساختار برای توابع درهم ساز مشخص شده‌است که "بسیار امن" ویژگی‌های ایده‌آل خاص رمز بلوکی را فرض می‌کند. با این حال، رمزهای بلوکی دارای ویژگی‌های توابع تصادفی نیستند (برای مثال، آن‌ها اجتناب‌ناپذیر هستند نکته ۹.۱۴ را ببینید )علاوه بر این، در عمل رمزهای بلوکی معمولا قواعد یا نقاط ضعف اضافی را نمایش می‌دهند، برای مثال یک بلوک رمز E را در نظر بگیرید. رمزنگاری دوتایی با استفاده از رمزگشایی و رمزنگاری با استفاده از کلید های K1و K2 زمانی که K1=K2 هست اثرش را بر نتایج نشان میدهد. به طور خلاصه، در حالی که شرایط لازم مشخص است، مشخص نیست که نیازمندی‌های یک رمز بلوکی برای ساختن یک عملکرد هش کامل کافی است و خواص کافی برای یک رمز بلوک (به عنوان مثال مقاومت در برابر حمله متن انتخاب‌شد) ممکن است یک عملکرد هش خوب را تضمین کند.یک تابع بلوک رمز (n,r) یک یک تابع برگشت پذیر از n بیت متن ساده به n بیت متن متن رمز شدهبا استفاده از r بیت کلید انجام می شود. اگر E یک رمزنگاری باشد پس Ek (x) رمزنگاری x با استفاده از کلید k را نشان میدهد.بحث توابع درهم سازی که از رمزهای بلوکی n ساخته شده اند بین آنهایی که دارای طول n بیت و طول 2n بیت هستند تقسیم می شود, که در آن واحد و دوتایی نسبت به اندازه خروجی بلوک صفر هستند. تحت این فرض که محاسبات 264 عملیات غیر عملی است 3 هدف توابع درهم سازی واحد ارائه یک OWHF برای رمزهای طول بلوک نزدیک n=64 است یا برای فراهم آوردن CRHFs برای طول بلوک صفر نزدیک n=128 است. هدف برای توابع درهم سازی دو طول این است که رمزهای بلوکی N بیتی از اندازه تقریبا n=64 وجود دارند و کدهای درهم سازی تک هش این اندازه مقاوم به برخورد نیستند. برای چنین رمزهایی هدف به دست آوردن کد های درهم سازی به طول 2n بیت است که CRHFs هستند. در ساده ترین حالت اندازه کلید مورد استفاده در چنین توابع درهم سازی تقریبا مشابه طول بلوک رمز است (یعنی n بیت). در موارد دیگر, توابع درهم سازی از کلیدهای بزرگتر (به عنوان مثال دو برابر) استفاده می کنند. مشخصه دیگر که در این توابع درهم ساز مورد توجه قرار می گیرند, تعداد عملیات رمز بلوکی می باشد که برای تولید خروجی درهم سازی طول بلوک برابر با رمز کلید مورد نیاز است.که تعریف زیر را تعمیم می دهد.فرض کنید که یک تابع هش تکراری ساخته شده از یک صفر بلوک, با تابع فشرده سازی f که بلوک دیاگرام سازی را برای پردازش هر بلوک پیام n بیتی متوالی انجام می دهد. سپس نرخ h برابر با 1/s است.توابع درهم ساز مورد بحث در این بخش به ترتیب در جدول 9.4 خلاصه شده است. The Matyas-Meyer-Oseas و MDC-2 به ترتیب از دو تابع درهم ساز عمومی در استاندارد iso 10118-2 هستند , که هر کدام اجازه استفاده از هر بلوک n بیت را با طول m ≤ n و m ≤ 2n fi به ترتیب را فراهم می کنند.جدول 9.4 - خلاصه توابع درهم ساز انتخاب‌شده براساس رمزهای بلوکی n بیت. k = اندازه بیت کلید (تقریبی)؛ تابع مقدار هش کمی را بدست می‌دهد.i) Single-length MDCs of rate 1سه طرح اولیه توصیف‌شده در زیر، و نشان‌داده‌شده در شکل ۹.۳، عملکردهای هش جداگانه با طول واحد مبتنی بر رمزهای بلوکی هستند. این‌ها از اجزای از پیش تعریف‌شده زیر استفاده می‌کنند:1. یک بلوک N بیتی عمومی به وسیله یک کلید متقارن K.2. تابع g که ورودی n - بیتی را به کلیدهایی که برای E مناسب هستند (اگر کلیدهای E هم دارای طول n باشند، g ممکن است تابع هویت باشند)؛3. یک مقدار اولیه (معمولا n بیتی) اولیه, مناسب برای استفاده با E.شکل 9.3 - سه - طول، نرخ - یک MDCs براساس رمزهای بلوکیالگوریتم Matyas-Meyer-Oseas hashورودی: رشته بیت xخروجی: n بیت کد هش شده از x1. ورودی x به بلوک¬ های n بیت تقسیم می شود و اگر لازم باشد تا بلوک آخر کامل شود. این پیغام شامل موارد زیر است: x1x2 ...x t. یک مقدار ثابت n بیتی IV باید از قبل مشخص شود.2. خروجی Ht به صورت زیر تعریف می شود:H0 = IV ; Hi = Eg(Hi−1)(xi)⊕xi, 1 ≤ i ≤ t.الگوریتم Davies-Meyer hashورودی: رشته بیت xخروجی: کد هش شده n بیتی x1- ورودی x به بلوک‌های k - بیت تقسیم می‌شود که در آن k اندازه اصلی است، و اگر لازم باشد، تا آخرین بلوک را کامل کنید. پیام padded متشکل از بلوک‌های k بیتیx1x2 .. x: است. یک مقدار بیتی IV باید از قبل مشخص باشد.2- خروجی Ht خواهد بود:H0 = IV ; Hi = Exi(Hi−1)⊕Hi−1, 1 ≤ i ≤ tالگوریتم Miyaguchi-Preneel hashاین روش نیز مشابه الگوریتم 9.41 می باشد با این تفاوت که خروجی Hi-1 از مرحله قبلی با این مرحله XOR خواهد شد. به طور جزئی Hi دوباره به این گونه تعریف می گردد:H0 = IV ; Hi = Eg(Hi−1)(xi)⊕xi⊕Hi−1, 1 ≤ i ≤ tنکته(روش دوگانه) هش Davies-Meyer ممکن است به عنوان دوگانه هش"Matyas-Meyer-Oseas" شناخته شود, به این معنا که Xi و Hi نقش معکوس را ایفا می کنند. هنگامی که DES به عنوان رمز بلوکی در Davies-Meyer استفاده می شود, ورودی در بلوک های 56 بیتی )نرخ بازده 56/64 < 1) پردازش می شود در حالی که Matyas-Meyer-Oseas و Miyaguchi-Preneel بلوک های 64 بیتی را پردازش می کنند.(جعبه سیاه امنیتی) صرف نظر از ارگومان ابتکاری که در مثال 9.13 داده شده است, به نظر می رسد که تمام 3 الگوریتم 9.41 , 9.42 و 9.43 حاصل توابع هش ای هستند که در قالب مناسبی از “جعبه سیاه” امن هستند (به طور مثال فرض کنید E دارای ویژگی های تصادفی هست که حملات از هیچ یک هز ویژگی های E نمی تواند استفاده کند). "امنیت" به این معنی است که پیدا کردن پیش نمایش و برخورد ( در حقیقت شبه پیش نمایش و شبه برخورد – 9.7.2 را ببینید) به ترتیب 2n و 2n/2 بلاک های n بیتی در عملیات رمزنگاری و برعکس نیاز است. با توجه به ماهیت تک طول آن ها, هیچ یک از این سه برخورد در برابر رمزهای موجود با طول بلوک نسبتا کوچک ( به عنوان مثال, DES که کد های هش شده 64 بیتی را خروجی میدهد) مقاوم هستند.چندین تابع درهم ساز چندتایی براساس رمزهای بلوکی بعدی در نظر گرفته می شوند.ii) Double-length MDCs: MDC-2 and MDC-4MDC-2 و MDC-4 کدهای تشخیص دستکاری هستند که به ترتیب 2 و 4 بلوک عملیات رمزنگاری به ازای هر بلوک از هش ورودی نیاز دارد. آنها ترکیبی از 2 یا 4 تکرار برنامه Matyas-Meyer-Oseas را بکار میگیرد تا یک هش جداگانه تولید کنند. هنگامی که از DES به عنوان رمز بلوکی اصلی استفاده می شود, کد هش 128 بیتی را تولید می کنند. با این حال, ساختار کلی می تواند با رمزهای بلوکی دیگری مورد استفاده قرار گیرد. MDC-2 و MDC-4 از اجزای از پیش تعیین شده استفاده می کنند.1. DES به عنوان بلوک رمزنگاری Ek با طول بیت n=64 و با 56 بیت کلید K معین شده است;2. دو تابع g و ˜ g مقدار 64 بیتی U را به کلید DES که 56 بیتی است به مانند زیر نگاشت می کند. برای U = u1u2 ...u64 هر 8 بیتی که با U8 آغاز می شود را حذف کنید و دومین و سومین بیت را برابر ‘10’ برای g قرار دهید و برای ˜ g این مقدار را برابر ‘01’ قرار دهید:g(U)=u1 10u4u5u6u7u9u10 ...u63.˜ g(U)=u1 01u4u5u6u7u9u10 ...u63.(مقادیر نتایج ضمانتی برای ضیف بودن یا تقریبا ضعیف بودن کلید های DES ندارد ولی تمام این کلید ها bit 2 = bit3; صفحه 375 را ببینید. همچنین ضمانت این را دارد که . )MDC-2 در الگوریتم 9.46 و شکل 9.4 مشخص شده استشکل 9.4- تابع فشرده‌سازی MDC -2 هش. E=DESالگوریتم MDC-2 hash function (DES-based)ورودی: رشته x به طول r = 64t به طوری که t>=2خروجی: 128 بیت کد هش شده x1. X را به بلاک های 64 بیتی میشکنیم xi: x = x1x2 ...xt2. یک عدد ثابت 64 بیتی ,IV ( همان مقدار ثابت باید برای تصدیق MDC استفاده شود) از مجموعه مقادیر از پیش تعیین شده انتخاب کنید. یکسری مقادیر از پیش تعیین شده (به صورت hexadecimal):IV^= 0x2525252525252525IV=0x52525252525252523. عملات || را به عنوان الحاق مشخص می کنیم, و 32 بیت چپ و راست مقدار هستند. خروجی برابر h(x) = Ht || t به مانند روبرو تعریف می شود:در الگوریتم 9.46 , padding ممکن است برای برآورده کردن محدودیت طول بیت در ورودی x ضروری باشد. در این مورد, یک روش padding بدون ابهام ممکن است مورد استفاده قرار گیرد ( توجه 9.31 را ملاحظه کنید), احتمالا شامل MD-strengthening. MDC-4 (الگوریتم 9.47 و شکل 9.5 را ببینید) با استفاده از تابع فشرده سازی MDC-2 ساخته شده است. یک تکرار از تابع فشرده سازی MDC-4 شامل دو اجرای متوالی از تابع فشرده سازی MDC-2 است. که در آن:1. دو ورودی داده 64 بیتی برای اولین MDC-2 هر دو همان بلوک پیغام 64 بیتی بعدی هستند;2. کلید برای اولین MDC-2 فشرده سازی از خروجی های (متغیرهای chaining) از compression قبلی MDC-4 مشتق شده اند;3. کلید ها برای دومین MDC-2 فشرده سازی از خروجی (متغیرهای chaining) اولین فشردگی MDC-2 استخراج شده­اند;4. دو ورودی داده 64 بیتی برای دومین MDC-2 فشرده سازی , خروجی (متغیرهای chaining) متقابل فشرده سازی MDC-4 قبلی می باشد.الگوریتم MDC-4 hash function (DES-basedورودی: رشته x متشکل از بیت های به طول r=64t طوری که t>=2 . )MDC-2 را در رابطه با padding ملاحظه کنید.)خروجی: 128 بیت کد هش شده از x.1. مانند مرحله اول MDC-2 بالا.2. مانند مرحله دوم MDC-2 بالا.3. با توجه به MDC-2 , خروجی h(x) = Gt || t مثل زیر تعریف می شود (1 ):سفارشی کردن تابع هش براساس MD4توابع هش کامل آن هایی هستند که به طور خاص "از صفر" برای هدف صریح درهم سازی, با عملکرد بهینه در ذهن طراحی شده­اند, و بدون توجه به استفاده مجدد از مولفه های سیستم موجود مانند رمزهای بلوکی یا حساب مدولار. کسانی که بیش ترین توجه را در عمل دریافت کرده اند مبتنی تابع درهم ساز MD4 هستند. شماره 4 در مجموعه ای از توابع درهم ساز(Message Digest algorithm), MD4 به طور خاص برای پیاده سازی نرم افزار روی ماشین های 32 بیتی طراحی شد. نگرانی های امنیتی طراحی MD5 را اندکی پس از آن, به عنوان یک تغییر محافظه کارانه تر از MD4 برانگیخته است.شکل 9.5- عملکرد فشرده سازی تابع هش MDC-4دیگر نسخه های بعدی مهم شامل الگوریتم( Secure Hash Algorithm SHA-1) , تابع درهم ساز RIPEMD و انواع تقویت شده آن RIPEMD-128 و RIPEMD-160 است. پارامترهای این تابع درهم ساز در جدول 9.5 "Rounds x Steps per round" خلاصه شده اند که به عملیات انجام شده بر روی بلوک های ورودی در تابع فشرده سازی مربوطه اشاره دارد. جدول 9.6 بردارهای تست را برای زیر مجموعه این توابع درهم ساز مشخص می کند.نشانه گذاری برای توصیف الگوریتم های خانواده MD4جدول 9.7 نماد برای توصیف الگوریتم خانواده MD4 را توصیف و تشریح می کند. توجه داشته باشید که 9.48 به مساله اجرایی تبدیل رشته های بایت به کلمات به روش صریح و بدون ابهام اشاره می کند.نکته(کم و بیش) برای اجرای تبدیل بایت به کلمه بر روی پردازنده های متفاوت (به عنوان مثال تبدیل بین کلمات 32 بیتی و گروهی از بایت های 8 بیتی) باید یک قرداد بدون ابهامی مشخص شود. یک رشته از بایت های Bi را با آدرس های حافظه ای در حال افزایش در نظر بگیریدکه به کلمه 32بیتی و یک مقدار عددی W ترجمه می شود. دراین اندک معماری های بایت با کمترین دسترسی حافظه (B1) حداقل بایت را دارد:W =224 B4 +216 B3 +28 B2 + B1در بیش تر پروژه ها بایت با کم ترین آدرس B1 مهم ترین byte محسوب می شوند:W =224 B1 +216 B2 +28 B3 + B4i) MD4الگوریتم MD4 ) Algorithm 9.49) یک تابع درهم ساز 128 بیتی است. اهداف طراحی اصلی MD4 این بود که شکستن آن باید به یک تلاش سخت نیاز داشته باشد, پیدا کردن پیام های متمایز با همان مقدار هش باید در حدود 264 عملیات را در نظر بگیرد و یک پیام را پیدا کند که با مقدار هش از پیش تعیین شده باید حدود 2128 عملیات را نیاز دارد. اکنون می دانیم که MD4 در رسیدن به این هدف ناموفق عمل می کند (نکته 9.50). با این وجود یک توصیف کامل از MD4 به عنوان الگوریتم 9.49 برای مرجع تحلیلی تاریخی و رمزنگاری گنجانده شده است. همچنین به عنوان مرجع مناسب برای توصیف , و اجازه داده به مقایسه ها بین دیگر توابع درهم ساز در این خانواده عمل می کند.جدول 9.5- خلاصه ی از توابع هش بر اساس MD4جدول 9.6- تست بردار ها برای تابع هش انتخابیجدول 9.7- علائم برای الگوریتم مشابه MD4الگوریتم MD4 hash functionورودی: رشته بیت x با طول دلخواه b . ( برای علائم جدول 9.7 را ملاحظه کنید.)خروجی: 128 بیت کد هش شده از x. ( جدول 9.6 را ملاحظه کنید.)1. تعریف ثابت ها. تعریف 4 مقدار اولیه chaining که هر کدام 32 بیت هستن( IVs):H1 = 0x67452301, h2 = 0xefcdab89, h3 = 0x98badcfe, h4 = 0x10325476تعریف مقادیر 32بیتی ثابت:y[j]=0, 0 ≤ j ≤ 15;y[j]=0x5a827999, 16 ≤ j ≤ 31; (constant = square-root of 2)y[j]=0x6ed9eba1, 32 ≤ j ≤ 47; (constant = square-root of 3)تعریف ترتیب دسترسی به منابع کلمات (هر لیست شامل 0 تا 15 می باشد):z[0..15] = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],z[16..31] = [0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15],z[32..47] = [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15].نهایتا تعریف موقعیت های بیت برای شیفت به چپ (چرخش):s[0..15] = [3,7,11,19,3,7,11,19,3,7,11,19,3,7,11,19],s[16..31] = [3,5,9,13,3,5,9,13,3,5,9,13,3,5,9,13],s[32..47] = [3,9,11,15,3,9,11,15,3,9,11,15,3,9,11,15].2. پیش پردازش. فاصله x به گونه ای است طول بیت آن برابر با مضربی از 512 است. یک بیت 1 را بیافزایید سپس به تعداد0) r-1 (بیت صفر نیز الحاق می کنیم که نتیجه آن طول بیت 64 که کمتر از مضرب های 512 می باشد. در آخر نمایش 64 بیتی b mod 264 را با دو عدد کلمه 32 بیتی با حداقل کلمه مشخص در اول به آن الحاق می کنیم. فرض کنید m یک تعدادی از بلاک های 512 بیتی باشد که به شکل رشته (b + r + 64 = 521m = 3216) نشان داده می شود. فرمت ورودی شامل 16m کلمه 32 بیتی می باشد: x0x1 ...x16m−1مقدار اولیه: (H1,H2,H3,H4) ← (h1,h2,h3,h4)3. پردازش. برای هر i از صفر تا m-1 , ith تعداد بلاک از 16 کلمه 32 بیتی را در حافظه موقت کپی کنید:X[j] ← x16i+j, 0 ≤ j ≤ 15 پردازش مانند زیر دارای 16 مرحله قبل به روز کردن chaining variable ها است:(initialize working variables) (A,B,C,D) ← (H1,H2,H3,H4).(Round 1) For j from 0 to 15 do the following:t ← (A + f(B,C,D)+X[z[j]] + y[j]), (A,B,C,D) ← (D,t ←s [j],B,C).(Round 2) For j from 16 to 31 do the following:t ← (A + g(B,C,D)+X[z[j]] + y[j]), (A,B,C,D) ← (D,t ←s [j]),B,C).(Round 3) For j from 32 to 47 do the following:t ← (A + h(B,C,D)+X[z[j]] + y[j]), (A,B,C,D) ← (D,t ←s [j]),B,C).(update chaining values) (H1,H2,H3,H4) ← (H1+A,H2+B,H3+C,H4+D).4. تکامل. مقدار هش نهایی حاصل الحاق این موارد هست: H1||H2||H3||H4(اولین و آخرین بایت ها کمترین و بیشترین از H1 , H4 به ترتیب هستند)حملات براساس ویژگی های رمزگذاریویژگی های خاص رمزهای بلوکی که ممکن است هیچ نگرانی کاربردی نداشته باشد وقتی برای رمزنگاری مورد استفاده قرار می گیرد , باید با دقت بررسی شود که این رمزهای بلوکی برای ساخت توابع درهم ساز مورد استفاده قرار می گیرند. خطر عمومی این است که چنین خواص ممکن است دستکاری معکوس ورودی های تابع فشرده سازی را تسهیل کند تا به پیش بینی یا کنترل بیشتر خروجی ها یا روابط بین خروجی های تکراری متوالی اجازه دهد. در بین ویژگی های رمز بلوکی ناشی از نگرانی احتمالی آمده است:1. ویژگی تکامل : Ek ( y = Ek(x) که در آن x بیانگر مکمل bitwise است. این مساله یافتن جفت پیغام کلید برای ورودی های رمز بلوکی آن است که خروجی های آن با روشی از پیش تعیین شده متفاوت هستند. برای مثال, برای چنین بلاک های رمزنگاری E تابع فشرده سازی xi (xi) xi f(Hi-1,xi) = EH(i-1) همان خروجی را برا ی xi مکمل bitwise تولید می کند.2. کلیدهای ضعیف: Ek(Ek(x)) = x . این ویژگی از رمز بلوکی ممکن است به رقیب اجازه دهد که به راحتی یک نقطه ثابت دو مرحله ای تابع فشرده سازی f را ایجاد کند که بلاک پیغام xi اثر مستقیم روی کلید های رمزنگاری ورودی دارد.3. نقاط ثابت: Ek(x) = x. نقاط ثابت بلوک صفر ممکن است حملات نقطه ای ثابت را تسهیل کنند اگر یک دشمن بتواند ورودی کلید رمز بلوکی را کنترل کند. برای مثال تابع فشرده سازی Devies-Meyer , f(Hi-1, xi) = Ex(Hi-1) Hi-1 اگر Hi-1 نقطه ثابت از بلوک رمزنگاری برای کلید xi باشد پس این باعث می شود تا خروجی تابع فشرده سازی قابل پیش بینی باشد f(Hi-1, xi) = 0 .4. تصادم کلید Ek(x)=Ek (x). این ممکن موجب تصادم توابع فشرده سازی شود.اگر چه آنها ممکن است به عنوان معیارهای متمایز عمل کنند, حملاتی که کاملا به صورت معمولی مشاهده می شوند. باید به طور جداگانه از دیگران مورد توجه قرار گیرند. برای مثال به نظر می رسد که حملات نقطه ثابت نتیجه عملی محدودی دارند.منابعاگر به این موضوع علاقمند هستید می‌توانید از این کتاب کمک بگیرید. در صورتیکه می‌خواهید موارد مشابه را ببینید به این نوشته مراجعه کنید. این لینک نیز توضیحات جامعی در این مورد دارد.Alfred J. Menezes، Paul C. van Oorschot & Scott A. Vanstone. Handbook of Applied Cryptography. Chapter 9W. Stallings. Cryptography and Network Security. Chapter 11https://en.wikipedia.org/wiki/History_of_cryptography"این مطلب در راستای درس رمزنگاری و امنیت در دانشگاه تحصیلات تکمیلی علوم پایه نوشته شده است.""تشکر میکنم از مهندس رضا رشیدنیا که این مطلب رو با یکدیگر تهیه نمودیم."