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

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

من الناحية الفنية: ^{[ 4 ]}

• احتمالية شيء معين${\displaystyle n}$نتيجة الإخراج ذات البتات ( قيمة التجزئة ) لسلسلة إدخال عشوائية ("الرسالة") هي${\displaystyle 2^{-n}}$(كما هو الحال بالنسبة لأي تجزئة جيدة)، لذلك يمكن استخدام قيمة التجزئة كممثل للرسالة؛
• يُعدّ إيجاد سلسلة إدخال تُطابق قيمة تجزئة مُعطاة ( صورة أصلية ) أمرًا غير عملي، بافتراض أن جميع سلاسل الإدخال متساوية الاحتمالية. تُقاس مقاومة هذا البحث بقوة الأمان : تجزئة تشفيرية ذات${\displaystyle n}$من المتوقع أن تتمتع بتات قيمة التجزئة بقوة مقاومة الصورة المسبقة بـ${\displaystyle n}$بتات، إلا إذا كانت مساحة قيم الإدخال الممكنة أصغر بكثير من${\displaystyle 2^{n}}$(يمكن العثور على مثال عملي في §  الهجمات على كلمات المرور المجزأة )؛
• تشير قوة مقاومة الصورة المسبقة الثانية ، مع نفس التوقعات، إلى مشكلة مماثلة تتمثل في إيجاد رسالة ثانية تطابق قيمة التجزئة المعطاة عندما تكون إحدى الرسائل معروفة بالفعل؛
• يُعدّ إيجاد أي زوج من الرسائل المختلفة التي تُنتج نفس قيمة التجزئة ( تصادم ) أمرًا غير ممكن أيضًا: من المتوقع أن تتمتع التجزئة المشفرة بقوة مقاومة للتصادم تبلغ${\displaystyle n/2}$بتات (أقل بسبب مفارقة عيد الميلاد ).

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

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

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

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

مقاومة ما قبل الصورة

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

مقاومة ما قبل الصورة الثانية

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

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

من الصعب إيجاد رسالتين مختلفتين m1 _و m2 بحيث يكون _تجزئة ( m1 ) = تجزئة ( m2 ) . يُطلق على هذا الزوج اسم تصادم التجزئة التشفيري . تُعرف هذه الخاصية أحيانًا باسم مقاومة التصادم القوية . تتطلب هذه الخاصية قيمة تجزئة لا تقل _عن ضعف القيمة المطلوبة لمقاومة الصورة المسبقة؛ وإلا، يمكن اكتشاف التصادمات من خلال هجوم عيد ^{الميلاد} . ^[ ₈ ^]

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

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

قد تمتلك الدالة التي تستوفي هذه المعايير خصائص غير مرغوب فيها. حاليًا، تُعدّ دوال التجزئة التشفيرية الشائعة عرضةً لهجمات تمديد الطول : فبمعرفة hash( m ) و len( m ) ولكن ليس m ، يمكن للمهاجم ، باختيار قيمة مناسبة لـ m ′، حساب hash( m ∥ m ′ ) ، حيث ∥ يرمز إلى عملية الربط . ^{[ 10 ]} يمكن استغلال هذه الخاصية لاختراق أنظمة المصادقة البسيطة القائمة على دوال التجزئة. ويتغلب بناء HMAC على هذه المشاكل.

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

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

An illustration of the potential use of a cryptographic hash is as follows: Alice poses a tough math problem to Bob and claims that she has solved it. Bob would like to try it himself, but would yet like to be sure that Alice is not bluffing. Therefore, Alice writes down her solution, computes its hash, and tells Bob the hash value (whilst keeping the solution secret). Then, when Bob comes up with the solution himself a few days later, Alice can prove that she had the solution earlier by revealing it and having Bob hash it and then check that it matches the hash value given to him before. (This is an example of a simple commitment scheme; in actual practice, Alice and Bob will often be computer programs, and the secret would be something less easily spoofed than a claimed puzzle solution.)

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

تُشبه هذه الطرق أنماط تشفير الكتل المستخدمة عادةً في التشفير. العديد من دوال التجزئة المعروفة، مثل MD4 و MD5 و SHA-1 و SHA-2 ، مبنية على مكونات شبيهة بتشفير الكتل مصممة لهذا الغرض، مع آلية تغذية راجعة لضمان عدم إمكانية عكس الدالة الناتجة. تضمنت القائمة النهائية لـ SHA-3 دوالًا بمكونات شبيهة بتشفير الكتل (مثل Skein و BLAKE )، إلا أن الدالة المختارة في النهاية، Keccak ، بُنيت على أساس إسفنجة تشفيرية .

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

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

تُبنى رموز مصادقة الرسائل (MACs) (وتُسمى أيضًا دوال التجزئة المفتاحية) غالبًا من دوال التجزئة. HMAC هو أحد هذه الرموز.

كما يمكن استخدام تشفيرات الكتل لبناء دوال التجزئة، يمكن استخدام دوال التجزئة لبناء تشفيرات الكتل. يمكن إثبات أمان بنى لوبي-راكوف التي تستخدم دوال التجزئة إذا كانت دالة التجزئة الأساسية آمنة. كذلك، تُبنى العديد من دوال التجزئة (بما في ذلك SHA-1 و SHA-2 ) باستخدام تشفير كتل مُخصص في بنية ديفيز-ماير أو غيرها. يمكن أيضًا استخدام هذا التشفير في وضع تشغيل تقليدي، دون ضمانات الأمان نفسها؛ على سبيل المثال، SHACAL و BEAR و LION .

يمكن بناء مولدات الأرقام شبه العشوائية (PRNGs) باستخدام دوال التجزئة. ويتم ذلك عن طريق دمج بذرة عشوائية (سرية) مع عداد ثم تجزئتها.

تُخرج بعض دوال التجزئة، مثل Skein و Keccak و RadioGatún ، سلسلة بيانات طويلة كيفما كانت، ويمكن استخدامها كخوارزمية تشفير متدفقة . كما يمكن بناء خوارزميات التشفير المتدفقة من دوال تجزئة ذات طول ثابت. غالبًا ما يتم ذلك عن طريق بناء مولد أرقام شبه عشوائية آمن تشفيريًا، ثم استخدام سلسلة البايتات العشوائية الناتجة عنه كسلسلة مفاتيح . SEAL هي خوارزمية تشفير متدفقة تستخدم SHA-1 لإنشاء جداول داخلية، تُستخدم بدورها في مولد سلسلة مفاتيح لا يرتبط ارتباطًا وثيقًا بخوارزمية التجزئة. لا يُضمن أن تكون SEAL بنفس قوة (أو ضعف) SHA-1. وبالمثل، يعتمد توسيع مفتاح خوارزميتي التشفير المتدفقتين HC-128 وHC-256 بشكل كبير على دالة التجزئة SHA-256 .

يُوفر دمج مخرجات دوال التجزئة المتعددة مقاومةً للتصادم تُضاهي أقوى الخوارزميات المُستخدمة في النتيجة المُدمجة. على سبيل المثال، استخدمت الإصدارات القديمة من بروتوكول أمان طبقة النقل (TLS) وبروتوكول طبقة المقابس الآمنة (SSL) مجموعات MD5 و SHA-1 المُدمجة . ^{[ 20 ] [ 21 ]} وهذا يضمن أن طريقة البحث عن التصادمات في إحدى دوال التجزئة لا تُؤدي إلى اختراق البيانات المحمية بواسطة كلتا الدالتين.

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

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

توجد قائمة طويلة من دوال التشفير التجزئية، ولكن تبين أن العديد منها عرضة للاختراق، لذا يُنصح بعدم استخدامها. على سبيل المثال، اختار المعهد الوطني للمعايير والتكنولوجيا (NIST) 51 دالة تجزئة ^{[ 25 ]} كمرشحة للجولة الأولى من مسابقة SHA-3، حيث اعتُبرت 10 منها معيبة، بينما أظهرت 16 دالة أخرى نقاط ضعف كبيرة، وبالتالي لم تتأهل للجولة التالية. يمكنكم الاطلاع على المزيد من المعلومات في المقال الرئيسي حول مسابقات دوال التجزئة التي يُنظمها المعهد الوطني للمعايير والتكنولوجيا .

حتى لو لم يتم اختراق دالة تجزئة مطلقًا، فإن هجومًا ناجحًا على نسخة مُضعفة منها قد يُزعزع ثقة الخبراء. على سبيل المثال، في أغسطس 2004، تم اكتشاف تصادمات في العديد من دوال التجزئة الشائعة آنذاك، بما في ذلك MD5. ^{[ 26 ]} وقد أثارت نقاط الضعف هذه تساؤلات حول أمان الخوارزميات الأقوى المُشتقة من دوال التجزئة الضعيفة، ولا سيما SHA-1 (نسخة مُعززة من SHA-0)، وRIPEMD-128، وRIPEMD-160 (كلاهما نسختان مُعززتان من RIPEMD). ^{[ 27 ]}

في 12 أغسطس/آب 2004، أعلن كلٌّ من جوكس وكاريبو وليمويل وجالبي عن اكتشاف تصادم لخوارزمية SHA-0 الكاملة. ^{[ 22 ]} وقد حقق جوكس وزملاؤه ذلك باستخدام تعميم لهجوم شابود وجوكس. ووجدوا أن التصادم ذو تعقيد 2^ ^51، واستغرق حوالي 80,000 ساعة معالجة على حاسوب فائق مزود بـ 256 معالجًا من نوع إيتانيوم 2 ، أي ما يعادل 13 يومًا من الاستخدام المتواصل للحاسوب.

In February 2005, an attack on SHA-1 was reported that would find collision in about 2⁶⁹ hashing operations, rather than the 2⁸⁰ expected for a 160-bit hash function. In August 2005, another attack on SHA-1 was reported that would find collisions in 2⁶³ operations. Other theoretical weaknesses of SHA-1 have been known,^[28][29] and in February 2017 Google announced a collision in SHA-1.^[30] Security researchers recommend that new applications can avoid these problems by using later members of the SHA family, such as SHA-2, or using techniques such as randomized hashing^[31] that do not require collision resistance.

A successful, practical attack broke MD5 (used within certificates for Transport Layer Security) in 2008.^[32]

Many cryptographic hashes are based on the Merkle–Damgård construction. All cryptographic hashes that directly use the full output of a Merkle–Damgård construction are vulnerable to length extension attacks. This makes the MD5, SHA-1, RIPEMD-160, Whirlpool, and the SHA-256 / SHA-512 hash algorithms all vulnerable to this specific attack. SHA-3, BLAKE2, BLAKE3, and the truncated SHA-2 variants are not vulnerable to this type of attack.

Rather than store plain user passwords, controlled-access systems frequently store the hash of each user's password in a file or database. When someone requests access, the password they submit is hashed and compared with the stored value. If the database is stolen (an all-too-frequent occurrence^[33]), the thief will only have the hash values, not the passwords.

Passwords may still be retrieved by an attacker from the hashes, because most people choose passwords in predictable ways. Lists of common passwords are widely circulated and many passwords are short enough that even all possible combinations may be tested if calculation of the hash does not take too much time.^[34]

The use of cryptographic salt prevents some attacks, such as building files of precomputing hash values, e.g. rainbow tables. But searches on the order of 100 billion tests per second are possible with high-end graphics processors, making direct attacks possible even with salt.^[35][36] The United States National Institute of Standards and Technology recommends storing passwords using special hashes called key derivation functions (KDFs) that have been created to slow brute force searches.^[13]:5.1.1.2 Slow hashes include pbkdf2, bcrypt, scrypt, argon2, Balloon and some recent modes of Unix crypt. For KDFs that perform multiple hashes to slow execution, NIST recommends an iteration count of 10,000 or more.^[13]:5.1.1.2

• بار، كريستوف؛ بيلزل، يان (2009). "11: دوال التجزئة" . فهم التشفير، كتاب مدرسي للطلاب والممارسين . سبرينغر .{{cite book}}: CS1 maint: deprecated archiveal service ( link ) (companion web site contains online cryptography course that covers hash functions)
• "موقع وظائف التجزئة ECRYPT" .
• بولداس، أ. (2011). "سلسلة من المحاضرات المصغرة حول وظائف التجزئة المشفرة" .{{cite web}}: CS1 maint: deprecated archiveal service ( link )
• تطبيق مفتوح المصدر قائم على لغة بايثون مع واجهة مستخدم رسومية يستخدم للتحقق من التنزيلات.