تصادم حاد

في علم الحاسوب ، يُعرف تصادم التجزئة أو تعارض التجزئة ^{[ 1 ]} بأنه عندما تتشارك قطعتان مختلفتان من البيانات في جدول التجزئة نفس قيمة التجزئة. تُستمد قيمة التجزئة في هذه الحالة من دالة تجزئة تأخذ مدخلات بيانات وتعيد طولًا ثابتًا من البتات. ^{[ 2 ]}

تُستخدم دالة التجزئة عادةً كدالة متعددة إلى واحد ، حيث يكون عدد المدخلات المحتملة (حجم نطاق الإدخال ) أكبر بكثير من عدد قيم الإخراج المحتملة ("النطاق")، مما يجعل التصادمات حتمية (" مبدأ التوزيع "). بالنسبة لدوال التجزئة التشفيرية (CHFs)، يكون الإخراج عبارة عن تمثيل مضغوط لقيمة إدخال معينة، تستخدمه خوارزميات سلامة البيانات للعمل بكفاءة باستخدام هذا التمثيل بدلاً من بيانات الإدخال الأكبر حجمًا. ^{[ 3 ]} يُخالف التصادم افتراضات خوارزميات السلامة، لذا صُممت دوال التجزئة التشفيرية بحيث يكون إيجاد تصادم عملي غير ممكن حسابيًا (ما يُسمى بمقاومة التصادم ). ^{[ 3 ]}

تُعدّ الاستخدامات الشائعة لدوال التجزئة غير المشفرة (NCHFs) - مثل مرشحات بلوم ، وجداول التجزئة ، ومخططات العد - أقل حساسيةً للتصادمات، لذا فهي لا تتطلب سوى خصائص التوزيع المنتظم والانهيار الجليدي . ^{[ 4 ]} ومع ذلك، تُعدّ مقاومة التصادم ميزةً إضافيةً مفيدةً ضد هجمات إغراق التجزئة ؛ إذ تفتقر دوال التجزئة غير المشفرة البسيطة، مثل فحص التكرار الدوري (CRC)، إلى مقاومة التصادمات ^{[ 5 ]} ، وبالتالي لا يمكن استخدامها مع مدخلات قابلة للتلاعب من قِبل المهاجم. وتستخدم التطبيقات غير المشفرة طرقًا متعددةً للتعامل مع تصادمات التجزئة عند حدوثها.

قد يكون حدوث تصادمات في التجزئة أمرًا لا مفر منه اعتمادًا على عدد العناصر في المجموعة وما إذا كانت سلسلة البتات التي تُربط بها طويلة بما يكفي أم لا. عندما تكون هناك مجموعة من${\displaystyle n}$الكائنات، إذا${\displaystyle n}$أكبر من${\displaystyle |R|}$، وهو ما ينطبق في هذه الحالة${\displaystyle R}$إذا كانت مجموعة قيم التجزئة، فإن حدوث تصادم في التجزئة أمر مضمون. ^{[ 6 ]}

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

يعتمد تأثير التصادمات على التطبيق. فعند استخدام دوال التجزئة وبصمات الأصابع لتحديد البيانات المتشابهة، مثل تسلسلات الحمض النووي المتماثلة أو ملفات الصوت المتشابهة، تُصمَّم هذه الدوال لزيادة احتمالية التصادم بين البيانات المتباينة ولكن المتشابهة، باستخدام تقنيات مثل التجزئة الحساسة للموقع . ^{[ 9 ]} أما مجاميع التحقق ، فتُصمَّم لتقليل احتمالية التصادم بين المدخلات المتشابهة، دون مراعاة التصادمات بين المدخلات المختلفة تمامًا. ^{[ 10 ]} وتُعرف الحالات التي يحاول فيها المخترقون إنشاء تصادمات التجزئة أو العثور عليها بهجمات التصادم. ^{[ 11 ]}

في الواقع العملي، تستخدم التطبيقات المتعلقة بالأمان خوارزميات التشفير التجزئية، المصممة لتكون طويلة بما يكفي لجعل التطابقات العشوائية غير محتملة، وسريعة بما يكفي لاستخدامها في أي مكان، وآمنة بما يكفي بحيث يصعب للغاية العثور على تصادمات. ^{[ 10 ]}

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

• قائمة دوال التجزئة
• دالة تجزئة أحادية الاتجاه عالمية
• علم التشفير – ممارسة ودراسة تقنيات الاتصال الآمن 
• التجزئة الشاملة – تقنية لاختيار دوال التجزئة 
• دالة تجزئة مثالية – دالة تجزئة بدون أي تصادمات 
• الخريطة الحقنية – دالة تحافظ على التميّز. صفحات تعرض أوصافًا مختصرة لأهداف إعادة التوجيه. 

• مينيز، ألفريد جيه؛ فان أورشوت، بول سي؛ فانستون، سكوت أ. (1997). دليل التشفير التطبيقي . الرياضيات المتقطعة وتطبيقاتها. بوكا راتون، فلوريدا: مطبعة سي آر سي. ISBN 978-0-8493-8523-0.{{cite book}}: CS1 maint: ref duplicates default ( link )
• ساتيسان، أريش؛ بيسمانز، جيلي؛ كلايسن، توماس؛ فليجن، جو؛ مينتنز، نيلي (أبريل 2023). "خوارزميات وهياكل مُحسَّنة لوظائف التجزئة السريعة غير المشفرة في الأجهزة" (ملف PDF) . المعالجات الدقيقة والأنظمة الدقيقة . 98 104782. doi : 10.1016/j.micpro.2023.104782 . ISSN 0141-9331 . 
• ستامب، مارك (8 نوفمبر 2011). "التجزئات غير المشفرة" . أمن المعلومات: المبادئ والتطبيق (  الطبعة الثانية). جون وايلي وأولاده. ISBN 978-1-118-02796-7. OCLC 1039294381 .