حجم جدول قوس قزح

خطوات الاستخدام

الخطوة 1: فهم جدول قوس قزح. جدول قوس قزح هو هيكل بيانات يستخدم في كسر كلمات المرور المخزنة بصيغة التجزئة (hash). يعتمد على تقنية المفاضلة بين الزمن والذاكرة (time-memory trade-off). يتم إنشاء الجدول باستخدام سلاسل من التجزئات (hashes) حيث كل سلسلة تبدأ بكلمة مرور محتملة وتنتهي بكلمة مرور أخرى بعد تطبيق دوال اختزال (reduction functions). الهدف هو تقليل حجم التخزين اللازم مقارنة بجداول البحث المباشرة. لتقدير حجم جدول قوس قزح، تحتاج إلى معرفة ثلاثة معاملات رئيسية: طول السلسلة (chain length)، عدد السلاسل (number of chains)، وحجم التجزئة (hash size) بالبت.

الخطوة 2: إدخال طول السلسلة (chain length). طول السلسلة هو عدد مرات تطبيق دالة التجزئة ودالة الاختزال بالتناوب على طول السلسلة. كلما زاد طول السلسلة، زادت التغطية (coverage) لمساحة كلمات المرور، ولكن على حساب وقت الحساب (وقت الكسر) وربما تقليل احتمال النجاح. أدخل قيمة طول السلسلة (مثل 1000 أو 10000). عادةً ما تكون الأطوال في حدود آلاف إلى مئات الآلاف.

الخطوة 3: إدخال عدد السلاسل (number of chains). عدد السلاسل هو عدد نقاط البداية المختلفة المستخدمة في الجدول. كل سلسلة تبدأ بكلمة مرور عشوائية وتنتهي بنقطة نهاية (endpoint). عدد السلاسل مضروباً في طول السلسلة يعطي إجمالي عدد الخطوات المحسوبة، لكن التخزين الفعلي هو فقط نقاط البداية والنهاية لكل سلسلة. كلما زاد عدد السلاسل، زاد حجم الجدول خطياً.

الأسئلة الشائعة

جدول التجزئة العادي (hash table) يخزن أزواج (كلمة المرور، التجزئة) لكل كلمة مرور في مساحة البحث. هذا يتطلب ذاكرة هائلة لمساحات كلمات المرور الكبيرة (مثل كل مجموعات 8 أحرف أبجدية رقمية). على سبيل المثال، مساحة 8 أحرف أبجدية رقمية تحتوي على 62^8 ≈ 2.18 × 10^14 كلمة مرور. تخزين كل زوج بحجم 16 بايت للتجزئة (MD5) و8 بايت لكلمة المرور (متوسط) يتطلب حوالي 5 بيتابايت - غير عملي. جدول قوس قزح يحل هذه المشكلة باستخدام تقنية المفاضلة بين الزمن والذاكرة. بدلاً من تخزين كل النقاط، يخزن فقط نقاط البداية والنهاية لسلاسل طويلة. عند البحث، يعاد حساب السلسلة حتى نجد تطابقاً. هذا يقلل الذاكرة بشكل كبير (على سبيل المثال، لمثالنا السابق بذاكرة 3.2 ميجابايت يغطي 0.05% من المساحة، بينما جدول التجزئة العادي لنفس المساحة يتطلب مئات التيرابايت). لكن هناك ثمناً: وقت البحث أطول (لأننا نحتاج لإعادة الحساب)، وهناك احتمال للفشل بسبب التصادمات (collisions) ووجود حلقات (loops). جدول قوس قزح يحسن على جدول هلمان الأصلي (Hellman's tables) باستخدام دوال اختزال مختلفة لتقليل التصادمات.

طول السلسلة (L) يلعب دوراً محورياً. بشكل عام، كلما زاد L، زادت التغطية لكل سلسلة، وبالتالي يمكن تقليل عدد السلاسل (N) لتحقيق نفس الاحتمالية، مما يقلل حجم الجدول (لأن الحجم يعتمد على N). لكن هناك عدة تأثيرات: 1) التغطية: التغطية المتوقعة = 1 - (1 - 1/M)^(N*L) تقريباً، حيث M حجم مساحة كلمات المرور. لزيادة التغطية، يمكن زيادة N أو L. 2) وقت البحث: عند البحث عن تجزئة معينة، نحتاج إلى تطبيق دالة الاختزال والتجزئة حتى L مرة في أسوأ الحالات. لذا وقت البحث يتناسب مع L. 3) احتمالية الفشل: بسبب التصادمات والحلقات، احتمالية النجاح الفعلية أقل من النظرية. وقد تظهر ظاهرة 'انخفاض العائدات' عند زيادة L بشكل كبير. في الممارسة، يختار L بحيث يكون (N * L) قريباً من M؟ ليس بالضرورة، ولكن غالباً ما يُختار L ليكون حول sqrt(M/N) أو بطريقة تحقق مفاضلة مقبولة. العامل الرئيسي هو تقليل إجمالي العمل (N*L) الذي يتناسب مع وقت الإنشاء، مع الحفاظ على حجم جدول معقول. مثال: إذا كان لديك ذاكرة 1 جيجابايت وتريد كسر SHA-256 (M=2^256، لكن مساحة كلمات المرور الفعلية أصغر، مثلاً M=10^12)، يمكنك اختيار N و L لتحقيق 90% تغطية. باستخدام الصيغ المتقدمة لجدول قوس قزح (مع دوال اختزال متنوعة)، يمكن تحسين الأداء. في النهاية، طول السلسلة هو معلمة تصميم رئيسية.

دالة الاختزال (R) هي دالة تحول تجزئة (hash) إلى كلمة مرور محتملة. في جداول هلمان الأصلية، تُستخدم نفس دالة الاختزال لكل خطوة في السلسلة. هذا يؤدي إلى مشكلة التصادمات: إذا التقت سلسلتان في نفس التجزئة، فإنهما تندمجان (merge)، مما يقلل التغطية. جدول قوس قزح يحل هذه المشكلة باستخدام سلسلة من دوال الاختزال المختلفة (R1, R2, ..., RL) لكل خطوة في السلسلة. هذا يضمن أنه حتى إذا التقت سلسلتان في نفس التجزئة في نفس الخطوة، فإنهما ستستمران مع دوال اختزال مختلفة، وبالتالي لن تندمجا. هذا يزيد فعالية الجدول بشكل كبير. عملياً، تُشتق دوال الاختزال من دالة اختزال أساسية عن طريق تغيير مفتاح أو معامل بسيط (مثل إضافة رقم الخطوة). كلما زاد عدد دوال الاختزال المختلفة، قل احتمال التصادم. لكن هذا يزيد أيضاً من تعقيد الحساب ووقت البحث (لكنه مقبول). في جدول قوس قزح، يكون عدد دوال الاختزال مساوياً لطول السلسلة، مما يسمح بتغطية أفضل بنفس حجم الذاكرة مقارنة بجداول هلمان.

هذه العلاقة ليست خطية ويمكن حسابها تقريباً باستخدام نظرية الاحتمالات. لنفترض أن مساحة كلمات المرور M كبيرة، وعدد السلاسل N، وطول السلسلة L. إذا كانت دوال الاختزال عشوائية ومستقلة، فإن التغطية المتوقعة (احتمال أن تكون كلمة المرور العشوائية موجودة في الجدول) تعطى بالصيغة: P = 1 - (1 - 1/M)^(N*L) (مع بعض التصحيحات للتصادمات). ولكن هذه الصيغة تهمل التصادمات بين السلاسل. الصيغة الأكثر دقة من أدب جدول قوس قزح: P ≈ 1 - e^(-N*L/M) في حالة عدم وجود تصادمات، لكن مع التصادمات، تكون أقل. في الواقع، إذا كان N*L أصغر بكثير من M، فإن P ≈ N*L/M. وهذا خطي تقريباً. على سبيل المثال، إذا كان M=10^12 و N*L=5*10^8 (كما في المثال السابق)، فإن P≈0.05%. لزيادة P إلى 50%، نحتاج N*L=0.5M=5*10^11. إذا اخترنا L=5000، فإن N=10^8، وحجم الجدول = N* (حجم نقطة النهاية * 2) = 10^8 * 64 بايت = 6.4 جيجابايت (لـ SHA-256). هذا معقول. يمكن تقليل الحجم بزيادة L، لكن وقت البحث سيزيد. لذا المفاضلة بين الحجم والوقت واضحة. في التطبيقات العملية (مثل RainbowCrack)، تستخدم جداول لمساحات محددة (مثل 95 حرف مطبوع، طول 1-7) وتكون احتمالية النجاح عالية جداً (أكثر من 99%) للكلمات المرور ضمن المساحة.

حجم جدول قوس قزح

أدخل القيم

خطوات الاستخدام

أمثلة محلولة

أمثلة محسوبة

الأسئلة الشائعة