موضوع مقاله: اس‌اچ‌ای-۳ | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # اس‌اچ‌ای-۳ | مقدمه: اس‌اچ‌ای۳ (الگوریتم امن درهم‌ساز ۳) آخرین عضو خانواده الگوریتم امن درهم‌ساز است که توسط مؤسسه ملی فناوری و استانداردها در ۵ اوت ۲۰۱۵ منتشر شد. | ## بخش 1: اس‌اچ‌ای-۳ | ساختار داخلی اس‌اچ‌ای۳ با ساختار اس‌اچ‌ای-۱ و اس‌اچ‌ای-۲ که بیشتر شبیه ام‌دی۵ می‌باشند تفاوت دارد، اگرچه عضوی از همان سری استانداردها محسوب می‌شود. ساخت اسفنجی مبتنی بر یک تابع تصادفی گسترده تصادفی یا جایگشت تصادفی است و این امکان را می‌دهد که هر مقدار از داده وارد شود("جذب" در اصطلاحات اسفنجی)، و هر مقدار از داده بیرون انداخته شود("فشردن")، در حالی که با توجه به همه ورودی‌های قبلی به عنوان یک تابع نیمه تصادفی عمل می‌کند. NIST در حال حاضر برنامه ای برای برداشت اس‌اچ‌ای۲ یا حذف آن از استاندارد اصلاح شده ایمن درهم‌سازی ندارد. هدف از اس‌اچ‌ای۳ این است که می‌تواند در برنامه‌های فعلی در صورت لزوم مستقیماً جایگزین اس‌اچ‌ای۲ شود و استحکام ابزار کلی الگوریتم درهم‌ساز NIST را به طرز قابل توجهی بهبود بخشد. در سال ۲۰۰۶، NIST برای ایجاد یک استاندارد جدید درهم‌سازی، اس‌اچ‌ای۳، اقدام به سازماندهی رقابت تابع درهم‌سازی NIST کرد. اس‌اچ‌ای۳ قرار نیست که جایگزین اس‌اچ‌ای۲ شود، زیرا هیچ حمله قابل توجهی به اس‌اچ‌ای۲ نشان داده نشده‌است. به دلیل حملات موفقیت‌آمیز بر اس‌اچ‌ای۰، ام‌دی۵ واس‌اچ‌ای۱، NIST احساس نیاز به یک رمزنگاری درهم‌ساز جایگزین و متفاوت کرد، که SHA-3 نام گرفت. در طول مسابقه، به شرکت کنندگان اجازه داده شد الگوریتم‌هایشان را «اصلاح» کنند تا مشکلاتی که کشف شده بود حل شوند. تغییراتی که در کچاک ایجاد شده‌است به این شرح است: تعداد دورها از به افزایش یافت تا از نظر امنیتی محافظه کارتر باشد. در ۵ اوت ۲۰۱۵، NIST اعلام کرد که اس‌اچ‌ای۳ به یک استاندارد درهم‌سازی تبدیل شده‌است. «ظرفیت» استفاده نشدهٔ c باید دو برابر مقاومت مورد نظر در برابر حمله تصادم یا حمله پیش‌نمایش باشد. اس‌اچ‌ای۳ از ساخت اسفنجی استفاده می‌کند، که در آن داده‌ها «جذب» اسفنج می‌شوند، سپس نتیجهٔ آن‌ها به بیرون «فشرده» می‌شود. در مرحله جذب، بلوک‌های پیام XOR شده و به زیر مجموعه ای از حالت تبدیل می‌شوند، که بعداً با استفاده از یک تابع جایگشت به صورت یک کل درمی‌آیند. در مرحله «فشردن»، بلوک‌های خروجی از همان زیر مجموعه حالت خوانده می‌شوند، و با استفاده از تابع تغییر حالت تغییر می‌یابند. سایز بخشی از حالت که نوشته شده و خوانده شده‌است «نرخ» (مشخص شده با ) نامیده می‌شود، و اندازه بخشی که توسط ورودی / خروجی دست نخورده می‌ماند، «ظرفیت» (مشخص شده با ) نامیده می‌شود. با درنظر گرفتن یک رشته بیت ورودی ، یک تابع پدینگ مانند ، یک تابع جایگشت که روی بلوک‌های بیتی با عرض کار می‌کند، نرخ و طول خروجی ، ظرفیتی برابر با و ساخت اسفنجی را داریم، می‌دهد رشتهٔ بیتی به طول ، که به شرح زیر کار می‌کند: پرکردن ورودی N با استفاده از تابع pad، که درنتیجه یک padded bit string مانند P با طولی بخش پذیر بر (به طوری که عدد صحیح باشد) می‌دهد. شکستن P به n قطعه متوالی r بیتی P0, … , Pn−1 مقداردهی اولیه وضعیت S به یک رشته که b بیت از آن مقدار صفر دارند ورودی را جذب حالت کنید: برای هر بلوک Pi: گسترش P i در پایان توسط یک رشته از c بیت از آن مقدار صفر دارند، که یک رشته با طول b تولید می‌کند XOR آن با S تابع جایگشت بلوکی f را روی نتیجه اعمال کنید تا حالت جدید S بدست آید Z را به عنوان رشته خالی مقداردهی اولیه کنید تازمانی‌که که طول Z کمتر از d است: r بیت اول از S را به Z اضافه کنید اگر Z هنوز کمتر از d بیت طول دارد، f را روی S اعمال کنید، تا حالت S بدست آید Z را به d بیت کاهش دهید این واقعیت که وضعیت داخلی S حاوی c بیت اضافی اطلاعات علاوه بر آنچه در خروجی Z نوشته می‌شود است، مانع از حملات طولانی مدت می‌شود که ام‌دی۵، اس‌اچ‌ای۱، اس‌اچ‌ای۲ و سایر درهم‌سازی‌های مبتنی بر ساخت و ساز مرکل-دامگارد مستعد آن هستند. در اس‌اچ‌ای۳، حالت S شامل یک آرایه شامل کلمات w بیتی (w=۶۴)، و درکل b = ۵ × ۵ × w = ۵ × ۵ × ۶۴ = ۱۶۰۰ بیت است. کچاک(Keccak) همچنین برای کلمه‌های توان دویی با اندازه‌های کوچکتر w و حتی با ۱ بیت (که درمجموع حالتی با ۲۵ بیت می‌سازد) هم تعریف شده‌است. اندازه‌های حالت کوچک می‌تواند برای آزمایش حملات تحلیل رمزنگاری مورد استفاده قرار گیرد، و اندازه‌های حالت متوسط (از ، با ۲۰۰ بیت، تا ، با ۸۰۰ بیت) در برنامه‌های کاربردی سبک استفاده می‌شود. برای موارد اس‌اچ‌ای۳–۲۲۴، اس‌اچ‌ای۳–۲۵۶، اس‌اچ‌ای۳–۳۸۴، و اس‌اچ‌ای۳–۵۱۲، مقدار r از d بیشتر است، بنابراین در مرحله فشردن نیازی به جایگشت‌های بلوکی اضافی نیست. با این حال، SHAKE-۱۲۸ و SHAKE-۲۵۶ امکان خروجی با طول دلخواه را به ما می‌دهند، که در برنامه‌هایی مانند رمزگذاری با پرکردن نامتقارن بهینه مفید است. لایه گذاری برای اطمینان از اینکه پیام را می‌توان به بلوک‌های r بیتی مساوی تقسیم کرد، لایه‌گذاری لازم است. اس‌اچ‌ای۳ از الگوی ۱*۱۰ در عملکرد لایه‌گذاری خود استفاده می‌کند: یک بیتِ ۱، به‌دنبال آن صفر یا بیشتر بیتِ ۰ (حداکثر تا) و یک بیتِ ۱ نهایی. | ## بخش 2: اس‌اچ‌ای-۳ | دراین‌حالت بلوک دیگری پس از بیتِ ۱ اولیه اضافه می‌شود که حاوی بیتِ صفر قبل از بیتِ ۱ نهایی است. در این حالت، یک بلوک دیگر به پیام اضافه می‌شود که حاوی یک بیتِ ۱ است، به دنبال آن یک بلوک تایی بیتِ صفر و یک بیتِ ۱ دیگر می‌باشد. این کار لازم است برای اینکه که یک پیام که طولش بر r بخش پذیر است و به چیزی که شبیه لایه‌گذاری به نظر می‌رسد ختم می‌شود، همان درهم‌سازی را تولید نکند که یک پیام دیگری که آن بیت‌ها را ندارد تولید می‌کند. بیتِ ۱ اولیه برای این نیاز است که پیام‌هایی که فقط چند بیتِ ۰ اضافی آخرشان متمایز است، یک درهم‌سازی مشابه ایجاد نکنند. موقعیت بیتِ ۱ نهایی نشان می‌دهد که از کدام نرخ r استفاده شده‌است (لایه‌گذاری چند نرخی)، که برای اثبات امنیت لازم است تا برای انواع مختلف درهم‌سازی کار کند. بدون آن، درهم‌سازی‌های مختلف از یک پیام کوتاه یکسان می‌تواند دارای برش یکسانی شود. فرض کنید برابر بیتِ ام از ورودی باشد، که در یک مدل Little Endian از قرارداد شمارش بیتی و اندیس گذاری ردیف-اول فرض شده‌است، یعنی شماره ردیف، شماره ستون و شماره بیت را مشخص می‌کند. اندیس گذاری حسابی برای دو بعد اول، در پیمانه ۵ و برای بعد سوم در پیمانه w انجام می‌شود. تابع جایگشت بلوکیِ پایه، متشکل از دورِ پنج مرحله‌ای است: (تتا) اعداد زوج و فرد هر یک از (برابر ۳۲۰ اگر ) ستون ۵بیتی را حساب کرده و xor آن را با دو ستون مجاورش در یک الگوی منظم محاسبه کنید. به‌طور دقیق‌تر، (رو) هر کدام از ۲۵ کلمه را با یک عدد مثلثی متمایز مانند ۰، ۱، ۳، ۶، ۱۰، ۱۵ ،...شیفت دورانی دهید. (پی) ۲۵ کلمه را در یک الگوی ثابت جایگشت دهید (خی) بیت به یبت با ردیف‌ها ترکیب کنید، با استفاده از رابطهٔ به‌طور دقیق، این تنها عملیات غیر خطی در اس‌اچ‌ای۳ است. به‌طور دقیق، در دور ام، به ازای ، مقدار با بیت ام از یک دنباله اجرایی حاصل از ثبات تغییر بازخورد خطی(LFSR) درجه-۸ xor می‌شود. با این حال، از آنجایی که c بیت آخر مقدار گسترش‌یافتهٔ P i درهرصورت صفر هستند، و XOR با ۰ یک NOP است، کافی است عملیات XOR را فقط برای r بیت انجام دهیم(r = ۱۶۰۰–۲ × ۲۲۴ = ۱۱۵۲ بیت برای اس‌اچ‌ای۳–۲۲۴، ۱۰۸۸ بیت برای اس‌اچ‌ای۳–۲۵۶، ۸۳۲ بیت برای اس‌اچ‌ای۳–۳۸۴ و ۵۷۶ بیت برای اس‌اچ‌ای۳–۵۱۲). هرچه r پایین‌تر باشد (و برعکس، هرچه c = b - r = 1600 - r بالاتر باشد)، درهم‌سازی ناکارآمدتر و پرهزینه‌تر اما ایمن تر می‌شود، زیرا تعداد بیت کمتری از پیام می‌تواند با حالت XOR شود (یک عملیات سریع) قبل از هر بار استفاده از f که از نظر محاسباتی پرهزینه است. اس‌اچ‌ای۳ به دلیل کند بودن در معماری‌های مجموعه دستورالعمل (CPU) که دستورالعمل خاصی برای محاسبه سریعتر توابع Keccak ندارند، مورد انتقاد قرار گرفته‌است - اس‌اچ‌ای۲–۵۱۲ بیش از دو برابر سریعتر از اس‌اچ‌ای۳، و اس‌اچ‌ای۱ بیش از سه برابر سریعتر از آن روی یک پردازنده Intel Skylake با فرکانس کلاک ۳٫۲ گیگاهرتز اجرا می‌شود. نویسندگان با پیشنهاد استفاده از SHAKE۱۲۸ و SHAKE۲۵۶ به جای اس‌اچ‌ای۳–۲۵۶ و اس‌اچ‌ای۳–۵۱۲، به قیمت کاهش یافتن نصف مقاومت‌پیش‌نمایش (اما با همان مقاومت برخورد)، به این انتقاد واکنش نشان داده‌اند. نمونه‌های اس‌اچ‌ای۳ جایگزین قطره‌ای برای اس‌اچ‌ای۲ هستند، با همان ادعاهای امنیتی یکسان. به عنوان مثال، SHAKE128(M، ۲۵۶) می‌تواند به عنوان یک تابع درهم‌سازی با طول ۲۵۶ بیت و امنیت کلی ۱۲۸بیتی استفاده شود. توجه داشته باشید که همه نمونه‌ها، تعدادی بیت به پیام اضافه می‌کنند، که سمت راست‌ترین آنها نشان‌دهندهٔ پسوند جدایی دامنه است. هدف از این کار این است که اطمینان حاصل شود نمی‌توان پیام‌هایی با همان خروجی درهم‌سازی‌شده را برای کاربردهای مختلف برنامه درهم‌سازی Keccak ساخت. با این حال، پسوند SHAKE با دقت انتخاب شده‌است تا این‌که سازگار با نسخه‌های بعدی ساکورا باشد. از آنجا که لایه‌گذاری ۱۰*۱ همیشه حداقل دو بیت را اضافه می‌کند، در کتابخانه‌های مرتب با بایت همیشه شش بیت صفر استفاده نشده وجود دارد؛ بنابراین، این بیت‌های اضافی هرگز پیام لایه‌گذاری را طولانی‌تر نمی‌کنند. همچنین می‌تواند بدون کلید به عنوان یک تابع درهم‌سازی معمولی مورد استفاده قرار گیرد. تعداد دور کاهش یافته با تلاش بسیار زیاد تحلیلی رمزنگاری متمرکز بر Keccak که نتوانست در حمله عملیاتی به هیچ الگوریتم Keccak با تعداد دور نزدیک به دوازده ایجاد کند، تصدیق می‌شود. | ## بخش 3: اس‌اچ‌ای-۳ | این الگوریتم‌های با سرعت بالاتر جزئی از اس‌اچ‌ای۳ نیستند (زیرا آنها بعداً توسعه یافته‌اند)، و بنابراین سازگار با FIPS نیستند. توجه داشته باشید که امنیت ۲۵۶ بیتی در عمل مفیدتر از امنیت ۱۲۸ بیتی نیست، اما ممکن است طبق برخی استانداردها مورد نیاز باشد. درحال حاضر ۱۲۸ بیت برای پیروزشدن بر حملات brute-force بر روی سخت‌افزار فعلی کافی است، بنابراین داشتن امنیت ۲۵۶ بیتی ارزش عملی نمی‌افزاید، مگر اینکه کاربر نگران پیشرفتهای چشمگیر سرعت کامپیوترهای کلاسیک باشد. یک حمله ساختار یافته پیش‌نمایش نشانگر یک حمله پیش‌نمایش دوم و در نتیجه یک حمله تصادم است. یک کامپیوتر کوانتومی همچنین می‌تواند یک حمله روز تولد را در (اگرچه این مورد اختلاف است) انجام دهد، درنتیجه مقاومت در برابر تصادم را ازبین ببرد. بحث و گفتگو در مورد تغییر ظرفیت در فوریه ۲۰۱۳در کنفرانس RSA، و سپس در اوت ۲۰۱۳ در CHES، NIST اعلام کرد که مقادیر مختلفی را برای ظرفیت، که پارامتر امنیتی است، برای استاندارد اس‌اچ‌ای۳، در مقایسه با ارسال اولیه، انتخاب می‌کنند. مسابقات توابع درهم‌سازی، خواستار توابع درهم‌ساز شد که حداقل به همان اندازه نمونه‌های اس‌اچ‌ای۲ امنیت داشته باشند. به این معنی که یک خروجی d بیتی باید مقاومت d/۲ بیتی درمقابل حملات تصادم و مقاومت d بیتی در برابر حملات پیش‌نمایش داشته باشد، مقدار حداکثری که برای d بیت از خروجی دست یافتنی است. اثبات امنیتی Keccak امکان تنظیم سطح امنیتی را مبتنی بر «ظرفیت» c می‌دهد، که مقاومت c/۲ بیتی در برابر هردو حمله تصادم و حمله پیش‌نمایش فراهم می‌کند. تغییر اعلام شده برای پذیرش همان امنیت d/۲ بیتی برای همه اشکال حمله و استانداردسازی c = d بود. این می‌توانست با فراهم کردن امکان درهم‌سازی d بیت اضافه‌تر از ورودی درهربار تکرار چرخه، سرعت Keccak را بالا ببرد؛ ولی، توابع درهم‌سازی دیگر نمی‌توانستند جایگزین‌های قطره‌ای با همان مقاومت پیش‌نمایشی اس‌اچ‌ای۲ باشند. با این کار مقاومت پیش‌نمایشی به نصف کاهش می‌یافت، باعث می‌شد در برابر پیشرفت‌های محاسبات کوانتومی آسیب‌پذیر شود، که به‌طور مؤثری آن را دوباره به نصف کاهش می‌داد. در سپتامبر ۲۰۱۳، دنیل جی برنشتاین در لیست پستی انجمن درهم‌سازی NIST پیشنهاد کرد که امنیت را با رساندن ظرفیت به ۵۷۶ بیت، که در ابتدا به عنوان پیش فرض کچاک پیشنهاد شده بود، و علاوه بر این در مشخصات فنی اس‌اچ‌ای۳ گنجانده نشده بود، تقویت کنند. این کار می‌توانست حداقل یک اس‌اچ‌ای۳–۲۲۴ و اس‌اچ‌ای۳–۲۵۶ با همان مقاومت پیش‌نمایشی به اندازه پیشینیان اس‌اچ‌ای۲ خود فراهم کند، اما اس‌اچ‌ای۳–۳۸۴ و اس‌اچ‌ای۳–۵۱۲ مقاومت پیش‌نمایشی بسیار کمتری نسبت به پیشینیان اس‌اچ‌ای۲ خود پیدا می‌کردند. در اواخر ماه سپتامبر، تیم کچاک با بیان این‌که آن‌ها قبلاً امنیت ۱۲۸ بیتی با تعیین را به عنوان یک گزینه در پروپوزال اس‌اچ‌ای۳ خود پیشنهاد داده‌بودند، پاسخ داد. اگرچه از نظر آنها کاهش ظرفیت قابل توجیه بود، با توجه به پاسخ منفی، آنها پیشنهاد کردند ظرفیت به c = ۵۱۲ بیت برای همه نمونه‌ها افزایش یابد. این مقدار ظرفیت به همان اندازهٔ هر استاندارد قبلی با حداکثر سطح امنیتی ۲۵۶ بیتی بود، و در عین حال بازده مناسبی هم داشت، اما نه به اندازهٔ مقاومت پیش‌نمایشی 384- / 512 بیتی ارائه شده توسط اس‌اچ‌ای۲–۳۸۴ و اس‌اچ‌ای۲–۵۱۲. نویسندگان سعی کردند با این ادعا که "ادعاکردن یا اعتماد بر سطح قدرت امنیتی بالای ۲۵۶ بیت بی معنی است" خود را توجیه کنند. در اوایل اکتبر ۲۰۱۳، بروس اشنیر با انتقاد از تصمیم NIST مبنی بر تأثیرات مضر آن بر پذیرش الگوریتم، گفت: پل کرولی، رمزنگار و توسعه دهنده ارشد در یک شرکت مستقل توسعه نرم‌افزار، با گفتن این‌که کچاک قرار است قابل تنظیم باشد و هیچ دلیلی بر وجود سطوح امنیتی مختلف درون یک اصل اولیه وجود ندارد، حمایت خود از این تصمیم را بیان کرد. وی همچنین اضافه کرد: برخی گمان‌ها نیز مبنی بر ایجاد تغییرات داخلی در کچاک وجود داشت. تیم کچاک این موضوع را روشن کرد و اظهار داشت که پیشنهاد NIST برای اس‌اچ‌ای۳ زیرمجموعه ای از خانواده کچاک است که برای آن بشود با استفاده از کد مرجع ارسال شده به مسابقه، بردارهای تست تولید کرد و این پیشنهاد نتیجه یک سری بحث‌ها بین آنها و تیم درهم‌سازی NIST بود. همچنین، بروس اشنایر اظهارات قبلی خود را اصلاح کرد و گفت: در پاسخ به این بحث و گفتگو، در نوامبر ۲۰۱۳ جان کلسی از NIST پیشنهاد بازگشت به طرح اصلی برای همه نمونه‌های جایگزینی قطره ای اس‌اچ‌ای۲ را داد. | ## جمع‌بندی | فرم‌های با ظرفیت کاهش‌یافته با عنوان SHAKE۱۲۸ و SHAKE۲۵۶ منتشر شدند، که عدد آن‌ها سطح امنیتی را نشان می‌دهد و تعداد بیت‌های خروجی متغیر است، اما باید دو برابر مقاومت موردنیاز در برابر تصادم باشد.