کلود در کمتر از ۳۰ دقیقه معمای ۲۵ساله رمزنگاری را حل کرد؛ رد بذرهای منحنی‌های NIST به زمان‌سنج‌های یونیکس و مولد اعداد شبه‌تصادفی رسید
شرکت هوش مصنوعی آنتروپیک در ۱۶ اکتبر از دستاورد پژوهشی قابل‌توجهی خبر داد: مدل پژوهشی داخلی این شرکت، کلود، توانست در کمتر از نیم ساعت منشأ تولید بذرهای پنج منحنی بیضوی استاندارد مؤسسه ملی استاندارد و فناوری آمریکا (NIST) را ردیابی کند و به معمایی پایان دهد که ۲۵ سال ذهن جامعه رمزنگاری را به خود مشغول کرده بود. نتایج نشان می‌دهد این بذرها با یک الگوریتم هش پیچیده و ازپیش‌طراحی‌شده تولید نشده‌اند، بلکه حاصل کار lrand48 بوده‌اند؛ مولد اعداد شبه‌تصادفی قدیمی موجود در کتابخانه زبان برنامه‌نویسی C که مدت‌هاست از نظر امنیتی ناکافی شناخته می‌شود. حالت اولیه این مولد نیز با استفاده از مُهرهای زمانی یونیکس تعیین شده بود.
این کشف به معنای شکستن الگوریتم امضای دیجیتال منحنی بیضوی ECDSA نیست و مسیر حمله جدیدی نیز ایجاد نمی‌کند. برعکس، آنتروپیک معتقد است این یافته احتمال تعبیه عمدی درِ پشتی در منحنی‌ها را کمتر می‌کند؛ زیرا اکنون می‌توان کل فرایند تولید آن‌ها را به‌صورت عمومی بازتولید کرد و در نتیجه، فضای کمتری برای دست‌کاری پنهانی نسبت به آنچه پیش‌تر تصور می‌شد باقی می‌ماند.
ریشه‌های یک معمای ۲۵ساله
رمزنگاری منحنی بیضوی یکی از ارکان اصلی رمزنگاری کلید عمومی در دنیای امروز است. مؤسسه ملی استاندارد و فناوری آمریکا در سال ۲۰۰۰، در استاندارد FIPS 186-2، چندین منحنی استاندارد با سطوح امنیتی متفاوت معرفی کرد که از جمله آن‌ها می‌توان به P-192، P-224، P-256، P-384 و P-521 اشاره کرد. این منحنی‌ها به‌طور گسترده در امضاهای دیجیتال، تبادل کلید و کاربردهای دیگر استفاده می‌شوند و بخش مهمی از زیرساخت امنیت اینترنت را تشکیل می‌دهند.
هر منحنی استاندارد مجموعه‌ای از پارامترها دارد که «بذر» نامیده می‌شوند. طبق روش تولید تعریف‌شده در استاندارد، هش بذر در تعیین ضرایب منحنی نقش دارد. مشکل این بود که این بذرها را آژانس امنیت ملی آمریکا (NSA) ارائه کرده بود، اما اسناد عمومی نه منشأ آن‌ها را توضیح می‌دادند و نه مشخص می‌کردند که چگونه انتخاب شده‌اند. همین ابهام نگرانی‌هایی دیرپا ایجاد کرده بود: شاید طراحان تعداد زیادی منحنی احتمالی را بررسی کرده و پارامترهایی را برگزیده بودند که ویژگی‌های پنهانی داشتند و می‌توانستند در آینده راه را برای حمله باز کنند.
جری سولیناس، رمزنگار آژانس امنیت ملی که در این پروژه مشارکت داشت، در سال ۲۰۱۵ به یاد آورده بود که بذرها شاید از یک گذرواژه شوخی‌آمیز، مانند «به باب و جری افزایش حقوق بدهید»، گرفته شده باشند. بااین‌حال، او دیگر جزئیات را به خاطر نداشت و اسناد بایگانی مرتبط نیز هرگز پیدا نشدند. سولیناس در سال ۲۰۲۳ درگذشت و این سرنخ هیچ‌گاه تأیید نشد.
روش پژوهشی کلود
پیش‌تر، چند نفر از کارکنان آنتروپیک در جست‌وجوی منشأ بذرها، احتمال استفاده از «گذرواژه‌های طنزآمیز» را بررسی کرده بودند، اما به نتیجه نرسیدند. بعدها مشخص شد که این سرنخ اساساً نادرست بوده است.
در اکتبر سال جاری، یکی از کارکنان از مدل پژوهشی داخلی کلود خواست راهی برای کشف چگونگی تولید این بذرها پیدا کند. این بار، او نه سرنخ مربوط به گذرواژه را در اختیار مدل گذاشت و نه راهنمایی کلیدی دیگری ارائه داد.
کلود از زاویه دیگری به مسئله پرداخت و درباره نرم‌افزاری فرضیه‌سازی کرد که ممکن بود در آن زمان برای تولید منحنی‌ها به کار رفته باشد. این مدل حدس زد که نرم‌افزار از مولدهای اعداد شبه‌تصادفی تعبیه‌شده در کتابخانه‌های زبان C در دهه ۱۹۹۰ استفاده کرده است؛ مولدهای اولیه‌ای که امنیت ضعیفی داشتند و خروجی آن‌ها معمولاً الگوهای قابل‌شناسایی ایجاد می‌کرد. با شناسایی این الگوها می‌توان مولد مورد استفاده نرم‌افزار را تشخیص داد و سپس حالت اولیه آن را بازیابی کرد.
مدل برنامه‌ای برای اسکن داده‌ها نوشت که به‌صورت بیت‌به‌بیت روی هر بذر عمومی حرکت می‌کرد و بررسی می‌کرد آیا بلوک‌های داده مجاور می‌توانند خروجی یک مولد اعداد تصادفی متعلق به دهه ۱۹۹۰ باشند یا خیر. این بررسی ۳۴ ترکیب مختلف از مولدهای اعداد تصادفی و روش‌های حذف یا کوتاه‌سازی بیت‌های خروجی را پوشش می‌داد.
سپس کلود در بیت‌های پرارزش برخی بذرها الگویی پیدا کرد: تمام بیت‌های موردنظر صفر بودند. اگر هر بذر را به‌صورت پنج واژه ۳۲بیتی نمایش دهیم، چهار مورد از ده بذر با این الگو مطابقت داشتند؛ یعنی در مجموع ۲۰ واژه ۳۲بیتی مربوط به این چهار بذر، بالاترین بیت در تمام موارد صفر بود. احتمال وقوع تصادفی چنین الگویی حدود یک در ۵۸۰۰ است. این ویژگی از نشانه‌های شناخته‌شده مولد هم‌نهشتی خطی lrand48 به شمار می‌رود؛ مولدی که از حالت داخلی ۴۸بیتی خود فقط ۳۱ بیت بالایی را برمی‌گرداند.
برای بازیابی حالت مولد، کلود نخستین واژه ۳۲بیتی را گرفت، تمام ۲ به توان ۱۷ حالت ممکن برای ۱۷ بیت پنهان را به‌طور کامل آزمود و سپس بررسی کرد که آیا چهار واژه بعدی نیز به‌ترتیب با خروجی مولد مطابقت دارند یا خیر. این روش برای هر چهار بذر یادشده جواب داد.
بذرهای منحنی‌های اول‌مرتبه نیز با lrand48 تولید شده بودند، اما تعداد کمتری از بیت‌های خروجی را در خود حفظ کرده بودند. کلود برای بازیابی حالت داخلی مولد از روی این اطلاعات محدود به سراغ یک مسئله کلاسیک شبکه‌ای رفت که با الگوریتم کاهش پایه شبکه LLL قابل‌حل است. از آنجا که مدل در ابتدا نمی‌دانست کدام بیت‌های حالت داخلی در بذرها باقی مانده‌اند، حل‌گر را برای تمام پنجره‌های احتمالی بیت‌ها اجرا کرد.
در نهایت، هر پنج بذر منحنی‌های اول‌مرتبه NIST و هر پنج بذر استاندارد ANSI X9.62 الگوی یکسانی داشتند. هر حالت داخلی ۴۸بیتی بازیابی‌شده می‌توانست تمام ۱۶۰ بیت بذر متناظر را دوباره تولید کند. این تطابق دقیق را نمی‌شد به تصادف نسبت داد.
مُهرهای زمانی، دوره تولید را آشکار می‌کنند
مولدهای هم‌نهشتی خطی را می‌توان هم در جهت جلو و هم در جهت عقب اجرا کرد. کلود از حالت مولد مربوط به هر بذر به عقب رفت تا به حالتی برسد که با قالب مقداردهی اولیه تابع srand48 مطابقت داشته باشد؛ در این قالب، ۱۶ بیت کم‌ارزش باید برابر با مقدار هگزادسیمال 0x330E باشند.
نکته کلیدی این بود که می‌توان مقادیر اولیه srand48 مربوط به هر ده بذر منحنی‌های اول‌مرتبه را به‌عنوان مُهرهای زمانی یونیکس تفسیر کرد. تاریخ‌های حاصل عمدتاً در فاصله مه ۱۹۹۷ تا آوریل ۱۹۹۸ قرار می‌گرفتند. این یافته نشان می‌دهد برنامه اصلی برای مقداردهی اولیه مولد اعداد شبه‌تصادفی از زمان یونیکس استفاده می‌کرده است.
اگر مقادیر اولیه مربوط به چهار منحنی دودویی مستقیماً خوانده شوند، به فوریه ۱۹۸۴ اشاره می‌کنند؛ اما اگر این مقادیر در عدد دو ضرب شوند، تاریخ ۱۷ آوریل ۱۹۹۸ به دست می‌آید که حدود دو هفته با زمان تولید منحنی P-224 فاصله دارد. بنابراین، ممکن است برنامه اصلی ساعت سیستم را بر دو تقسیم کرده باشد.
کلود منشأ نقاط پایه شش منحنی، از جمله P-192، را نیز ردیابی کرد. نتایج نشان داد این نقاط پایه با استفاده از مولد اعداد تصادفی موجود در FreeLIP تولید شده‌اند؛ بسته‌ای نرم‌افزاری برای محاسبات حسابی اعداد صحیح بزرگ. آنتروپیک خاطرنشان کرد که پیش از این، توضیحی برای فرایند تولید نقاط پایه منحنی‌های NIST ارائه نشده بود.
پیامدها و پرسش‌های بی‌پاسخ
مُهرهای زمانی به‌خودی‌خود هیچ امنیت رمزنگاری‌شده‌ای ندارند و lrand48 نیز مدت‌هاست مولدی ضعیف برای تولید اعداد تصادفی محسوب می‌شود. بااین‌حال، این ابزارها در این مورد برای تولید پارامترهای عمومی منحنی به کار رفته بودند، نه برای حفاظت از کلیدهای خصوصی. مهم‌تر از همه اینکه اکنون می‌توان فرایند تولید را به‌صورت عمومی بازتولید کرد. در مقایسه با گذرواژه‌هایی با منشأ نامعلوم یا پارامترهایی که دستی تعیین شده‌اند، توضیح مبتنی بر یک مولد معمولی اعداد شبه‌تصادفی و مُهرهای زمانی، فضای کمتری برای دست‌کاری پنهانی منحنی‌ها باقی می‌گذارد.
آنتروپیک تأکید کرد که این یافته هیچ آسیب‌پذیری امنیتی جدیدی ایجاد نمی‌کند و کاربران نیازی ندارند اقدام متقابلی انجام دهند یا در شیوه استفاده خود تغییری ایجاد کنند.
بااین‌حال، برخی پرسش‌ها همچنان بی‌پاسخ مانده‌اند. در فرایند تولید منحنی P-256، مقدار نامزد شماره ۸۷۶ نیز ظاهراً شرایط لازم را داشت، اما در نهایت مقدار نامزد شماره ۱۸۴۲ انتخاب شد. در اجرای فرایندهای دیگر نیز تعداد اندکی از منحنی‌های قابل‌استفاده کنار گذاشته شده بودند و معیارهای دقیق این غربالگری همچنان مشخص نیست. منشأ بذر منحنی B-163 هنوز ردیابی نشده است و روش تولید نقاط پایه منحنی‌های P-224، P-256، P-384 و P-521 نیز همچنان توضیح داده نشده است.
از نظر آنتروپیک، تعداد اندک گزینه‌هایی که کنار گذاشته شده‌اند، برای پشتیبانی از این فرضیه که منحنی‌های ضعیف عمداً انتخاب شده‌اند، کافی نیست. این کشف اعتماد بیرونی به پارامترهای موردبحث را افزایش می‌دهد، اما هنوز نمی‌توان آن را بازسازی کامل فرایند طراحی دانست.
جایزه ۳۶٬۸۶۴ دلاری که پیش‌تر برای کشف منشأ بذرها تعیین شده بود، به گروه پژوهشی امنیت اینترنت (Internet Security Research Group) اهدا خواهد شد. آنتروپیک همچنین کد پایتون مورد استفاده برای بازتولید بذرها را با مجوز CC0 و در قالب مالکیت عمومی منتشر کرده است.
این پژوهش نمونه دیگری از مشارکت مدل‌های پیشرفته در تحقیقات علمی را نیز نشان می‌دهد. کلود در قالب یک وظیفه واحد، فرضیه‌سازی، نوشتن کد، شناسایی الگوها، به‌کارگیری الگوریتم‌های ریاضی و راستی‌آزمایی نتایج را انجام داد. از آنجا که می‌توان حالت‌های مولد را دوباره محاسبه کرد، بذرهای ۱۶۰بیتی نیز با دقت کامل بازتولید می‌شوند و در نتیجه، امکان بررسی و تأیید نتیجه بسیار بالاست. البته این فرایند همچنان به انسان‌ها نیاز دارد تا پرسش‌ها را مطرح کنند، داده‌های عمومی را فراهم آورند و نتایج را با محاسبات قابل‌بازتولید تأیید کنند. بااین‌حال، هنگامی که محدوده مسئله روشن باشد، داده‌ها عمومی باشند و نتایج را بتوان به‌طور دقیق راستی‌آزمایی کرد، مدل‌های پیشرفته به ابزاری بسیار کارآمد برای پژوهش تبدیل می‌شوند.