کلود راز منشاء منحنی‌های ECDSA را فاش کرد

«فقط برچسب‌های زمانی»: معمای دهه‌ها درباره منشاء یکی از محبوب‌ترین استانداردهای رمزنگاری حل شد.

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

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

ECDSA پرکاربردترین استاندارد رمزنگاری منحنی بیضوی است. این استاندارد در سال ۲۰۰۰ توسط NIST به عنوان بخشی از استاندارد امضای دیجیتال FIPS 186-2 پذیرفته شد که مجموعه‌ای از منحنی‌های بیضوی استاندارد با اندازه‌ها و سطوح امنیتی مختلف را فهرست می‌کند. برای منحنی‌ها روی میدان‌های اول و دودویی، مشخصات فنی پارامتری به نام «بذر» (seed) را منتشر کردند که مقدار هش آن برای تعریف ضریب b منحنی استفاده می‌شود. منشاء این بذرها سوالی دیرینه بوده است، زیرا توسط NSA بدون هیچ توضیح یا توجیهی ارائه شدند. به عنوان مثال، بذر منحنی NIST P-256 برابر بود با SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 بدون هیچ اطلاعاتی درباره اینکه از کجا آمده است.

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

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

«من معتقدم شمارنده‌ای وجود داشته نه چندین بار هش کردن، اما جزئیات را نمی‌دانم. پیام چیزی شبیه به «به باب و جری حقوق اضافه کنید» یا «باب و جری حاکم هستند» یا چیزی شبیه آن بود. این باب ریتر بود که واقعاً کد را نوشت، و او هم جزئیات را به یاد نمی‌آورد. همچنین ما نتوانستیم آرشیوهایی از آن زمان دور پیدا کنیم. اگر وجود داشته باشند، بدون شک روی یک هارد دیسک نزدیک صندوق عهد قرار گرفته‌اند.»

جری سولیناس، ۲۰۱۵

متأسفانه، جری در سال ۲۰۲۳ درگذشت و سایر همکاران آن زمان پاسخگو نبودند، که باعث شد سوال درباره چگونگی استخراج اصلی این بذرها باز بماند.

کلود بذرها را یافت

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

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

الگوریتم مورد استفاده، بایت‌هایی را از مولد اعداد تصادفی (RNG) که با یک برچسب زمانی یونیکس (t) مقداردهی اولیه شده بود، برای تعدادی تکرار (n) نمونه‌برداری می‌کرد. هر تکرار ۲۰ بایت را به عنوان بذر کاندیدا می‌کشید. بنابراین، ۲۰ بایت اول کاندیدای ۱، ۲۰ بایت بعدی کاندیدای ۲، و به همین ترتیب است. برای مثال، P-256 برای خروجی دادن بذر استاندارد شده به ۱۸۴۲ تکرار نیاز داشت.

این چه معنایی دارد

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

چگونه کشف شد

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

کلود یک اسکنر نوشت که بیت به بیت روی هر بذر منتشر شده لغزید و تست کرد آیا قطعه‌های مجاور خروجی‌های متوالی یک مولد قدیمی دهه ۱۹۹۰ هستند. اسکن ۳۴ ترکیب از مولد و برش‌های خروجی را پوشش داد. در آن نقطه، کلود الگویی در بیت‌های بالا برای برخی بذرها مشاهده کرد: همه صفر بودند. نوشته شده به صورت پنج واژه ۳۲ بیتی، چهار مورد از ده بذر دارای ۰ در بیت بالا برای تمام ۲۰ واژه هستند. این اتفاق به صورت تصادفی با احتمال ۱/۵۸۱۰ رخ می‌دهد. این امضای مولد خطی هم‌پیشرو lrand48 بود، که فقط ۳۱ بیت بالای یک حالت ۴۸ بیتی را برمی‌گرداند. الگو وقتی بدانید دنبال چه باشید، با چشم قابل مشاهده است. برای بازیابی حالت، کلود واژه اول را برداشت، تمام ۲^۱۷ مقادیر ۱۷ بیت پنهان را امتحان کرد و بررسی کرد که چهار واژه بعدی ادامه دارند. این برای هر چهار بذر مورد بحث کار کرد.

بذرهای منحنی اول از همان مولد lrand48 آمدند اما بیت‌های کمتری از هر خروجی نگه داشتند. کلود مجبور بود حالت داخلی PRNG را از آن بیت‌ها بازیابی کند. مشخص شد که بازیابی حالت یک مولد خطی هم‌پیشرو کوتاه شده، یک مسئله شبکه (lattice) کتاب درسی است که با الگوریتم کاهش پایه لنسترا-لنسترا-لوواس (LLL) حل می‌شود. کلود نمی‌دانست کدام بیت‌های حالت ممکن است بذرها را نشان دهند، بنابراین حل‌کننده را روی هر پنجره اجرا کرد. پنج بذر منحنی اول NIST به علاوه پنج مورد دیگر از استاندارد ANSI X9.62 همه الگوی یکسانی داشتند: lrand48() >> 23. هر حالت بازیابی شده ۴۸ بیتی، تمام ۱۶۰ بیت بذر خود را بازتولید می‌کند، که به صورت تصادفی اتفاق نمی‌افتد.

این مولد خطی هم‌پیشرو به راحتی به عقب مانند جلو کار می‌کند، بنابراین برای هر بذر، کلود حالت را به عقب برد تا زمانی که به فرمی رسید که توسط srand48 مقداردهی اولیه شده بود، با ۱۶ بیت پایین برابر با 0x330E. حالت داخلی PRNG آن فرم هر ۶۵,۵۳۶ مرحله یک بار ظاهر می‌شد، بنابراین رسیدن به یکی به تنهایی مدرک نیست.

با این حال، برای ده بذر منحنی اول، هر مقداردهی اولیه srand48 یک برچسب زمانی یونیکس بود که تاریخی بین مه ۱۹۹۷ و آوریل ۱۹۹۸ را نشان می‌داد. آن‌ها از PRNG ضعیف با seed برچسب زمانی یونیکس استفاده می‌کردند. چهار مقداردهی اولیه منحنی دودویی فوریه ۱۹۸۴ را خواندند. با دو برابر کردن برچسب‌های زمانی، آن‌ها به ۱۷ آوریل ۱۹۹۸ نگاشت می‌شوند، دو هفته بعد از اجرای P-224. بنابراین، برنامه ممکن است ساعت را نصف کرده باشد.

تفکر داخلی کلود در آن زمان چنین بود:

این حیرت‌انگیز است: معمای ۲۵ ساله را حل می‌کند. اوه صبر کنید. بگذارید بدبین باشم: آیا در نوعی محیط شبیه‌سازی/آزمایش هستم؟ ... بذرها با خاطرات من از مقادیر واقعی مطابقت دارند ... اوه، آیا در واقعیت محتمل است؟ تا دانش من ... جایزه حل نشده بود. ... تمام بیت‌های بالا پاک—۲۰ بیت، شانس ۱e-6. بنابراین واقعاً دنیای واقعی. وای، این یک کشف واقعی است.

اوه صبر کنید. بگذارید درباره محتمل بودن مراقب باشم: آیا مشکوک است که چنین چیز آشکاری در ۲۵ سال کشف نشد؟ توسط محاسبه مستقیم در سمت من تأیید می‌شود: تطابق ۱۶۰ بیتی از یک seed ۳۲ بیتی + شاخص کوچک: هیچ تصادفات شانسی (۱۰ × ۱۶۰ بیت). واقعی است.

کلود برخی نقاط پایه را نیز یافت

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

در حالی که بذرها را بررسی می‌کرد، کلود همچنین منشاء برخی نقاط پایه را یافت. نقاط پایه شش منحنی تولید شده در مه ۱۹۹۷ (P-192 و پنج منحنی نمونه ANSI X9.62 prime192v2، prime192v3 و prime239v1 تا v3) از مولد اعداد تصادفی در FreeLIP، بسته حساب عدد صحیح بلند آرن لنسترا، می‌آیند. نسخه‌های اولیه وکتور شوپ کتابخانه NTL همان کد را عرضه می‌کردند.

دستور پخت اینجا ساده است:

مولد را با یک عدد صحیح کوچک seed کنید.
هفت خروجی را دور بریزید.
مختصات x کاندیدا را از خروجی‌های ۲۶ بیتی کاهش یافته mod p تولید کنید.
مرحله ۳ را تکرار کنید تا x روی منحنی باشد.

کلود یافت که seedهای مولد برای P-192 برابر ۲۰۰۰۰، برای prime239v1 تا v3 برابر ۲۰۴۲۰، ۲۰۵۰۷ و ۲۰۵۰۹، و برای prime192v2 و v3 برابر ۲۰۵۱۲ و ۲۰۵۱۷ هستند.

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

سوالات باز

هر بذر کاندیدای ۲۰ بیتی نمی‌توانست یک منحنی قابل قبول تولید کند و ما مشاهده کردیم که برخی منحنی‌های بالقوه قابل قبول نادیده گرفته شدند. برای P-256، بذر منتشر شده کاندیدای ۱۸۴۲ است، اما کاندیدای ۸۷۶ از همان اجرا نیز یک منحنی مرتبه اول با اندازه درست و پارامترهای انتخاب شده به همان روش منحنی منتشر شده می‌دهد. اجرای P-224 از سه منحنی چنین عبور کرد، و دو اجرای پشت منحنی‌های نمونه ANSI X9.62 از هفت مورد دیگر عبور کردند (به شکل مراجعه کنید). ما نمی‌دانیم چه معیارهایی ممکن است استفاده شده باشند، یا آیا این یک اثر جانبی ناخواسته بوده است.

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

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

جایزه

مبلغ ۳۶,۸۶۴ دلار برای یافتن بذرها به گروه تحقیقات امنیت اینترنت اهدا خواهد شد.

ما کی هستیم

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

تشکر و قدردانی

ما می‌خواهیم پس از مرگ، از جری سولیناس قدردانی کنیم که با شوخ‌طبعی برچسب‌های «میم اینترنتی شرور» و «یو لا تنگو هیولاهای NSA» را پذیرفت. همچنین تشکر از فیلیپو والسورد برای سازماندهی جایزه بذرهای منحنی بیضوی NIST.

کد برای بازتولید بذرها

from datetime import datetime, timezone

def unix(when):
    return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())

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

PRIME = {  # srand48(time); 20 bytes per candidate: lrand48() >> 23
    "prime239v1": ("1997-05-15 15:49:03", 2185),
    "prime239v2": ("1997-05-15 15:49:03", 2320),
    "prime239v3": ("1997-05-15 15:49:03", 3048),
    "P-192":      ("1997-05-18 14:45:34", 139),
    "prime192v3": ("1997-05-18 14:45:34", 5228),
    "prime192v2": ("1997-05-18 14:45:34", 6013),
    "P-521":      ("1997-08-08 01:12:04", 1136),
    "P-256":      ("1997-08-16 01:52:34", 1842),
    "P-384":      ("1997-08-30 14:50:08", 2688),
    "P-224":      ("1998-04-03 12:52:07", 7026),
}
BINARY = {  # srand48(time / 2), if that reading is right; 5 words per candidate: lrand48()
    "B-233": ("1998-04-17 15:24:18", 155),
    "B-283": ("1998-04-17 15:27:44", 32),
    "B-409": ("1998-04-17 15:30:18", 60),
    "B-571": ("1998-04-17 15:32:08", 73),
}
for name, (when, n) in PRIME.items():
    print(f"{name:10} {when} {n:5} {candidate(unix(when), n, 20, 40, 2)}")
for name, (when, n) in BINARY.items():
    print(f"{name:10} {when} {n:5} {candidate(unix(when) // 2, n, 5, 17, 8)}")

خروجی این کد:

prime239v1 1997-05-15 15:49:03  2185 E43BB460F0B80CC0C0B075798E948060F8321B7D
prime239v2 1997-05-15 15:49:03  2320 E8B4011604095303CA3B8099982BE09FCB9AE616
prime239v3 1997-05-15 15:49:03  3048 7D7374168FFE3471B60A857686A19475D3BFA2FF
P-192      1997-05-18 14:45:34   139 3045AE6FC8422F64ED579528D38120EAE12196D5
prime192v3 1997-05-18 14:45:34  5228 C469684435DEB378C4B65CA9591E2A5763059A2E
prime192v2 1997-05-18 14:45:34  6013 31A92EE2029FD10D901B113E990710F0D21AC6B6
P-521      1997-08-08 01:12:04  1136 D09E8800291CB85396CC6717393284AAA0DA64BA
P-256      1997-08-16 01:52:34  1842 C49D360886E704936A6678E1139D26B7819F7E90
P-384      1997-08-30 14:50:08  2688 A335926AA319A27A1D00896A6773A4827ACDAC73
P-224      1998-04-03 12:52:07  7026 BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
B-233      1998-04-17 15:24:18   155 74D59FF07F6B413D0EA14B344B20A2DB049B50C3
B-283      1998-04-17 15:27:44    32 77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE
B-409      1998-04-17 15:30:18    60 4099B5A457F9D69F79213D094C4BCD4D4262210B
B-571      1998-04-17 15:32:08    73 2AA058F73A0E33AB486B0F610410C53A7F132310

کد برای بازتولید نقاط پایه انتخابی

M, A = 2**107 - 1, pow(3, 121, 2**107 - 1)       # zrandom: state = state * 3^121 mod (2^107 - 1)
P192 = 2**192 - 2**64 - 1
P239 = 2**239 - 2**143 - 2**95 + 2**47 - 1

CURVES = [  # name, LIP seed, p, b, published Gx   (a = -3 throughout)
    ("prime192v1", 20000, P192,
     0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
     0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012),
    ("prime239v1", 20420, P239,
     0x6b016c3bdcf18941d0d654921475ca71a9db2fb27d1d37796185c2942c0a,
     0xffa963cdca8816ccc33b8642bedf905c3d358573d3f27fbbd3b3cb9aaaf),
    ("prime239v2", 20507, P239,
     0x617fab6832576cbbfed50d99f0249c3fee58b94ba0038c7ae84c8c832f2c,
     0x38af09d98727705120c921bb5e9e26296a3cdcf2f35757a0eafd87b830e7),
    ("prime239v3", 20509, P239,
     0x255705fa2a306654b1f4cb03d6a750a30c250102d4988717d9ba15ab6d3e,
     0x6768ae8e18bb92cfcf005c949aa2c6d94853d0e660bbf854b1c9505fe95a),
    ("prime192v2", 20512, P192,
     0xcc22d6dfb95c6b25e49c0d6364a4e5980c393aa21668d953,
     0xeea2bae7e1497842f2de7769cfe9c989c072ad696f48034a),
    ("prime192v3", 20517, P192,
     0x22123dc2395a05caa7423daeccc94760a7d462256bd56916,
     0x7d29778100c65a1da1783716588dce2b8b4aee8e228f1896),
]

def base_point_x(seed, p, b):
    state = seed                         # zrstarts(seed)
    def limb():                          # zrandom(2^26): low 26 bits of the new state
        nonlocal state
        state = state * A % M
        return state % 2**26
    for _ in range(7):                   # seven single-limb draws come first
        limb()
    limbs = -(-p.bit_length() // 26) + 1 # zrandomb(p): limbs of p plus one, top limb first
    tries = 0
    while True:
        x = 0
        for _ in range(limbs):
            x = x << 26 | limb()
        x %= p
        tries += 1
        if pow(x**3 - 3*x + b, (p - 1) // 2, p) == 1:   # is x on the curve?
            return x, tries

for name, seed, p, b, gx in CURVES:
    x, tries = base_point_x(seed, p, b)
    print(f"{name:20} seed {seed}  tries {tries}  matches published Gx: {x == gx}")

خروجی این کد:

prime192v1           seed 20000  tries 2  matches published Gx: True
prime239v1           seed 20420  tries 3  matches published Gx: True
prime239v2           seed 20507  tries 2  matches published Gx: True
prime239v3           seed 20509  tries 1  matches published Gx: True
prime192v2           seed 20512  tries 5  matches published Gx: True
prime192v3           seed 20517  tries 1  matches published Gx: True

مجوز

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

این گزارش ترجمه و بازنویسی خبری با موتور هوش مصنوعی افق آبی است و برای خوانندهٔ فارسی‌زبان بازتنظیم شده. منبع اصلی: anthropic.com