آسیب‌پذیری $2^{n/2}$: چرا پارادوکس تولد ثابت می‌کند یک هش ۲۵۶ بیتی فقط ۱۲۸ بیت امنیت دارد؟

یک مهندس نرم‌افزار به یک هش رمزنگاری ۲۵۶ بیتی نگاه می‌کند و دیوار نفوذناپذیری از $2^{256}$ حالت ممکن را می‌بیند؛ عددی که به مراتب از تعداد اتم‌های تخمین‌زده‌شده در جهان قابل مشاهده بزرگ‌تر است. اما یک رمزنگار با نگاه به همان خروجی ۲۵۶ بیتی، تنها ۱۲۸ بیت امنیت واقعی را می‌بیند؛ آستانه‌ای که خوشه‌های پردازشی مدرن به طور پیوسته در حال نزدیک شدن به آن هستند. مهندس تصور می‌کند که برای شکستن سیستم باید یک خروجی خاص را حدس زد، در حالی که رمزنگار می‌داند برای در هم شکستن این سد، تنها کافی است دو ورودی متفاوت پیدا کرد که خروجی یکسانی تولید کنند.[6]

این تضاد دیدگاه، ریشه در یک سوءتفاهم بنیادین درباره رسالت اصلی توابع هش دارد. یک تابع هش، پیامی با طول دلخواه را دریافت کرده و خروجی با اندازه ثابت تولید می‌کند. اگر یک مهاجم بخواهد رمز عبور خاصی را از روی هش آن مهندسی معکوس کند، باید یک «حمله پیش‌تصویر» (preimage attack) را اجرا کند که واقعاً نیازمند جستجو در کل فضای $2^{256}$ است. اما امضاهای دیجیتال و سیستم‌های تأیید اسناد به مقاومت در برابر پیش‌تصویر متکی نیستند؛ تکیه‌گاه آن‌ها «مقاومت در برابر تصادم» (collision resistance) است.[1][4]

مقاومت در برابر تصادم تابع یک پدیده آماری است که نخستین بار در سال ۱۹۳۹ توسط ریچارد فون میزس (Richard von Mises) فرمول‌بندی شد، هرچند به هارولد داونپورت (Harold Davenport) در سال ۱۹۲۷ نیز نسبت داده می‌شود. در نظریه احتمالات، «مسئله تولد» این پرسش را مطرح می‌کند که چند نفر باید به طور تصادفی در یک اتاق حضور داشته باشند تا احتمال اینکه حداقل دو نفر از آن‌ها روز تولد یکسانی داشته باشند به ۵۰ درصد برسد؟ شهود انسانی به ما می‌گوید این عدد باید تقریباً نیمی از روزهای سال، یعنی ۱۸۲ نفر باشد.[5]

اما عدد واقعی ۲۳ است. همان‌طور که در مدخل ریاضیات ویکی‌پدیا نیز اشاره شده: «پارادوکس تولد یک پارادوکس حقیقی است؛ در نگاه اول غلط به نظر می‌رسد، اما در واقعیت کاملاً درست است.» دلیل کارکرد این ریاضیات آن است که مقایسه‌ها نه بین یک نفر و بقیه افراد اتاق، بلکه بین تک‌تک جفت‌های ممکن از افراد انجام می‌شود. با حضور ۲۳ نفر، ۲۵۳ جفت متمایز برای بررسی وجود دارد که همین امر، احتمال را از مرز ۵۰ درصد عبور می‌دهد.[5]

وقتی این واقعیت آماری در رمزنگاری پیاده‌سازی می‌شود، به «حمله تولد» (Birthday Attack) تغییر نام می‌دهد. در اینجا به جای ۳۶۵ روز سال، «لانه‌های کبوتر» همان تعداد کل خروجی‌های ممکن هش هستند و به جای افراد، «کبوترها» همان اسناد هش‌شده‌اند. از آنجا که مهاجم تنها به دنبال یافتن هر دو سندی است که هش یکسانی داشته باشند - نه یک سند خاص با یک هش خاص - تعداد تلاش‌های مورد نیاز با جذر کل احتمالات متناسب است.[3][5]

اینجاست که قانون آسیب‌پذیری $2^{n/2}$ شکل می‌گیرد. برای هر تابع هش که خروجی $n$ بیتی تولید می‌کند، یک مهاجم تنها نیاز به محاسبه حدود $2^{n/2}$ مقدار هش دارد تا شانس یافتن یک تصادم به ۵۰ درصد برسد. بنابراین، یک هش ۲۵۶ بیتی دقیقاً ۱۲۸ بیت امنیت مؤثر در برابر تصادم ارائه می‌دهد. طول فیزیکی خروجی ۲۵۶ بیت است، اما حفاظت ریاضیاتی که فراهم می‌کند دقیقاً به نصف کاهش می‌یابد.[1][6]

تبعات این نصف شدن کاملاً عملی و ملموس است. در یک سیستم امضای دیجیتال، کاربر یک سند را هش کرده و آن هش را با کلید خصوصی خود رمزنگاری می‌کند. اگر مهاجمی بتواند یک سند بی‌خطر و یک سند مخرب پیدا کند که دقیقاً هش یکسانی تولید کنند، می‌تواند از کاربر بخواهد نسخه بی‌خطر را امضا کند. سپس مهاجم امضا را جدا کرده و به سند مخرب می‌چسباند. از آنجا که هش‌ها یکسان هستند، نرم‌افزار رمزنگاری این امضای جعلی را کاملاً معتبر و بی‌نقص تشخیص خواهد داد.[3]

اجرای این حمله نیازی به نوشتن دو سند کاملاً متفاوت که به طرز جادویی هش یکسانی تولید کنند، ندارد. مهاجمان میلیون‌ها نسخه تغییریافته و ظریف از هر دو سند را با ایجاد تغییرات نامرئی - مانند افزودن فاصله، تغییر کاراکترهای چاپ‌نشدنی یا دستکاری فرمت - تولید می‌کنند. آن‌ها تمام نسخه‌های سند الف و تمام نسخه‌های سند ب را هش می‌کنند و به دنبال تنها یک تطابق میان این دو مجموعه می‌گردند.[3]

تاریخچه رمزنگاری، گورستانی از الگوریتم‌هایی است که به این ریاضیات احترام نگذاشتند. الگوریتم MD5 که در سال ۱۹۹۲ معرفی شد، یک هش ۱۲۸ بیتی تولید می‌کرد. مهندسان در آن زمان تصور می‌کردند انجام $2^{128}$ عملیات کاملاً دور از دسترس است. اما پارادوکس تولد، مقاومت آن در برابر تصادم را به $2^{64}$ عملیات کاهش داد. تا سال ۲۰۰۸، پژوهشگران با موفقیت از یک تصادم MD5 برای جعل یک گواهی SSL استفاده کردند و عملاً مدل اعتماد اینترنت را در هم شکستند.[3][6]

پس از آن، صنعت به سمت SHA-1 حرکت کرد که خروجی ۱۶۰ بیتی و مقاومت نظری $2^{80}$ عملیات در برابر تصادم را ارائه می‌داد. اما الگوریتم‌های رمزنگاری اغلب دارای ضعف‌های ساختاری هستند که به مهاجمان اجازه می‌دهد تصادم‌ها را حتی سریع‌تر از پیش‌بینی خالص پارادوکس تولد پیدا کنند. در اول فوریه ۲۰۰۵، بروس اشنایر (Bruce Schneier)، رمزنگار برجسته، هشدار تندی به جامعه امنیتی داد.[2]

اشنایر فاش کرد که تیمی از پژوهشگران راهی برای شکستن SHA-1 در $2^{69}$ عملیات (به جای $2^{80}$ مورد انتظار) پیدا کرده‌اند. اگرچه $2^{69}$ در آن زمان هنوز حجم عظیمی از توان پردازشی را می‌طلبید، اما ثابت کرد که این الگوریتم از اساس دارای نقص است. امنیت مؤثر SHA-1 به زیر کف ریاضیاتی خود سقوط کرده بود.[2]

در واکنش به این آسیب‌پذیری‌ها، مؤسسه ملی استاندارد و فناوری (NIST) در آگوست ۲۰۱۲ سند ویژه 800-107 نسخه ۱ را منتشر کرد. این سند رسماً استفاده از SHA-1 را برای امضاهای دیجیتال منسوخ اعلام کرد و گذار به خانواده SHA-2، با توصیه ویژه به استفاده از SHA-256 و SHA-512 برای برنامه‌های امن، را الزامی دانست.[1]

مهاجرت به SHA-256 با ارتقای آستانه تصادم به $2^{128}$ عملیات، حاشیه امنیت را بازگرداند. برای درک عظمت عدد $2^{128}$، محدودیت‌های فیزیکی محاسبات را در نظر بگیرید. اصل لانداور (Landauer's principle) حداقل انرژی مورد نیاز برای پاک کردن یک بیت اطلاعات را تعیین می‌کند. حتی اگر یک کامپیوتر در مرز مطلق و نظری بازده ترمودینامیکی کار کند، شمارش تا $2^{128}$ باعث به جوش آمدن اقیانوس‌ها می‌شود.[1][6]

به همین دلیل است که امروزه ۱۲۸ بیت امنیت مؤثر به عنوان خط پایه رمزنگاری مدرن در نظر گرفته می‌شود. این میزان، سپری ایجاد می‌کند که در برابر مقیاس‌پذیری حملات جستجوی فراگیر با استفاده از سیلیکون‌های کلاسیک مصون است. با این حال، قانون $2^{n/2}$ حرف آخر را در امنیت هش نمی‌زند. چشم‌انداز ریاضیات در حال آماده شدن برای یک تغییر بنیادین دیگر است.[4][6]

ایستگاه قابل تأیید بعدی برای امنیت رمزنگاری، ظهور محاسبات کوانتومی تحمل‌پذیر در برابر خطا است. درست همان‌طور که پارادوکس تولد طول بیت مؤثر یک هش را در برابر حملات تصادم کلاسیک نصف می‌کند، الگوریتم گراور (Grover's algorithm) به یک کامپیوتر کوانتومی اجازه می‌دهد از فضای جستجوی یک حمله پیش‌تصویر جذر بگیرد. زمانی که آن سخت‌افزار از راه برسد، امنیت مؤثر یک هش ۲۵۶ بیتی بار دیگر نصف خواهد شد و صنعت را مجبور خواهد کرد تا مهاجرت به استانداردهای ۵۱۲ بیتی را آغاز کند.[6]