أدوات المطور · مولد UUID
ما عدد البتات العشوائية الموجودة في الإصدار 4 UUID؟ 122، ليس 128
· كيف يعمل
uuid التشفير متصفح API
تم إصلاح ستة من 128 bits في UUID العشوائية بواسطة المعيار، مع ترك 122 للعشوائية. يوضح هذا المنشور كيفية تقدير احتمالات الاصطدام بأمانة ولماذا تأتي الاصطدامات الحقيقية من المولدات المعطلة، وليس من الرياضيات.
سؤال المهندس المعماري: هل سنحصل على نسخة مكررة؟ - من أين يأتي القلق ولماذا تعتمد الإجابة على المولد
يسأل المهندس المعماري: إذا قمنا بإنشاء 10 مليون UUID يوميًا لمدة عشر سنوات، فهل سنحصل على نسخة مكررة؟ الإجابة الصادقة هي: من المؤكد تقريبًا لا، إذا كان المولد آمنًا من الناحية المشفرة؛ من المؤكد تقريبا نعم، إذا كان المولد معطلا. إن الرياضيات RFC 9562 سليمة: v4 UUID مع 122 بتات عشوائية لديها احتمالية تصادم تقريبًا n² / 2 للأس 123، حيث n هو عدد المعرفات التي تم إنشاؤها. بالنسبة لمعظم الأنظمة الحقيقية، هذا الاحتمال لا يكاد يذكر. المهم هو أن هذه الصيغة تفترض أن كل جزء عشوائي حقًا. إذا تسرب المولد أو تكرر أو تم زرعه بشكل متوقع، فستكون الصيغة خاطئة، وتصبح التكرارات أمرًا لا مفر منه. يشتمل تخطيط 128-بت على أربع بتات إصدار (0100 للإصدار 4) وبتتين مختلفتين (10 لـ RFC 9562)، والتي يتم إصلاحها وتعيينها بواسطة المعيار.
ما هي البتات الست التي يتم التحدث عنها - بتات الإصدار الأربعة والبتات المتغيرة، ولماذا تم تعيينها بدلاً من أن تكون عشوائية
وهذا يترك 122 bits للعشوائية. تُسمى الصيغة أحيانًا 2 إلى البتات العشوائية 122، مما يؤدي إلى إنتاج قيم فريدة. باستخدام تقريب مفارقة عيد الميلاد، يكون احتمال حدوث تصادم واحد على الأقل بين القيم المولدة عشوائيًا n² / 2 تقريبًا إلى 123. بالنسبة إلى n = 1 مليون، هذا هو (10^6)² / 2^123 = 10^12 / 9. 3 × 10^36، وهو حوالي 10^-25. بالنسبة لـ n = 10 مليار، لا يزال حوالي 10^-16. هذه ليست "صفرًا فعليًا"؛ هم "لن تلاحظ هذا أبدًا." يعطي تقريب عيد الميلاد طريقة ملموسة لحساب المخاطر: قم بحساب UUIDs التي تخطط لإنشاءها، وقم بتربيع هذا الرقم، وتقسيمه على 2 إلى القوة 123. إذا كان المولد هو crypto.getRandomValues الخاص بالمتصفح، فإن كل بت يتم دعمه بواسطة إنتروبيا نظام التشغيل. إذا كانت الرياضيات.
تقريب تاريخ الميلاد بعبارات واضحة - احتمال حدوث تصادم واحد على الأقل بين معرفات n هو تقريبًا n تربيع مقسومًا على 2 إلى 123
بالنسبة إلى UUID التي يتم إنتاجها بواسطة مولد حالة غير مناسب أو متكرر، ينهار النموذج الرياضي لأن افتراض استقلاله خاطئ. يمكن لبذرة الاختبار الثابتة أو التركيبات المنسوخة أو لقطة العملية إعادة تشغيل القيم على الرغم من أن النص لا يزال يحمل الإصدار 4. هذه عيوب في التنفيذ، وليست دليلاً على أن حساب الحقل 122 كان خاطئًا. يقوم مصدر عادي آخر بنسخ نفس المعرف الحرفي في العديد من التركيبات ثم دمج بياناتها لاحقًا. عند التحقيق في نسخة مكررة، احتفظ بالمولد وسياسة البذور ودورة حياة العملية وتاريخ الاستيراد. لا تقفز من قيمة واحدة متكررة إلى ادعاء بأن الإخراج المستقل CSPRNG استنفد مساحة UUID.
مثال عملي - إدخال معدل التوليد المحدد والفترة الزمنية في التقريب، مع عرض كل خطوة حتى تتمكن من استبدال الأرقام الخاصة بك
عملية التفرع دون إعادة مزامنة الحالة العشوائية. خطأ حيث تم استخدام Math.random بدلاً من crypto.getRandomValues. أداة اختبار تم تصنيعها يدويًا بنفس UUID في صفوف متعددة وتم استخدامها عن طريق الخطأ في الإنتاج. نسخة قديمة من مكتبة UUID بها قيود على النطاق أو خطأ في الحالة. لا يتضمن أي من هذه السيناريوهات رياضيات تقريبية لتاريخ الميلاد؛ أنها تنطوي على تنفيذ معطل أو أخطاء تشغيلية. قم بحساب مخاطر الاصطدام لنظامك بأمانة: قم بحساب معدل توليد UUID (في الثانية، في اليوم، في السنة)، وقم بإسقاطه على مدار الوقت الذي سيتم فيه تشغيل النظام، وقم بإدخال الإجمالي في صيغة عيد الميلاد. إذا كان نظامك ينشئ 100,000 UUID يوميًا لمدة خمس سنوات (182 مليون إجمالاً)، فإن احتمال التصادم هو (1. 82 × 10^8)² / 2^123 ≈ 3. 3 × 10^-22، وهو أمر لا يكاد يذكر.
من أين تأتي النسخ المكررة فعليًا — Math.random البذور، والأجهزة الافتراضية المستنسخة، والعمليات المتشعبة ذات الحالة المنسوخة، والنسخ واللصق في التركيبات
إذا قمت بتوليد 10 مليون في الثانية لمدة عام (315 تريليون إجمالاً)، فإن الاحتمال هو (3. 15 × 10^14)² / 2^123 ≈ 10^-10، والتي لا تزال صغيرة إلى حد التلاشي. تفترض هذه التقديرات أن كل جزء مستقل وعشوائي. يستخدم المولد ToolAcre crypto.getRandomValues، مما يمنحك عشوائية مدعومة بـ CSPRNG؛ العملية هي الجزء الوحيد الذي يجب أن تثق به. لا تعتمد أبدًا على احتمالية الاصطدام كذريعة لتخطي عمليات التحقق من الترخيص المناسبة. UUID ليست كلمة مرور، وليست رمز وصول، وليست سرًا حتى لو كانت 122 بتات عشوائية. التفرد هو المنفعة؛ عدم القدرة على التنبؤ هي خاصية منفصلة (وأكثر أهمية) تمنع التخمين. تتعامل رياضيات عيد الميلاد مع التفرد؛ لا يتناول مدى الحياة (هل يجب أن تنتهي صلاحية UUID؟) أو السرية (هل يجب تجزئتها قبل التخزين؟) أو التفويض (هل يثبت امتلاك UUID أي شيء عن المتصل؟). يمنحك المولد ToolAcre معرفات UUID مدعومة بـ CSPRNG مع 122 بتات عشوائية، مما يعني أن الرياضيات الفريدة التي تحملها وعدم القدرة على التنبؤ سليمة. كل شيء آخر - التحقق من صحة الرمز المميز، وانتهاء الصلاحية، والتحكم في الوصول - هو مسؤولية التطبيق الخاص بك. تفترض صيغة الاحتمالية استقلالية كل UUID التي تم إنشاؤها عن الأجيال السابقة. إذا قام نظامك بإنشاء معرفات من مثيل CSPRNG واحد، وكل استدعاء يستمد عشوائية جديدة من نظام التشغيل، فإن افتراض الاستقلال يظل ساريًا. إذا كان نظامك يستخدم حالة CSPRNG مخبأة أو منشئًا مصنفًا دون إعادة زرع نظام التشغيل، فسينهار الافتراض. يزداد خطر الاصطدام بشكل كبير إذا تم استنفاد مصدر الإنتروبيا (يحدث في بعض الأنظمة المدمجة أو الأجهزة الافتراضية تحت التحميل) أو إذا لم تتم إعادة تعيين الحالة العشوائية مطلقًا بين العمليات (تفرع العملية دون إعادة زرع CSPRNG).
ما لا يغطيه هذا هو تفرد الإصدارين v1 وv7، والذي يعتمد على الطوابع الزمنية وتسلسلات الساعة بدلاً من العشوائية وحدها
يستدعي الإجراء الاحتياطي ToolAcre crypto.getRandomValues لكل مصفوفة بايت ولا يحمل أي حالة PRNG على مستوى التطبيق. تظل الأجزاء الداخلية للمنصة مسؤولية المتصفح ونظام التشغيل. تُظهر محاكاة الاصطدامات بمولدات حقيقية الفرق بين النظرية والممارسة المعطلة. المولد الذي تم إنشاؤه بـ Math.random بدءًا من نفس البذرة سوف ينتج تسلسلات متطابقة؛ ستشاهد أول تصادم UUID خلال بضع مئات إلى بضعة آلاف من القيم التي تم إنشاؤها، وليس بعد قيم 2^60 (الجذر التربيعي لـ 2^122) كما يتوقع تقريب عيد الميلاد. المولد الذي يستخدم crypto.getRandomValues من إنتروبيا نظام التشغيل الصوتي لن ينتج عنه تصادمات إلا عندما يصبح الاحتمال النظري لا مفر منه (حوالي 2^60 UUIDs)، وهو رقم كبير جدًا لدرجة أنك لن تصل إليه أبدًا. المولد الذي يستخدم مصدر إنتروبيا ضعيفًا أو مُعاد استخدامه (شائع في مكتبات UUID سيئة التنفيذ أو أطر الاختبار) سوف ينتج عنه تصادمات في مكان ما بينهما.
الخلاصة: ثق في الرياضيات، ودقق في المولد — يستخدم المولد ToolAcre CSPRNG الخاص بالمتصفح، وهو الجزء الذي يجب عدم تزييفه
يمكن للاختبار الدفعي التقاط تطبيق يُرجع ثابتًا أو يعيد تشغيل تسلسل واضح، لكن العينة الناجحة لا يمكنها إثبات التفرد المستقبلي. يجب أن تستمر أنظمة الإنتاج في فرض قيد فريد حيثما تؤدي المعرفات المكررة إلى إتلاف البيانات. تستحق الواردات اهتمامًا خاصًا لأن نظامي مصدر صالحين قد يحتويان بالفعل على نفس المعرف الحرفي، ويمكن نسخ التركيبات عبر البيئات. تتحقق اختبارات ToolAcre من أن مجموعة 500 تحتوي على 500 قيم مميزة؛ وهذا هو التحقق من الانحدار لهذا التنفيذ، وليس ضمانًا إحصائيًا. في حالة ظهور نسخة مكررة، احتفظ بالأدلة وافحص مسارات الإنشاء والاستيراد والتركيب والتخزين قبل إسناد السبب.