مولد أرقام عشوائية زائفة آمن تشفيريًا

مولد الأرقام شبه العشوائية الآمن تشفيريًا ( CSPRNG ) أو مولد الأرقام شبه العشوائية المشفر ( CPRNG ) هو مولد أرقام شبه عشوائية (PRNG) يتمتع بخصائص تجعله مناسبًا للاستخدام في التشفير . ويشار إليه أيضًا باسم مولد الأرقام العشوائية المشفر ( CRNG ).

لا يستشهد هذا القسم بأي مصادر . يُرجى المساعدة في تحسين هذا القسم من خلال إضافة الاستشهادات إلى مصادر موثوقة . قد يتم الطعن في المواد غير الموثقة وإزالتها . ( يونيو 2024 ) ( تعرف على كيفية ومتى يمكنك إزالة هذه الرسالة )

تتطلب معظم تطبيقات التشفير أرقامًا عشوائية ، على سبيل المثال:

• توليد المفتاح
• متجهات التهيئة
• نونس
• الأملاح في مخططات التوقيع المحددة، بما في ذلك ECDSA و RSASSA-PSS
• توليد الرمز

تختلف "جودة" العشوائية المطلوبة لهذه التطبيقات. على سبيل المثال، لا يحتاج إنشاء رقم عشوائي في بعض البروتوكولات إلا إلى التفرد. من ناحية أخرى، يتطلب إنشاء مفتاح رئيسي جودة أعلى، مثل المزيد من الإنتروبيا . وفي حالة الفوط التي تستخدم لمرة واحدة ، لا ينطبق ضمان نظرية المعلومات للسرية التامة إلا إذا جاءت مادة المفتاح من مصدر عشوائي حقيقي ذي إنتروبيا عالية، وبالتالي فإن أي نوع من مولدات الأرقام شبه العشوائية غير كافٍ.

من الناحية المثالية، يستخدم توليد الأرقام العشوائية في CSPRNGs الإنتروبيا التي تم الحصول عليها من مصدر عالي الجودة، وعادةً ما يكون واجهة برمجة تطبيقات العشوائية لنظام التشغيل . ومع ذلك، تم العثور على ارتباطات غير متوقعة في العديد من هذه العمليات المستقلة ظاهريًا. من وجهة نظر نظرية المعلومات، فإن مقدار العشوائية، الإنتروبيا التي يمكن توليدها، يساوي الإنتروبيا التي يوفرها النظام. ولكن في بعض الأحيان، في المواقف العملية، تكون هناك حاجة إلى أرقام ذات عشوائية أكبر مما يمكن أن توفره الإنتروبيا المتاحة. أيضًا، تكون العمليات اللازمة لاستخراج العشوائية من نظام قيد التشغيل بطيئة في الممارسة الفعلية. في مثل هذه الحالات، يمكن استخدام CSPRNG في بعض الأحيان. يمكن لـ CSPRNG "تمديد" الإنتروبيا المتاحة على المزيد من البتات.

يتم أيضًا تلبية متطلبات مولد الأرقام العشوائية العادي بواسطة مولد الأرقام العشوائية الآمن تشفيريًا، ولكن العكس ليس صحيحًا. تنقسم متطلبات مولد الأرقام العشوائية الآمن تشفيريًا إلى مجموعتين:

1. يجتازون اختبارات العشوائية الإحصائية :
   • يجب أن يفي كل CSPRNG باختبار البت التالي . أي أنه بالنظر إلى أول k بت من تسلسل عشوائي، لا توجد خوارزمية زمنية متعددة الحدود يمكنها التنبؤ بالبت ( k +1) باحتمال نجاح أفضل بشكل لا يمكن إهماله من 50٪. ^{[1] أثبت} أندرو ياو في عام 1982 أن المولد الذي يجتاز اختبار البت التالي سيجتاز جميع الاختبارات الإحصائية الأخرى متعددة الحدود للعشوائية. ^[2]
2. إنهم يصمدون بشكل جيد في مواجهة أي هجوم خطير، حتى عندما يصبح جزء من حالتهم الأولية أو حالتهم التشغيلية متاحًا للمهاجم: ^[3]
   • يجب أن يتحمل كل CSPRNG "هجمات تمديد تسوية الحالة". ^{[3] : 4} في حالة الكشف عن جزء أو كل حالته (أو تخمينه بشكل صحيح)، يجب أن يكون من المستحيل إعادة بناء تدفق الأرقام العشوائية قبل الكشف. بالإضافة إلى ذلك، إذا كان هناك إدخال إنتروبيا أثناء التشغيل، فيجب أن يكون من غير الممكن استخدام معرفة حالة الإدخال للتنبؤ بالظروف المستقبلية لحالة CSPRNG.

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

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

تم تصميم CSPRNGs بشكل صريح لمقاومة هذا النوع من تحليل الشفرات .

في الإعداد المقارب ، فإن عائلة من الدوال الحسابية ذات الزمن المتعدد الحدود الحتمي لبعض متعدد الحدود p ، هي مولد أرقام عشوائية زائفة (PRNG، أو PRG في بعض المراجع)، إذا قامت بتمديد طول مدخلاتها ( لأي k )، وإذا كان إخراجها غير قابل للتمييز حسابيًا عن العشوائية الحقيقية، أي لأي خوارزمية زمنية متعددة الحدود احتمالية A ، والتي تخرج 1 أو 0 كمميز، ${\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}}$${\displaystyle p(k)>k}$

${\displaystyle \left|\Pr _{x\يحصل على \{0,1\}^{k}}[A(G(x))=1]-\Pr _{r\يحصل على \{0,1\}^{p(k)}}[A(r)=1]\right|\leq \mu (k)}$

لبعض الوظائف المهملة . ^[4] ( تعني هذه الصيغة أن x يتم اختيارها عشوائيًا وبشكل موحد من المجموعة X. ) ${\displaystyle \mu }$${\displaystyle x\يحصل على X}$

يوجد توصيف مكافئ: بالنسبة لأي عائلة دالة ، فإن G هي مولد أرقام عشوائية متكررة إذا وفقط إذا لم يكن من الممكن التنبؤ بالبت الناتج التالي من G بواسطة خوارزمية وقت متعدد الحدود. ^[5]${\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}}$

مولد الأرقام العشوائية المؤمن للأمام بطول كتلة هو مولد أرقام عشوائية ، حيث سلسلة الإدخال بطول k هي الحالة الحالية في الفترة i ، ويتكون الخرج ( ، ) من الحالة التالية وكتلة الخرج شبه العشوائية للفترة i ، والتي تتحمل امتدادات تسوية الحالة بالمعنى التالي. إذا تم اختيار الحالة الأولية بشكل عشوائي وموحد من ، فبالنسبة لأي i ، يجب أن يكون التسلسل غير قابل للتمييز حسابيًا عن ، حيث يتم اختيارها بشكل عشوائي وموحد من . ^[6]${\displaystyle t(k)}$${\displaystyle G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}}$${\displaystyle s_{i}}$${\displaystyle s_{i+1}}$${\displaystyle y_{i}}$${\displaystyle s_{i+1}}$${\displaystyle y_{i}}$${\displaystyle s_{1}}$${\displaystyle \{0,1\}^{k}}$${\displaystyle (y_{1},y_{2},\dots ,y_{i},s_{i+1})}$${\displaystyle (r_{1},r_{2},\dots ,r_{i},s_{i+1})}$${\displaystyle r_{i}}$${\displaystyle \{0,1\}^{t(k)}}$

يمكن تحويل أي PRNG إلى PRNG آمن أمامي بطول كتلة عن طريق تقسيم خرجه إلى الحالة التالية والخرج الفعلي. يتم ذلك عن طريق ضبط ، حيث و ؛ ثم يكون G عبارة عن PRNG آمن أمامي مع كحالة تالية وككتلة خرج شبه عشوائية للفترة الحالية. ${\displaystyle G\colon \{0,1\}^{k}\to \{0,1\}^{p(k)}}$${\displaystyle p(k)-k}$${\displaystyle G(s)=G_{0}(s)\رأس G_{1}(s)}$${\displaystyle |G_{0}(s)|=|s|=k}$${\displaystyle G_{1}(s)|=p(k)-k}$${\displaystyle G_{0}}$${\displaystyle G_{1}}$

أثبت سانثا وفازيراني أنه يمكن دمج العديد من تدفقات البتات ذات العشوائية الضعيفة لإنتاج تدفق بتات شبه عشوائي وأعلى جودة. ^[7] وحتى في وقت سابق، أثبت جون فون نيومان أن خوارزمية بسيطة يمكن أن تزيل قدرًا كبيرًا من التحيز في أي تدفق بتات، ^[8] والذي يجب تطبيقه على كل تدفق بتات قبل استخدام أي اختلاف في تصميم سانثا وفازيراني.

تنقسم تصميمات CSPRNG إلى فئتين:

1. التصميمات القائمة على البدائيات التشفيرية مثل الشفرات والتجزئات التشفيرية
2. تصميمات مبنية على مسائل رياضية يعتقد أنها صعبة

• يمكن تحويل تشفير كتلة آمن إلى CSPRNG عن طريق تشغيله في وضع العداد باستخدام، على سبيل المثال، بنية خاصة يطلق عليها NIST في SP 800-90A اسم CTR_DRBG . يستخدم CTR_DBRG عادةً معيار التشفير المتقدم (AES).
  • غالبًا ما يتم استخدام AES- CTR _DRBG كمولد أرقام عشوائية في الأنظمة التي تستخدم تشفير AES. ^{[9] [10]}
  • يقوم مخطط NIST CTR_DRBG بمسح المفتاح بعد إخراج العشوائية المطلوبة من خلال تشغيل دورات إضافية. هذا أمر مضيعة من منظور الأداء، لكنه لا يسبب مشاكل فورية مع السرية الأمامية. ومع ذلك، وإدراكًا لتداعيات الأداء، يوصي NIST بـ "واجهة AES-CTR-DRBG الموسعة" لإرساليات مشروع التشفير بعد الكم . تسمح هذه الواجهة بإنشاء مجموعات متعددة من العشوائية دون محو متداخل، ولا يتم المحو إلا عندما يشير المستخدم صراحةً إلى نهاية الطلبات. ونتيجة لذلك، يمكن أن يظل المفتاح في الذاكرة لفترة طويلة إذا تم إساءة استخدام "الواجهة الموسعة". تقوم مولدات الأرقام العشوائية "المحو السريع للمفتاح" الأحدث بمسح المفتاح بالعشوائية بمجرد طلب العشوائية. ^[11]
• يمكن تحويل تشفير التدفق إلى CSPRNG. وقد تم ذلك باستخدام RC4 و ISAAC و ChaCha20 ، على سبيل المثال لا الحصر.
• قد تكون التجزئة الآمنة تشفيريًا أيضًا بمثابة أساس لـ CSPRNG جيد، وذلك باستخدام، على سبيل المثال، بنية يطلق عليها NIST اسم Hash_DRBG .
• يمكن استخدام بدائية HMAC كأساس لـ CSPRNG، على سبيل المثال، كجزء من البنية التي يطلق عليها NIST اسم HMAC_DRBG .

• تتمتع خوارزمية بلوم بلوم شوب بإثبات أمان يعتمد على صعوبة مشكلة البقايا التربيعية . ونظرًا لأن الطريقة الوحيدة المعروفة لحل هذه المشكلة هي تحليل معامل العامل، فمن المعتقد عمومًا أن صعوبة تحليل العوامل الصحيحة توفر إثبات أمان مشروطًا لخوارزمية بلوم بلوم شوب. ومع ذلك، فإن الخوارزمية غير فعّالة للغاية وبالتالي غير عملية ما لم تكن هناك حاجة إلى أمان شديد.
• تتمتع خوارزمية بلوم-ميكالي بإثبات أمان يعتمد على صعوبة مشكلة اللوغاريتم المنفصل ولكنها أيضًا غير فعالة للغاية.
• كتب دانييل براون من شركة Certicom دليل أمان في عام 2006 لـ Dual EC DRBG ، استنادًا إلى الصلابة المفترضة لافتراض Decisional Diffie–Hellman ، ومشكلة اللوغاريتم x ، ومشكلة النقطة المقطوعة . يفترض دليل عام 2006 صراحةً أن outlen (كمية البتات المقدمة لكل تكرار) أقل من معيار Dual_EC_DRBG، وأن قيم P و Q في معيار Dual_EC_DRBG (والتي تم الكشف عنها في عام 2013 على أنها ربما تكون مخترقة من قبل NSA) تم استبدالها بقيم غير مخترقة.

لا تتضمن مخططات CSPRNG "العملية" خوارزمية CSPRNG فحسب، بل تتضمن أيضًا طريقة لتهيئة (" البذرة ") مع الحفاظ على سرية البذرة. وقد تم تعريف عدد من هذه المخططات، بما في ذلك:

• تنفيذات /dev/random في أنظمة شبيهة بنظام يونكس.
  • Yarrow ، الذي يحاول تقييم الجودة الإنتروبية لمدخلات البذر الخاصة به، ويستخدم SHA-1 و3DES داخليًا. تم استخدام Yarrow في macOS وأنظمة تشغيل Apple الأخرى حتى ديسمبر 2019 تقريبًا، وبعد ذلك تم التحول إلى Fortuna.
  • Fortuna ، خليفة Yarrow، الذي لا يحاول تقييم جودة الإنتروبيا لمدخلاته؛ فهو يستخدم SHA-256 و"أي تشفير كتلة جيد". يُستخدم Fortuna في FreeBSD. قامت Apple بتغييره إلى Fortuna لمعظم أو جميع أنظمة تشغيل Apple بدءًا من حوالي ديسمبر 2019.
  • نواة Linux CSPRNG، التي تستخدم ChaCha20 لتوليد البيانات، ^[12] و BLAKE2s لاستيعاب الإنتروبيا. ^[13]
• arc4random ، وهو CSPRNG في أنظمة شبيهة بـUnix يزرع من /dev/random . وهو في الأصل يعتمد على RC4 ، لكن جميع التطبيقات الرئيسية تستخدم الآن ChaCha20 . ^{[14] [15] [16]}
• CryptGenRandom ، جزء من CryptoAPI الخاص بشركة Microsoft ، متوفر على نظام Windows. تستخدم الإصدارات المختلفة من Windows تنفيذات مختلفة.
• معيار ANSI X9.17 ( إدارة مفاتيح المؤسسات المالية (بالجملة) )، والذي تم اعتماده كمعيار FIPS أيضًا. يأخذ كمدخلات مجموعة مفاتيح TDEA ( خيار التشفير 2 ) k و(القيمة الأولية) لبذرة عشوائية مكونة من 64 بت s . ^[17] في كل مرة يكون مطلوبًا فيها رقم عشوائي، فإنه ينفذ الخطوات التالية:
  1. احصل على التاريخ/الوقت الحالي D إلى أقصى دقة ممكنة.
  2. احسب القيمة المؤقتة t = TDEA _k ( D ) .
  3. احسب القيمة العشوائية x = TDEA _k ( s ⊕ t ) ، حيث ⊕ تشير إلى البتات الحصرية أو .
  4. قم بتحديث البذرة s = TDEA _k ( x ⊕ t ) .

من الواضح أن هذه التقنية يمكن تعميمها بسهولة على أي تشفير كتلة؛ وقد تم اقتراح AES . ^[18] إذا تم تسريب المفتاح k ، فيمكن التنبؤ بتدفق X9.17 بالكامل؛ يُستشهد بهذا الضعف كسبب لإنشاء Yarrow. ^[19]

تمزج كل هذه المخططات المذكورة أعلاه، باستثناء X9.17، أيضًا حالة CSPRNG مع مصدر إضافي للإنتروبيا. وبالتالي فهي ليست مولدات أرقام عشوائية زائفة "نقية"، بمعنى أن الناتج لا يتم تحديده تمامًا من خلال حالتها الأولية. تهدف هذه الإضافة إلى منع الهجمات حتى إذا تم المساس بالحالة الأولية. ^[أ]

تم توحيد معايير العديد من CSPRNGs. على سبيل المثال:

• FIPS 186-4 ^[21]
• معيار المعهد الوطني للمعايير والتكنولوجيا رقم 800-90A

• NIST SP 800-90A الإصدار 1

• ANSI X9.17-1985 الملحق ج
• ANSI X9.31-1998 الملحق A.2.4
• ANSI X9.62-1998 Annex A.4، تم إلغاؤه بواسطة ANSI X9.62-2005، Annex D (HMAC_DRBG)

يتم الحفاظ على مرجع جيد بواسطة NIST . ^[26]

هناك أيضًا معايير للاختبار الإحصائي لتصميمات CSPRNG الجديدة:

• مجموعة اختبارات إحصائية لمولدات الأرقام العشوائية وشبه العشوائية ، منشور خاص من المعهد الوطني للمعايير والتكنولوجيا رقم 800-22. ^[27]

ذكرت صحيفة الجارديان وصحيفة نيويورك تايمز في عام 2013 أن وكالة الأمن القومي (NSA) أدخلت بابًا خلفيًا في مولد أرقام عشوائية زائفة (PRNG) لـ NIST SP 800-90A ، مما يسمح لوكالة الأمن القومي بفك تشفير المواد المشفرة بسهولة بمساعدة Dual EC DRBG . ذكرت كلتا الصحيفتين ^{[28] [29]} أنه، كما اشتبه خبراء الأمن المستقلون منذ فترة طويلة، ^[30] كانت وكالة الأمن القومي تُدخل نقاط ضعف في معيار CSPRNG 800-90؛ وقد تم تأكيد ذلك لأول مرة من خلال إحدى الوثائق السرية للغاية التي سربها إدوارد سنودن إلىصحيفة الجارديان . عملت وكالة الأمن القومي سراً للحصول على نسختها الخاصة من مسودة معيار أمان NIST المعتمدة للاستخدام العالمي في عام 2006. تنص الوثيقة المسربة على أنه "في النهاية، أصبحت وكالة الأمن القومي المحرر الوحيد". على الرغم من الإمكانات المعروفة لوجود باب خلفي للسرقات وغيرها من العيوب المهمة المعروفة في Dual_EC_DRBG، استمرت العديد من الشركات مثل RSA Security في استخدام Dual_EC_DRBG حتى تم تأكيد الباب الخلفي في عام 2013. ^[31] تلقت RSA Security مبلغ 10 ملايين دولار من وكالة الأمن القومي للقيام بذلك. ^[32]

في 23 أكتوبر 2017، أصدر شانان كوني، وماثيو جرين ، ونادية هينينجر ، خبراء التشفير في جامعة بنسلفانيا وجامعة جونز هوبكنز ، تفاصيل هجوم DUHK (عدم استخدام مفاتيح مبرمجة بشكل ثابت) على WPA2 حيث يستخدم بائعو الأجهزة مفتاحًا أساسيًا مبرمجًا بشكل ثابت لخوارزمية ANSI X9.31 RNG، مشيرين إلى أن "المهاجم يمكنه استخدام القوة الغاشمة لكشف بقية معلمات التشفير واستنتاج مفتاح التشفير الرئيسي المستخدم لتشفير جلسات الويب أو اتصالات الشبكة الخاصة الافتراضية (VPN)". ^{[33] [34]}

خلال الحرب العالمية الثانية ، استخدمت اليابان آلة تشفير للاتصالات الدبلوماسية؛ وتمكنت الولايات المتحدة من اختراقها وقراءة رسائلها ، ويرجع ذلك في الغالب إلى أن "القيم الأساسية" المستخدمة لم تكن عشوائية بدرجة كافية.

• RFC  4086، متطلبات العشوائية للأمان
• "مجموعة إنتروبيا" بلغة جافا للأرقام العشوائية غير المتوقعة الآمنة تشفيريًا. محفوظ في 2008-12-02 على موقع Wayback Machine
• فئة Java القياسية التي توفر مولد أرقام عشوائية زائفة قوية تشفيريًا (PRNG).
• رقم عشوائي آمن تشفيريًا على نظام التشغيل Windows دون استخدام CryptoAPI
• الأمن المفترض لمولد الأرقام العشوائية المنحني الإهليلجي ANSI-NIST، دانيال آر إل براون، IACR ePrint 2006/117.
• تحليل أمني لمولد الأرقام العشوائية ذو المنحنى الإهليلجي SP 800-90 التابع للمعهد الوطني للمعايير والتكنولوجيا، دانيال آر إل براون وكريستيان جوستين، IACR ePrint 2007/048. سيظهر في مجلة CRYPTO 2007.
• تحليل تشفير مولد شبه عشوائي ثنائي المنحنى الإهليلجي، بيري شوينماكرز وأندري سيدورينكو، IACR ePrint 2006/190.
• مولدات شبه عشوائية فعالة تعتمد على افتراض DDH، رضا رضائيان فاراشاهي وبيري شوينماكرز وأندري سيدورينكو، IACR ePrint 2006/321.
• تحليل مولد الأرقام العشوائية في لينكس، زفي جوتيرمان وبيني بينكاس وتزاتشي راينمان.
• تنزيل وثائق مجموعة الاختبارات الإحصائية NIST وبرنامجها.