اس‌اچ‌ای-۱

در رمزنگاری اس‌اچ‌ای-۱ یا شا-۱ (به انگلیسی: SHA-1) تابع درهم‌سازی در مقولهٔ رمزنگاری است که یک ورودی می‌گیرد و یک مقدار درهم ۱۶۰ بیتی (۲۰ بایت) به نام message digest تولید می‌کند - که معمولاً به عنوان یک عدد ۱۰ رقمی در مبنای ۱۶ نمایش داده می‌شود. توسط سازمان امنیت ملی در ایالات متحدهٔ آمریکا طراحی شده و یک استاندارد مؤسسه ملی فناوری و استانداردها محسوب می‌شود. از ابتدای سال ۲۰۰۵ SHA-1 در برابر حمله کننده‌های با امکانات بالا امن محسوب نمی‌شود. از سال ۲۰۱۰ سازمان‌های بسیاری جایگزین برای آن پیشنهاد داده‌اند. سازمان NIST به صورت رسمی استفاده از SHA-1 را در سال ۲۰۱۱ منسوخ اعلام کرد و در سال ۲۰۱۳ استفاده آن در امضای دیجیتال را ممنوع کرد. در سال ۲۰۲۰ حمله‌های علیه SHA-1 به اندازهٔ حمله علیه MD5 کاربردی هستند. در نتیجه پیشنهاد می‌شود که SHA-1 را از تمام محصولات هر چه سریع تر حذف کنیم و به جای آن از SHA-256 یا SHA-3 استفاده کنیم. جایگزین کردن SHA-1 در جاهایی که برای امضای دیجیتال استفاده می‌شود ضروری است. تمام فروشندگان مرورگرهای اینترنتی از سال ۲۰۱۷ پذیرش گواهی ssl که با SHA-1 تولید شده‌است را متوقف کردند. در فروردین سال ۲۰۱۷ CWI و Google اعلام کردند که با اجرای یک حمله ی برخورد علیه SHA-1 دو فایل PDF غیر مشابه ایجاد کرده‌اند که hash یکسانی برای آن‌ها تولید می‌شود.

Development

[ویرایش]
یک چرخه الگوریتم SHA-1
A, B, C, D, E کلمات ۳۲ بیتی وضعیت هستند؛
F یک تابع غیر خطی است که متغیر است؛
نشان دهنده یک چرخش به چپ بیتی n تای است؛
n برای هر عملیات متفاوت است. ;
Wt پیام گسترش داده شده در مرحله t است. ;
Kt is the round constant of round t;
Addition نشان دهنده باقی مانده جمع به 232.

SHA-1 یک message digest بر اساس قوانینی مشابه آن‌هایی که توسط Ronald L. Rivest از MIT در طراحی message digestهای MD2 و MD4 و MD5 از آن‌ها استفاده کرده‌است تولید می‌کند اما یک مقدار درهم بزرگ‌تر (۱۶۰ بیت به جای ۱۲۸ بیت) تولید می‌کند.

SHA-1 به عنوان بخشی از پروژهٔ Capstone project.[۱] دولت آمریکا به وجود آمد. توضیحات اولیهٔ الگوریتم در سال ۱۹۹۳ تحت عنوان Secure Hash Standard در انتشار ۱۸۰ FIPS توسط سازمان استاندارد دولتی آمریکاNIST.[۲][۳] منتشر شد. این نسخه الان معمولاً با نام SHA-0 شناخته می‌شود. این نسخه مدت کوتاهی پس از انتشار توسط NSA پس گرفته شد و توسط نسخه اصلاح شده جایگزین شد (منتشر شده در انتشار ۱۸۰–۱ از FIPS). SHA-1 تنها در یک چرخش بیتی در برنامه پیام compression function خود با SHA-0 متفاوت است. طبق حرف‌های NSA این کار برای تصحیح یک ایراد در الگوریتم اصلی انجام شده بود که امنیت رمزنگاری آن را کاهش می‌داد اما آن‌ها توضیحات بیشتری ندادند.[۴][۵] روش‌های در اختیار عموم در سال ۲۰۰۴ یک ایراد را در SHA-0 قبل از SHA-1 در ۲۰۱۷ نشان دادند.

SHA-1 در واقع ابتدای واژه‌های این عبارت است: «الگوریتم درهم‌سازی ایمن» یا به انگلیسی SHA-1 (Secure Hash Algorithm 1). در حال حاضر سه الگوریتم درهم‌سازی از این گروه با نسخه‌های ۰ و ۱ و ۲ وجود دارد. الگوریتم SHA-1 شباهت بسیار زیادی به اس‌اچ‌ای-۰ دارد ولی در اصل ایرادهایی اساسی که در نسخه ۰ وجود داشته و سبب ضعف این الگوریتم شده بود را برطرف نموده‌است. نسخهٔ ۰ در تعداد کمی از نرم‌افزارهای امنیتی به کار می‌رود و کاربرد گسترده‌ای ندارد. در حالی که نسخه ۲ این الگوریتم بسیار با نسخه‌های ۰ و ۱ متفاوت است.

الگوریتم درهم‌سازی ایمن با نسخهٔ ۱ در حال حاضر پرکاربردترین الگوریتم درهم‌سازی از این خانواده‌است و در بسیاری از نرم‌افزارها و کاربری‌های امنیتی امروزه به خدمت گرفته شده‌است. در سال ۲۰۰۵ خطاهای امنیتی این الگوریتم در موضوع ریاضیات به کار رفته در آن تشخیص داده شد که نشان می‌داد ممکن است این الگوریتم شکسته شود. و از آن زمان بود که نیاز به یک الگوریتم بهتر در این حوزه احساس شد. اس‌اچ‌ای-۲ از بعضی SHA-1 است. در سال ۲۰۱۷، مؤسسهٔ ملی تحقیقات ریاضی و علوم کامپیوتر آمستردام و گوگل، مشترکاً دو فهرست از رشته‌های متفاوت منتشر کردند که خروجی یکسانی داشتند.[۶][۷][۸]

با این تفسیر الگوریتم دیگری هم در حال توسعه‌است با نسخه ۳ که NIST برای انتخاب بهترین الگوریتم با این نام، مسابقه‌ای مثل دوره‌های قبل برگزار کرده که تا پایان سال ۲۰۱۲ پیش‌بینی شده به طول انجامد.

تابع درهم‌سازی SHA-1

[ویرایش]

الگوریتم SHA-1 یک چکیده پیام ۱۶۰ بیتی بر اساس روشی مشابه به الگوریتم‌های MD4 و ام‌دی۵ تولید می‌کند و البته قدری هم محافظه کارانه‌است.

مشخصه‌های اصلی این الگوریتم اولین بار در سال ۱۹۹۳ به عنوان استاندارد درهم‌سازی ایمن توسط NIST انتشار یافت. این نسخه را به نسخه ۰ هم ارجاع می‌دهند چون ساختار به کار رفته در آن همان‌طور که قبلاً گفتیم شبیه نسخه ۰ است. NSA مدتی پس از انتشار نسخهٔ ۰ آن را پس گرفت و با یک نسخه جدید با تجدید نظر کلی جانشین کرد که امروز آن را با نام sha-1 می‌شناسیم. در واقع فرق میان این دو نسخه یعنی ۰ و ۱ در یک گردش بیتی در الگوریتم ساخت پیام است؛ یعنی بخش تابع فشرده‌سازی تغییر یافته‌است. البته NSA هم برای این عملکرد خود دلیل مشخص و واضحی بیان نکرد و معتقد بود با این کار امنیت الگوریتم نسبت به نسخه قبلی ارتقا خواهد یافت.

مقایسه‌ای میان توابع درهم‌سازی

[ویرایش]
اطلاعات بیشتر: ساختار Merkle–Damgård
الگوریتم و
متغیر 		اندازه خروجی (بیت) اندازه وضعیت داخلی (بیت) اندازه بلوک (بیت) اندازه ماکزیمم پیغام (بیت) اندازه کلمه (بیت) دوره عملگرها تداخل‌های یافته‌شده پرفورمانس (MiB/s)[۹]
MD5 (به‌عنوان مرجع) ۱۲۸ ۱۲۸ ۵۱۲ ۲۶۴ − ۱ ۳۲ ۶۴ and,or,xor,rot بله ۲۵۵
SHA-0 ۱۶۰ ۱۶۰ ۵۱۲ ۲۶۴ − ۱ ۳۲ ۸۰ +,and,or,xor,rot بله -
SHA-1 ۱۶۰ ۱۶۰ ۵۱۲ ۲۶۴ − ۱ ۳۲ ۸۰ +,and,or,xor,rot بله ۱۵۳
SHA-2 SHA-256/224 ۲۵۶/۲۲۴ ۲۵۶ ۵۱۲ ۲۶۴ − ۱ ۳۲ ۶۴ +,and,or,xor,shr,rot نه ۱۱۱
SHA-512/384 ۵۱۲/۳۸۴ ۵۱۲ ۱۰۲۴ ۲۱۲۸ − ۱ ۶۴ ۸۰ +,and,or,xor,shr,rot نه ۹۹

سیستم تست شده در جدول بالا سیستمی یک ریسه (thread) با پردازنده intel Core 2 1.83Ghz است تحت ویندوز Vista ایکس۸۶. لازم است ذکر شود نوع ۵۱۲ بیتی بر روی سیستم‌های ۶۴ بیتی بسیار سریعتر از ۲۵۶ بیتی است.

کاربردها

[ویرایش]

SHA-1 امروزه در نرم‌افزارها و پروتکلهای متعددی کاربرد دارد. از میان آن‌ها می‌توان به TLS, SSL, PGP, SSH, S/MIME و آی‌پی‌سک اشاره کرد. در این کاربردها می‌توان از الگوریتم درهم‌سازی MD5 هم استفاده کرد و به همین صورت می‌توان MD4 را هم در این کاربردها جایگزین کرد که البته امنیت کمتری را تضمین خواهند نمود. از sha-1 هم چنین در سیستم‌های کنترل بازنگری استفاده می‌شود از قبیل گیت (Git) و مرکوریال و Monotone. در این موارد از sha-1 برای شناسایی و بازنگری تغییرات و تشخیص تخریب داده‌ای یا تغییر داده‌ای استفاده می‌شود. از این الگوریتم هم چنین در کنسول بازی Nintendo’s Wii در زمانی که سیستم بوت می‌شود جهت تأیید امضای شخص استفاده می‌شود. اما با وجود همهٔ این کاربردها، یک حملهٔ بالقوه و سازمان یافته در مقابل این الگوریتم ممکن است سبب شکسته شدن آن و گذر از سیستم یا سرویس امنیتی شود.

الگوریتم‌های درهم‌سازی SHA-1 و اس‌اچ‌ای-۲ الگوریتمهای ایمنی هستند که بنابر قانون در آمریکا بر روی نرم‌افزارهای مشخصی حتماً باید مورد استفاده قرار گیرند که می‌توانند همراه با الگوریتم‌های رمزنگاری دیگری هم استفاده شوند. در کابردهایی مثل محافظت داده‌های حساس طبقه‌بندی نشده. و البته sha-1 در بیشتر موارد استفادهٔ حکومتی در دولت آمریکا استفاده نمی‌شود و کنار گذاشته شده، به‌طوری‌که NIST گفته «آژانسهای فدرال آمریکا باید استفاده از SHA-1 را کنار بگذارند برای مصارف مختلف و در مصارفی که توانایی تحمل خطا مهم است و باید بالا باشد، از سال ۲۰۱۰ به بعد باید از نسخه ۲ استفاده کنند.»

انگیزهٔ اولیه برای انتشار خانواده sha، امضای دیجیتال بود.

توابع درهم‌سازی sha بنیان و اساس SHACAL block ciphers هستند.

صحت داده

[ویرایش]

Git در ساختار خود از SHA-1 نه برای امنیت، بلکه جهت صحت و اطمینان از عدم تغییر داده‌ها استفاده می‌کند. و البته Git با این الگوریتم بسیار هم موفق است به‌طوری‌که اگر به عنوان مثال شما داده‌ای را در آن ذخیره کنید و حتی ۵ سال از آن زمان بگذرد و شما بخواهید داده‌های خود را ملاحظه کنید خواهید دید که داده‌ها به‌طور تضمین شده‌ای دچار هیچ گونه تغییری نشده‌اند.

آنالیز و ارزیابی رمزنگاری

[ویرایش]

وقتی یک چکیده پیام با طول L داریم در اغلب موارد می‌توانیم رمز شدهٔ این پیام را با همین طول با پیچیدگی ۲ به توان L، مورد حملهٔ Brute Force قرار داد و آن را افشا نمود. به آن حمله Preimage Attack هم گفته می‌شود. که حتی می‌تواند غیر وابسته به طول پیام یا شرایط محاسباتی حمله باشد. مسئله دومی که در اینجا مطرح می‌شود پیدا کردن دو الگوریتم رمزنگاری متفاوت است که هر دو یک چکیده پیام را تولید کنند. در چنین مواقعی می‌گوییم یک برخورد به وجود آمده و زمان لازم برای کشف آن از مرتبهٔ ۲ به توان L/2 است. حملهٔ اخیر را با نام حملهٔ روز تولد یاد می‌کنند. با دلایل ذکر شده و یک سری دلایل محاسباتی طول کلید تابع در هم‌سازی را با نصف طول چکیده پیام رمز شده در رمزنگاری متقارن مقایسه می‌کنند تا نتایج بهتری بدست آورند. با این شرایط SHA-1 طولی بالغ بر ۸۰ خواهد داشت تا امنیت لازم را برای عملیات رمزنگاری تضمین کند.

البته دانشمندان رمزنگاری، برخوردهای دوتایی برای الگوریتم sha-0 و نیز sha-1 پیدا کردند. با وجود این برخورد در الگوریتم sha-1 تعداد کل حالات به جای آنکه از مرتبهٔ ۲ به توان ۸۰ باشد کادرهم‌سازی یافته و از مرتبهٔ همان عدد به توان ۴۰ خواهد شد که زمان بسیار کمتری را برای افشا نیازمند است. بعضی کاربردهایی که از درهم سازی رمزنگاری استفاده می‌کنند (مثل ذخیره‌سازی رمزعبور) خیلی کم توسط حملهٔ برخورد تحت تأثیر قرار می‌گیرند. ساختن کلمه‌عبوری که برای یک حساب‌کاربری کار می‌کند علاوه بر preimage attack نیازمند دسترسی به hash کلمه‌عبور اولیه می‌باشد که ممکن است بدیهی نباشد. برعکس کردن رمزنگاری کلمه‌عبور (به عنوان مثال برای بدست آوردن کلمه‌عبوری که بتوان برای یک حساب کاربری دیگر کاربر استفاده کرد) توسط این حمله‌ها ممکن نیست. (با این حال یک الگوریتم hash امن نمی‌تواند از یک حمله brute-force به یک کلمه‌عبور ضعیف جلوگیری کند) در مورد امضای دیجیتال اسناد حمله‌کننده نمی‌تواند به سادگی یک امضا از یک سند موجود را جعل کند. برای این کار باید دو سند را تولید کند. یکی بدون آسیب و دیگری آسیب زننده و کاری کند تا نگه‌دارنده کلید خصوصی نسخه بدون آسیب را امضا کند. البته شرایطی وجود دارد که این کار ممکن باشد. تا پایان سال ۲۰۰۸ ایجاد گواهی‌نامه‌های جعلی SSL با استفاده از حمله برخورد MD5 ممکن بود.[۱۰]

به خاطر ساختار بلوکی و تکرارشونده الگوریتم‌ها و غیبت مراحل پایانی اضافی تمام توابع خانواده SHA (به جز SHA-3[۱۱]) نسبت به حملات length-extension و partial-message collision attacks آسیب‌پذیر هستند.[۱۲] این حملات به حمله‌کننده اجازه می‌دهند تا یک پیام که فقط توسط یک keyed hash – SHA(message || key) or SHA(key || message) – امضا شده‌است با استفاده از گسترش پیام و محاسبه دوباره hash بدون دانستن کلید جعل کنند. یک بهبود ساده برای جلوگیری از این حمله دو بار درهم‌سازی است SHAd(message) = SHA(SHA(0b || message)) (طول 0b و zero block برابر اندازه بلوک الگوریتم درهم‌سازی می‌باشد)

در اصطلاح امنیت کاربردی، نگرانی ویژه در مورد این گونه حملات تازه بنیاد اینست که روزی ممکن است راه افشا را از این هم که هست راحتتر کنند. و البته استفاده از الگوریتمهای رمزنگاری قدرتمندتر قدری اطمینان بخش است. نرم‌افزارهایی که رمز عبور را با استفاده از درهم‌سازی ذخیره می‌کنند کمتر در معرض خطر collision هستند. برای این موارد می‌توان از حملات Preimage Attack استفاده کرد. بدین صورت که پس از دستیابی به رمز عبور، آن را با الگوریتمی که تبدیل کردند، به صورت معکوس، رمز واقعی و Plain Text بدست می‌آورند. در چنین مواقعی هم وجود یک الگوریتم درهم‌سازی قدرتمند احساس می‌شود.

به دلیل ویژگی‌های ساختاری الگوریتم‌های درهم‌سازی sha، کلیهٔ آن‌ها نسبت به حملات تداخلی آسیب‌پذیر هستند. این دسته از حملات به حمله‌کننده اجازه پیشرفت و نفوذ بیشتر را می‌دهند.

Attacks

[ویرایش]

در اوایل سال ۲۰۰۵ Rijmen و Oswald مطلبی در مورد یک حمله روی یک نسخه کاهش یافته از SHA-1 که ۵۳ دور از ۸۰ دور را داشت منتشر کردند که برخوردها را با هزینه محاسباتی کمتر از 280 عملیات پیدا می‌کند.[۱۳] در ماه اول سال ۲۰۰۵ حمله‌ای توسط Xiaoyun Wang وYiqun Lisa Yin و Hongbo Yu منتشر شد[۱۴] که می‌توانست برخوردها را در نسخه کامل SHA-1 با هزینهٔ محاسباتی کمتر از 269 عملیات پیدا کند. (یک جستجوی brute-force search به 280 عملیات نیاز دارد) طبق نویسندگان مطلب بالا: <<به صورت خاص تحلیل ما بر اساس حملات differential اصلی بر روی SHA-0 و تکنیک‌های برخورد چند بلوکی علاوه بر تکنیک‌های تغییر پیام استفاده شده در حمله collision search بر روی MD5 می‌باشد. شکستن SHA-1 بدون استفاده از این حملات تحلیلی قوی ممکن نمی‌بود>>"[۱۵] مقاله حاوی توضیحات کامل د مورد حمله در سال ۲۰۰۵ در کنفرانس CRYPTO منتشر شد. در یک مصاحبه Yin می‌گوید که «به‌طور کلی ما از این دو ضعف استفاده می‌کنیم: یکی این که مرحله پیش پردازش فایل به اندازه کافی پیچیده نیست و دیگری این که بعضی حملات ریاضی در ۲۰ دور اول ویژگی‌های پیش‌بینی نشده امنیتی دارند.»[۱۶] در ۱۷ اوت ۲۰۰۵ یک بهبود روی حمله به SHA-1 از طرف Xiaoyun Wang, Andrew Yao و Frances Yao در جلسه CRYPTO 2005 Rump اعلام شد که پیچیدگی مورد نیاز برای یافتن برخورد در SHA-1 را به 263 کاهش می‌داد.[۱۷] در ۱۸ دسامبر ۲۰۰۷ جزئیات این نتیجه توسط Martin Cochran تأیید و توضیح داده شدند.[۱۸]

Christophe De Cannière و Christian Rechberger در مقاله "Finding SHA-1 Characteristics: General Results and Applications,"[۱۹] حمله به SHA-1 را بهبود دادند و جایزه بهترین مقاله را از ASIACRYPT در سال ۲۰۰۶ دریافت کردند. یک برخورد دو بلوکی که توسط توابع غیر بهینه با 235 عملیات مقایسه پیدا شده بود برای SHA-1 نشان داده شد. به خاطر این که این حمله تنها حدوداً 235 ارزیابی نیاز دارد یک پیشرفت تءوری بزرگ در نظر گرفته می‌شود.[۲۰] حملهٔ آن‌ها در سال ۲۰۱۰ به ۷۳ از ۸۰ دور توسط Grechnikov ارتقا یافت.[۲۱] با این حال برای این که یک برخورد در ۸۰ دور کامل الگوریتم درهم‌سازی پیدا شود مقدار بسیار زیادی زمان مورد نیاز است. در همین راستا یک جست‌وجوی برخورد در SHA-1 با استفاده از یک گروه کامپیوتر توزیع شده (BOINC) در ۸ اوت سال ۲۰۰۷ توسط Graz University of Technology شروع شد. این تلاش در ۱۲ ماه مه سال ۲۰۰۹ به علت عدم پیشرفت متوقف شد.[۲۲]

در جلسه Rump همایش CRYPTO سال ۲۰۰۶ Christian Rechberger و Christophe De Cannière ادعا کردند که یک حملهٔ برخورد روی SHA-1 پیدا کرده‌اند که به فرد متهاجم اجازه می‌دهد حداقل قسمت‌هایی از پیام را انتخاب کند.[۲۳][۲۴]

در سال ۲۰۰۸ یک روش حمله توسط Stéphane Manuel با پیچیدگی تءوری 251 تا 257 عملیات برخوردها را گزارش می‌داد.[۲۵] با این حال او بعداً پس از همیدا این که مسیرهای برخورد محلی از هم مستقل نبودند از این موضع عقب‌نیشنی کرد.[۲۶] Cameron McDonald و Philip Hawkes و Josef Pieprzyk در جلسه RUMP همایش Eurocryptدر سال ۲۰۰۹ یک حمله برخورد hash با ادعای پیچیدگی زمانی 252 را ارایه کردند.[۲۷] با این حال مقاله همراه با این ادعا ("Differential Path for SHA-1 with complexity O(252)") به این علت که نویسندگان آن متوجه شدند که تخمینشان اشتباه بوده‌است حذف شده‌است.[۲۸] یک حمله علیه SHA-1 توسط Marc Stevens[۲۹] با هزینهٔ تقریبی $2.77M(2012) با هدف شکستن تنها یک مقدار hash شده با استفاده از اجاره پردازش CPU از سرورهای ابری اتفاق افتاد.[۳۰] وی این حمله را در پروژه‌ای به اسم HashClash با پیاده‌سازی یک حمله differential path attack ایجاد کرد.[۳۱] در ۸ نوامبر سال ۲۰۱۰ او ادعا کرد که یک حمله near-collision کاملاً عملی علیه SHA-1 کامل که با پیچیدگی حدوداً 257.5 مقایسه کار می‌کند در اختیار دارد. او تخمین زد که این حمله می‌تواند به یک حمله full collision با 261 مقایسه ارتقا داده شود.

The SHAppening

[ویرایش]

در ۸ اکتبر ۲۰۱۵ Marc Stevens و Pierre Karpman و Thomas Peyrin یک حمله freestart collision روی SHA-1 منتشر کردند که فقط 257 ارزیابی SHA-1 نیاز داشت. این مستقیم به یک حمله برخورد کامل روی SHA-1 ترجمه نمی‌شود. (که در آن مهاجم نمی‌تواند وضعیت اولیه درونی را انتخاب کند) ولی ادعاهای امنیتی SHA-1 را تضعیف می‌کند. به‌طور خاص این اولین بار بود که یک حمله روی SHA-1 کامل نمایش داده می‌شد. تمام حملات قبلی برای این که طراحان آن‌ها آن‌ها را نمایش بدهند زیادی هزینه‌بر بودند. نویسندگان این مقاله آن را یک پیشرفت قابل توجه در آنالیز SHA-1 می‌دانستند و نام آن را The SHAppening گذاشتند.[۳۲] روش کار آن‌ها بر پایه کار قبلی خودشان و همچنین تکنیک‌های سرعت بخشی با استفاده از مسیرهای کمکی (یا همان بومرنگ) که توسط Joux و Peyrin ابداع شده بودند و استفاده از کارت گرافیک‌های با کارایی بالا و هزینه پایین شرکت NVIDIA بود. برخورد در یک خوشه ۱۶ گره‌ای با ۶۴ کارت گرافیک پیدا شده بود. نویسندگان ادعا کردند که یک برخورد مشابه می‌تواند توسط خرید US$۲٬۰۰۰ زمان GPU از EC2 پیدا شود.[۳۲] نویسندگان تخمین زدند که هزینه اجاره زمان کافی EC2 CPU/GPU برای ایجاد یک برخورد کامل SHA-1 در زمان انتشار مقاله بین US$75K و 120K می‌بود و اشاره کردند که این مبلغ به سادگی در بودجه سازمان‌های محرم چه برسد به سازمان‌های ملی مثل intelligence agencies می‌گنجد. در نتیجه نویسندگان پیشنهاد کردند که SHA-1 هر چه سریع‌تر منسوخ شود.[۳۲]

SHAttered – first public collision

[ویرایش]

در ۲۳ فوریه ۲۰۱۷ CWI (Centrum Wiskunde & Informatica) و Google حمله SHAttered را اعلام کردند که در آن آن‌ها دو فایل pdf با hash یکسان را با تقریباً 263.1 ارزیابی SHA-1 تولید کردند. این حمله تقریباً ۱۰۰۰۰۰ بار سریع‌تر از brute-force کردن یک برخورد SHA-1 با استفاده از یک birthday attack می‌باشد که تخمین زده می‌شد که 280 ارزیابی SHA-1 نیاز داشته باشد. این حمله معادل ۶۵۰۰ سال محاسبه CPU و ۱۱۰ سال محاسبه GPU بود.[۳۳]

Birthday-Near-Collision Attack – first practical chosen-prefix attack

[ویرایش]

در ۲۴ آوریل ۲۰۱۹ یک مقاله توسط Gaëtan Leurent و Thomas Peyrin در Eurocrypt 2019 ارایه شد که یک پیشرفت برای بهترین حمله تا آن زمان (chosen-prefix attack در توابع شبه Merkle–Damgård بر اساس رمزهای بلوکی Davies–Meyer) اریه می‌کرد. با این پیشرفت این تابع توانایی پیدا کردن برخوردهای chosen-prefix را در تقریباً 268 ارزیابی SHA-1 دارد. این تقریباً یک بیلیون برابر سریع تر (و قابل استفاده برای بسیاری از حملات هدفمند به خاطر امکان انتخاب prefix) از حملات قبلی است که 277.1 ارزیابی نیاز داشتند.[۳۴] و به اندازهٔ کافی برای متهاجم‌های با منابع کافی سریع می‌باشد (حدود $۱۰۰٬۰۰۰ پردازش ابری نیاز دارد). این روش هم‌چنان می‌تواند برخوردهای chosen-prefix را دز تابع MD5 با پیچیدگی زمانی 246.3 پیدا کند که از بهترین روش تا آن زمان برای این کار که در تءوری 239 (البته در عمل ممکن بود به ≤249 ارزیابی برسد) ارزیابی نیاز داشت بهتر نیست.[۳۵][۳۶] این حمله نیازمند 500+ GB حافظه می‌باشد. در ۵ ژانویه ۲۰۲۰ نویسندگان یک حمله بهبود یافته را منتشر کردند.[۳۷] در این مقاله یک حمله chosen-prefix با پیچیدگی 263.4 را نمایش دادند که در زمان انتشار 45k USD به ازای هر برخورد هزینه داشت.

SHA-0

[ویرایش]

در سال ۱۹۹۸ توسط دو فرانسوی این الگوریتم مورد حمله تداخلی قرار گرفت که با پیچیدگی ۲ به توان ۶۱ که خیلی کمتر از حمله نرمال آن بود (یعنی ۲ به توان ۸۱) به موفقیت رسید. به‌طور مشابه در سال ۲۰۰۴ با پیدا کردن collision این میزان به ۲ به توان ۶۲ کادرهم‌سازی یافت و موفق شدند آن را بشکنند. در اوت همان سال توسط تیمی دیگر این میزان به ۲ به توان ۵۱ کادرهم‌سازی یافت که با امکاناتی که در آن روز در اختیار داشتند فرایند حمله را ظرف مدت ۱۳ روز به اتمام رسانیدند. بعد از آن حملاتی با پیچیدگی ۲ به توان ۴۰ و ۳۹ هم اتفاق افتاد که به زمان کمتری جهت شکستن الگوریتم نیاز داشتند.

منابع

[ویرایش]
  1. ↑ RSA FAQ on Capstone
  2. ↑ Selvarani, R.; Aswatha, Kumar; T V Suresh, Kumar (2012). Proceedings of International Conference on Advances in Computing. Springer Science & Business Media. p. 551. ISBN 978-81-322-0740-5.
  3. ↑ Secure Hash Standard, Federal Information Processing Standards Publication FIPS PUB 180, National Institute of Standards and Technology, 11 May 1993
  4. ↑ Kramer, Samuel (11 July 1994). "Proposed Revision of Federal Information Processing Standard (FIPS) 180, Secure Hash Standard". Federal Register.
  5. ↑ fgrieu. "Where can I find a description of the SHA-0 hash algorithm?". Cryptography Stack Exchange.
  6. ↑ "CWI, Google announce first collision for Industry Security Standard SHA-1". Retrieved 2017-02-23.
  7. ↑ "Announcing the first SHA1 collision". Google Online Security Blog. 2017-02-23.
  8. ↑ "SHAttered". Retrieved 2017-02-23.
  9. ↑ "Crypto++ 5.6.0 Benchmarks". Archived from the original on 15 اكتبر 2008. Retrieved 2011-02-27. {{cite web}}: Check date values in: |archive-date= (help)
  10. ↑ Sotirov, Alexander; Stevens, Marc; Appelbaum, Jacob; Lenstra, Arjen; Molnar, David; Osvik, Dag Arne; de Weger, Benne (دسامبر ۳۰, ۲۰۰۸). "MD5 considered harmful today: Creating a rogue CA certificate". Retrieved March 29, 2009.
  11. ↑ "Strengths of Keccak – Design and security". The Keccak sponge function family. Keccak team. Retrieved 20 September 2015. Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.
  12. ↑ Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno, Cryptography Engineering, John Wiley & Sons, 2010. شابک ‎۹۷۸−۰−۴۷۰−۴۷۴۲۴−۲
  13. ↑ "Cryptology ePrint Archive: Report 2005/010".
  14. ↑ خطای یادکرد: خطای یادکرد:برچسب <ref>‎ غیرمجاز؛ متنی برای یادکردهای با نام autogenerated1 وارد نشده است. (صفحهٔ راهنما را مطالعه کنید.).
  15. ↑ Collision Search Attacks on SHA1 بایگانی‌شده در ۲۰۰۵-۰۲-۱۹ توسط Wayback Machine, Massachusetts Institute of Technology
  16. ↑ Lemos, Robert. "Fixing a hole in security". ZDNet.
  17. ↑ "New Cryptanalytic Results Against SHA-1 – Schneier on Security".
  18. ↑ Notes on the Wang et al. 263 SHA-1 Differential Path
  19. ↑ De Cannière, Christophe; Rechberger, Christian (2006-11-15). "Finding SHA-1 Characteristics: General Results and Applications". Advances in Cryptology – ASIACRYPT 2006. Lecture Notes in Computer Science. Vol. 4284. pp. 1–20. doi:10.1007/11935230_1. ISBN 978-3-540-49475-1.
  20. ↑ "IAIK Krypto Group — Description of SHA-1 Collision Search Project". Archived from the original on 2013-01-15. Retrieved 2009-06-30.
  21. ↑ "Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics". Retrieved 2010-07-24.
  22. ↑ "SHA-1 Collision Search Graz". Archived from the original on 2009-02-25. Retrieved 2009-06-30.
  23. ↑ "heise online – IT-News, Nachrichten und Hintergründe". heise online.
  24. ↑ "Crypto 2006 Rump Schedule".
  25. ↑ Manuel, Stéphane. "Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1" (PDF). Retrieved 2011-05-19. {{cite journal}}: Cite journal requires |journal= (help)
  26. ↑ Manuel, Stéphane (2011). "Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1". Designs, Codes and Cryptography. 59 (1–3): 247–263. doi:10.1007/s10623-010-9458-9. the most efficient disturbance vector is Codeword2 first reported by Jutla and Patthak
  27. ↑ SHA-1 collisions now 2^52
  28. ↑ "Cryptology ePrint Archive: Report 2009/259".
  29. ↑ Cryptanalysis of MD5 & SHA-1
  30. ↑ "When Will We See Collisions for SHA-1? – Schneier on Security".
  31. ↑ "Google Project Hosting".
  32. ↑ ۳۲٫۰ ۳۲٫۱ ۳۲٫۲ Stevens1, Marc; Karpman, Pierre; Peyrin, Thomas. "The SHAppening: freestart collisions for SHA-1". Retrieved 2015-10-09.
  33. ↑ خطای یادکرد: خطای یادکرد:برچسب <ref>‎ غیرمجاز؛ متنی برای یادکردهای با نام sha1-shattered وارد نشده است. (صفحهٔ راهنما را مطالعه کنید.).
  34. ↑ Marc Stevens (2012-06-19). "Attacks on Hash Functions and Applications" (PDF). PHD Thesis.
  35. ↑ Leurent, Gaëtan; Peyrin, Thomas (2019). "From Collisions to Chosen-Prefix Collisions Application to Full SHA-1" (PDF). Advances in Cryptology – EUROCRYPT 2019. Lecture Notes in Computer Science. Vol. 11478. pp. 527–555. doi:10.1007/978-3-030-17659-4_18. ISBN 978-3-030-17658-7.
  36. ↑ Gaëtan Leurent; Thomas Peyrin (2019-04-24). "From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1" (PDF). Eurocrypt 2019.
  37. ↑ Gaëtan Leurent; Thomas Peyrin (2020-01-05). "SHA-1 is a Shambles First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust" (PDF). Cryptology ePrint Archive, Report 2020/014.

استانداردها: SHA-1, SHA-2