مقاومة التصادم

في علم التشفير ، تُعدّ مقاومة التصادم خاصيةً من خصائص دوال التجزئة التشفيرية (CHFs): تكون دالة التجزئة H مقاومةً للتصادم إذا كان من الصعب إيجاد مدخلين يُنتجان نفس المخرج؛ أي مدخلين a و b حيث a ≠ b ولكن H ( a ) = H ( b ). ^{[ 1 ] : 136} ويعني مبدأ التوزيع أن أي دالة تجزئة ذات عدد مدخلات أكبر من عدد مخرجاتها ستشهد بالضرورة مثل هذه التصادمات؛ ^{[ 1 ] : 136} وكلما كان من الصعب إيجادها، زادت أمان دالة التجزئة من الناحية التشفيرية.

تضع " مفارقة عيد الميلاد " حدًا أقصى لمقاومة التصادم: إذا أنتجت دالة التجزئة N بت من المخرجات، فإن المهاجم الذي يحسب فقط 2^ ^{N / 2^N} (أو${\displaystyle \scriptstyle {\sqrt {2^{N}}}}$من المرجح أن تؤدي عمليات التجزئة على مدخلات عشوائية إلى إيجاد مخرجين متطابقين. إذا كانت هناك طريقة أسهل للقيام بذلك من هجوم القوة الغاشمة ، فعادةً ما يُعتبر ذلك عيبًا في دالة التجزئة. ^{[ 2 ]}

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

تُعتبر عائلة الدوال { h _k  : {0, 1} ^{m ( k )} → {0, 1} ^{l ( k )} } المُولَّدة بواسطة خوارزمية G عائلةً من دوال التجزئة المقاومة للتصادم، إذا كان | m ( k )| > | l ( k )| لأي قيمة لـ k ، أي أن h _k تضغط سلسلة الإدخال، ويمكن حساب كل h _k في وقت متعدد الحدود بمعلومية k ، ولكن لأي خوارزمية احتمالية متعددة الحدود A ، لدينا

Pr [ k ← G (1 ⁿ ), ( x ₁ , x ₂ ) ← A ( k , 1 ⁿ ) st x ₁ ≠ x ₂ but h _k ( x ₁ ) = h _k ( x ₂ )] < negl( n ),

حيث تشير negl(·) إلى دالة مهملة ، و n هو معامل الأمان . ^{[ 5 ]}

يوجد نوعان مختلفان من مقاومة التصادم.

تتمتع دالة التجزئة بمقاومة ضعيفة للتصادم عندما، عند إعطاء دالة التجزئة H وقيمة x، لا يمكن إيجاد قيمة x' أخرى بحيث يكون H(x)=H(x'). بعبارة أخرى، عند إعطاء قيمة x، لا يمكن إيجاد قيمة x' أخرى بحيث تُحدث دالة التجزئة تصادمًا.

تتمتع دالة التجزئة بمقاومة عالية للتصادم عندما لا يمكن، عند إعطاء دالة التجزئة H، إيجاد قيمتين عشوائيتين x و x' بحيث يكون H(x)=H(x'). بعبارة أخرى، لا يمكن إيجاد قيمتين x بحيث تؤدي دالة التجزئة إلى حدوث تصادم.

تُعد مقاومة التصادم أمراً مرغوباً فيه لعدة أسباب.

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

أثناء تقييم خوارزميات التشفير الآمنة (CHFs)، يتمثل أحد الأساليب في دراسة الهجمات على خوارزميات مشابهة مع تعديلات طفيفة. عادةً، يُسمح باختيار قيمة تهيئة التجزئة (IV في بنية Merkle-Damgård ) بحرية. إذا لوحظت نفس قيمة التجزئة لمجموعتين مختلفتين من (قيمة الإدخال، IV) ، تُسمى النتيجة تصادمًا زائفًا . لا تؤثر التصادمات الزائفة بشكل مباشر على أمان الخوارزمية - حيث أن قيمة IV ثابتة في تصميم التجزئة العملي - ولكنها تُعامل على أنها مشبوهة عند النظر في معايير التشفير الجديدة . ^{[ 6 ]}

• هجوم عيد الميلاد
• سهولة حل الألغاز
• هجوم تصادمي
• هجوم ما قبل الصورة
• مسابقة دالة التجزئة التابعة للمعهد الوطني للمعايير والتكنولوجيا
• دالة تجزئة تشفيرية آمنة قابلة للإثبات
• اكتشاف الأخطاء وتصحيحها

• مينيز، ألفريد جيه؛ فان أورشوت، بول سي؛ فانستون، سكوت أ. (1997). دليل التشفير التطبيقي . الرياضيات المتقطعة وتطبيقاتها. بوكا راتون، فلوريدا: مطبعة سي آر سي. ISBN 978-0-8493-8523-0.{{cite book}}: CS1 maint: ref duplicates default ( link )