اس‌اچ‌ای-۳

الگوریتم‌های ایمن درهم‌ساز
مفاهیم
توابع درهم‌ساز · اس‌اچ‌ای · دی‌اس‌اِی
استانداردهای اصلی
اس‌اچ‌ای۰ · اس‌اچ‌ای۱ · اس‌اچ‌ای۲ · اس‌اچ‌ای-۳

اس‌اچ‌ای۳
(کچاک)

عمومی
طراحان	گیدو برتونی، جوان دیمِن، مایکل پیترز و ژیل وان آش.
تاریخ اولین انتشار	۲۰۱۵
بهترین تحلیل رمز منتشر شده
حمله پیش نمایش به کچاک-۵۱۲ به ۸ دور کاهش یافت که به ۵۱۱٫۵ ۲ زمان و ۵۰۸ ۲ حافظه نیاز دارد. تمایزدهنده‌های دارای مجموع صفر برای یک Keccak-f [1600] کامل ۲۴ دوره وجود دارند، اگرچه نمی‌توان از آنها برای حمله به خود تابع درهم‌ساز استفاده کرد.

اس‌اچ‌ای۳ (الگوریتم امن درهم‌ساز ۳) آخرین عضو خانواده الگوریتم امن درهم‌ساز است که توسط مؤسسه ملی فناوری و استانداردها در ۵ اوت ۲۰۱۵ منتشر شد. ساختار داخلی اس‌اچ‌ای۳ با ساختار اس‌اچ‌ای-۱ و اس‌اچ‌ای-۲ که بیشتر شبیه ام‌دی۵ می‌باشند تفاوت دارد، اگرچه عضوی از همان سری استانداردها محسوب می‌شود.

اس‌اچ‌ای۳ یک زیر مجموعه از خانواده بدوی گسترده‌تر رمزنگاری Keccak(‎/ˈkɛtʃæk, -ɑːk/‎) است، که توسط گیدو برتونی، جوان دیمِن، مایکل پیترز و ژیل وان آش طراحی شده و بر روی RadioGatún بنا شده‌اند. نویسندگان Keccak کاربردهای اضافی برای این تابع ارائه داده‌اند، که البته هنوز توسط NIST استاندارد نشده‌اند، از جمله رمز دنباله‌ای، یک سیستم رمزگذاری تأیید هویت، یک برنامه درهم‌ساز «درختی» برای درهم‌سازی سریعتر بر روی برخی معماری‌های خاص، و رمزهای AEAD کیاک(Keyak) و کِتجه(Ketje).

Keccak مبتنی بر یک رویکرد جدید به نام ساخت اسفنجی است. ساخت اسفنجی مبتنی بر یک تابع تصادفی گسترده تصادفی یا جایگشت تصادفی است و این امکان را می‌دهد که هر مقدار از داده وارد شود("جذب" در اصطلاحات اسفنجی)، و هر مقدار از داده بیرون انداخته شود("فشردن")، در حالی که با توجه به همه ورودی‌های قبلی به عنوان یک تابع نیمه تصادفی عمل می‌کند. این منجر به انعطاف‌پذیری زیادی می‌شود.

NIST در حال حاضر برنامه ای برای برداشت اس‌اچ‌ای۲ یا حذف آن از استاندارد اصلاح شده ایمن درهم‌سازی ندارد. هدف از اس‌اچ‌ای۳ این است که می‌تواند در برنامه‌های فعلی در صورت لزوم مستقیماً جایگزین اس‌اچ‌ای۲ شود و استحکام ابزار کلی الگوریتم درهم‌ساز NIST را به طرز قابل توجهی بهبود بخشد.

سازندگان الگوریتم‌های Keccak و توابع اس‌اچ‌ای۳ پیشنهاد می‌کنند از تابع سریعتر KangarooTwelve با پارامترهای تنظیم شده و حالت درهم‌سازی درختی جدید بدون سربار اضافی، برای پیام‌های با اندازه کوچک استفاده کنند.

تاریخچه

الگوریتم Keccak اثری از گیدو برتونی، جوان دیمِن (که وی همچنین رمزنگاری Rijndael را با همکاری وینسنت رجمن طراحی کرده)، مایکل پیترز، و ژیل وان آش می‌باشد. این الگوریتم مبتنی بر طرح‌های درهم‌سازی قبلی PANAMA و RadioGatún است. PANAMA در سال ۱۹۹۸ توسط دیمِن و کریگ کلَپ طراحی شده‌است. RadioGatún، جانشین PANAMA، توسط پیترز، دیمِن و وان آش طراحی شد و در کارگاه NIST Hash در سال ۲۰۰۶ ارائه شد. کد منبع اجرای مرجع از طریق چشم پوشی CC0 به حوزه عمومی اختصاص داده شده است.

در سال ۲۰۰۶، NIST برای ایجاد یک استاندارد جدید درهم‌سازی، اس‌اچ‌ای۳، اقدام به سازماندهی رقابت تابع درهم‌سازی NIST کرد. اس‌اچ‌ای۳ قرار نیست که جایگزین اس‌اچ‌ای۲ شود، زیرا هیچ حمله قابل توجهی به اس‌اچ‌ای۲ نشان داده نشده‌است. به دلیل حملات موفقیت‌آمیز بر اس‌اچ‌ای۰، ام‌دی۵ واس‌اچ‌ای۱، NIST احساس نیاز به یک رمزنگاری درهم‌ساز جایگزین و متفاوت کرد، که SHA-3 نام گرفت.

پس از یک دوره تنظیم، پذیرش‌ها باید تا پایان سال ۲۰۰۸ ارسال می‌شدند. کچاک(Keccak) به عنوان یکی از ۵۱ نامزد پذیرفته شد. در ژانویه ۲۰۰۹، ۱۴ الگوریتم برای دور دوم انتخاب شد. کچاک به آخرین مرحله در دسامبر ۲۰۱۰ رسید.

در طول مسابقه، به شرکت کنندگان اجازه داده شد الگوریتم‌هایشان را «اصلاح» کنند تا مشکلاتی که کشف شده بود حل شوند. تغییراتی که در کچاک ایجاد شده‌است به این شرح است:

• تعداد دورها از 12 + ℓ به 12 + 2ℓ افزایش یافت تا از نظر امنیتی محافظه کارتر باشد.
• message padding از یک طرح پیچیده‌تر به الگوی ساده 1 ^* 10 که در زیر شرح داده شده تغییر یافت.
• نرخ r به جای گرد کردن پایین به نزدیکترین توان ۲، به حد امنیتی (security limit) افزایش یافت.

در تاریخ ۲ اکتبر ۲۰۱۲، کچاک به عنوان برنده مسابقه انتخاب شد.

در سال ۲۰۱۴، NIST پیش نویس FIPS 202 «استاندارد SHA-3: توابع هش مبتنی بر permutation و توابع خروجی قابل گسترش» را منتشر کرد. FIPS 202 در ۵ اوت ۲۰۱۵ تصویب شد.

در ۵ اوت ۲۰۱۵، NIST اعلام کرد که اس‌اچ‌ای۳ به یک استاندارد درهم‌سازی تبدیل شده‌است.

طرح

ساخت اسفنج برای توابع درهمساز. P_i‌ها ورودی، و Z_i‌ها خروجی درهم‌سازی شده می‌باشند. «ظرفیت» استفاده نشدهٔ c باید دو برابر مقاومت مورد نظر در برابر حمله تصادم یا حمله پیش‌نمایش باشد.

اس‌اچ‌ای۳ از ساخت اسفنجی استفاده می‌کند، که در آن داده‌ها «جذب» اسفنج می‌شوند، سپس نتیجهٔ آن‌ها به بیرون «فشرده» می‌شود. در مرحله جذب، بلوک‌های پیام XOR شده و به زیر مجموعه ای از حالت تبدیل می‌شوند، که بعداً با استفاده از یک تابع جایگشت $f$ به صورت یک کل درمی‌آیند. در مرحله «فشردن»، بلوک‌های خروجی از همان زیر مجموعه حالت خوانده می‌شوند، و با استفاده از تابع تغییر حالت $f$ تغییر می‌یابند. سایز بخشی از حالت که نوشته شده و خوانده شده‌است «نرخ» (مشخص شده با $r$) نامیده می‌شود، و اندازه بخشی که توسط ورودی / خروجی دست نخورده می‌ماند، «ظرفیت» (مشخص شده با $c$) نامیده می‌شود. ظرفیت تعیین‌کننده امنیت طرح است. حداکثر سطح امنیتی برابر نصف ظرفیت است.

با درنظر گرفتن یک رشته بیت ورودی $N$ ، یک تابع پدینگ مانند $pad$ ، یک تابع جایگشت $f$ که روی بلوک‌های بیتی با عرض $b$ کار می‌کند، نرخ $r$ و طول خروجی $d$ ، ظرفیتی برابر با $c=b-r$ و ساخت اسفنجی $Z={\text{sponge}}[f,pad,r](N,d)$ را داریم، می‌دهد رشتهٔ بیتی $Z$ به طول $d$، که به شرح زیر کار می‌کند:

• پرکردن ورودی N با استفاده از تابع pad، که درنتیجه یک padded bit string مانند P با طولی بخش پذیر بر $r$ (به طوری که $n={\text{len}}(P)/r$ عدد صحیح باشد) می‌دهد.
• شکستن P به n قطعه متوالی r بیتی P₀, … , P_n−1
• مقداردهی اولیه وضعیت S به یک رشته که b بیت از آن مقدار صفر دارند
• ورودی را جذب حالت کنید: برای هر بلوک P_i:
  • گسترش 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 و حتی با ۱ بیت (که درمجموع حالتی با ۲۵ بیت می‌سازد) هم تعریف شده‌است. اندازه‌های حالت کوچک می‌تواند برای آزمایش حملات تحلیل رمزنگاری مورد استفاده قرار گیرد، و اندازه‌های حالت متوسط (از w = ۸، با ۲۰۰ بیت، تا w = ۳۲، با ۸۰۰ بیت) در برنامه‌های کاربردی سبک استفاده می‌شود.

برای موارد اس‌اچ‌ای۳–۲۲۴، اس‌اچ‌ای۳–۲۵۶، اس‌اچ‌ای۳–۳۸۴، و اس‌اچ‌ای۳–۵۱۲، مقدار r از d بیشتر است، بنابراین در مرحله فشردن نیازی به جایگشت‌های بلوکی اضافی نیست. d بیت اول از وضعیت، همان درهم‌سازی مورد نظر ما می‌باشد. با این حال، SHAKE-۱۲۸ و SHAKE-۲۵۶ امکان خروجی با طول دلخواه را به ما می‌دهند، که در برنامه‌هایی مانند رمزگذاری با پرکردن نامتقارن بهینه مفید است.

لایه گذاری

برای اطمینان از اینکه پیام را می‌توان به بلوک‌های r بیتی مساوی تقسیم کرد، لایه‌گذاری لازم است. اس‌اچ‌ای۳ از الگوی ۱^*۱۰ در عملکرد لایه‌گذاری خود استفاده می‌کند: یک بیتِ ۱، به‌دنبال آن صفر یا بیشتر بیتِ ۰ (حداکثر r − ۱ تا) و یک بیتِ ۱ نهایی.

حداکثر r − ۱ بیت صفر زمانی رخ می‌دهد که آخرین بلوک پیام r − ۱ بیت طول داشته باشد. دراین‌حالت بلوک دیگری پس از بیتِ ۱ اولیه اضافه می‌شود که حاوی r − ۱ بیتِ صفر قبل از بیتِ ۱ نهایی است.

دو بیتِ ۱، حتی اگر طول پیام در حال حاضر بر r بخش‌پذیر باشد، اضافه می‌شوند. در این حالت، یک بلوک دیگر به پیام اضافه می‌شود که حاوی یک بیتِ ۱ است، به دنبال آن یک بلوک r − ۲ تایی بیتِ صفر و یک بیتِ ۱ دیگر می‌باشد. این کار لازم است برای اینکه که یک پیام که طولش بر r بخش پذیر است و به چیزی که شبیه لایه‌گذاری به نظر می‌رسد ختم می‌شود، همان درهم‌سازی را تولید نکند که یک پیام دیگری که آن بیت‌ها را ندارد تولید می‌کند.

بیتِ ۱ اولیه برای این نیاز است که پیام‌هایی که فقط چند بیتِ ۰ اضافی آخرشان متمایز است، یک درهم‌سازی مشابه ایجاد نکنند.

موقعیت بیتِ ۱ نهایی نشان می‌دهد که از کدام نرخ r استفاده شده‌است (لایه‌گذاری چند نرخی)، که برای اثبات امنیت لازم است تا برای انواع مختلف درهم‌سازی کار کند. بدون آن، درهم‌سازی‌های مختلف از یک پیام کوتاه یکسان می‌تواند دارای برش یکسانی شود.

جایگشت بلوکی

تبدیل بلوکی f، که Keccak-f [1600] برای اس‌اچ‌ای۳ است، جایگشتی است که از عملیات XOR، AND و NOT استفاده می‌کند و برای پیاده‌سازی آسان در هردوی نرم‌افزار و سخت‌افزار طراحی شده‌است.

این تبدیل برای هر طول کلمه‌ای که توانی از دو باشد، w = 2^ℓ تعریف شده‌است. نسخه اصلی اس‌اچ‌ای۳، از کلمات ۶۴ بیتی، ℓ = ۶ استفاده می‌کند.

آرایهٔ حالت می‌تواند به صورت یک آرایهٔ ۵ × ۵ × w بیتی در نظر گرفته شود. فرض کنید a[i][ j][k] برابر بیتِ (۵i + j) × w + k ام از ورودی باشد، که در یک مدل Little Endian از قرارداد شمارش بیتی و اندیس گذاری ردیف-اول فرض شده‌است، یعنی i شماره ردیف، j شماره ستون و k شماره بیت را مشخص می‌کند.

اندیس گذاری حسابی برای دو بعد اول، در پیمانه ۵ و برای بعد سوم در پیمانه w انجام می‌شود.

تابع جایگشت بلوکیِ پایه، متشکل از ۱۲ + ۲ℓ دورِ پنج مرحله‌ای است:

θ (تتا)

اعداد زوج و فرد هر یک از ۵w (برابر ۳۲۰ اگر w = ۶۴) ستون ۵بیتی را حساب کرده و xor آن را با دو ستون مجاورش در یک الگوی منظم محاسبه کنید. به‌طور دقیق‌تر، a[i][ j][k] ← a[i][ j][k] ⊕ parity(a[0...4][ j−1][k]) ⊕ parity(a[0...4][ j+1][k−۱])

ρ (رو)

هر کدام از ۲۵ کلمه را با یک عدد مثلثی متمایز مانند ۰، ۱، ۳، ۶، ۱۰، ۱۵ ،...شیفت دورانی دهید. به‌طور دقیق،a[۰][۰] دوران نمی‌یابد، و به ازای هر ۰ ≤ t < ۲۴،

a[i][ j][k] ← a[i][ j][k−(t+1)(t+۲)/۲]، درصورتی که${\begin{pmatrix}i\\j\end{pmatrix}}={\begin{pmatrix}3&2\\1&0\end{pmatrix}}^{t}{\begin{pmatrix}0\\1\end{pmatrix}}$ .

π (پی)

۲۵ کلمه را در یک الگوی ثابت جایگشت دهید a[j][2i+3j] ← a[ i][j]

χ (خی)

بیت به یبت با ردیف‌ها ترکیب کنید، با استفاده از رابطهٔ x ← x ⊕ (¬y & z) به‌طور دقیق، a[i][ j][k] ← a[i][ j][k] ⊕ (¬a[i][ j+۱][k] & a[i][ j+۲][k]) این تنها عملیات غیر خطی در اس‌اچ‌ای۳ است.

ι (iota)

یک ثابت دور را با یک کلمه از حالت xor کنید. به‌طور دقیق، در دور nام، به ازای ۰ ≤ m ≤ ℓ، مقدار a[0][0][2^m−۱] با بیت m + 7nام از یک دنباله اجرایی حاصل از ثبات تغییر بازخورد خطی(LFSR) درجه-۸ xor می‌شود. این کار تقارنی را که در مراحل دیگر حفظ می‌شود، می‌شکند.

سرعت

سرعت درهم‌سازی پیام‌های طولانی توسط اس‌اچ‌ای۳، بسیار تحت تأثیر محاسبهٔ f = Keccak-f [۱۶۰۰] و XOR کردن S با مقدار گسترش‌یافتهٔ P _i، که یک عملیات روی b = ۱۶۰۰ بیت است، می‌باشد. با این حال، از آنجایی که c بیت آخر مقدار گسترش‌یافتهٔ P _i درهرصورت صفر هستند، و XOR با ۰ یک NOP است، کافی است عملیات XOR را فقط برای r بیت انجام دهیم(r = ۱۶۰۰–۲ × ۲۲۴ = ۱۱۵۲ بیت برای اس‌اچ‌ای۳–۲۲۴، ۱۰۸۸ بیت برای اس‌اچ‌ای۳–۲۵۶، ۸۳۲ بیت برای اس‌اچ‌ای۳–۳۸۴ و ۵۷۶ بیت برای اس‌اچ‌ای۳–۵۱۲). هرچه r پایین‌تر باشد (و برعکس، هرچه c = b - r = 1600 - r بالاتر باشد)، درهم‌سازی ناکارآمدتر و پرهزینه‌تر اما ایمن تر می‌شود، زیرا تعداد بیت کمتری از پیام می‌تواند با حالت XOR شود (یک عملیات سریع) قبل از هر بار استفاده از f که از نظر محاسباتی پرهزینه است. نویسندگان سرعت‌های زیر را برای اجرای پیاده‌سازی‌های نرم‌افزاری Keccak-f [1600] به اضافه XOR کردن ۱۰۲۴بیت گزارش می‌دهند، که تقریباً با اس‌اچ‌ای۳–۲۵۶ مطابقت دارد:

• ۵۷٫۴ cpb در IA-32 , Intel Pentium 3
• ۴۱ cpb در IA-32 + MMX , Intel Pentium ۳۲
• ۲۰ cpb در IA-32 + SSE , Intel Core 2 Duo یا AMD Athlon ۶۴
• ۱۲٫۶ cpb در دستگاه معمولی مبتنی بر x۸۶–۶۴
• ۶–۷ cpb در IA-64

برنشتاین به‌طور دقیق برای اس‌اچ‌ای۳–۲۵۶ روی x۸۶–۶۴، عدد ۱۱٫۷–۱۲٫۲۵ cpb را بسته به CPU اندازه‌گیری کرده‌است. اس‌اچ‌ای۳ به دلیل کند بودن در معماری‌های مجموعه دستورالعمل (CPU) که دستورالعمل خاصی برای محاسبه سریعتر توابع Keccak ندارند، مورد انتقاد قرار گرفته‌است - اس‌اچ‌ای۲–۵۱۲ بیش از دو برابر سریعتر از اس‌اچ‌ای۳، و اس‌اچ‌ای۱ بیش از سه برابر سریعتر از آن روی یک پردازنده Intel Skylake با فرکانس کلاک ۳٫۲ گیگاهرتز اجرا می‌شود. نویسندگان با پیشنهاد استفاده از SHAKE۱۲۸ و SHAKE۲۵۶ به جای اس‌اچ‌ای۳–۲۵۶ و اس‌اچ‌ای۳–۵۱۲، به قیمت کاهش یافتن نصف مقاومت‌پیش‌نمایش (اما با همان مقاومت برخورد)، به این انتقاد واکنش نشان داده‌اند. با این کار، عملکرد برابر می‌شود با اس‌اچ‌ای۲–۲۵۶ و اس‌اچ‌ای۲–۵۱۲.

با این حال، از نظر پیاده‌سازی سخت‌افزاری، اس‌اچ‌ای۳ به طرز ویژه‌ای سریعتر از سایر فینالیست‌ها است، و همچنین سریع تر از اس‌اچ‌ای۲ و اس‌اچ‌ای۱.

معماری‌های ARMv8 و IBM s۳۹۰x در حال حاضر (از سال ۲۰۱۸) شامل دستورالعمل‌های ویژه ای هستند که الگوریتم‌های Keccak را قادر می‌سازند سریعتر اجرا شوند.

نمونه‌ها

استاندارد NIST نمونه‌های زیر را برای پیام M و طول خروجی d نشان می‌دهد:

نمونه	طول خروجی d	نرخ r = اندازه بلوک	ظرفیت c	تعریف	نقاط قوت امنیتی در بیت‌ها
					برخورد	پیش نمایش	پیش نمایش دوم
اس‌اچ‌ای۳–۲۲۴ (M)	۲۲۴	۱۱۵۲	۴۴۸	Keccak[448](M || 01, 224)	۱۱۲	۲۲۴	۲۲۴
اس‌اچ‌ای۳–۲۵۶ (M)	۲۵۶	۱۰۸۸	۵۱۲	Keccak[512](M || 01, 256)	۱۲۸	۲۵۶	۲۵۶
اس‌اچ‌ای۳–۳۸۴ (M)	۳۸۴	۸۳۲	۷۶۸	Keccak[768](M || 01, 384)	۱۹۲	۳۸۴	۳۸۴
اس‌اچ‌ای۳–۵۱۲ (M)	۵۱۲	۵۷۶	۱۰۲۴	Keccak[1024](M || 01, 512)	۲۵۶	۵۱۲	۵۱۲
SHAKE128(M, d)	d	۱۳۴۴	۲۵۶	Keccak[256](M || 1111, d)	min(d/2,128)	≥min(d,128)	min(d,128)
SHAKE256(M, d)	d	۱۰۸۸	۵۱۲	Keccak[512](M || 1111, d)	min(d/2,256)	≥min(d,256)	min(d,256)

با تعاریف زیر

• Keccak[c](N, d)=sponge[Keccak-f[1600], pad10^*1, r](N, d)
• Keccak-f [1600] = Keccak-p [1600، 24]
• c ظرفیت است
• r نرخ است و = ۱۶۰۰ - c می‌باشد
• N رشته بیت ورودی است

توجه داشته باشید که پسوندهای اضافه شده به صورت رشته‌های بیتی نوشته می‌شوند، نه رقم‌های مبنای ۱۶.

نمونه‌های اس‌اچ‌ای۳ جایگزین قطره‌ای برای اس‌اچ‌ای۲ هستند، با همان ادعاهای امنیتی یکسان. نمونه‌های SHAKE به اصطلاح توابع خروجی قابل گسترش XOF گفته می‌شوند. به عنوان مثال، SHAKE128(M، ۲۵۶) می‌تواند به عنوان یک تابع درهم‌سازی با طول ۲۵۶ بیت و امنیت کلی ۱۲۸بیتی استفاده شود.

توجه داشته باشید که همه نمونه‌ها، تعدادی بیت به پیام اضافه می‌کنند، که سمت راست‌ترین آنها نشان‌دهندهٔ پسوند جدایی دامنه است. هدف از این کار این است که اطمینان حاصل شود نمی‌توان پیام‌هایی با همان خروجی درهم‌سازی‌شده را برای کاربردهای مختلف برنامه درهم‌سازی Keccak ساخت. پسوندهای جدایی دامنه زیر موجودند:

پسوند	معنی
… ۰	برای استفاده بعدی محفوظ است
۰۱	SHA-3
… ۱۱	RawSHAKE

RawSHAKE پایه ای است برای رمزگذاری ساکورا جهت درهم‌سازی درختی، که هنوز استاندارد نشده‌است. با این حال، پسوند SHAKE با دقت انتخاب شده‌است تا این‌که سازگار با نسخه‌های بعدی ساکورا باشد. قبل از اعمال RawSHAKE، Sakura بیت ۰ را برای یک هاپ زنجیره‌ای یا بیت ۱ را برای یک پیام، سپس ۱۰^*۰ را برای یک گره غیرنهایی (داخلی) یا ۱ را برای یک گره نهایی، اضافه می‌کند. درهم‌سازی متوالی مربوط به درخت هاپ با یک گره پیام است، بدین معنی که ۱۱ قبل از اعمال RawSHAKE به پیام اضافه می‌شود؛ بنابراین، SHAKE XOFs مقدار ۱۱۱۱ را به پیام اضافه می‌کند، یعنی ۱ برای پیام، ۱ برای گره نهایی و ۱۱ برای پسوند جدایی دامنه RawSHAKE.

از آنجا که لایه‌گذاری ۱۰^*۱ همیشه حداقل دو بیت را اضافه می‌کند، در کتابخانه‌های مرتب با بایت همیشه شش بیت صفر استفاده نشده وجود دارد؛ بنابراین، این بیت‌های اضافی هرگز پیام لایه‌گذاری را طولانی‌تر نمی‌کنند.

نمونه‌های اضافی

در دسامبر سال ۲۰۱۶، NIST یک سند جدید با نام NIST SP.800-185 منتشر کرد که عملکردهای اضافی مشتق شده اس‌اچ‌ای۳ را شرح می‌دهد:

نمونه	شرح
cSHAKE128 (X , L، N , S)	یک نسخه از SHAKE با پشتیبانی از جداسازی صریح دامنه از طریق پارامترهای شخصی‌سازی
cSHAKE256 (X , L، N , S)
KMAC128 (K , X، L , S)	یک تابع درهم‌سازی کلید دار بر اساس Keccak. همچنین می‌تواند بدون کلید به عنوان یک تابع درهم‌سازی معمولی مورد استفاده قرار گیرد.
KMAC256 (K , X، L , S)
KMACXOF128 (K , X، L , S)
KMACXOF256 (K , X، L , S)
TupleHash128 (X , L، S)	یک تابع برای درهم‌سازی یک چندتایی (تاپل) از رشته‌ها. خروجی این تابع، هم به محتویات و هم توالی رشته‌های ورودی بستگی دارد.
TupleHash256 (X , L، S)
TupleHashXOF128 (X , L، S)
TupleHashXOF256 (X , L، S)
ParallelHash128 (X , B، L , S)	یک تابع که به منظور بهره‌برداری از موازی‌سازی در پردازنده‌های مدرن حهت درهم‌سازی سریع‌تر ساخته شده‌است. بر خلاف KangarooTwelve، از Keccak با دورِکاهش‌یافته استفاده نمی‌کند.
ParallelHash256 (X , B، L , S)
ParallelHashXOF128 (X , B، L , S)
ParallelHashXOF256 (X , B، L , S)

• X رشته بیت ورودی اصلی است. این رشته ممکن است هر طولی، از جمله صفر داشته باشد.
• L عدد صحیحی است که تعداد بیت خروجی درخواستی را نشان می‌دهد.
• N نام یک تابع به صورت رشتهٔ بیتی است که توسط NIST برای تعریف توابع بر اساس cSHAKE استفاده می‌شود. هنگامی که هیچ تابعی غیر از cSHAKE مورد نظر باشد، N با رشته خالی مقداردهی می‌شود.
• S یک رشتهٔ بیتی جهت سفارشی‌سازی است. کاربر این رشته را برای تعریف یک پارامتر متغیر از تابع انتخاب می‌کند. هنگامی که هیچ سفارشی سازی مورد نظر نیست، S با رشته خالی مقداردهی می‌شود.
• K یک کلید به صورت رشتهٔ بیتی با هر طولی، از جمله صفر است.
• B تعداد بایت‌های هر بلوک حهت درهم‌سازی موازی است. B می‌تواند هر عدد صحیحی باشد به طوری که 0 <B <2 ²⁰⁴⁰.

تحولات بعدی

درخت درهم‌سازی

در سال ۲۰۱۶، همان تیمی که توابع اس‌اچ‌ای۳ و الگوریتم Keccak را ایجاد کرده بودند، یک جایگزین سریعتر با تعداد دورهای کاهش‌یافته (کاهش‌یافته به ۱۲ و ۱۴دور، از ۲۴ دور در اس‌اچ‌ای۳) که به دلیل استفاده از درهم‌سازی درختی، می‌تواند از قابلیت اجرای موازی بهره بگیرد، ارائه کردند: KangarooTwelve و MarsupilamiFourteen.

این توابع با ParallelHash، تابع درهم‌سازی استاندارشده FIPS باقابلیت موازی سازی و مبتنی بر Keccak، از نظر موازی‌سازی متفاوت است، زیرا در پیام‌های با اندازه کوچک سریعتر از ParallelHash هستند.

تعداد دور کاهش یافته با تلاش بسیار زیاد تحلیلی رمزنگاری متمرکز بر Keccak که نتوانست در حمله عملیاتی به هیچ الگوریتم Keccak با تعداد دور نزدیک به دوازده ایجاد کند، تصدیق می‌شود. این الگوریتم‌های با سرعت بالاتر جزئی از اس‌اچ‌ای۳ نیستند (زیرا آنها بعداً توسعه یافته‌اند)، و بنابراین سازگار با FIPS نیستند. اما آنها به همان اندازه توابع اس‌اچ‌ای۳ ایمن هستند، زیرا آنها از همان جایگشت Keccak استفاده می‌کنند و هیچ حمله ای به Keccak ۱۲ دوری نشده‌است.

KangarooTwelve یک نسخه با تعداد دور کاهش یافته (از ۲۴ به ۱۲ دور) با عملکرد بالاتر از Keccak است که ادعا می‌کند ۱۲۸ بیت امنیت دارد در حالی که عملکردی برابر با ۰٫۵۵ چرخه در هر بایت دارد. این الگوریتم یک پیش نویس IETF RFC است.

MarsupilamiFourteen، نسخهٔ اندکی تغییریافتهٔ KangarooTwelve، از ۱۴ دور جایگشت Keccak استفاده می‌کند و ادعا می‌کند ۲۵۶ بیت امنیت دارد. توجه داشته باشید که امنیت ۲۵۶ بیتی در عمل مفیدتر از امنیت ۱۲۸ بیتی نیست، اما ممکن است طبق برخی استانداردها مورد نیاز باشد. درحال حاضر ۱۲۸ بیت برای پیروزشدن بر حملات brute-force بر روی سخت‌افزار فعلی کافی است، بنابراین داشتن امنیت ۲۵۶ بیتی ارزش عملی نمی‌افزاید، مگر اینکه کاربر نگران پیشرفتهای چشمگیر سرعت کامپیوترهای کلاسیک باشد. برای مقاومت در برابر رایانه‌های کوانتومی، به زیر مراجعه کنید.

KangarooTwelve و MarsupilamiFourteen، مشابه SHAKE، توابع با قابلیت گسنرش خروجی هستند، بنابراین آنها برای یک پیام مشترک با طول خروجی متفاوت، خروجی نزدیک به هم تولید می‌کنند (خروجی طولانی‌تر تعمیم‌یافتهٔ خروجی کوتاه‌تر می‌باشد). توابع درهم‌ساز مانند اس‌اچ‌ای۳ یا ParallelHash (به جز انواع مختلف XOF) چنین خاصیتی از خود نشان نمی‌دهند.

ساخت و ساز فارفاله(Farfalle)

در سال ۲۰۱۶، تیم Keccak یک ساخت و ساز مختلف به نام ساخت و ساز فارفاله، و Kravatte، یک نمونه از فارفاله که از جایگشت Keccak-p استفاده می‌کند، منتشر کردند، به‌علاوهٔ دو الگوریتم رمزگذاری معتبر

Kravatte-SANE و Kravatte-SANSE

امنیت در برابر حملات کوانتومی

یک نتیجه کلی (الگوریتم گرور) وجود دارد که کامپیوترهای کوانتومی می‌توانند یک حمله پیش‌نمایش ساختار یافته را در ${\sqrt {2^{d}}}=2^{d/2}$ انجام دهند، در حالی که یک حمله brute-force کلاسیک به 2^d نیاز دارد. یک حمله ساختار یافته پیش‌نمایش نشانگر یک حمله پیش‌نمایش دوم و در نتیجه یک حمله تصادم است. یک کامپیوتر کوانتومی همچنین می‌تواند یک حمله روز تولد را در ${\sqrt[{3}]{2^{d}}}=2^{d/3}$ (اگرچه این مورد اختلاف است) انجام دهد، درنتیجه مقاومت در برابر تصادم را ازبین ببرد. با توجه به این که حداکثر قدرت می‌تواند $c/2$ باشد، کران‌های بالای زیر بر روی امنیت کوانتومی اس‌اچ‌ای۳ حاصل می‌شوند:

نمونه	نقاط قوت امنیتی در بیت‌ها
	تصادم (براسارد و همکاران)	تصادم (برنشتاین)	پیش نمایش	پیش نمایش ۲
SHA3-224 (M)	۷۴⅔	۱۱۲	۱۱۲	۱۱۲
SHA3-256 (M)	۸۵⅓	۱۲۸	۱۲۸	۱۲۸
SHA3-384 (M)	۱۲۸	۱۹۲	۱۹۲	۱۹۲
SHA3-512 (M)	۱۷۰⅔	۲۵۶	۲۵۶	۲۵۶
SHAKE128(M, d)	min(d/3,128)	min(d/2,128)	≥min(d/2,128)	min(d/2,128)
SHAKE256(M, d)	min(d/3,256)	min(d/2,256)	≥min(d/2,256)	min(d/2,256)

نشان داده شده‌است که ساخت و ساز مرکل-دامگورد، که در اس‌اچ‌ای۲ از آن استفاده می‌شود، در حال فروپاشی است و به تبع آن، مقاوم در برابر تصادم کوانتومی است، اما برای ساخت اسفنج مورد استفاده در اس‌اچ‌ای۳، نویسندگان فقط برای این مورد که تابع بلوکی f باهزینه‌کم وارون‌پذیر نیست اثبات کرده‌اند. Keccak-f [۱۶۰۰]، ولی، باهزینه‌کم وارون‌پذیر است و بنابراین اثبات آنها کاربردی نیست.

بحث و گفتگو در مورد تغییر ظرفیت

در فوریه ۲۰۱۳در کنفرانس RSA، و سپس در اوت ۲۰۱۳ در CHES، NIST اعلام کرد که مقادیر مختلفی را برای ظرفیت، که پارامتر امنیتی است، برای استاندارد اس‌اچ‌ای۳، در مقایسه با ارسال اولیه، انتخاب می‌کنند. این تغییرات باعث سردرگمی شد.

مسابقات توابع درهم‌سازی، خواستار توابع درهم‌ساز شد که حداقل به همان اندازه نمونه‌های اس‌اچ‌ای۲ امنیت داشته باشند. به این معنی که یک خروجی d بیتی باید مقاومت d/۲ بیتی درمقابل حملات تصادم و مقاومت d بیتی در برابر حملات پیش‌نمایش داشته باشد، مقدار حداکثری که برای d بیت از خروجی دست یافتنی است. اثبات امنیتی Keccak امکان تنظیم سطح امنیتی را مبتنی بر «ظرفیت» c می‌دهد، که مقاومت c/۲ بیتی در برابر هردو حمله تصادم و حمله پیش‌نمایش فراهم می‌کند. جهت برآورده ساختن قوانین اصلی رقابت، نویسندگان کچاک c = ۲d را پیشنهاد کردند. تغییر اعلام شده برای پذیرش همان امنیت d/۲ بیتی برای همه اشکال حمله و استانداردسازی c = d بود. این می‌توانست با فراهم کردن امکان درهم‌سازی d بیت اضافه‌تر از ورودی درهربار تکرار چرخه، سرعت Keccak را بالا ببرد؛ ولی، توابع درهم‌سازی دیگر نمی‌توانستند جایگزین‌های قطره‌ای با همان مقاومت پیش‌نمایشی اس‌اچ‌ای۲ باشند. با این کار مقاومت پیش‌نمایشی به نصف کاهش می‌یافت، باعث می‌شد در برابر پیشرفت‌های محاسبات کوانتومی آسیب‌پذیر شود، که به‌طور مؤثری آن را دوباره به نصف کاهش می‌داد.

در سپتامبر ۲۰۱۳، دنیل جی برنشتاین در لیست پستی انجمن درهم‌سازی NIST پیشنهاد کرد که امنیت را با رساندن ظرفیت به ۵۷۶ بیت، که در ابتدا به عنوان پیش فرض کچاک پیشنهاد شده بود، و علاوه بر این در مشخصات فنی اس‌اچ‌ای۳ گنجانده نشده بود، تقویت کنند. این کار می‌توانست حداقل یک اس‌اچ‌ای۳–۲۲۴ و اس‌اچ‌ای۳–۲۵۶ با همان مقاومت پیش‌نمایشی به اندازه پیشینیان اس‌اچ‌ای۲ خود فراهم کند، اما اس‌اچ‌ای۳–۳۸۴ و اس‌اچ‌ای۳–۵۱۲ مقاومت پیش‌نمایشی بسیار کمتری نسبت به پیشینیان اس‌اچ‌ای۲ خود پیدا می‌کردند. در اواخر ماه سپتامبر، تیم کچاک با بیان این‌که آن‌ها قبلاً امنیت ۱۲۸ بیتی با تعیین c = ۲۵۶ را به عنوان یک گزینه در پروپوزال اس‌اچ‌ای۳ خود پیشنهاد داده‌بودند، پاسخ داد. اگرچه از نظر آنها کاهش ظرفیت قابل توجیه بود، با توجه به پاسخ منفی، آنها پیشنهاد کردند ظرفیت به c = ۵۱۲ بیت برای همه نمونه‌ها افزایش یابد. این مقدار ظرفیت به همان اندازهٔ هر استاندارد قبلی با حداکثر سطح امنیتی ۲۵۶ بیتی بود، و در عین حال بازده مناسبی هم داشت، اما نه به اندازهٔ مقاومت پیش‌نمایشی 384- / 512 بیتی ارائه شده توسط اس‌اچ‌ای۲–۳۸۴ و اس‌اچ‌ای۲–۵۱۲. نویسندگان سعی کردند با این ادعا که "ادعاکردن یا اعتماد بر سطح قدرت امنیتی بالای ۲۵۶ بیت بی معنی است" خود را توجیه کنند.

در اوایل اکتبر ۲۰۱۳، بروس اشنیر با انتقاد از تصمیم NIST مبنی بر تأثیرات مضر آن بر پذیرش الگوریتم، گفت:

There is too much mistrust in the air. NIST risks publishing an algorithm that no one will trust and no one (except those forced) will use.

پل کرولی، رمزنگار و توسعه دهنده ارشد در یک شرکت مستقل توسعه نرم‌افزار، با گفتن این‌که کچاک قرار است قابل تنظیم باشد و هیچ دلیلی بر وجود سطوح امنیتی مختلف درون یک اصل اولیه وجود ندارد، حمایت خود از این تصمیم را بیان کرد. وی همچنین اضافه کرد:

Yes, it's a bit of a shame for the competition that they demanded a certain security level for entrants, then went to publish a standard with a different one. But there's nothing that can be done to fix that now, except re-opening the competition. Demanding that they stick to their mistake doesn't improve things for anyone.

برخی گمان‌ها نیز مبنی بر ایجاد تغییرات داخلی در کچاک وجود داشت. تیم کچاک این موضوع را روشن کرد و اظهار داشت که پیشنهاد NIST برای اس‌اچ‌ای۳ زیرمجموعه ای از خانواده کچاک است که برای آن بشود با استفاده از کد مرجع ارسال شده به مسابقه، بردارهای تست تولید کرد و این پیشنهاد نتیجه یک سری بحث‌ها بین آنها و تیم درهم‌سازی NIST بود. همچنین، بروس اشنایر اظهارات قبلی خود را اصلاح کرد و گفت:

وقتی نوشتم که NIST «تغییرات داخلی» در الگوریتم ایجاد کرده‌است، اشتباه کردم. این بی‌دقتی من بود. جایگشت کچاک بدون تغییر باقی مانده‌است. آنچه NIST پیشنهاد کرد کاهش ظرفیت تابع درهم‌سازی جهت کمک به افزایش عملکرد بود. یکی از ویژگی‌های خوب کچاک این است که بسیار قابل تنظیم است.

در پاسخ به این بحث و گفتگو، در نوامبر ۲۰۱۳ جان کلسی از NIST پیشنهاد بازگشت به طرح اصلی c = ۲d برای همه نمونه‌های جایگزینی قطره ای اس‌اچ‌ای۲ را داد. این بازبینی در پیش نویس آوریل ۲۰۱۴ تأیید شد. این پیشنهاد در استاندارد انتشار نهایی در اوت ۲۰۱۵ پیاده‌سازی شد.

فرم‌های با ظرفیت کاهش‌یافته با عنوان SHAKE۱۲۸ و SHAKE۲۵۶ منتشر شدند، که عدد آن‌ها سطح امنیتی را نشان می‌دهد و تعداد بیت‌های خروجی متغیر است، اما باید دو برابر مقاومت موردنیاز در برابر تصادم باشد.

نمونه‌هایی از انواع اس‌اچ‌ای۳

مقادیر درهم‌سازی زیر از NIST.gov است:

 SHA3-224 ("")
6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
SHA3-256 ("")
a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
SHA3-384 ("")
0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
SHA3-512 ("")
a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26
SHAKE128 (""، 256)
7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26
SHAKE256 (""، 512)
46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab4840292eacb3b7c4be

تغییر یک بیت واحد باعث می‌شود که هر بیت در خروجی با احتمال ۵۰٪ تغییر کند که یک اثر بهمنی را نشان می‌دهد:

 SHAKE128("The quick brown fox jumps over the lazy dog", 256)
f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e
SHAKE128("The quick brown fox jumps over the lazy dof", 256)
853f4538be0db9621a6cea659a06c1107b1f83f02b13d1

مقایسه توابع اس‌اچ‌ای

در جدول زیر، حالت داخلی به معنی تعداد بیت‌هایی است که به بلوک بعدی منتقل می‌شوند.

مقایسه‌ی توابع اس‌اچ‌ای

الگوریتم و نوع‌ آن		اندازه‌ی خروجی (تعداد بیت)	اندازه حالت داخلی (تعداد بیت)	اندازه بلوک (تعدادبیت)	تعداد دورها	عملیات‌ها	امنیت(در بیت) درمقابل حمله تصادم	ظرفیت در مقابل حمله طولانی مدت	عملکرد در Skylake (متوسط cpb)		اولین انتشار
									پیام های طولانی	۸ بایت
MD5 (as reference)		128	128 (4 × 32)	512	64	And, Xor, Rot, Add (mod 232), Or	≤18 (collisions found)	0	4.99	55.00	1992
SHA-0		160	160 (5 × 32)	512	80	And, Xor, Rot, Add (mod 232), Or	<34 (collisions found)	0	≈ SHA-1	≈ SHA-1	1993
SHA-1							<63 (collisions found)		3.47	52.00	1995
SHA-2	SHA-224 SHA-256	224 256	256 (8 × 32)	512	64	And, Xor, Rot, Add (mod 232), Or, Shr	112 128	32 0	7.62 7.63	84.50 85.25	2004 2001
	SHA-384 SHA-512	384 512	512 (8 × 64)	1024	80	And, Xor, Rot, Add (mod 264), Or, Shr	192 256	128 (≤ 384) 0	5.12 5.06	135.75 135.50	2001
	SHA-512/224 SHA-512/256	224 256					112 128	288 256	≈ SHA-384	≈ SHA-384	2012
SHA-3	SHA3-224 SHA3-256 SHA3-384 SHA3-512	224 256 384 512	1600 (5 × 5 × 64)	1152 1088 832 576	24	And, Xor, Rot, Not	112 128 192 256	448 512 768 1024	8.12 8.59 11.06 15.88	154.25 155.50 164.00 164.00	2015
	SHAKE128 SHAKE256	d (arbitrary) d (arbitrary)		1344 1088			min(d/2, 128) min(d/2, 256)	256 512	7.08 8.59	155.25 155.50

پیاده‌سازی‌ها

در زیر لیستی از کتابخانه‌های رمزنگاری که از اس‌اچ‌ای۳ پشتیبانی می‌کنند آمده‌است:

• sha3 Rust's
• Botan
• Bouncy Castle
• ++Crypto
• Libgcrypt
• Nettle
• OpenSSL
• wolfSSL
• MIRACL Cryptographic SDK
• Golang's x/crypto/sha3

استفاده در پروتکل‌ها

• Ethereum § Ether

جستارهای وابسته

• Ethash - یکی دیگر از درهم‌سازی‌های مبتنی‌بر کچاک

پیوند به بیرون

• وب سایت کچاک