‏Claude راز ۲۵ ساله seedهای منحنی‌های ECDSA رو حل کرد

ECDSA پرکاربردترین استاندارد امضای دیجیتال با رمزنگاری منحنی بیضویه که NIST سال ۲۰۰۰ تو FIPS 186-2 تصویبش کرد. برای هر منحنی یه seed منتشر شده (یعنی عددی که هشش ضریب b منحنی رو مشخص می‌کنه)، ولی NSA هیچ‌وقت نگفت این عددها از کجا اومدن. همین باعث شد سال‌ها نگرانی وجود داشته باشه که شاید عمداً یه در پشتی تو منحنی‌ها گذاشته شده. شایعهٔ معروف این بود که seedها هش یه جملهٔ شوخی مثل «Give Bob and Jerry a raise» هستن.

تیم Anthropic می‌گه اکتبر ۲۰۲۶ یکی از کارمندها، بدون اینکه سرنخ شایعه رو بده، از یه مدل تحقیقاتی داخلی پرسید این seedها چطور ساخته شدن. Claude تو کمتر از نیم ساعت منشأ seedهای P-192، P-224، P-256، P-384 و P-521 رو پیدا کرد. هیچ‌کدوم هش نبودن. همه خروجی تابع lrand48 کتابخونهٔ C بودن که با یه Unix timestamp مقداردهی شده. مثلاً seed منحنی P-256 کاندیدای شمارهٔ ۱۸۴۲ از همون اجرا بوده.

روش پیدا کردنش جالبه. Claude حدس زد نرم‌افزار اون زمان از یه PRNG (یعنی تولیدکنندهٔ عدد شبه‌تصادفی) قدیمی دهه ۹۰ استفاده کرده که خروجیش قابل تشخیصه. یه اسکنر نوشت و دید تو بعضی seedها بیت بالای همهٔ کلمه‌های ۳۲ بیتی صفره، که امضای lrand48 هست چون فقط ۳۱ بیت بالای یه حالت ۴۸ بیتی رو برمی‌گردونه. برای seedهای منحنی‌های اول که بیت‌های کمتری نگه داشته بودن، بازیابی حالت با الگوریتم LLL (یه روش استاندارد برای حل مسائل lattice) انجام شد. بعد حالت رو عقب برد تا به نقطه‌ای رسید که srand48 مقداردهیش کرده بود.

این کد کوتاه از خود مقاله نشون می‌ده هر کاندیدا چطور از timestamp ساخته می‌شه:

def candidate(t, n, per, shift, width):
    x, out = (t << 16) | 0x330E, ""
    for i in range(per * n):
        x = (0x5DEECE66D * x + 0xB) % 2**48
        if i >= per * (n - 1):
            out += "%0*X" % (width, x >> shift)
    return out

همهٔ timestampهای منحنی‌های اول بین می ۱۹۹۷ تا آوریل ۱۹۹۸ بودن. برای منحنی‌های باینری هم به نظر می‌رسه برنامه زمان رو نصف کرده بود. Claude منشأ base point (یعنی نقطهٔ ثابتی که همهٔ کلیدهای عمومی مضربی ازش هستن) شش منحنی، از جمله P-192، رو هم پیدا کرد که از تولیدکنندهٔ عدد تصادفی کتابخونهٔ FreeLIP اومده بودن. به گفتهٔ تیم، تا حالا هیچ base point از NIST توضیح داده نشده بود.

نویسنده‌ها تأکید می‌کنن این یه حمله یا ضعف نیست و هیچ کاری لازم نیست بکنید. برعکس، چون هر کسی می‌تونه این seedها رو دوباره بسازه، جای کمی برای خرابکاری می‌مونه. چند سؤال هنوز بازه: چرا بعضی کاندیداهای قابل استفاده رد شدن (مثلاً کاندیدای ۸۷۶ برای P-256)، seed منحنی B-163 هنوز توضیحی نداره، و base pointهای P-224 تا P-521 معلوم نیست چطور انتخاب شدن. جایزهٔ ۳۶٬۸۶۴ دلاری این معما هم به Internet Security Research Group اهدا می‌شه.

نکات کلیدی:

• seedهای P-192، P-224، P-256، P-384 و P-521 خروجی lrand48 با مقداردهی Unix timestamp بودن، نه هش
• همهٔ timestampهای منحنی‌های اول بین می ۱۹۹۷ تا آوریل ۱۹۹۸ هستن
• بازیابی حالت PRNG از بیت‌های بریده‌شده با الگوریتم LLL انجام شد
• base point شش منحنی از جمله P-192 از تولیدکنندهٔ عدد تصادفی FreeLIP اومده
• seed منحنی B-163 و base pointهای P-224 تا P-521 هنوز توضیحی ندارن
• جایزهٔ ۳۶٬۸۶۴ دلاری به Internet Security Research Group اهدا می‌شه