طاولة قوس قزح

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

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

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

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

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

إن تعلم كلمة مرور من دالة تجزئة يعني إيجاد سلسلة نصية، عند إدخالها في دالة التجزئة، تُنتج نفس قيمة التجزئة. وهذا يُشبه عكس دالة التجزئة.

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

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

بفرض وجود دالة تجزئة لكلمات المرور H ومجموعة محدودة من كلمات المرور P، فإن الهدف هو حساب بنية بيانات مسبقًا ، بحيث إذا أُعطيت أي قيمة h لمخرجات دالة التجزئة، يمكنها إما تحديد موقع عنصر p في P بحيث يكون H( p ) = h ، أو تحديد عدم وجود عنصر p في P. أبسط طريقة لتحقيق ذلك هي حساب H( p ) لجميع قيم p في P، ولكن تخزين الجدول يتطلب مساحة Θ (|P| n ) بت، حيث |P| هو حجم المجموعة P و n هو حجم مخرجات H، وهو ما يُعدّ مكلفًا للغاية بالنسبة لقيم |P| الكبيرة. تُعدّ سلاسل التجزئة تقنية لتقليل متطلبات المساحة هذه. الفكرة هي تعريف دالة اختزال R تُعيد ربط قيم التجزئة بقيم في P. تجدر الإشارة إلى أن دالة الاختزال ليست في الواقع معكوس دالة التجزئة، بل هي دالة مختلفة ذات مجال ونطاق مُتبادلين مع دالة التجزئة. من خلال التناوب بين دالة التجزئة ودالة الاختزال، تتشكل سلاسل من كلمات المرور وقيم التجزئة المتناوبة. على سبيل المثال، إذا كانت P هي مجموعة كلمات المرور المكونة من 6 أحرف أبجدية صغيرة، وكانت قيم التجزئة بطول 32 بت، فقد تبدو السلسلة على النحو التالي:

${\displaystyle {\color {Red}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}$

الشرط الوحيد لوظيفة الاختزال هو القدرة على إرجاع قيمة "نص عادي" بحجم محدد.

لإنشاء الجدول، نختار مجموعة عشوائية من كلمات المرور الأولية من P، ونحسب سلاسل بطول ثابت k لكل كلمة مرور، ونخزن كلمة المرور الأولى والأخيرة فقط في كل سلسلة. تُسمى كلمة المرور الأولى نقطة البداية ، والأخيرة نقطة النهاية . في سلسلة المثال أعلاه، ستكون "aaaaaa" هي نقطة البداية، و"kiebgt" هي نقطة النهاية، ولن يتم تخزين أي من كلمات المرور الأخرى (أو قيم التجزئة).

الآن، إذا كان لدينا قيمة تجزئة h نريد عكسها (إيجاد كلمة المرور المقابلة لها)، نحسب سلسلة تبدأ بـ h بتطبيق R، ثم H، ثم R، وهكذا. إذا تطابقت أي قيمة في أي نقطة مع إحدى نقاط النهاية في الجدول، فإن نقطة البداية المقابلة تسمح بإعادة إنشاء السلسلة كاملة. هناك احتمال كبير أن تحتوي هذه السلسلة على القيمة h ، وإذا كان الأمر كذلك، فإن القيمة السابقة لها مباشرة في السلسلة هي كلمة المرور p التي نبحث عنها.

على سبيل المثال، إذا تم إعطاء التجزئة 920ECF10 ، فيمكن حساب سلسلتها عن طريق تطبيق R أولاً:

${\displaystyle {\mathtt {920ECF10}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}$

بما أن " kiebgt " هي إحدى نقاط النهاية في جدولنا، فإن كلمة المرور الأولية المقابلة " aaaaaa " تسمح بتتبع سلسلتها حتى الوصول إلى 920ECF10 :

${\displaystyle {\color {Red}{\mathtt {aaaaaa}}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {281DAF40}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {sgfnyd}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {920ECF10}}}$

وبالتالي، فإن كلمة المرور هي " sgfnyd " (أو كلمة مرور مختلفة لها نفس قيمة التجزئة).

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

${\displaystyle {\mathtt {FB107E70}}\,{\xrightarrow[{\;R\;}]{}}\,{\mathtt {bvtdll}}\,{\xrightarrow[{\;H\;}]{}}\,{\mathtt {0EE80890}}\,{\xrightarrow[{\;R\;}]{}}\,{\color {Violet}{\mathtt {kiebgt}}}}$

يتم تتبع السلسلة الناتجة عن كلمة المرور الأولية " aaaaaa " حتى الوصول إلى FB107E70 . سينتهي البحث دون الوصول إلى FB107E70 لأن هذه القيمة غير موجودة في السلسلة. يُسمى هذا إنذارًا خاطئًا . في هذه الحالة، يتم تجاهل التطابق ويتم تمديد السلسلة h بحثًا عن تطابق آخر. إذا امتدت السلسلة h إلى الطول k دون أي تطابقات صحيحة، فهذا يعني أن كلمة المرور لم تُنتج أبدًا في أي من السلاسل.

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

تُعاني سلاسل التجزئة البسيطة من عدة عيوب. أخطرها هو حدوث تصادم بين سلسلتين (أي إنتاجهما نفس القيمة)، حيث ستندمجان، وبالتالي لن يغطي الجدول عددًا كافيًا من كلمات المرور، على الرغم من أن تكلفة إنشائهما الحسابية متساوية. ولأن السلاسل السابقة لا تُخزن بكاملها، يستحيل اكتشاف هذا التصادم بكفاءة. على سبيل المثال، إذا تطابقت القيمة الثالثة في السلسلة 3 مع القيمة الثانية في السلسلة 7، فستغطي السلسلتان تقريبًا نفس تسلسل القيم، لكن قيمهما النهائية لن تكون متطابقة. من غير المرجح أن تُنتج دالة التجزئة H تصادمات، إذ يُعتبر تجنبها ميزة أمنية مهمة، لكن دالة الاختزال R، نظرًا لحاجتها إلى تغطية النصوص الأصلية المحتملة بشكل صحيح، لا يُمكن أن تكون مقاومة للتصادمات .

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

تُعالج جداول قوس قزح مشكلة التصادمات في سلاسل التجزئة العادية بفعالية، وذلك باستبدال دالة الاختزال R بسلسلة من دوال الاختزال المترابطة R1 _إلى Rk _. بهذه الطريقة، لكي تتصادم سلسلتان وتندمجا، يجب أن تصلا إلى القيمة نفسها في التكرار نفسه ؛ وبالتالي، ستكون القيم النهائية في هاتين السلسلتين متطابقة. يمكن لعملية معالجة لاحقة نهائية فرز السلاسل في الجدول وإزالة أي سلاسل "مكررة" لها نفس القيم النهائية لسلاسل أخرى. ثم تُنشأ سلاسل جديدة لملء الجدول. هذه السلاسل ليست خالية من التصادمات (قد تتداخل لفترة وجيزة)، لكنها لن تندمج، مما يقلل بشكل كبير من العدد الإجمالي للتصادمات.

يُغيّر استخدام تسلسلات دوال الاختزال طريقة البحث: نظرًا لإمكانية وجود قيمة التجزئة المطلوبة في أي مكان ضمن السلسلة، فمن الضروري إنشاء k سلسلة مختلفة. تفترض السلسلة الأولى أن قيمة التجزئة موجودة في آخر موضع تجزئة وتُطبّق عليها R _k ؛ بينما تفترض السلسلة التالية أن قيمة التجزئة موجودة في الموضع قبل الأخير وتُطبّق عليها R _{k −1} ، ثم H، ثم R _k ؛ وهكذا حتى السلسلة الأخيرة التي تُطبّق جميع دوال الاختزال بالتناوب مع H. يُؤدي هذا إلى طريقة جديدة لإصدار إنذار خاطئ: فقد يُؤدي "تخمين" غير صحيح لموضع قيمة التجزئة إلى تقييم سلسلة دون داعٍ.

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

لا يُعدّ جدول قوس قزح فعالاً ضدّ التجزئات أحادية الاتجاه التي تتضمن قيمًا كبيرة من الملح . على سبيل المثال، لنفترض تجزئة كلمة مرور تم إنشاؤها باستخدام الدالة التالية (حيث " + " هو عامل الربط ):

saltedhash(password) = hash(password + salt)

أو

saltedhash(password) = hash(hash(password) + salt)

قيمة الملح ليست سرية، ويمكن توليدها عشوائيًا وتخزينها مع تجزئة كلمة المرور. تمنع قيمة الملح الكبيرة هجمات الحساب المسبق، بما في ذلك جداول قوس قزح، من خلال ضمان تجزئة كلمة مرور كل مستخدم بشكل فريد. هذا يعني أن مستخدمين يستخدمان نفس كلمة المرور سيحصلان على تجزئات مختلفة (بافتراض استخدام قيم ملح مختلفة). لكي ينجح المهاجم، يحتاج إلى حساب جداول مسبقًا لكل قيمة ملح محتملة. يجب أن تكون قيمة الملح كبيرة بما يكفي، وإلا سيتمكن المهاجم من إنشاء جدول لكل قيمة ملح. بالنسبة لكلمات مرور يونكس القديمة التي كانت تستخدم قيمة ملح 12 بت، سيتطلب ذلك 4096 جدولًا، مما يمثل زيادة كبيرة في التكلفة على المهاجم، ولكنه ليس مستحيلاً مع محركات الأقراص الصلبة ذات سعة تيرابايت. تستخدم طرق SHA2-crypt و bcrypt - المستخدمة في لينكس ، وأنظمة يونكس BSD ، وسولاريس - قيم ملح 128 بت. ^{[ 4 ]} تجعل قيم الملح الكبيرة هذه هجمات الحساب المسبق ضد هذه الأنظمة غير ممكنة عمليًا لأي طول تقريبًا لكلمة المرور. حتى لو تمكن المهاجم من إنشاء مليون جدول في الثانية، فسيظل بحاجة إلى مليارات السنين لإنشاء جداول لجميع الأملاح الممكنة.

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

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

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

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

تستخدم جميع توزيعات وأنظمة يونكس ولينكس وبي إس دي تقريبًا التشفير مع إضافة قيمة عشوائية ( Salt)، على الرغم من أن العديد من التطبيقات تستخدم التشفير فقط (عادةً MD5 ) بدون إضافة قيمة عشوائية . تستخدم عائلة أنظمة مايكروسوفت ويندوز NT/2000 طريقة التشفير LAN Manager و NT LAN Manager (المبنية على MD4 ) وهي أيضًا بدون إضافة قيمة عشوائية، مما يجعلها من أكثر الجداول شيوعًا. شهد استخدام جداول قوس قزح انخفاضًا منذ عام 2020 نظرًا لانتشار إضافة القيمة العشوائية (Salt) وزيادة فعالية هجمات القوة الغاشمة القائمة على وحدات معالجة الرسومات (GPU) . مع ذلك، تتوفر جداول قوس قزح لكلمات مرور NTLM المكونة من ثمانية وتسعة أحرف . ^{[ 10 ]}

• A5/1
• هجوم بالقوة الغاشمة
• ديسترجين
• خوارزمية الكنغر لبولارد

• أوشلين، فيليب (17 أغسطس/آب 2003). "تحقيق توازن أسرع بين وقت الذاكرة في التحليل التشفيري". التطورات في علم التشفير - CRYPTO 2003 (ملف PDF) . سلسلة محاضرات في علوم الحاسوب. المجلد  2729. سانتا باربرا، كاليفورنيا ، الولايات المتحدة الأمريكية: سبرينغر. الصفحات 617-630 . doi : 10.1007/978-3-540-45146-4_36 . ISBN  978-3-540-40674-7S2CID 16086595. مؤرشف من الأصل (PDF) بتاريخ 26-09-2020 . تم الاطلاع عليه بتاريخ 13-03-2019 . 

• صفحة Ophcrack من إعداد فيليب أوشلين، البحث الأصلي حول جدول قوس قزح