اختبار تطبيقات RNG والتحقق منها

يواجه اختبار مولدات الأرقام العشوائية تحديًا أساسيًا: فالتسلسلات العشوائية حقًا والتسلسلات شبه العشوائية الناتجة عن مولد أرقام شبه عشوائية جيد تبدو متطابقة أمام الاختبارات الإحصائية. ولا يمكن لأي اختبار محدود الطول أن يثبت أن التسلسل عشوائي؛ إذ لا تستطيع الإحصاءات سوى اكتشاف عدم العشوائية بدرجة معينة من الثقة. ويتحقق الاختبار من أن مولد الأرقام العشوائية لا يحتوي على انحيازات أو أنماط واضحة، لكنه لا يستطيع إثبات الأمان التشفيري. ولهذا الغرض هدفان متميزان لاختبار مولدات الأرقام العشوائية التشفيرية: (1) الجودة الإحصائية، أي التحقق من أن توزيع المخرجات يبدو منتظمًا ومستقلًا؛ (2) القوة التشفيرية، أي التحقق من تنفيذ خوارزمية DRBG تنفيذًا صحيحًا ومن صحة ادعاءات الأمان. ويتطلب هذان الهدفان أسلوبي اختبار مختلفين.

يوفر NIST SP 800-22 عددًا من 15 اختبارًا إحصائيًا لتقييم تسلسلات البتات. وتشمل الاختبارات: اختبار التكرار (أحادي البت)، إذ ينبغي أن تكون نسبة البتات 1 قريبة من 0.5؛ واختبار تكرار الكتل، الذي يقيس تكرار البتات 1 في كل كتلة مؤلفة من m بتات؛ واختبار السلاسل المتتابعة، الذي يحسب عدد السلاسل غير المنقطعة من البتات المتطابقة؛ واختبار أطول سلسلة، الذي يقيس طول أطول سلسلة من البتات 1؛ واختبار رتبة المصفوفة الثنائية، الذي يقيس رتبة المصفوفات الثنائية المشكلة من التسلسل؛ والاختبار الطيفي (DFT)، لاكتشاف الأنماط الدورية؛ واختبار مطابقة القوالب المتداخلة، لحساب مرات ظهور أنماط محددة؛ والاختبار الإحصائي العام لمورر، الذي يضغط التسلسل ويقيس مقدار قِصره بعد الضغط. ينتج كل اختبار قيمة p؛ وتشير p < 0.01 إلى عدم العشوائية. وتُجرى الاختبارات على ما يتراوح بين مليون ومليار بت.

يُعد TestU01، الذي طوّره L'Ecuyer وSimard عام 2007، حزمة شاملة من الاختبارات الإحصائية تُستخدم على نطاق واسع في مجتمع مولدات الأرقام العشوائية. يضم SmallCrush عشرة اختبارات ويستغرق نحو 35 ثانية، وهو مناسب للفحوصات السريعة. ويضم Crush عددًا من 144 اختبارًا ويستغرق نحو ساعتين. أما BigCrush فيضم 160 اختبارًا ويستغرق نحو 24 ساعة. وتكتشف اختبارات BigCrush الارتباطات الدقيقة التي لا يكتشفها NIST SP 800-22. وتجتاز مولدات DRBG التشفيرية المصممة جيدًا، مثل HMAC_DRBG وCTR_DRBG، اختبار BigCrush بسهولة؛ إذ لا يمكن للخوارزميات ذات الزمن متعدد الحدود تمييز مخرجاتها حسابيًا عن العشوائية. وتفشل مولدات الأرقام شبه العشوائية غير التشفيرية، مثل Mersenne Twister والمولدات التوافقية الخطية، في بعض اختبارات BigCrush. ويُعد الفشل في BigCrush مؤشرًا قويًا على أنه ينبغي عدم استخدام مولد الأرقام العشوائية لأغراض تشفيرية.

يحددان SP 800-90B و90A اختبارات سلامة يجب على مولدات DRBG إجراؤها باستمرار أثناء التشغيل. يقارن اختبار مولد الأرقام العشوائية المستمر (CRNGT) كل كتلة مولّدة بالكتلة السابقة؛ فإذا تساوتا، أي إذا كان المولد عالقًا، يجب أن يدخل DRBG في حالة خطأ ويتوقف عن التوليد. وفي اختبار عدّ التكرار، إذا احتوت عينات متتالية على القيمة نفسها مكررة مرات أكثر مما هو متوقع إحصائيًا وفقًا لتقدير الإنتروبيا، يُعلن الفشل. وفي اختبار النسبة التكيفية، يُعلن الفشل إذا ظهرت القيمة الأكثر تكرارًا عددًا من المرات يتجاوز عتبة معينة ضمن نافذة. وتكتشف اختبارات السلامة هذه أعطال مصادر الإنتروبيا، مثل مستشعر عالق أو عطل في أجهزة HWRNG، قبل أن تؤدي بصمت إلى الإضرار بتوليد المفاتيح التشفيرية.

PractRand أداة حديثة لاختبار مولدات الأرقام العشوائية، صُممت للتقييم المتدفق، إذ تحلل التسلسل أثناء توليده بدل اشتراط طول محدد مسبقًا. وتطبق اختبارات تشمل اختبارات الفجوات، واختبارات توزيع البتات، والاختبارات الطيفية، مع دقة تكيفية. وتتميز PractRand بفاعلية خاصة في اكتشاف مولدات الأرقام العشوائية التي تنتج تسلسلات قصيرة جيدة، لكنها تكشف عن أنماط عند فحص مليارات البتات. وتنتج مولدات DRBG التشفيرية مخرجات لا تستطيع PractRand تمييزها عن العشوائية مهما بلغ طول التسلسل؛ وهذا هو التعريف العملي لعدم التمييز الحسابي. وتُستخدم PractRand أيضًا لتقييم مصادر الإنتروبيا، مثل اختبار مخرجات /dev/urandom ومخرجات RDRAND، لاكتشاف أعطال الأجهزة أو الانحيازات المنهجية.

يوفر برنامج التحقق من الخوارزميات التشفيرية (CAVP) متجهات اختبار رسمية لمولدات DRBG الخاصة بـ SP 800-90A. ويتضمن اختبار CAVP تقديم تطبيق إلى نظام الاختبار الآلي التابع لـ NIST باستخدام متجهات اختبار الإجابة المعروفة (KAT): فعند إعطائه مدخل إنتروبيا محددًا، وnonce، وسلسلة تخصيص، وadditional_input، يجب أن ينتج التطبيق بتات المخرجات المتوقعة نفسها تمامًا. ولا يختبر CAVP الخصائص الإحصائية، بل يختبر الصحة الخوارزمية. ويتطلب اعتماد FIPS 140-3 التحقق من CAVP لجميع الخوارزميات التشفيرية المستخدمة ضمن حدود الوحدة. وتتوافر متجهات اختبار CAVP علنًا من خادم ACVP (بروتوكول التحقق الآلي من التشفير) التابع لـ NIST، كما أُدمجت في حزم اختبارات OpenSSL وmbedTLS وBoringSSL.

قبل أن يمكن تهيئة مولد DRBG بأمان، يجب التحقق من صحة مصدر الإنتروبيا الخاص به. ويحدد SP 800-90B ما يلي: (1) تقدير الإنتروبيا، أي قياس الإنتروبيا الفعلية لكل بت باستخدام الاختبارات الإحصائية، وتحديدًا تقدير الحد الأدنى للإنتروبيا؛ (2) اختبارات بدء التشغيل، للتحقق من أن مصدر الإنتروبيا ينتج مخرجات صحيحة قبل أول استخدام؛ (3) اختبارات عند الطلب، وهي اختبارات اختيارية تشغّلها التطبيقات؛ (4) اختبارات سلامة مصدر الضوضاء، لاكتشاف تدهور الأجهزة. وتشمل مصادر الإنتروبيا الشائعة وإنتروبياها المقدّرة لكل بت ما يلي: RDRAND/RDSEED في وحدة المعالجة المركزية (نحو 1 بت/بت، مع اعتماد عتادي)؛ /dev/urandom (يمزج عدة مصادر، ويستخدم تقديرًا محافظًا للإنتروبيا)؛ مولد الأرقام العشوائية الحقيقي القائم على مذبذب حلقي (0.5–0.9 بت/بت بحسب التصميم)؛ وضوضاء ADC ‏(0.1–0.5 بت/بت). ويتطلب التحقق وفق SP 800-90B اختبارات مخبرية باستخدام معدات متخصصة.

تفرض البيئات الافتراضية تحديات محددة عند اختبار RNG. فقد تواجه الأجهزة الافتراضية ظروفًا منخفضة الإنتروبيا عند بدء التشغيل، بسبب عدم وجود أحداث عتادية، أو بعد استعادة لقطة، بسبب إعادة ضبط الحالة. تشارك حاويات Docker نواة المضيف وRNG الخاص بها، لذلك لا تستطيع الحاوية اختبار جودة الإنتروبيا الأساسية مباشرة. اختبارات عمليات النشر على الأجهزة الافتراضية: (1) قياس الزمن اللازم لاكتمال القراءة من /dev/random — فترات الانتظار الطويلة تشير إلى عدم كفاية الإنتروبيا. (2) اختبار عدم تكرار UUIDs أو المفاتيح المُنشأة بالتوازي في مثيلات الأجهزة الافتراضية، فهذا نمط فشل حقيقي موثق في عمليات النشر السحابية. (3) التحقق من تحميل VIRTIO-RNG (virtio_rng.ko) في الأجهزة الافتراضية — إذ يوفر ذلك حقن الإنتروبيا من المضيف إلى الضيف. (4) تدقيق تسلسل بدء تشغيل التطبيق: هل يحدث توليد المفاتيح قبل توفر إنتروبيا كافية؟

يمنع اختبار سلامة RNG عند fork ثغرة دقيقة: فعندما تنفذ عملية fork، تتشارك العملية الأصلية والعملية التابعة حالة DRBG نفسها، مما يؤدي إلى توليد تسلسلات متطابقة. للكشف عن ذلك: أنشئ N من العمليات التابعة، وولّد UUID في كل منها، ثم تحقق من أن جميع UUIDs فريدة. إذا تطابق أي اثنين منها، فإن RNG لا يضمن السلامة عند fork. أصلحت OpenSSL عيبًا متعلقًا بالسلامة عند fork في عام 2020 (لم تتضمن CVE-2020-1971 مشكلة في DRBG مباشرة، لكن النمط مشابه). تستخدم OpenSSL حاليًا تحديثًا للبذرة قائمًا على PID: فإذا تغير PID منذ الاستدعاء السابق، مما يشير إلى حدوث fork، يُعاد توليد بذرة DRBG تلقائيًا. لاختبار ذلك: شغّل الاختبار قبل fork وبعده، وتحقق من حدوث إعادة البذر من خلال التأكد من اختلاف المخرجات.

قائمة تدقيق عملية لمراجعة تطبيقات RNG: (1) هل تتم تهيئة RNG من نظام التشغيل، باستخدام getrandom أو BCryptGenRandom، بدلًا من بذور تعتمد على الوقت؟ (2) هل نوع DRBG آلية معتمدة في NIST SP 800-90A، مثل Hash أو HMAC أو CTR؟ (3) هل طول البذرة كافٍ لمستوى الأمان المعلن؟ (4) هل تُجرى إعادة البذر دوريًا أو بعد عدد ثابت من استدعاءات generate؟ (5) هل يتعامل التطبيق مع سلامة fork، أي هل يعيد البذر بعد fork؟ (6) هل اختبارات الصحة مفعّلة، وهل توقف النظام عند الفشل؟ (7) هل تُصفّر الحالة عند إيقاف التشغيل؟ (8) هل تُشغّل متجهات اختبار CAVP في CI/CD؟ (9) هل تقديرات الإنتروبيا موثقة وجرى التحقق منها؟ (10) بالنسبة إلى متطلبات FIPS: هل الوحدة حاصلة على شهادة FIPS 140-3؟

توضح إخفاقات RNG التاريخية حجم المخاطر. Debian OpenSSL (2006-2008): أزالت رقعة برمجية عن طريق الخطأ سطرين من شيفرة جمع الإنتروبيا، مما خفّض مجموعة البذور إلى فضاء PID من 15 بتًا — فلم يكن ممكنًا توليد سوى 32,767 مفتاح SSH مختلفًا لقاعدة مستخدمي Debian بأكملها. وكان يلزم استبدال جميع مفاتيح مضيفي SSH ومفاتيح المستخدمين التي ولّدها Debian. محافظ Bitcoin على Android (2013): استخدمت SecureRandom في Android تهيئةً للبذرة على مستوى Java فشلت في بعض الأجهزة، مما تسبب في تكرار قيم k في توقيعات ECDSA — وهو ما كشف المفاتيح الخاصة مباشرةً. Sony PS3 (2010): استخدمت قيمة nonce ثابتة في توقيع البرامج الثابتة باستخدام ECDSA، مما أتاح استخراج المفتاح الخاص من توقيعين؛ فتكرار k نفسه عبر رسائل مختلفة يكشف المفتاح باستخدام جبر بسيط.

أيّ من الاختبارات التالية يكشف أن DRBG قد يكون يولّد مخرجات ثابتة، أي القيمة نفسها مرارًا؟

تتحقق الاختبارات الإحصائية، مثل NIST SP 800-22 وTestU01 BigCrush وPractRand، من جودة المخرجات، لكنها لا تستطيع إثبات الأمان التشفيري. وتتحقق اختبارات الإجابة المعروفة في CAVP من الصحة الخوارزمية لتطبيقات SP 800-90A. أما اختبارات مصدر الإنتروبيا في SP 800-90B، مثل تقدير الحد الأدنى للإنتروبيا واختبارات الصحة، فتحقق من صحة مدخل البذرة. ويكشف Continuous RNG Test (CRNGT) المخرجات الثابتة في الوقت الفعلي. وتتطلب عمليات النشر على الأجهزة الافتراضية والحاويات حقن الإنتروبيا، باستخدام VIRTIO-RNG، وفحوصات إنتروبيا بدء التشغيل. ويتحقق اختبار السلامة عند fork من أن العمليات التابعة لا ترث حالة DRBG الخاصة بالعملية الأصلية. وتوضح الإخفاقات الواقعية، مثل Debian وAndroid، أن أخطاء RNG تؤدي مباشرةً إلى اختراق المفاتيح التشفيرية. وتعمل قوائم التدقيق على تنظيم هذه الفحوصات لعمليات النشر الإنتاجية.