كيف تكتشف الملفات المتطابقة دون مقارنتها ببعضها البعض؟

Question

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

أسلوبي الحالي هو جعل قاعدة البيانات التي تتعقب كل ملف تم تحميله تخزن المعلومات التالية حول كل ملف:

• حجم الملف بالبايت
• مجموع MD5 لمحتويات الملف
• SHA1 مجموع محتويات الملف

ثم فهرس فريد على تلك الأعمدة الثلاثة.باستخدام اثنين من التجزئة ل تصغير خطر ايجابيات كاذبة.

لذا فإن سؤالي هو في الواقع: ما هو احتمال وجود ملفين مختلفين ("في العالم الحقيقي") بنفس الحجم لهما MD5 متطابقان و تجزئة SHA1؟

أو: هل هناك طريقة أكثر ذكاءً للتعقيد (غير) المماثل؟

(أفهم أن الاحتمال قد يعتمد على حجم الملف).

شكرًا!

Answer 1

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

إن إضافة MD5 إلى المزيج هو مبالغة كاملة.إذا كنت لا تثق في SHA-1، فالخيار الأفضل هو التبديل إليه شا-2.

إذا كنت مصابًا بجنون العظمة حقًا، فحاول مقارنة الملفات ذات التوقيعات المتطابقة (الحجم، SHA1).ومع ذلك، سيتعين عليه قراءة كلا الملفين بالكامل إذا كانا كذلك نكون متساوي.

Answer 2

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

يحرر:لم أقم بتحديد احتمالات حصولك على تصادم MD5 + SHA1.أود أن أقول أنه صفر.من خلال حساب أولي للمغلف، فإن احتمالات وجود ملفين مختلفين بأحجام ملفات عشوائية لهما صف متطابق (SHA1، MD5) هي 2 ^ -288، وهو صفر بقدر ما أشعر بالقلق.إن الاضطرار إلى طلب حجم ملف مماثل يقلل من ذلك بشكل أكبر.

Answer 3

يمكنك استخدام تطبيق Broders لخوارزمية بصمات رابين.إنه أسرع في الحساب من sha1 وmd5 وقد ثبت أنه مقاوم للتصادم.ومع ذلك، لا يعتبر آمنًا ضد الهجمات الضارة، فمن الممكن أن يقوم شخص ما بتغيير الملف المعني عمدًا دون تغيير بصمة الإصبع نفسها.إذا كنت تريد فقط التحقق من تشابه الملفات، فهذا حل جيد جدًا.

تنفيذ C#، لم يتم اختباره:

http://www.developpez.net/forums/d863959/dotnet/general-dotnet/contribuez/algorithm-rabin-fingerprint/