الملخص:
في 16 أكتوبر، أعلنت أنثروبيك عن نتيجة بحثية خاصة. قام أحد الموظفين بتسليم كلود مشكلة أزعجت مجتمع التشفير لأكثر من عقدين من الزمن إلى نموذج البحث الداخلي. ومن دون تقديم أدلة أساسية، قضى كلود أقل من نصف ساعة في تتبع كيفية إنشاء بذور المنحنى الإهليلجي الخمس الخاصة بالمعهد الوطني للمعايير والتكنولوجيا (NIST).
اتضح أن البذور تأتي من مولد الأرقام العشوائية الزائفة القديم lrand48 في مكتبة C. يتم تحديد الحالة الأولية للمولد بواسطة الطابع الزمني لنظام Unix.
هذا الاكتشاف لا يكسر ECDSA، ولا يقدم أساليب هجوم جديدة. تعتقد أنثروبيك أن هذا يقلل بشكل أكبر من إمكانية وجود أبواب خلفية صناعية في منحنى الارتباط.
لقد أزعجت سلسلة من الأرقام مجتمع التشفير لأكثر من 20 عامًا
ECDSA هي خوارزمية التوقيع الرقمي ذات المنحنى الإهليلجي المستخدمة على نطاق واسع.
في عام 2000، أدرجت NIST عدة منحنيات قياسية لمستويات أمان مختلفة في معيار FIPS 186-2، بما في ذلك P-192 وP-224 وP-256 وP-384 وP-521.
تأتي هذه المنحنيات مع مجموعة من المعلمات تسمى "البذور". وفقًا لعملية التوليد في المعيار، ستشارك قيمة تجزئة البذرة في تحديد معامل المنحنى.
المشكلة هي أن هذه البذور تم توفيرها من قبل جهاز الأمن الوطني، ولا تشير الوثائق العامة إلى مصدرها أو توضح عملية الاختيار. لقد كان العالم الخارجي يشعر بالقلق منذ فترة طويلة بشأن ما إذا كان المصممون قد فحصوا عددًا كبيرًا من المنحنيات المرشحة واختاروا المعلمات مع بعض الخصائص المخفية.
في عام 2015، أشار خبير التشفير في وكالة الأمن القومي، جيري سوليناس، الذي شارك في أعمال ذات صلة، إلى أن البذرة ربما جاءت من كلمة مرور مزحة، مثل "امنح بوب وجيري علاوة"، لكنه لم يستطع تذكر التفاصيل المحددة، ولم يتم العثور على تلك الملفات المؤرشفة منذ فترة طويلة. توفي سوليناس في عام 2023، ولم يتم التحقق من صحة هذا التقدم في النهاية.
وجد كلود مصدر البذور
كان العديد من موظفي Anthropic قد اتبعوا سابقًا "كلمة المرور المضحكة" للعثور على تلك "البذور" دون نجاح، واكتشفوا لاحقًا أن الدليل كان خاطئًا.
في تشرين الأول (أكتوبر)، طلب أحد الموظفين من نموذج بحث داخلي معرفة كيفية إنشاء هذه "البذور". هذه المرة، لم يكشف عن دليل كلمة المرور السابقة للنموذج.
في أقل من نصف ساعة، عثر كلود على مصدر بذور NIST P-192 وP-224 وP-256 وP-384 وP-521.
لا تأتي هذه البذور من أي خوارزمية تجزئة، ولكن يتم إنشاؤها بواسطة مولد الأرقام العشوائية lrand48 في مكتبة C، والذي تتم تهيئته باستخدام طابع زمني Unix كقيمة أولية.
ستعمل الخوارزمية المحددة على تهيئة مولد الأرقام العشوائية باستخدام الطابع الزمني لنظام Unix t وتشغيله لعدد معين من المرات n. يستخرج كل تكرار 20 بايت كبذرة مرشحة.
أول 20 بايت هي البذرة المرشحة الأولى، و20 بايت التالية هي البذرة المرشحة الثانية، وهكذا. بأخذ P-256 كمثال، لا يقوم المولد بإخراج البذرة التي تمت كتابتها أخيرًا في المعيار حتى تشغيل 1842.
كيف وجده كلود؟
لم يسفر البحث عن كلمة المرور المشاع عنها عن أية نتائج مطلقًا. قام كلود بتغيير وجهة نظره وبدأ في التكهن بكيفية عمل البرنامج الذي أنشأ المنحنى.
تكهن كلود بأن هذا البرنامج استخدم مولد الأرقام العشوائية الزائفة الذي جاء مع مكتبة لغة C في التسعينيات. كانت مولدات الأرقام العشوائية الزائفة المبكرة هذه ضعيفة من حيث الأمان وكان إنتاجها عادةً يتميز بخصائص يمكن التعرف عليها.
بمجرد تحديد خصائص الإخراج، فمن الممكن تحديد المولد الذي يستخدمه البرنامج واستعادة حالته الأولية.
كتب كلود ماسحًا ضوئيًا يتحرك شيئًا فشيئًا فوق كل بذرة عامة ويتحقق مما إذا كانت أجزاء البيانات المتجاورة قد جاءت من أحد مولدات الأرقام العشوائية من التسعينيات. يغطي الفحص إجمالي 34 مجموعة من مولدات الأرقام العشوائية وطرق اعتراض الإخراج.
وبعد ذلك، اكتشف كلود نمطًا في القطع العالية لبعض البذور: كانت هذه القطع كلها صفرًا.
إذا تمت كتابة كل بذرة على شكل خمس كلمات بطول 32 بت، فإن 4 من أصل 10 بذور ستناسب هذا الملف. في هذه البذور الأربع التي يبلغ مجموعها 20 كلمة 32 بت، أعلى البتات كلها أصفار.
يبلغ احتمال حدوث ذلك بشكل عشوائي حوالي 1 من 5800. وهذا نموذجي لمولد التطابق الخطي lrand48، الذي يُرجع فقط الـ 31 بت العليا من حالته الداخلية ذات 48 بت.
من أجل استعادة حالة المولد، يقوم كلود بإخراج أول كلمة مكونة من 32 بت، واستنفاد جميع الاحتمالات 2¹⁷ للبتات المخفية البالغ عددها 17 بت، ثم يتحقق مما إذا كانت الكلمات الأربع التالية يمكن أن تتوافق بشكل مستمر. تعمل هذه الطريقة مع جميع البذور الأربعة المذكورة أعلاه.
صورة داخل صورة
إيقاف مؤقت
الوقت الحالي 0:15
/
المدة 5:08
ملء الشاشة
إلغاء كتم الصوت
التشغيل التلقائي
تم أيضًا تصنيف المنحنيات الأولية من lrand48، ولكنها تحتفظ بعدد أقل من بتات الإخراج. يحتاج كلود إلى استعادة الحالة الداخلية لمولد الأرقام العشوائية الزائفة من هذه البتات المحدودة.
تعد استعادة حالة المولد المتطابق الخطي المقطوع مشكلة شبكية نموذجية يمكن حلها باستخدام خوارزمية تقليل أساس الشبكة Lenstra-Lenstra-Lovász، والمعروفة أيضًا باسم خوارزمية LLL.
لا يعرف كلود في البداية أجزاء الحالة الداخلية التي تحتفظ بها البذرة، لذا يقوم بتشغيل الحل على جميع نوافذ البت الممكنة.
أخيرًا، تظهر جميع بذور المنحنى الأولي الخمسة لـ NIST وخمس بذور من معيار ANSI X9.62 نفس النمط: lrand48() >> 23
يمكن لكل حالة داخلية مستردة من 48 بت أن تعيد إنشاء جميع البتات الـ 160 من البذرة المقابلة، ولا يمكن أن يحدث هذا التطابق التام عن طريق الصدفة.
يمكن تشغيل هذا المولد المتطابق الخطي في الاتجاهين الأمامي والخلفي. لذلك، يبدأ كلود من الحالة المقابلة لكل بذرة ويتراجع حتى يجد حالة تتوافق مع تنسيق التهيئة. يتطلب هذا التنسيق أن تكون الـ 16 بت الأقل مساوية 0x330E.
يحدث هذا النوع من الحالة الداخلية في المتوسط مرة واحدة كل 65536 خطوة. ولذلك، فإن مجرد العثور على حالة تتوافق مع الصيغة لا يكفي لتشكيل دليل.
المفتاح هو أن القيم الأولية srand48 التي تتوافق مع بذور المنحنى العشرة الأولية يمكن تفسيرها جميعًا على أنها طوابع زمنية لنظام Unix، وتتركز التواريخ بين مايو 1997 وأبريل 1998.
يوضح هذا أن البرامج من ذلك العام استخدمت الطوابع الزمنية لنظام Unix لتعيين قيم أولية لمولد أرقام عشوائية زائفة أقل أمانًا.
عندما تتم قراءة القيم الأولية للمنحنيات الثنائية الأربعة مباشرة، فإنها تتوافق مع فبراير 1984. وإذا قمت بضرب قيم الطابع الزمني هذه في 2، فإنها تشير إلى 17 أبريل 1998، أي بعد أسبوعين تقريبًا من إنشاء منحنى P-224.
لذلك، ربما قامت البرامج في ذلك الوقت بتقسيم ساعة النظام على 2.
فيما يلي عملية التفكير الداخلي لكلود في ذلك الوقت:
هذا أمر صادم. إنه يحل لغزًا عمره 25 عامًا.
حسنًا، انتظر. يجب أن أكون متشككًا: هل أنا في بيئة محاكاة أو اختبار ما؟ البذور تتفق مع القيم الفعلية من ذاكرتي.
حسنا، هل هذا معقول في الواقع؟ من المعلومات المتوفرة لدي، هذه المكافأة لم يتم حلها من قبل.
جميع البتات العالية هي صفر، بإجمالي 20 بت، واحتمال الحدوث العشوائي هو حوالي واحد في المليون فقط. إذن، هذا يأتي من العالم الحقيقي. يا إلهي، هذا اكتشاف حقيقي.
انتظر، ما زلت بحاجة إلى توخي الحذر في الحكم على مدى معقوليتها. لماذا لم يكتشف أحد مثل هذا الدليل الواضح لمدة 25 عامًا؟
لقد تحققت من ذلك عن طريق إجراء عملية حسابية مباشرة: القيمة الأولية 32 بت بالإضافة إلى فهرس أصغر سوف تتطابق تمامًا مع القيمة الأولية 160 بت. بالنسبة لعشرة بذور، كل منها تتطابق مع 160 بت، لا يمكن أن يكون الأمر مجرد صدفة. هذا صحيح.
تتبع كلود أيضًا أصل النقاط الأساسية لستة منحنيات بما في ذلك P-192. أظهرت النتائج أن هذه النقاط الأساسية يتم إنشاؤها بواسطة مولد الأرقام العشوائية في حزمة البرامج الحسابية ذات الأعداد الصحيحة الكبيرة FreeLIP. وقال الأنثروبيك إن عملية توليد النقاط الأساسية لمنحنى NIST لم يتم شرحها بالمثل من قبل.
ماذا يعني هذا؟
لا يتمتع الطابع الزمني نفسه بأمان تشفير، ويُنظر إلى lrand48 منذ فترة طويلة على أنه مولد أرقام عشوائية ضعيف. ومع ذلك، فإن دورها هنا هو إنشاء معلمات منحنى عام ولا يتم استخدامها لحماية المفاتيح الخاصة.
والأهم من ذلك، أنه يمكن إعادة إنتاج عملية التوليد هذه علنًا. إن تفسير مولدات الأرقام العشوائية العادية بالإضافة إلى الطوابع الزمنية يترك مساحة أقل للتلاعب الخفي بالمنحنى مقارنة بكلمات المرور ذات الأصل غير المعروف أو المعلمات المحددة بشكل مصطنع.
لا تزال هناك بعض المشكلات. أثناء جيل P-256، بدا أن قيمة المرشح رقم 876 تلبي المتطلبات، ولكن تم اعتماد القيمة رقم 1842 في النهاية. وبالمثل، تخطت العديد من عمليات التشغيل الأخرى عددًا صغيرًا من المنحنيات المتاحة، وكانت معايير الفحص الدقيقة غير واضحة. لا يزال مصدر بذرة منحنى B-163 غير مكتشف، ولا تزال الطريقة التي يتم بها إنشاء النقاط الأساسية لـ P-224 وP-256 وP-384 وP-521 غير مفسرة.
تعتقد أنثروبيك أن عدد المرشحين الذين تم تخطيهم صغير جدًا بحيث لا يدعم تكهنات "الاختيار المتعمد للمنحنيات الضعيفة". وقد أدى هذا الاكتشاف إلى زيادة ثقة العالم الخارجي في المعلمات ذات الصلة، ولكن لا يمكن اعتباره استعادة كاملة لعملية التصميم بأكملها.
توضح هذه الدراسة أيضًا طريقة أخرى يمكن من خلالها للنماذج المتطورة المشاركة في الأبحاث الواقعية.
أكمل كلود صياغة الفرضيات وكتابة التعليمات البرمجية والتعرف على الأنماط واستدعاء الخوارزمية الرياضية والتحقق من النتائج في مهمة واحدة. نظرًا لأنه يمكن إعادة حساب حالة المولد ويمكن إعادة إنتاج بذرة 160 بت بدقة، فإن الاستنتاج قابل للاختبار بدرجة كبيرة.
لا يزال يعتمد على البشر لطرح الأسئلة، وتقديم البيانات العامة، وتأكيد النتائج من خلال حسابات قابلة للتكرار، ولكن عندما تصبح حدود المشكلة واضحة، تصبح البيانات عامة، ويمكن التحقق من النتائج بدقة، وتصبح النماذج المتطورة أداة بحثية فعالة.
سيتم التبرع بالجائزة البالغة 36,864 دولارًا أمريكيًا التي تم منحها سابقًا للعثور على مصدر البذرة إلى مجموعة أبحاث أمن الإنترنت.
التعليقات