كيف يمكنني تقييم احتمالية تصادم التجزئة؟

Question

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

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

المشكلة هي كيفية التعرف على الملفات.أسمائهم تتغير بشكل عشوائي.أنوي استخدام وظيفة التجزئة مثل MD5 لتجزئة محتويات الملف.أنا على دراية جيدة بالأمر مفارقة عيد ميلاد واستخدم تقديرًا من المقالة المرتبطة لحساب الاحتمال.إذا افترضت أنه ليس لدي أكثر من 100000 ملف، فإن احتمال وجود ملفين لهما نفس MD5 (128 بت) هو حوالي 1,47x10^-29.

هل يجب أن أهتم باحتمالية التصادم هذه أم أفترض فقط أن قيم التجزئة المتساوية تعني محتويات ملف متساوية؟

Answer 1

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

لا توجد اصطدامات عرضية لـ MD5، 1,47x10^-29 هو حقا عدد صغير حقا.

للتغلب على مشكلة إعادة صياغة الملفات الكبيرة، سيكون لدي مخطط هوية ثلاثي المراحل.

1. حجم الملف وحده
2. حجم الملف + تجزئة 64 كيلو بايت * 4 في مواضع مختلفة في الملف
3. تجزئة كاملة

لذا، إذا رأيت ملفًا بحجم جديد، فأنت تعلم على وجه اليقين أنه ليس لديك نسخة مكررة.وما إلى ذلك وهلم جرا.

Answer 2

وفقط لأن الاحتمال هو 1 / X وهذا لا يعني أنه لن يحدث لك حتى يكون لديك سجلات X. انها مثل اليانصيب، وكنت غير المرجح أن يفوز، ولكن شخص هناك <م> سوف الفوز.

ومع سرعة وقدرة أجهزة الكمبيوتر هذه الأيام (وليس حتى نتحدث عن الأمن، والموثوقية فقط) هناك حقا أي سبب لعدم مجرد استخدام / أفضل وظيفة التجزئة أكبر من MD5 عن أي شيء بالغ الأهمية. يجب أن تصعد إلى SHA-1 تساعدك على النوم بشكل أفضل ليلا، ولكن إذا كنت تريد المزيد من الحذر ثم انتقل إلى SHA-265 و أبدا التفكير في الامر مرة أخرى.

وإذا كان الأداء حقا قضية ثم استخدام BLAKE2 وهو أسرع فعلا من MD5 ولكن يدعم 256+ بت لجعل الاصطدام أقل احتمالا في حين وجود نفس أو أفضل أداء. ومع ذلك، في حين BLAKE2 اعتمد بشكل جيد، وربما يتطلب إضافة تبعية جديدة إلى المشروع.

Answer 3

وأعتقد أنك لا ينبغي.

ولكن، يجب عليك إذا كان لديك فكرة وجود ملفين متساوية مختلفة (الأسماء الحقيقية، وليس المستندة إلى MD5). مثل، في نظام البحث قد يكون اثنين ثيقة المحتوى نفسه بالضبط، ولكن يجري متميزة لانهم تقع في أماكن مختلفة.

Answer 4

وخطرت لي نهج مونت كارلو ليكون قادرا على النوم بسلام أثناء استخدام UUID عن النظم الموزعة التي لديها تسلسل دون الاصطدام.

from random import randint
from math import log
from collections import Counter

def colltest(exp):
    uniques = []
    while True:
        r = randint(0,2**exp)
        if r in uniques:
            return log(len(uniques) + 1, 2)
        uniques.append(r)

for k,v in Counter([colltest(20) for i in xrange(1000)]):
    print k, "hash orders of magnitude events before collission:",v

وسوف تطبع شيئا مثل:

5 hash orders of magnitude events before collission: 1
6 hash orders of magnitude events before collission: 5
7 hash orders of magnitude events before collission: 21
8 hash orders of magnitude events before collission: 91
9 hash orders of magnitude events before collission: 274
10 hash orders of magnitude events before collission: 469
11 hash orders of magnitude events before collission: 138
12 hash orders of magnitude events before collission: 1

وكنت قد سمعت الصيغة قبل: إذا كنت بحاجة لتخزين تسجيل (س / 2) مفاتيح، استخدم دالة التجزئة التي لديها ما لا يقل عن keyspace ه ** (خ)

والتجارب المتكررة تظهر أن ليبلغ عدد سكانها 1000 سجل 20 مسافات، تحصل في بعض الأحيان اصطدام في وقت مبكر من السجل (س / 4).

لuuid4 الذي هو 122 بت وهذا يعني أن أنام بسلام في حين اختيار العديد من أجهزة الكمبيوتر عشوائية في UUID حتى لدي حوالي 2 ** 31 العناصر. المعاملات الذروة في النظام أفكر هو تقريبا 10-20 الأحداث في الثانية الواحدة، وأنا على افتراض ما معدله 7. أن يعطيني نافذة تشغيل ما يقرب من 10 عاما، نظرا إلى أن جنون العظمة المدقع.

Answer 5

وهنا حاسبة التفاعلية التي تمكنك من تقدير احتمال الاصطدام لأي حجم التجزئة وعدد من الكائنات - <وأ href = "http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/" يختلط = "نوفولو"> http://everydayinternetstuff.com/2015/04/hash-collision-probability-calculator/