أمان وظائف التجزئة المشفرة

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

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

أنواع أمان دوال التجزئة

بشكل عام، يمكن النظر إلى الأمان الأساسي لوظائف التجزئة المشفرة من زوايا مختلفة: مقاومة الصورة المسبقة، ومقاومة الصورة المسبقة الثانية، ومقاومة التصادم، والعشوائية الزائفة.

مقاومة الصورة المسبقة : عند إعطاء دالة تجزئة $h$ ، ينبغي أن يكون من الصعب إيجاد أي رسالة $m$ بحيث يكون $h = hash(m)$ . يرتبط هذا المفهوم بمفهوم الدالة أحادية الاتجاه . الدوال التي تفتقر إلى هذه الخاصية تكون عرضة لهجمات الصورة المسبقة .
مقاومة الصورة السابقة الثانية : $عند$ إعطاء مُدخل $m1 ،$ يصعب إيجاد مُدخل آخر $m2$ $\neq$ $m1$ بحيث يكون $hash($ $m1$ $)$ $=$ $hash($ $m2$ $)$ $.$ تُعرف هذه الخاصية أحيانًا بمقاومة التصادم الضعيفة. الدوال التي تفتقر إلى هذه الخاصية تكون عُرضة لهجمات الصورة السابقة الثانية .
مقاومة التصادم : ينبغي أن يكون $من$ الصعب إيجاد رسالتين مختلفتين m1 و m2 بحيث $يكون تجزئة$ $($ m1 $)$ $مساويًا لتجزئة (m2) .$ يُطلق على هذا الزوج اسم تصادم التجزئة (التشفيري). تُعرف هذه الخاصية أحيانًا بمقاومة التصادم القوية. تتطلب هذه الخاصية قيمة تجزئة لا تقل عن ضعف القيمة المطلوبة لمقاومة الصورة المسبقة؛ وإلا، يمكن اكتشاف التصادمات باستخدام هجوم عيد الميلاد .
العشوائية الزائفة : ينبغي أن يكون من الصعب التمييز بين مولد الأرقام العشوائية الزائفة القائم على دالة التجزئة ومولد الأرقام العشوائية الحقيقية؛ على سبيل المثال، يجتاز اختبارات العشوائية المعتادة .

معنى كلمة صعب

السؤال الأساسي هو معنى كلمة "صعب" . هناك منهجان للإجابة على هذا السؤال. الأول هو المنهج البديهي/العملي: " يعني مصطلح " صعب " أنه يكاد يكون من المستحيل على أي خصم اختراق النظام، ويجب منعه من ذلك طالما أن أمن النظام يُعتبر مهمًا". أما المنهج الثاني فهو نظري ويستند إلى نظرية التعقيد الحسابي : إذا كانت المسألة ( أ) صعبة، فإنه يوجد اختزال أمني رسمي من مسألة تُعتبر على نطاق واسع غير قابلة للحل في وقت متعدد الحدود ، مثل تحليل الأعداد الصحيحة إلى عواملها الأولية أو مسألة اللوغاريتم المنفصل .

مع ذلك، فإن عدم وجود خوارزمية ذات زمن متعدد الحدود لا يضمن بالضرورة أمان النظام. كما أن صعوبة المسألة تعتمد على حجمها. فعلى سبيل المثال، لا تُعتبر تشفيرات المفتاح العام RSA (التي تعتمد على صعوبة تحليل الأعداد الصحيحة إلى عواملها الأولية ) آمنة إلا بمفاتيح لا يقل طولها عن 2048 بت، بينما تتراوح مفاتيح نظام تشفير ElGamal (الذي يعتمد على صعوبة مسألة اللوغاريتم المنفصل ) عادةً بين 256 و512 بت.

حافظة كلمات المرور

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

دوال التجزئة المشفرة

تُبنى معظم دوال التجزئة على أساس مخصص، حيث تُخلط بتات الرسالة بشكل متجانس لإنتاج التجزئة. وتُستخدم عمليات بتية متنوعة (مثل التدوير)، وعمليات الجمع المعياري ، ودوال الضغط في وضع تكراري لضمان تعقيد عالٍ وعشوائية زائفة للمخرجات. وبهذه الطريقة، يصعب إثبات الأمان، وعادةً لا يُجرى الإثبات. قبل بضع سنوات فقط ، تبيّن أن إحدى دوال التجزئة الأكثر شيوعًا، SHA-1 ، أقل أمانًا مما يوحي به طولها: إذ وُجدت تصادمات في 2 ^{^}⁵¹ اختبارًا فقط، بدلًا من العدد الإجمالي البالغ ²^{^}⁸⁰ .

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

دوال تجزئة آمنة قابلة للتحقق

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

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

هذا يعني أنه إذا كان إيجاد التصادمات ممكنًا في وقت متعدد الحدود باستخدام الخوارزمية A ، فإنه يمكن إيجاد واستخدام خوارزمية R (خوارزمية الاختزال) متعددة الحدود التي تستخدم الخوارزمية A لحل المسألة P ، والتي يُفترض على نطاق واسع أنها غير قابلة للحل في وقت متعدد الحدود. وهذا تناقض. وهذا يعني أن إيجاد التصادمات لا يمكن أن يكون أسهل من حل المسألة P.

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

مشاكل صعبة

تتضمن أمثلة المشكلات التي يُفترض أنها غير قابلة للحل في وقت متعدد الحدود ما يلي:

سلبيات النهج القابل للإثبات

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

يُعدّ SWIFFT مثالًا على دالة تجزئة تتجاوز هذه المشكلات الأمنية. ويمكن إثبات أنه لأي خوارزمية قادرة على اختراق SWIFFT باحتمالية $p$ خلال زمن مُقدّر $t$ ، يُمكن إيجاد خوارزمية أخرى تُحلّ أسوأ سيناريو لمسألة رياضية معقدة خلال زمن $t'$ يعتمد على $t$ و $p$ . ^{[ 3 ]}

مثال على دالة تجزئة (غير عملية) يمكن إثبات أمانها

لنفترض أن $hash(m) = x m mod n$ ، حيث $n$ عدد مركب يصعب تحليله إلى عوامله الأولية، و $x$ قيمة أساسية محددة مسبقًا. يكشف التصادم $x m \equiv x m (mod n)$ عن مضاعف $m 1 - m 2$ من الرتبة الضربية لـ $x$ modulo $n$ . يمكن استخدام هذه المعلومة لتحليل $n$ إلى عوامله الأولية في وقت متعدد الحدود، بافتراض خصائص معينة لـ $x$ .

لكن الخوارزمية غير فعالة إلى حد كبير لأنها تتطلب في المتوسط 1.5 عملية ضرب modulo $n$ لكل بت من الرسالة.

وظائف تجزئة أكثر عملية وآمنة بشكل مثبت

VSH —Very Smooth Hash— دالة تجزئة مقاومة للتصادم آمنة بشكل مثبت تفترض صعوبة إيجاد الجذور التربيعية المعيارية غير التافهة modulo العدد المركب $n$ (ثبت أن هذا صعب مثل تحليل $n$ ).
محاش
ECOH - دالة تجزئة تعتمد على المنحنيات الإهليلجية فقط - تستند إلى مفهوم المنحنيات الإهليلجية ، ومسألة مجموع المجموعات الجزئية ، ومجموع كثيرات الحدود. وقد استند برهان أمان مقاومة التصادم إلى افتراضات مخففة، وفي النهاية تم اكتشاف هجوم سابق للصورة ثانٍ.
FSB - دالة التجزئة السريعة القائمة على المتلازمة - يمكن إثبات أن كسر FSB لا يقل صعوبة عن حل فك تشفير المتلازمة العادية ، وهو أمر معروف بأنه NP-كامل.
SWIFFT — يعتمد SWIFFT على تحويل فورييه السريع وهو مقاوم للتصادم بشكل مثبت، في ظل افتراض معتدل نسبيًا حول صعوبة أسوأ الحالات في إيجاد متجهات قصيرة في الشبكات الدورية / المثالية .
دالة التجزئة Chaum, van Heijst, Pfitzmann — دالة ضغط حيث يكون إيجاد التصادمات صعبًا مثل حل مشكلة اللوغاريتم المنفصل في مجموعة محدودة $F 2 p +1$ .
دوال التجزئة القائمة على مشكلة الحقيبة - عائلة من دوال التجزئة القائمة على مشكلة الحقيبة .
دالة التجزئة زيمور-تيليش هي عائلة من دوال التجزئة تعتمد على العمليات الحسابية لمجموعة المصفوفات SL² . يُعدّ إيجاد التصادمات صعبًا على الأقل مثل إيجاد تحليل لبعض عناصر هذه المجموعة. من المفترض أن يكون هذا صعبًا، على الأقل من _فئة PSPACE-complete . بالنسبة لهذه التجزئة، تم اكتشاف هجوم في النهاية بتعقيد زمني قريب من $2ⁿ$ $/$ $2$ . وقد تفوّق هذا بشكل كبير على حدّ عيد الميلاد وتعقيد الصورة الأولية المثالي، واللذان يبلغان $2³ⁿ$ $/$ $2$ $و2³ⁿ$ لدالة التجزئة زيمور- $تيليش$ . بما أن الهجمات تتضمن بحثًا عن عيد الميلاد في مجموعة مُصغّرة بحجم $2ⁿ$ $، فإنها في الواقع لا$ $تُدمّر$ فكرة الأمان القابل للإثبات أو تُبطل المخطط، بل تُشير إلى أن المعلمات الأولية كانت صغيرة جدًا $.$ ^[⁴^]
دوال التجزئة من بروتوكولات سيجما — توجد طريقة عامة لإنشاء تجزئة آمنة قابلة للإثبات، تحديدًا من أي بروتوكول سيجما (مناسب) . ويمكن الحصول على نسخة أسرع من VSH (تسمى VSH*) بهذه الطريقة.

مراجع

↑ غودين، دان (10 ديسمبر 2012). "مجموعة حاسوبية تضم 25 وحدة معالجة رسومية تكسر جميع كلمات مرور ويندوز القياسية في أقل من 6 ساعات" . آرس تكنيكا . تاريخ الاسترجاع: 23 نوفمبر 2020 .
↑ "تصنيف وتوليد متجهات التشويش لهجمات التصادم ضد SHA-1" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 15-01-2009.
↑ ليوباشيفسكي، فاديم؛ ميتشيانسيو، دانييلي؛ بيكرت، كريس؛ روزين، ألون. "SWIFFT: اقتراح متواضع لتجزئة FFT" (ملف PDF) . تم الاطلاع عليه بتاريخ 16 يناير 2026 .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
↑ Petit, C.; Quisquater, J.-J.; Tillich, J.-P., “Hard and easy Components of Collision Search in the Zémor-Tillich hash function:new Attacks and Reduced Variants with Equivalent Security” (PDF) ,{{citation}}: مفقود أو فارغ |title=( مساعدة )

[1] غودين، دان (10 ديسمبر 2012). "مجموعة حاسوبية تضم 25 وحدة معالجة رسومية تكسر جميع كلمات مرور ويندوز القياسية في أقل من 6 ساعات" . آرس تكنيكا . تاريخ الاسترجاع: 23 نوفمبر 2020 .

[2] "تصنيف وتوليد متجهات التشويش لهجمات التصادم ضد SHA-1" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 15-01-2009.

[SWIFFT_Paper-3] ليوباشيفسكي، فاديم؛ ميتشيانسيو، دانييلي؛ بيكرت، كريس؛ روزين، ألون. "SWIFFT: اقتراح متواضع لتجزئة FFT" (ملف PDF) . تم الاطلاع عليه بتاريخ 16 يناير 2026 .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=

[4] Petit, C.; Quisquater, J.-J.; Tillich, J.-P., “Hard and easy Components of Collision Search in the Zémor-Tillich hash function:new Attacks and Reduced Variants with Equivalent Security” (PDF) ,{{citation}}: مفقود أو فارغ |title=( مساعدة )

[ 1 ]

^

[ 3 ]

[

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗