دوال التجزئة
دوالّ التجزئة
الوصف
دوالّ التجزئة (hash functions) هي دوالّ تأخذ دخلًا بطول غير محدّد وتُنتج قيمة بطول ثابت، تُسمّى أيضًا «التجزئة» (digest).
وللدوالّ البسيطة للتجزئة تطبيقات كثيرة. فجداول التجزئة (hash tables)، وهي بنية بيانات شائعة، تعتمد عليها. وهذه الدوالّ البسيطة للتجزئة لا تضمن في الحقيقة إلّا أمرًا واحدًا: أنّ دخلَين متطابقَين يُنتجان خرجًا متطابقًا. ومن المهمّ ألّا يكون هناك ضمان بأنّ خرجَين متطابقَين يعني أنّ الدخلَين كانا متطابقَين. فذلك مستحيل: فهناك عدد محدود من التجزئات لأنّها ذات حجم ثابت، في حين أنّ هناك عددًا لا نهائيًّا من الدخاخل. كما أنّ دالة التجزئة الجيّدة سريعة الحساب أيضًا.
وبما أنّ هذا كتاب عن التشفير (cryptography)، فإنّ اهتمامنا ينصبّ على نحو خاصّ على دوالّ التجزئة التشفيرية (cryptographic). ويمكن استعمال دوالّ التجزئة التشفيرية لبناء خوارزميات آمنة لمصادقة الرسائل (المتماثلة)، وخوارزميات توقيع (لامتماثلة)، وأدوات أخرى متنوّعة مثل مولّدات الأعداد العشوائية. وسنرى بعض هذه الأنظمة بالتفصيل في فصول قادمة.
ولدوالّ التجزئة التشفيرية خصائص أقوى بكثير من دوالّ التجزئة الاعتيادية، مثل تلك التي تجدها في جدول تجزئة. بالنسبة إلى دالة التجزئة التشفيرية، نريد أن يكون من المستحيل عمليًّا ما يلي:
#. تعديل رسالة من دون تغيير التجزئة. #. توليد رسالة لها تجزئة معطاة. #. إيجاد رسالتين مختلفتين لهما التجزئة نفسها.
تنصّ الخاصية الأولى على أنّ دوالّ التجزئة التشفيرية تُظهر ما يُسمّى «أثر الانهيار الجليدي» (avalanche effect). ف تغيير بتّ واحد فقط في الدخل يُحدث انهيارًا من التغييرات في التجزئة كلّها: إذ لكلّ بتّ في التجزئة احتمال تقريبي قدره 50% بأن يُقلَب. وهذا لا يعني أنّ كلّ تغيير سيُحدث قلبًا لنحو نصف البتّات، لكنّ دالة التجزئة التشفيرية تضمن أنّ احتمالات حدوث ذلك كبيرة إلى حدٍّ متطرّف. والأهمّ أنّه من المستحيل عمليًّا إيجاد تصادمات (collisions) من هذا النوع أو شبه تصادمات.
أمّا الخاصية الثانية، التي تنصّ على أنّ من الصعب إيجاد رسالة m لها قيمة تجزئة
معطاة h، فتُسمّى مقاومة الصورة الأوّلية (pre-image resistance). وتجعل هذه
الخاصية دالة التجزئة دالةً أحادية الاتجاه: فمن السهل جدًا حساب تجزئة رسالة
معطاة، ومن الصعب جدًا حساب رسالة لتجزئة معطاة.
وتتعلّق الخاصية الثالثة بإيجاد رسائل لها قيمة التجزئة نفسها، وتأتي في نوعين. في
النوع الأوّل، هناك رسالة معطاة m، وينبغي أن يكون من الصعب إيجاد رسالة أخرى
m^{\prime} لها قيمة التجزئة نفسها: وتُسمَّى مقاومة الصورة الأوّلية الثانية
(second pre-image resistance). أمّا النوع الثاني فهو أقوى، إذ ينصّ على أنّه ينبغي أن
يكون من الصعب إيجاد أيّ رسالتين m, m^{\prime} لهما قيمة التجزئة نفسها. وتُسمَّى
هذه مقاومة التصادم (collision resistance). ولأنّ مقاومة التصادم شكل أقوى من
مقاومة الصورة الأوّلية الثانية، فإنّهما تُسمّيان أحيانًا مقاومة التصادم الضعيفة
ومقاومة التصادم القوية على التوالي.
غالبًا ما تُسمَّى هذه المفاهيم من منظور الهجوم لا من منظور المقاومة له. فمثلًا، ستسمع كثيرًا عن هجوم تصادم (collision attack)، وهو هجوم يحاول توليد تصادم تجزئة، أو عن هجوم الصورة الأوّلية الثانية، الذي يحاول إيجاد صورة أوّلية ثانية تُجزّئ إلى القيمة نفسها التي تُجزّئ إليها صورة أوّلية معطاة، وهكذا.
TODO: ربما ضع رابطًا إلى http://www.cs.ucdavis.edu/~rogaway/papers/relates.pdf لمزيد من القراءة
MD5
MD5 هي دالة تجزئة صمّمها Ronald Rivest سنة 1991 كامتداد لـ MD4. وتُنتج هذه الدالة
تجزئات بطول 128 بتًّا. وعلى مدى السنين، كشف مجتمع التشفير مرارًا نقاط ضعف MD5. ففي
سنة 1993، نشر Bert den Boer وAntoon Bosselaers بحثًا يبرهن «شبه تصادمات»
(pseudo-collisions) لدالة الضغط في MD5. denboer:md5 ووسّع Dobbertin هذا البحث
وتمكّن من إنتاج تصادمات لدالة الضغط. وفي سنة 2004، بالاستناد إلى عمل Dobbertin،
أظهر Xiaoyun Wang وDengguo Feng وXuejia Lai وHongbo Yu أنّ MD5 معرَّضة لهجمات
تصادم حقيقية. cryptoeprint:2005:067 وجاءت الضربة القاضية عندما تمكّن Xiaoyun
Wang وآخرون من توليد شهادات X.509 متصادمة، ثمّ قدّموا هجوم تمييز على HMAC-MD5.
cryptoeprint:2005:067
eurocrypt-2009-23793
وفي الوقت الحالي، لا يُنصح باستعمال MD5 لتوليد التوقيعات الرقمية، لكنّ من المهمّ الإشارة إلى أنّ HMAC-MD5 لا يزال شكلًا آمنًا من مصادقة الرسائل؛ غير أنّه على الأرجح لا ينبغي تنفيذه في أنظمة تشفير جديدة.
خمسة خطوات لازمة لحساب تجزئة رسالة MD5:
#. أضف الحشو. أوّلًا، تُلحق بالرسالة بتّة واحدة، ثمّ تُلحق أصفار إلى نهايتها حتى
يبلغ الطول 448 \pmod {512}.
#. املأ البتّات الـ64 المتبقّية بطول الرسالة الأصلية ناتج القسمة على 2^{64}، بحيث
تصير الرسالة كاملة مضاعفات لـ512 بتًّا.
#. هيّئ الحالة على شكل أربع كلمات بطول 32 بتًّا: A وB وC وD. وتُهيَّأ هذه بقيم
ثابتة معرَّفة في المواصفة.
#. عالِج الدخل في كتل بطول 512 بتًّا؛ ولكلّ كتلة، نفّذ أربع «جولات» (rounds) تتكوّن
كلّ منها من 16 عملية متماثلة. وتتكوّن العمليات جميعًا من إزاحات وجمع نمطيّ ودالة
لاخطية معيّنة، مختلفة في كلّ جولة.
وعند الانتهاء، تكون A \| B \| C \| D هي خرج دالة التجزئة. وهذا النمط من الحشو،
مع الدمج في النهاية، هو ما يجعل MD5 معرَّضة لهجمات تمديد الطول (length extension
attacks)؛ وسنتحدّث عن ذلك لاحقًا.
وفي بايثون، يمكن استعمال وحدة hashlib لإنشاء تجزئة MD5 على النحو التالي:
import hashlib
hashlib.md5(b"crypto101").hexdigest()
SHA-1
SHA-1 هي دالة تجزئة أخرى من عائلة MD4 صمّمتها NSA، وتُنتج تجزئة بطول 160 بتًّا.
ومثل MD5 تمامًا، لم تعد SHA-1 تُعدّ آمنة للتوقيعات الرقمية. وقد بدأت كثير من شركات
البرمجيات والمتصفّحات، ومنها Google Chrome، في إنهاء دعم خوارزمية التوقيع الخاصّة
بـ SHA-1. وفي 23 شباط (فبراير) 2017، تمكّن باحثون من CWI في أمستردام ومن Google من
إنتاج تصادم على دالة SHA-1 الكاملة. Shattered وقد نُشرت في الماضي طرائق لإحداث
تصادمات على نسخ مخفَّضة من SHA-1، منها واحدة من Xiaoyun Wang. وأظهر «The
SHAppening» تصادمات بدء حرّة (freestart collisions) لـ SHA-1. ويتيح تصادم البدء
الحرّ للمفكّر اختيار القيمة الابتدائية المعروفة باسم متجه التهيئة (initialization
vector) في بداية دالة الضغط. cryptoeprint:2015:967
ويمكن مرّة أخرى استعمال وحدة hashlib في بايثون لتوليد تجزئة SHA-1:
import hashlib
hashlib.sha1(b"crypto101").hexdigest()
SHA-2
SHA-2 هي عائلة من دوالّ التجزئة تشمل SHA-224 وSHA-256 وSHA-384 وSHA-512 وSHA-512/224 وSHA-512/256، وأحجام تجزئاتها 224 و256 و384 و512 و224 و256 على التوالي. وتقوم هذه الدوالّ على بناء Merkle–Damgård، ويمكن استعمالها للتوقيعات الرقمية ومصادقة الرسائل ومولّدات الأعداد العشوائية. وSHA-2 لا تؤدّي أداءً أفضل من SHA-1 فحسب، بل تقدّم أمنًا أفضل أيضًا بفضل زيادة مقاومتها للتصادم.
صُمّمت SHA-224 وSHA-256 لسجلّات المعالجات ذات 32 بتًّا، بينما صُمّمت SHA-384 وSHA-512 لسجلّات ذات 64 بتًّا. لذا تعمل التنويعات ذات السجلّات الـ32 بتًّا أسرع على معالج 32 بتًّا، وتؤدّي التنويعات ذات السجلّات الـ64 بتًّا أداءً أفضل على معالج 64 بتًّا. وSHA-512/224 وSHA-512/256 هما نسختان مختصرتان من SHA-512 تسمحان باستعمال كلمات بطول 64 بتًّا مع حجم خرج يعادل نظيرتي السجلّات الـ32 بتًّا (أي تجزئتان بطول 224 و256، وأداء أفضل على معالج 64 بتًّا).
وفيما يلي جدول يعطي صورة عامة جيّدة عن عائلة SHA-2:
============= =============== ========== ========= ===========
الدالة حجم الرسالة حجم الكتلة الكلمة حجم التجزئة
============= =============== ========== ========= ===========
SHA-224 < 2\ 64 512 32 224
SHA-256 < 2\ 64 512 32 256
SHA-384 < 2\ 128 1024 64 384
SHA-512 < 2\ 128 1024 64 512
SHA-512/224 < 2\ 128 1024 64 224
SHA-512/256 < 2\ 128 1024 64 256
============= =============== ========== ========= ===========
ويمكنك تجزئة سلسلة فارغة بوحدة hashlib ومقارنة أحجام التجزئات على النحو التالي:
>>> import hashlib
>>> len(hashlib.sha224(b"").hexdigest())
56
>>> len(hashlib.sha256(b"").hexdigest())
64
>>> len(hashlib.sha384(b"").hexdigest())
96
>>> len(hashlib.sha512(b"").hexdigest())
128
الهجمات على SHA-2
لقد أُثبتت عدّة هجمات (شبه) تصادم وصور أوّلية باستخدام SHA-256 وSHA-512 بعدد جولات
أقلّ. ومن المهمّ الإشارة إلى أنّه بحذف عدد معيّن من الجولات لا يمكن مهاجمة
الخوارزمية كاملة. فمثلًا، تمكّن Somitra Kumar Sanadhya وPalash Sarkar من إحداث
تصادمات مع SHA-256 باستعمال 24 جولة من أصل 64 (بإزالة آخر 40 جولة).
eprint-2008-18172
Keccak وSHA-3
Keccak هي عائلة من دوالّ الإسفنجة (sponge functions) صمّمها Guido Bertoni وJoan Daemen وGilles Van Assche وMichaël Peeters، وقد فازت بمسابقة خوارزمية التجزئة الآمنة التي نظّمتها NIST سنة 2012. ومنذ ذلك الحين جرى توحيد Keccak على شكل دوالّ التجزئة SHA3-224 وSHA3-256 وSHA3-384 وSHA3-512.
وفيما توحي SHA-3 بأنّها قد تأتي من العائلة نفسها التي تنتمي إليها SHA-2، فإنّ
التصميمين مختلفان إلى حدٍّ كبير. فSHA-3 فعّالة جدًّا في العتاد SHA-3-hardware،
لكنّها بطيئة نسبيًّا في البرمجيات مقارنةً بـ SHA-2. SHA-3-finalists وستجد في وقت
لاحق من الكتاب الجوانب الأمنية لـ SHA-3، مثل منع هجمات تمديد الطول.
وأُدخلت دوالّ التجزئة SHA-3 في الإصدار 3.6 من بايثون، ويمكن استعمالها على النحو التالي:
import hashlib
hashlib.sha3_224(b"crypto101").hexdigest()
hashlib.sha3_256(b"crypto101").hexdigest()
hashlib.sha3_384(b"crypto101").hexdigest()
hashlib.sha3_512(b"crypto101").hexdigest()
تخزين كلمات المرور
أكثر استعمالات دوالّ التجزئة التشفيرية شيوعًا — وهو للأسف استعمال مكسور تمامًا — هو تخزين كلمات المرور.
فلنفترض أنّ لديك خدمة يسجّل فيها الناس دخولهم باستعمال اسم مستخدم وكلمة مرور. وستضطر إلى تخزين كلمة المرور في مكان ما، بحيث في المرة التالية التي يسجّل فيها المستخدم دخوله تستطيع التحقّق من كلمة المرور التي قدّمها.
وتخزين كلمة المرور مباشرةً له عدّة مشكلات. فإلى جانب هجوم توقيت (timing attack) واضح في مقارنة السلاسل، فإنّ لو أُخْرِقت قاعدة بيانات كلمات المرور، لأمكن للمهاجم أن يقرأ ببساطة جميع كلمات المرور. وبما أنّ كثيرًا من المستخدمين يعيدون استعمال كلمات المرور، فإنّ ذلك فشلٌ كارثيّ. كما أنّ معظم قواعد بيانات المستخدمين تحوي عناوين بريدهم الإلكترونيّة، لذا يكون من السهل جدًا اختطاف حسابات كثير من مستخدميك غير المرتبطة بهذه الخدمة.
دوالّ التجزئة إلى النجدة
ويبدو واضحًا أنّ نُجزّئ كلمة المرور باستعمال دالة تجزئة آمنة تشفيريًا. وبما أنّ دالة التجزئة سهلة الحساب، فإنّه كلّما قدّم المستخدم كلمة مروره تستطيع ببساطة حساب قيمة تجزئتها، ومقارنتها بما خزّنته في قاعدة البيانات.
ولو سرق مهاجم قاعدة بيانات المستخدمين، فإنّه لن يرى إلّا قيم التجزئات لا كلمات المرور الفعلية. وبما أنّ عكس دالة التجزئة مستحيل على المهاجم، فإنّه لن يستطيع تحويل تلك القيم مجدّدًا إلى كلمات المرور الأصلية. أو هكذا كان يظنّ الناس.
جداول قوس قزح
تبيّن أنّ هذا الاستدلال معطوب. فعدد كلمات المرور التي يستعملها الناس فعليًا محدود
جدًّا. فحتى مع ممارسات جيدة جدًّا في اختيار كلمات المرور، فإنّها سلاسل طولها بين 10
و20 محرفًا، تتكوّن في معظمها ممّا يمكن كتابته على لوحات المفاتيح المعتادة. لكنّ الناس
في الممارسة العملية يستعملون كلمات مرور أسوأ من ذلك: أشياء مبنيّة على كلمات حقيقية
(password، swordfish)، أو متكوّنة من رموز قليلة ومن أنواع رموز قليلة (1234)،
أو مع تعديلات يمكن التنبّؤ بها لما سبق (passw0rd).
وفوق ذلك، دوالّ التجزئة هي نفسها في كلّ مكان. فإذا أعاد مستخدم استعمال كلمة المرور
نفسها في موقعين، وكان كلاهما يُجزّئ كلمة المرور باستعمال MD5، فإنّ القيم في قاعدة
بيانات كلمات المرور ستكون متطابقة. ولا يلزم حتى أن يكون ذلك لكلّ مستخدم: فكثير من
كلمات المرور شديدة الشيوع (password)، لذا سيستعملها كثير من المستخدمين.
وتذكّر أنّ دالة التجزئة سهلة التقييم. فماذا لو جرّبنا ببساطة عددًا كبيرًا من تلك الكلمات المرور، لننشئ جداول ضخمة تربط بين كلمات المرور وقيم تجزئاتها؟
وهذا بالضبط ما فعله بعض الناس، وكانت الجداول فعّالة بالقدر المتوقّع تمامًا، إذ كسرت
كاملًا أيّ مخزن كلمات مرور معرَّض للخطر. وتُسمَّى هذه الجداول جداول قوس قزح
(rainbow tables). والسبب في ذلك أنّها في جوهرها قوائم مرتّبة لمخرجات دالة التجزئة.
وتكون هذه المخرجات موزّعة عشوائيًّا إلى حدٍّ ما. وحين كُتبت بصيغ ست عشرية، ذكّرت ذلك
بعض الناس بمواصفات الألوان المستعملة في HTML، مثل #52f211، وهو أخضر ليمونيّ.
الأملاح
كان سبب الفعالية البالغة لجداول قوس قزح هو أنّ الجميع كان يستعمل إحدى بضع دوالّ تجزئة. فكلمة المرور نفسها كانت تُنتج التجزئة نفسها في كلّ مكان.
وتُحلّت هذه المشكلة عمومًا باستعمال الأملاح (salts). فبمزج كلمة المرور مع قيمة
عشوائية (بإلحاقها أو إلحاق القيمة بها مقدّمًا [1]) قبل تجزئتها، تستطيع إنتاج قيم
تجزئة مختلفة تمامًا من دالة التجزئة نفسها. فهو يحوّل دالة التجزئة عمليًّا إلى عائلة
كاملة من دوالّ التجزئة المتّصلة، ذات خصائص أمن وأداء متطابقة تقريبًا، لكنّ بمخرجات
مختلفة تمامًا.
تُخزَّن قيمة salt بجوار تجزئة كلمة المرور في قاعدة البيانات. وحين يُصادِق المستخدم بكلمة المرور، فأنت تجمع salt مع كلمة المرور وتُجزّئها، وتقارن النتيجة بالتجزئة المخزَّنة.
وإن اخترت salt عشوائيًّا تشفيريًا وحجمه كافيًا (ولنفرض 160 بتًّا/32 بايتًا)، فإنّك تُفشل تمامًا الهجمات المسبقة مثل جداول قوس قزح. ولأن ينجح مهاجم في تنفيذ هجوم بجدول قوس قزح، فعليه أن يملك جدولًا منفصلًا لكلّ قيمة من تلك قيم salt. وبما أنّ الجدول الواحد كان عادةً كبيرًا إلى حدٍّ كبير، فإنّ تخزين عدد كبير منها مستحيل. وحتى لو تمكّن المهاجم من تخزين كلّ تلك البيانات، لكان عليه أوّلًا حسابها. فحساب جدول واحد يستغرق وقتًا لا بأس به، بينما حساب 2^{160} جدولًا مختلفًا مستحيل.
استعملت أنظمة كثيرة salt واحدة لجميع المستخدمين. وبينما كان ذلك يمنع هجوم جدول قوس قزح المسبق، فإنّه سمح للمهاجمين بمهاجمة جميع كلمات المرور دفعة واحدة، بمجرّد معرفتهم قيمة salt. إذ يكفي أن يحسب المهاجم جدول قوس قزح واحدًا لتلك salt، ويقارن النتائج بكلمات المرور المُجزَّأة في قاعدة البيانات. وبينما كان ذلك يمكن منعه باستعمال salt مختلفة لكلّ مستخدم، فإنّ الأنظمة التي تستعمل تجزئة تشفيرية مع salt خاصة بكلّ مستخدم ما تزال تُعدّ مكسورة على نحو جوهريّ اليوم؛ فهي أصعب في الكسر فحسب، وليست آمنة البتّة.
ولعلّ أكبر مشكلة في الأملاح (salts) هي أنّ كثيرًا من المبرمجين اقتنعوا فجأةً بأنّهم يفعلون الصواب. فقد سمعوا بمخطّطات تخزين كلمات المرور المكسورة، ويعرفون ما ينبغي فعله بدلًا منها، تجاهلوا كلّ الكلام عن كيفية اختراق قاعدة بيانات كلمات المرور. لم يكونوا هم من يخزّن كلمات المرور بنصّ صريح، أو من ينسى وضع salt على تجزئاته، أو من يعيد استعمال salts لمستخدمين مختلفين. إنّما كانت تلك المشكلات عند كلّ هؤلاء الأشخاص الآخرين الذين لا يعرفون ما يفعلون. وللأسف، ليس هذا صحيحًا. ولعلّ هذا هو سبب بقاء مخطّطات تخزين كلمات المرور المكسورة هي القاعدة.
الهجمات الحديثة على أنظمة كلمات المرور الضعيفة
بالنسبة إلى الهجوم الحديث، لا تساعد الأملاح (salts) ببساطة. فالهجمات الحديثة
تستغلّ الحقيقة بأنّ دالة التجزئة المستعملة سهلة الحساب. وباستعمال عتاد أسرع، ولا سيما
بطاقات الرسوميات، يمكننا ببساطة تعداد جميع كلمات المرور، بصرف النظر عن salt.
TODO: أرقام أداء أكثر تحديدًا عن وحدات معالجة الرسوميات
Salt <salt>\s قد تجعل الهجمات المحسوبة مسبقًا مستحيلة، لكنها لا تفعل شيئًا تقريبًا
ضدّ مهاجم يعرف salt فعلًا. وأحد المناهج التي قد تميل إلى اتّخاذه هو محاولة إخفاء
salt عن المهاجم. لكنّ ذلك ليس مفيدًا عادةً: فإذا تمكّن المهاجم من الوصول إلى قاعدة
البيانات، فاحتمالات نجاح إخفاء salt ضئيلة. ومثل كثير من مخطّطات التشفير المنزلية غير
الفعّالة، فإنّ هذا لا يحمي إلّا من حدث مستبعد إلى حدٍّ هائل. وسيكون أنفع بكثير أن
تستعمل منذ البداية مخزن كلمات مرور جيّدًا، بدلًا من محاولة إصلاح مخزن مكسور.
من أين نذهب بعد ذلك؟
ولحماية كلمات المرور، تحتاج إلى :ref:دالة اشتقاق مفاتيح <key derivation function> (ذات إنتروبيا منخفضة). وسنتحدّث عنها بمزيد من التفصيل في
فصل قادم.
وفيما يمكن بناء دوالّ اشتقاق المفاتيح باستعمال دوالّ التجزئة التشفيرية، فإنّ لها خصائص أداء مختلفة إلى حدٍّ كبير. وهذا نمط شائع: فبينما دوالّ التجزئة التشفيرية بناءات (primitives) بالغة الأهمية لبناء أدوات آمنة (مثل دوالّ اشتقاق المفاتيح أو خوارزميات مصادقة الرسائل)، فإنّها تُساء استعمالها بوصفها تلك الأدوات بعينها. وفي بقية هذا الفصل، سنرى أمثلة أخرى على كيفية استعمال دوالّ التجزئة التشفيرية وإساءة استعمالها.
هجمات تمديد الطول
في كثير من دوالّ التجزئة، ولا سيما الأجيال السابقة منها، تُستعمل الحالة
الداخلية التي تحتفظ بها دالة التجزئة بوصفها قيمة التجزئة. وفي بعض الأنظمة سيئة
الهندسة، يسبّب ذلك خللًا بالغًا: فإذا عرف المهاجم H(M_1)، فإنّ حساب
H(M_1 \| M_2) جدًّا بسيط، من دون معرفة قيمة M_1 فعليًّا. وبما أنّك تعرف
H(M_1)، فإنّك تعرف حالة دالة التجزئة بعد أن جزّأت M_1. ويمكنك أن تستعمل ذلك
لإعادة بناء دالة التجزئة، وتطلب منها أن تجزّئ بايتات إضافية. واستعمالة الحالة
الداخلية لدالة التجزئة على حالة معروفة حصلت عليها من مكان آخر (مثل H(M_1))
تُسمّى التثبيت (fixation).
بالنسبة إلى معظم دوالّ التجزئة في العالم الحقيقي، فإنّ الأمر أعقد قليلًا من ذلك. فغالبًا ما لديها خطوة حشو يحتاج المهاجم إلى إعادة إنشائها. وMD5 وSHA-1 لهما خطوة الحشو نفسها. وهي بسيطة إلى حدٍّ معقول، لذا سنمرّ عليها:
#. أضف بتّة واحدة إلى الرسالة.
#. أضف بتّات فارغة حتى يبلغ الطول 448 \pmod {512}.
#. خذ الطول الكلّي للرسالة قبل الحشو، وأضفه بوصفه عددًا صحيحًا بطول 64 بتًّا.
كي يتمكّن المهاجم من حساب H(M_1 \| M_2) معطى H(M_1)، عليه أن يقلّد ذلك الحشو
أيضًا. فسيحسب المهاجم فعليًا H(M_1 \| G \| M_2)، حيث G هو حشو اللصق (glue
padding)، ويُسمّى كذلك لأنّه يلصق الرسالتين معًا. والصعوبة في معرفة طول الرسالة
M_1.
لكنّ المهاجم في أنظمة كثيرة يستطيع في الواقع أن يضع تخمينات مبنيّة على معلومات وجيهة
عن طول M_1. فمثلًا، خُذ المثال الشائع (المكسور) لرمز مصادقة ذا بادئة سرّية.
يُرسِل الناس رسائل M_i مصادَقًا عليها باستعمال A_i = H(S \| M_i)، حيث S سرّ
مشترك. وسنرى (ونكسر) خوارزمية MAC هذه في قسم قادم.
ومن السهل جدًا على المستقبِل أن يحسب الدالة نفسها، ويتأكّد من صحّة الرمز. وأيّ تغيير
في الرسالة M_i يغيّر قيمة A_i تغييرًا كبيرًا، بفضل أثر الانهيار الجليدي.
وللأسف، من السهل إلى حدٍّ كبير على المهاجمين تزوير الرسائل. وبما أنّ رمز المصادقة
يُرسَل عادةً مع الرسالة الأصلية، فإنّ المهاجم يعرف طول الرسالة الأصلية. ثمّ لا على
المهاجم إلّا أن يخمّن طول السرّ، وهو ثابت في الغالب كجزء من البروتوكول، وحتى إن لم
يكن كذلك، فالمهاجم سيتواصل على الأغلب في مئة محاولة أو أقلّ. وقارن ذلك بتخمّن السرّ
نفسه، وهو أمر مستحيل لأيّ سرّ مختار باعتدال.
وهناك رموز مصادقة آمنة يمكن تصميمها باستعمال دوالّ التجزئة التشفيرية: لكنّ هذا الرمز ليس منها. وسنرى رموزًا أفضل في فصل لاحق.
بعض دوالّ التجزئة، ولا سيما الأحدث مثل المتأهّلين في مسابقة SHA-3، لا تظهر هذه الخاصية. فالتجزئة تُحسب من الحالة الداخلية، بدلًا من استعمال الحالة الداخلية مباشرةً.
وهذا يجعل دوالّ التجزئة في عصر SHA-3 أكثر مناعة للخطأ قليلًا، ويتيح لها أيضًا إنتاج مخطّطات أبسط لمصادقة الرسائل. (وسنُفصّل في ذلك في فصل لاحق.) وبينما اقتصرت هجمات تمديد الطول على الأنظمة التي كانت دوالّ التجزئة التشفيرية تُساء فيها استعمالًا في الأساس، فإنّ منعها يستحقّ في كلّ الأحوال. فالناس ينتهي بهم المطاف إلى ارتكاب أخطاء، ولا ضير في أن نخفّف من أثرها حيث نستطيع.
TODO: اشرح لماذا يمنع هذا هجمات اللقاء في المنتصف
شجرات التجزئة
شجرات التجزئة (hash trees) هي أشجار [2] تُعرَّف كلّ عقدة فيها بقيمة تجزئة، تتكوّن من محتواها وقيمة تجزئة سلفها. أمّا العقدة الجذر، وليس لها سلف، فإنّها تجزّئ محتواها الخاصّ فحسب.
هذا التعريف واسع جدًّا: فشجرات التجزئة العملية أعقد إلى حدٍّ كبير. فقد تكون أشجارًا ثنائية [3]، أو ربّما تحمل العقد الورقية وحدها بيانات خاصة بها، فيما تحمل العقد الأصلية بيانات مشتقّة فحسب. وتُسمَّى هذه الأنواع المحدّدة بصفة خاصة أشجار ميركل (Merkle trees).
تُستعمل أنظمة من هذا النوع أو تنويعاتها في أنظمة كثيرة، ولا سيما الأنظمة الموزّعة. ومن الأمثلة أنظمة إدارة الإصدارات الموزّعة مثل Git، والعملات الرقمية مثل Bitcoin، وشبكات الند للند الموزّعة مثل Bittorrent، وقواعد البيانات الموزّعة مثل Cassandra.
المشكلات المتبقّية
لقد بيّنا من قبل أنّ دوالّ التجزئة وحدها لا تستطيع مصادقة الرسائل، لأنّ أيّ شخص يستطيع حسابها. كما بيّنا أنّ دوالّ التجزئة لا يمكن استعمالها لتأمين كلمات المرور. وسنعالج المشكلتين معًا في الفصلين التاليين.
وفيما ركّز هذا الفصل كثيرًا على ما لا تستطيع دوالّ التجزئة فعله، فإنّ من المفيد تكرار القول إنّها لا تزال بناءات تشفيرية بالغة الأهمية. فهي مجرّد بناءات تشفيرية يُساء استعمالها عادةً.