کلود منشأ منحنی ECDSA را نشان می دهد

"این فقط مهرهای زمانی است": راز چند دهه ای منشأ یکی از محبوب ترین استانداردهای رمزنگاری توضیح داده شده است.

ما این سوال باز دیرینه جامعه رمزنگاری را دنبال کردیم تا نگرانی‌های مربوط به ECDSA را که یکی از پرکاربردترین استانداردهای رمزنگاری ما است برطرف کنیم.

خوانندگان باید این را به عنوان یک فصل پایانی سرگرم کننده و پایان سال های حدس و گمان در نظر بگیرند. هیچ اقدامی برای انجام یا کاری برای انجام متفاوت وجود ندارد. اکثر محققان قبلا به منحنی ها اعتماد داشتند. لذت ببرید.

ECDSA پرکاربردترین استاندارد رمزنگاری منحنی بیضوی است. در سال 2000 توسط NIST به عنوان بخشی از استاندارد امضای دیجیتال FIPS 186-2 پذیرفته شد که مجموعه ای از منحنی های بیضوی استاندارد را با اندازه ها و سطوح امنیتی مختلف فهرست می کند. برای منحنی‌های فیلدهای اول و باینری، مشخصات یک پارامتر "seed" منتشر کرد که مقدار هش آن برای تعریف ضریب b منحنی استفاده می‌شود. منشا این بذرها یک سوال دیرینه بوده است، زیرا آنها توسط NSA بدون هیچ توضیح یا توجیهی ارائه شده اند.

به عنوان مثال، دانه منحنی NIST P-256 SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 بود، بدون اینکه اطلاعاتی از کجا آمده است.

نیل کوبلیتز و آلفرد منزز خلاصه‌ای عالی درباره این بحث نوشتند، «معمای پیچیده در یک معما» که تاریخچه و نگرانی‌های پیرامون ارزش‌های بذر را مورد بحث قرار می‌دهد. این رمز و راز منجر به تحقیقات آماتوری در مورد منشاء دانه ها و جایزه برای هر کسی که می تواند آنها را پیدا کند.

بهترین داستان این بود که جری سولیناس، کارمند باسابقه NSA، دانه‌ها را با استفاده از یک کلمه عبور طنز آمیز ایجاد کرد:

متأسفانه، جری در سال 2023 درگذشت و سایر همکاران در آن زمان پاسخگو نبودند، و این سؤال را باز گذاشت که چگونه این دانه ها در اصل به دست آمدند.

چندین کارمند آنتروپیک به دنبال نکته ای مبنی بر این که یک عبارت طنز آمیز است، دانه ها را تعقیب ناموفق کردند. معلوم شد که اشتباه است. در اکتبر سال 2026، یک کارمند کنجکاو Anthropic از یک مدل تحقیقاتی داخلی پرسید که آیا می تواند بدون اشاره به سرنخ، بفهمد که این دانه ها چگونه تولید شده اند.

در کمتر از نیم ساعت، کلود منشا دانه های NIST P-192، P-224، P-256، P-384 و P-521 را کشف کرد. هیچ کدام از آنها اصلا نتیجه هیچ الگوریتم هش نبودند، بلکه خروجی مولد اعداد تصادفی lrand48 کتابخانه C بود که با مهر زمانی یونیکس کاشته شده بود!

الگوریتم مورد استفاده، بایت‌ها را از مولد اعداد تصادفی (RNG) نمونه‌برداری می‌کند که توسط یک مهر زمانی یونیکس (t) برای تعدادی تکرار (n) مقداردهی اولیه شده است. هر تکرار 20 بایت را به عنوان دانه کاندید ترسیم می کند. بنابراین، 20 بایت اول کاندید 1، 20 بایت بعدی کاندید 2، و غیره است. برای مثال، P-256 به 1842 تکرار نیاز داشت تا دانه استاندارد شده را تولید کند.

این یک شکست رمزنگاری، حمله جدید یا ضعف در منحنی های ECDSA نیست. در واقع، این باعث می‌شود که مطمئن شویم منحنی‌ها بدون هیچ گونه درپشتی یا ضعف عمدی انتخاب شده‌اند. برای سال‌ها، مردم به منشأ پارامترهای منحنی NIST مشکوک بودند. آنها بدون هیچ اشاره ای به نحوه انتخاب آنها به NIST ارائه شدند، و مردم را متعجب کرد که آیا ممکن است آنها برای داشتن درهای پشتی عمدی در آنها انتخاب شده باشند. این یافته ها آن را بسیار کمتر قابل قبول می کند.

دانه ها به روشی بسیار ساده تولید شدند: یک مولد اعداد شبه تصادفی معمولی که از ساعت مقداردهی اولیه شده است، که اکنون هر کسی می تواند آن را بازتولید کند. که فضای بسیار کمتری را برای براندازی باقی می‌گذارد و می‌توانیم مطمئن باشیم که پارامترها ایمن هستند.

جستجو برای عبارت، ساخته شده از شایعات، خالی بود. کلود زاویه دیگری را امتحان کرد: پیش‌بینی اینکه نرم‌افزاری که منحنی‌ها را ایجاد می‌کرد چگونه کار می‌کرد. کلود حدس زد که نرم افزار از یک مولد اعداد شبه تصادفی (PRNG) استفاده می کند که با کتابخانه های C دهه 1990 عرضه می شد. این PRNG های قدیمی به اندازه کافی ضعیف هستند که خروجی آنها قابل تشخیص باشد. تشخیص آن خروجی نشان می دهد که کدام PRNG استفاده شده است و احتمالا امکان بازیابی حالت اولیه آن را فراهم می کند.

کلود یک اسکنر نوشت که در امتداد هر دانه منتشر شده یک بیت می لغزد و آزمایش کرد که آیا تکه های مجاور خروجی های متوالی یک ژنراتور قدیمی دهه 1990 هستند یا خیر. اسکن 34 ترکیب از ژنراتور و برش های خروجی را پوشش داد. در آن نقطه، کلود متوجه الگویی در قسمت های بالایی برای برخی از دانه ها شد: همه آنها صفر بودند. به صورت پنج کلمه 32 بیتی نوشته شده است، چهار دانه از ده دانه دارای 0 در بیت بالایی برای هر 20 کلمه هستند. این اتفاق با احتمال 1/5810 اتفاق می افتد. این امضایی از مولد همخوانی خطی lrand48 بود که فقط 31 بیت بالای یک حالت 48 بیتی را برمی گرداند.

این الگو به محض اینکه بدانید باید آن را جستجو کنید با چشم قابل مشاهده است. برای بازیابی حالت، کلود اولین کلمه را گرفت، تمام 217 بیت پنهان را امتحان کرد و بررسی کرد که چهار کلمه بعدی دنبال می‌شوند. که برای هر چهار دانه مورد بحث کارساز بود.

دانه های منحنی اول از همان ژنراتور lrand48 به دست آمدند اما بیت های کمتری از هر خروجی را نگه داشتند. کلود باید وضعیت داخلی PRNG را از آن بیت ها بازیابی می کرد. به نظر می رسد که بازیابی وضعیت یک مولد متجانس خطی کوتاه یک مسئله شبکه درسی است که با الگوریتم کاهش پایه Lenstra–Lenstra–Lovász (LLL) حل شده است. کلود نمی‌دانست دانه‌ها کدام بخش از حالت را نشان می‌دهند، بنابراین حل‌کننده را روی هر پنجره می‌چرخاند. پنج دانه اصلی منحنی NIST به اضافه پنج دانه دیگر از استاندارد ANSI X9.62 همگی الگوی یکسانی داشتند: lrand48() >> 23.

هر حالت 48 بیتی بازیابی شده تمام 160 بیت دانه خود را بازسازی می کند، که تصادفی اتفاق نمی افتد.

این مولد همخوانی خطی به آسانی به سمت جلو حرکت می کند، بنابراین برای هر دانه، کلود از حالت عقب نشینی می کند تا زمانی که به شکلی که توسط srand48 مقداردهی اولیه می شد، با 16 بیت کم برابر با 0x330E برسد. حالت PRNG داخلی آن فرم هر 65536 مرحله یک بار ظاهر می شود، بنابراین رسیدن به یک به تنهایی مدرکی نیست.

با این حال، برای ده دانه اصلی منحنی، هر مقدار اولیه srand48 یک مهر زمانی یونیکس بود که نشان‌دهنده تاریخی بین مه 1997 و آوریل 1998 بود. چهار مقدار اولیه منحنی باینری به‌عنوان فوریه 1984 خوانده می‌شوند. با دوبرابر شدن مهرهای زمانی، آنها به 17 آوریل 1998، دو هفته پس از اجرای P-224، نگاشت می‌شوند. بنابراین، برنامه ممکن است ساعت را به نصف کاهش داده باشد.

اما صبر کنید، موارد بیشتری وجود دارد... هر منحنی همچنین دارای یک نقطه پایه، G، نقطه ثابتی است که هر کلید عمومی ECDSA مضربی از آن است. دانه‌ای که در بالا یافت شد این G را تعیین نمی‌کند، و بنابراین سؤال دیگری مطرح می‌شود: این نقاط پایه چگونه ایجاد شدند؟

هنگام بررسی دانه ها، کلود همچنین متوجه شد که برخی از نقاط پایه از کجا آمده اند. نقاط پایه شش منحنی تولید شده در می 1997 (P-192 و پنج منحنی نمونه ANSI X9.62 prime192v2، prime192v3 و prime239v1 تا v3) از مولد اعداد تصادفی در FreeLIP، بسته حسابی اعداد صحیح بلند Arjen Lenstra آمده است. نسخه های اولیه کتابخانه NTL Victor Shoup همان کد را ارسال می کرد.

کلود دریافت که دانه های ژنراتور برای P-192، 20420، 20507 و 20509 برای prime239v1 تا v3، 20000 و برای prime192v2 و 20512 و 20517 هستند.

تا آنجا که می دانیم، هیچ نقطه پایه NIST قبلا توضیح داده نشده است. نقاط پایه P-224، P-256، P-384 و P-521 با این دستور مطابقت ندارند. ما نتوانستیم نحوه انتخاب آنها را توضیح دهیم.

هر دانه کاندید 20 بایتی نمی تواند یک منحنی قابل دوام ایجاد کند و ما مشاهده کردیم که برخی از منحنی های بالقوه قابل دوام نادیده گرفته شدند. برای P-256، دانه منتشر شده کاندید 1842 است، اما کاندید 876 از همان اجرا، منحنی مرتبه اول با اندازه مناسب و با پارامترهای انتخاب شده مشابه منحنی منتشر شده را ارائه می دهد. حرکت P-224 از سه منحنی از این قبیل گذشت و دو منحنی پشت منحنی نمونه ANSI X9.62 از هفت منحنی دیگر گذشت (شکل را ببینید). ما نمی دانیم چه معیارهایی ممکن است مورد استفاده قرار گرفته باشد یا اینکه آیا این یک مصنوع غیرعمدی بوده است.

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

همچنین یک دانه وجود دارد که نتوانستیم آن را بازیابی کنیم. پنجمین دانه دوتایی، B-163، با هیچ چیزی که کلود امتحان کرده است مناسب نیست و توضیح داده نشده است. در نهایت، ما نمی دانیم که نقاط پایه برای P-224، P-256، P-384، و P-521 چگونه ایجاد شده اند. منحنی های باینری NIST هم همینطور.

این اثر در آنتروپیک توسط جان وود، هنری دی والنس، آوا هاول، زک ووس، لوسی سویت، امیر امیدی، پل کراولی، ایین مک گینیس، نیکلاس کارلینی و استیو ویس اجرا شد.

ما می‌خواهیم پس از مرگ جری سولیناس را بشناسیم که با شوخ طبعی به او برچسب "مم اینترنتی شیطانی" و "یو لا تنگوی آدم‌های بدخیم NSA" داده شد. همچنین از فیلیپو والسوردا برای سازماندهی NIST Elliptic Curves Seeds Bounty تشکر می کنیم.

تا حد ممکن طبق قانون، نویسندگان از کلیه حق چاپ و حقوق مرتبط یا همسایه کد موجود در این صفحه چشم پوشی کرده اند و آن را به مالکیت عمومی تحت CC0 1.0 Universal اختصاص داده اند (https://creativecommons.org/publicdomain/zero/1.0/).