جدول رنگین‌کمانی

یک جدول رنگین کمانی (به انگلیسی: rainbow table)، یک جدول از پیش محاسبه شده‌است برای معکوس کردن تابع کدنویسی درهم ساز (هش کریپتوگرافیک). معمولاً برای شکستن کدهای هش از آن استفاده می‌کنند. این جدول‌ها گاهی برای بازیابی گذرواژه (یا شماره کارت‌های اعتباری و…)استفاده می‌شوند. این جدول‌ها دارای طول مشخصی هستند و شامل تعدادی مولفهٔ محدود می‌باشند. این یک مثال کاربردی از یک مبادلهٔ فضا-زمانی می‌باشد که از پردازش کامپیوتری کمتر و ذخیره‌سازی بیشتری نسبت به یک حمله بروت فورس استفاده می‌کند و هش را نیز در هر تلاش محاسبه می‌کند. اما در عین حال از پردازش کامپیوتری بیشتر و ذخیره‌سازی کمتری نسبت به یک جدول جستجو (جدول لوک آپ) ساده با یک ورودی در هش، استفاده می‌کند. استفاده از یک تابع مشتقی کلیدی که از یک سالت بهره می‌برد می‌تواند این حمله را غیرقابل نفوذ کند.

جدول‌های رنگین کمانی توسط فیلیپ اوچسلین و بعنوان یک اپلیکیشن از یک الگوریتم ساده‌تر توسط مارتین هلمن اختراع شد.

یک جدول رنگین کمان ساده با ۳ مرحله

زمینه

هر سیستم کامپیوتری که در آن احراز هویت پسورد وجود دارد، باید شامل بانک اطلاعاتی از پسوردها باشد، با استفاده از مبهم ساختن (برای در امان ماندن از مهاجمین) یا با استفاده از پلین تکست، و روش‌های متفاوتی برای ذخیره‌سازی این پسوردها وجود دارد. به این دلیل که جدول‌ها در برابر سارقین آسیب‌پذیر هستند ذخیره‌سازی پسورد پلین تکست خطرناک می‌باشد، به همین دلیل اکثر بانک‌های اطلاعاتی یک تابع درهم ساز رمزنگارانه از پسورد کاربران را در بانکشان ذخیره می‌کنند. در چنین سیستم‌هایی هیچ چیزـ از جمله سیستم احراز هویت ـ نمی‌تواند با صرفاً نگاهی به میزان ولیوی ذخیره شده در بانک اطلاعات پسورد کاربر را پیدا کند، در عوض وقتی یک کاربرپسوردی را برای احراز هویت وارد می‌کند، سیستم میزان هش را برای پسورد وارد شده محاسبه می‌کند و آن مقدار هش با هش ذخیره شده توسط کاربر مقایسه می‌شود و احراز هویت موفق خواهد بود اگر دو هش با هم تطابق داشته باشند.

بعد از جمع‌آوری یک هش کد، استفاده از هش مذکور بعنوان پسورد، با عدم موفقیت مواجه می‌شود، زیرا سیستم احراز هویت آن را برای بار دوم نیز هش می‌کند. برای دستیابی به پسورد یک کاربر، یک پسوردی که میزان یکسانی هش تولید می‌کند، معمولاً از طریق یک بروت فورس یا دیکشنری اتک (حملهٔ لغت نامه ای) باید پیدا شود.

جدول‌های رنگین کمانی معمولاً آن دسته ابزاری هستند که ایجاد شده‌اند تا تنها با بررسی میزان هش شده از یک پسورد مشتق می‌گیرند.

جدول‌های رنگین کمانی همیشه مورد نیاز نیستند با توجه به اینکه روش‌های مستقیم تری برای واژگونی هش (هش ریورسال) وجود دارد، حملات بروت فورس و لغت نامه ای از مستقیم‌ترین روش‌ها برای آن می‌باشند. اگرچه این‌ها برای سیستم‌هایی که از کدهای طولانی استفاده می‌کنند به دلیل دشوار بودن ذخیره‌سازی تمام آپشن‌های موجود و همچنین دشواری آن در سرچ کردن از طریق چنین بانک اطلاعاتی گسترده‌ای برای انجام سرچ معکوس (ریورس لوک آپ) از یک هش، مناسب نیستند.

برای حل این مسئله جدول‌های ریورس لوک آپ (جستجوی معکوس) تولید شده‌اند تا مقدار کمی از هش‌های انتخابی را ذخیره کنند، که زمانی که معکوس شوند می‌توانند زنجیرهٔ بزرگی از کدها را ایجاد کند. اگرچه که جستجوی معکوس یک هش در یک جدول زنجیره ای زمان محاسبات بیشتری صرف می‌کند، اما جدول لوک آپ (جستجو) به خودی خود می‌تواند بسیار کوچک باشد، تا هش‌هایی از کدهای طولانی‌تر بتوانند در آن ذخیره شوند. جدول‌های رنگین کمانی اصلاحیه‌های هستند بر این تکنیک زنجیره ای راه حلی را برای مشکلی بنام تصادم (برخورد) فراهم کرده‌اند.

کاربردها

تقریباً تمام ویرایش‌های یونیکس و لینوکس و BSD از رشته درهم سازی شده با Salt استفاده می‌کنند. هر سیستم کامپیوتری که در آن احراز هویت پسورد وجود دارد، باید شامل بانک اطلاعاتی از پسوردها باشد، با استفاده از مبهم ساختن (برای در امان ماندن از مهاجمین) یا با استفاده از پلین تکست، و روش‌های متفاوتی برای ذخیره‌سازی این پسوردها وجود دارد.

به این دلیل که جدول‌ها در برابر سارقین آسیب‌پذیر هستند ذخیره‌سازی پسورد پلین تکست خطرناک می‌باشد، به همین دلیل اکثر بانک‌های اطلاعاتی یک هش هیپتوگرافی (تابع درهم‌ساز رمزنگارانه) از پسورد کاربران را در بانکشان ذخیره می‌کنند. در چنین سیستم‌هایی هیچ چیزـ از جمله سیستم احراز هویت ـ نمی‌تواند با صرفاً نگاهی به میزان ولیوی ذخیره شده در بانک اطلاعات پسورد کاربر را پیدا کند، در عوض وقتی یک کاربرپسوردی را برای احراز هویت وارد می‌کند، سیستم میزان هش را برای پسورد وارد شده محاسبه می‌کند و آن مقدار هش با هش ذخیره شده توسط کاربر مقایسه می‌شود و احراز هویت موفق خواهد بود اگر دو هش با هم تطابق داشته باشند.

بعد از جمع‌آوری یک هش کد، استفاده از هش مذکور بعنوان پسورد، با عدم موفقیت مواجه می‌شود، زیرا سیستم احراز هویت آن را برای بار دوم نیز هش می‌کند.

برای دستیابی به پسورد یک کاربر، یک پسوردی که میزان یکسانی هش تولید می‌کند، معمولاً از طریق یک حمله جستجوی فراگیر (Brute-force attacks)یا حمله لغت‌نامه‌ای(dictionary attacks) باید پیدا شود.

جدول‌های رنگین کمانی معمولاً آن دسته ابزاری هستند که ایجاد شده‌اند تا تنها با بررسی میزان هش شده از یک پسورد مشتق می‌گیرند.

جدول‌های رنگین کمانی همیشه مورد نیاز نیستند با توجه به اینکه روش‌های مستقیم تری برای واژگونی هش (هش ریورسال) وجود دارد، حملات بروت فورس و لغت نامه ای از مستقیم‌ترین روش‌ها برای آن می‌باشند. اگرچه این‌ها برای سیستم‌هایی که از کدهای طولانی استفاده می‌کنند به دلیل دشوار بودن ذخیره‌سازی تمام آپشن‌های موجود و همچنین دشواری آن در سرچ کردن از طریق چنین بانک اطلاعاتی گسترده‌ای برای انجام سرچ معکوس (ریورس لوک آپ) از یک هش، مناسب نیستند.

برای حل این مسئله جدول‌های ریورس لوک آپ (جستجوی معکوس) تولید شده‌اند تا مقدار کمی از هش‌های انتخابی را ذخیره کنند، که زمانی که معکوس شوند می‌توانند زنجیرهٔ بزرگی از کدها را ایجاد کند. اگرچه که جستجوی معکوس یک هش در یک جدول زنجیره ای زمان محاسبات بیشتری صرف می‌کند، اما جدول لوک آپ (جستجو) به خودی خود می‌تواند بسیار کوچک باشد، تا هش‌هایی از کدهای طولانی‌تر بتوانند در آن ذخیره شوند.

جدول‌های رنگین کمانی اصلاحیه‌های هستند بر این تکنیک زنجیره ای راه حلی را برای مشکلی بنام تصادم (برخورد) فراهم کرده‌اند.

ریشه یابی

اصطلاح «جداول رنگین کمان» برای اولین بار در مقاله اولیه دکتر اوچسلین استفاده شد. این اصطلاح به روشی است که از توابع کاهش متفاوتی برای افزایش میزان موفقیت حمله استفاده می‌شود. در روش اصلی هلمن از جدولهای کوچک زیادی با عملکرد متفاوت استفاده می‌شود. جداول رنگین کمان بسیار بزرگتر هستند و در هر ستون از یک تابع کاهش متفاوت استفاده می‌کنند. هنگامی که از رنگ‌ها برای نشان دادن توابع کاهش استفاده می‌شود، رنگین کمان در جدول رنگین کمان ظاهر می‌شود.

شکل ۲ مقاله دکتر اوچسلین حاوی گرافیکی سیاه و سفید است که نحوه ارتباط این بخش‌ها را نشان می‌دهد. دکتر اوچسلین برای ارائه در کنفرانس Crypto 2003، رنگی را به این گرافیک اضافه کرد تا ارتباط رنگین کمان روشن‌تر شود. گرافیکی پیشرفته ای که در کنفرانس ارائه شده‌است در سمت راست نشان داده شده‌است.

مقدمهٔ زنجیرهای درهمسازی

برای زنجیرهای هش به غیر از آنچه در اینجا ذکر شد، زنجیره درهم سازی را ببینید.

فرض کنید ما یک تابع درهم ساز کد (تابع هش کد) H و یک سری محدود از کدهای P داریم، هدف محاسبهٔ اولیه ساختار یک دیتا می‌باشد. از هر خروجی H در تابع درهم ساز داده شده می‌توان یک عنصر p در P را مانند H(P)=h پیدا کرد، یا نشان داد که عنصر p در P وجود ندارد. ساده‌ترین روش برای انجام آن، محاسبهٔ (H(P برای همهٔ pهای داخل P است. اما آن موقع ذخیره کردن جدول نیازمند (|P|n) $\theta$ بیت فضا می‌باشد که در آن |P| اندازهٔ سری p و n اندازهٔ یک خروجی از H است که مانعی برای |P| بزرگ می‌باشد.

هش چین تکنیکی برای کاهش این فضای درخواست شده می‌باشد. ایدهٔ مشخص کردن یک تابع کاهشی R می‌باشد که میزان هش را به میزان ولیوها در P تقلیل دهد. به یاد داشته باشید، تابع کاهشی درواقع معکوسی از تابع درهم ساز نیست، بلکه بیشتر یک تابع متفاوت با دامنهٔ تابع و با دامنهٔ مشترک درهم ساز می‌باشد. با تناوبی کردن تابع درهم ساز با تابع کاهشی (reduction function) زنجیره‌هایی از کدهای متناوب هش ولیوهایی (یا میزانی از هش) شکل می‌گیرد. برای مثال اگر p یک سری پسوردهای شش حرفی با حروف کوچ بود و هش ولیوها ۳۲ بیتی بودند، این زنجیره به این شکل درمی‌آمد:

${\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 می‌باشد، که ما بدنبال آن هستیم.

برای مثال اگر به ما هش 920EC10 داده شده باشد، ما زنجیرهٔ آن را با اعمال اولیه R محاسبه می‌کنیم:

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

چون “KIEBGT” یکی از نقاط پایان در جدول ما می‌باشد، ما کد متناظر شروع کنندهٔ “aaaaaa” را برمی‌داریم و زنجیرهٔ آن را دنبال می‌کنیم تا به 920ECF10 برسیم:

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

بنابراین کد (پسورد) SGFNYD (یا هر پسوردی دیگری که هش ولیوی یکسانی دارد) می‌باشد. به یاد داشته باشید که این زنجیره همیشه شامل هش ولیوی h نمی‌باشد؛ حتی ممکن است زنجیره ای که با h شروع شده با زنجیره ای که نقطهٔ شروع متفاوتی دارد ادغام شود. برای مثال ممکن است به ما هش ولیوی FB107E70 داده شده باشد و وقتی زنجیرهٔ آن را دنبال می‌کنیم به KEIBGT برسیم:

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

اما FB107E70 زنجیره ای نیست که با “aaaaaa” شروع شود، که به این اخطار غلط (فالس آلارم) گفته می‌شود. در این حالت ما آن تطابق را رد می‌کنیم و به گسترش زنجیرهٔ h به جستجوی تطابق (مچ) دیگری می‌پردازیم. اگر زنجیرهٔ h به اندازهٔ طول زنجیرهٔ k بدون هیچ تطابق (مچ) مناسبی گسترش پیدا کرد، به این نتیجه می‌رسیم که پسورد (کد) مورد نظر در هیچ‌کدام از زنجیره‌ها تولید نشده‌است.

محتوای جدول به هش ولیو بستگی ندارد که بخواهد معکوس شود، این محتوا یکبار تولید می‌شود و سپس برای جستجوهای اصلاح نشده تکرار می‌شود. افزایش طول زنجیره اندازهٔ جدول را کاهش می‌دهد، این همچنان زمان مورد نیاز برای اجرای جستجوها را افزایش می‌دهد، این همان تبادل زمان-حافظهٔ جدول رنگین کمانی می‌باشد. در یک حالت ساده از زنجیره‌های تک موردی (تک آیتمی) جستجو بسیار سریع ولی جدول نیز بسیار بزرگ است. زمانی که زنجیره‌ها بلندتر شوند جستجو کندتر می‌شود، ولی اندازهٔ جدول کاهش می‌یابد.

هش چین‌های ساده چندین نقص دارند، جدی‌ترین آن‌ها این است، که اگر در هر نقطه ای دو زنجیره برخورد کنند (یعنی هردو ولیوی یکسانی تولید کنند) آن‌ها ادغام می‌شوند و در نتیجه جدول کد (پسورد)های زیادی را با وجود پرداخت هزینه محاسباتی یکسان، پوشش نمی‌دهد؛ زیرا زنجیره‌های قبلی کاملاً آنجا ذخیره نگشته‌اند و پیدا شدن تشخیص درست در این حالت غیرممکن است. برای مثال، اگر سومین ولیو در زنجیره ۳ با دومین ولیو در زمینهٔ ۷ تطابق داشته باشد، آن دو زنجیره تقریباً توالی یکسانی از ولیوها را پوشش می‌دهند، اما ولیوی آخر آن‌ها یکسان نخواهد بود. تابع درهم ساز H بعید است که برخوردی داشته باشد، با توجه به اینکه اتفاق نیفتادن آن یک ویژگی مهم برای ایمنی تابع محسوب می‌شود. اما تابع کاهشی R به دلیل لزومش بر درست پوشش دادن پلین تکست‌های مشابه، نمی‌تواند برای ایجاد نشدن برخورد از خود مقاومتی نشان دهد.

دیگر مشکلات منتج شده برای اهمیت انتخاب تابع مناسب برای R است.انتخاب R برای اینکه هویت آن را تشکیل دهد کمی از یک تلاش بروت فورس بهتر است. تنها زمانیکه مهاجم ایدهٔ خوبی دربارهٔ اینکه پلین تکست به چه صورت خواهد بود داشته باشد، می‌تواند یک تابع R انتخاب کند و مطئن شود که زمان و فضا تنها برای پلین تکست‌های مشابه مصرف می‌شوند، تمام فضای کدهای محتمل نیز استفاده نمی‌شوند. در اصل R نتایج اولین هش محاسباتی را به سمت مشابهی به پلین تکست‌ها هدایت می‌کند، اما این مزایا به شکلی ایجاد می‌شوند که R تقریباً همهٔ پلین تکست‌های ممکن را تولید نمی‌کند. در رده ای که مهاجم ترجیح می‌دهد آن را چک کند، انکار کردن قطعیت مهاجم نسبت به اینکه هیچ کدی از ردهٔ آن‌ها وارد نشده. همچنین طراحی تابع R بگونه ای که با پلین تکست‌های مورد انتظار تطابق داشته باشد می‌تواند سخت باشد.

جدول‌های رنگین کمانی

جدول‌های رنگین کمانی به‌طور مؤثری مشکل برخورد کردن با هش چین‌های معمولی را بوسیلهٔ جابجایی یک تابع کاهشی R با یک توالی از توابع مرتبط به R₁ از طریق R_k حل می‌کند. از این طریق برای اینکه دو زنجیره به هم برخورد کنند و ادغام شوند، آن‌ها باید به ولیوی مشترکی با تکراری یکسان برخورد کنند. در نتیجه در این حالت، آخرین ولیوها در هر زنجیره دارای یک هویت مختص به خود خواهند بود. آخرین پس پردازش رد شده می‌تواندزنجیره‌ها را در داخل جدول بچیند و هرگونه تکرار زنجیره‌هایی را که ولیوی نهایی مشترکی با سایر زنجیره‌ها دارند حذف کند. سپس زنجیره‌های جدید تولید می‌شوند تا داخل جدول را پر کنند، این زنجیره‌ها نیز از برخورد به هم مصون نیستند (می‌توانند بصورت کوتاه همپوشانی داشته باشند) اما آن‌ها ادغام نخواهند شد و به شدت آمار برخورد زنجیره‌ها به هم را کاهش می‌دهند.

استفاده از توالی توابع کاهشی نحوهٔ چگونگی انجام جستجو را تغییر داده‌است، زیرا هش ولیو مورد نظر می‌تواند در هر مکانی در زنجیره پیدا شود. این ضروری است که k زنجیره‌های متفاوت تولید شوند. اولین زنجیره فرض می‌کند که هش ولیو در موقعیت یکی مانده به آخر هش قرار گرفته‌است و R_K-1 را بکار می‌برد، سپس H، سپسR_K و … تا آخرین زنجیره که همهٔ توابع کاهشی را که با H متناوب هستند بکار می‌برد. این یک راه جدید برای تولید یک هشدار غلط ایجاد می‌کند، و اگر ما موقعیت هش ولیو را غلط حدس بزنیم در آن صورت باید بدون استفاده از آن یک زنجیره را ارزیابی کنیم.

اگرچه جدول‌های رنگین کمانی باید زنجیره‌های بیشتری را دنبال کنند، اما آن‌ها این مسئله را با داشتن جدول‌ها کمتر جبران می‌کنند. افزایش اندازهٔ هش چین‌های ساده نسبت به اندازهٔ مشخصی به دلیل ادغام زنجیره‌ها آن‌ها را ناکار آمد می‌کند؛ برای مقابله با این موضوع آن‌ها چندین جدول نگه داری می‌کنند و هر سرچی باید از یک جدول جداگانه صورت بگیرد. جدول‌های رنگین کمانی می‌توانند عملکرد مشابهی با جدولهایی که k بار از آن‌ها بزرگتر هستند داشته باشند و این نکته به آن‌ها اجازه می‌دهد که k فاکتور عملکرد جستحو را اجرا کنند.

مثال

1. با شروع از هش(re3xes) در تصویر پایین، یک جدول آخرین تقلیل (کاهش) استفاده شده در جدول را محاسبه می‌کند و چک می‌کند که آیا کد در آخرین ستون جدول ظاهر شده یا خیر (گام ۱)
2. اگر آزمایش شکست بخورد (رامبو در جدول ظاهر نمی‌شود) دیگری زنجیره را با تقلیل یکی مانده به آخر محاسبه می‌کند. (این دو تقلیل در گام دوم معرفی شده‌اند). (یادداشت:این تست‌های بعدی نیز شکست بخورند جدول‌های دیگری با تقلیل ۳ مانده به آخر، ۴ مانده به آخر و … ادامه می‌دهند. اگر هیچ زنجیره ای حامل پسورد مورد نظر نباشد در این صورت حمله شکست خورده‌است)
3. اگر تست مثبت باشد (گام ۳، لینوکس ۲۳ در آخرین زنجیره و جدول ظاهر می‌شود) پسورد (کد) در ابتدای زنجیره ای که لینوکس ۲۳ را تولید می‌کند بازیابی می‌شود، اینجا ما پسورد را در ابتدای زنجیره تطابقی ذخیره شده در جدول پیدا می‌کنیم
4. در این مرحله (گام ۴)یک جدول، زنجیره ای تولید می‌کند و آن را در هر تکرارهش با هش هدف (مورد نظر) مقایسه می‌کند. آزمایش به درستی انجام می‌شود و ماهش re3xes را در زنجیره پیدا می‌کنیم، پسورد کنونی culture، همان کدی است که کل زنجیره‌ها را تولید کرده‌است؛ حمله موفقیت‌آمیز بوده‌است.

جدول‌های رنگین کمانی از یک الگوریتم اصلاح شده با یک تابع کاهشی متفاوت برای هر لینک در یک زنجیره استفاده می‌کنند. در این صورت زمانیکه بین هش‌ها در حداقل دو زنجیره برخوردی اتفاق بیوفتد، تا زمانیکه در هر زنجیره برخوردی در یک موقعیت مشابه بین آن‌ها ایجاد نشود، زنجیره‌ها ادغام نخواهند شد. این احتمال کرک صحیح را برای یک جدول با اندازهٔ مشخص، البته با هزینه مجذور شدن تعداد گام‌های لازم برا ی هر جستجو افزایش می‌دهد. همانگونه جستجوی روتین (معمولی)، در حال حاضر همچنان به تکرار کردن فهرست اولین تابع کاهشی استفاده شده در زنجیره نیاز دارد.

جدول‌های رنگین کمانی مخصوص توابع در هم سازی هستند که برایشان ساخته شده‌است. برای مثال جدول‌های MD5 فقط هش‌های MD5 را می‌توانند کرک کنند. تئوری این تکنیک توسط فیلیپ اوکسلین بعنوان یک شکل سریع از تبادل زمان/حافظه اختراع شده بود، که او آن را در کشف گذرواژه ویندوز پیاده‌سازی کرده بود. قوی‌ترین برنامهٔ کرک رنگین کمانی بعداً بوجود آمد که می‌توانست جدول‌های رنگین کمانی را برای مجموعهٔ مشخصه‌های متفاوت برای هشینگ الگوریتم‌ها (الگوریتم‌های خرد شده) تولید و استفاده کند که شامل هش LM,MD5 و SHA-1 می‌شود.

در حالت ساده که تابع کاهشی باتابع درهم ساز هیچ برخوردی ندارد، دادن یک جدول رنگین کمانی کامل (که آن شما را برای پیدا کردن کد تطابق داده شده که از هر هش داده می‌شود، مطمئن می‌کند) به اندازهٔ سری پسورد |P| و به زمان T که زمان مورد نیاز برای محاسبهٔ جدول است، با طول جدول L و با t میانگین زمان مورد نیاز برای پیدا کردن کد مطابق با هش داده شده مستقیماً با هم در ارتباط اند؛$T=|P|$

$t={\frac {|P|}{2L}}$

بنابراین پسورد الفبایی ۸ رقمی با حروف کوچک (P|~۳*10¹²$\mid$) به راحتی با استفاده از یک کامپیوتر شخصی قابل ردیابی است، درحالیکه یک پسورد الفبایی ۱۶ رقمی با حروف کوچک (P|~10²⁵$\mid$) کاملاً برای جدول‌های رنگین کمانی یک دفاع غیرقابل ردیابی محسوب می‌شود.

حفاظت در برابر جدول‌های رنگین کمانی

یک جدول رنگین کمانی در مقابل هش‌های یکطرفه که شامل سالت (salt) بزرگ می‌باشند بی تأثیر است. برای مثال یک هش کد را در نظر بگیرید که با استفاده از دنبال کردن تابع روبرو تولید شده‌است. (که در آن "||" الحاق اپراتور است):

$saltedhash(password)=hash(password||salt)$

یا

$saltedhash(password)=hash(hash(password)||salt)$

سالت ولیو پنهان نیست و شاید بصورت تصادفی ساخته و با هش کد ذخیره شود. یک مقدار زیادی از سالت ولیو از حملات پیش پردازش جلوگیری می‌کند، که شامل جدول‌های رنگین کمانی نیز می‌باشد و اطمینان حاصل می‌کند که پسورد کاربران به‌طور منحصر به فردی هش شده (ریز شده) است. به این معنی که دو کاربر با پسوردی یکسان هش‌های متفاوتی خواهند داشت. (با فرض اینکه از سالت‌های متفاوتی استفاده شده‌است). برای رسیدن به نتیجه ای موفق مهاجم باید همهٔ جدول‌ها را برای هر سالت ولیو (میزان سالت) ممکن پیش پردازش کند. سالت باید به اندازهٔ کافی بزرگ باشد وگرنه مهاجم می‌تواند یک جدول برای هر سالت ولیو ایجاد کند. برای پسوردهای قدیمی یونیکس(unix) از سالت ۱۲ بیتی استفاده می‌شد؛ و این نیاز به ۴۰۹۶ عدد جدول داشت، که یک افزایش هزینهٔ قابل توجهی برای مهاجم داشت، ولی با توجه به هارد درایوهای (دیسک‌های سخت) ترابایتی غیر عملی نیز نبود. روش‌های SHA2-crypt و bcrypt که در LINUX و BSD Unixes و سولاریس استفاده می‌شوند سالت ۱۲۸ بیتی دارند. این سالت ولیوی بزرگ حمله در مقابل این سیستم‌ها را برای تقریباً هر مقدار کد (اینجا منظور از مقدار طول کد است) غیرقابل نفوذ می‌کند. حتی اگر مهاجم می‌توانست یک میلیون جدول در ثانیه ایجاد کند، باز هم او نیاز به میلیون‌ها سالت داشت تا جدول هارا برای همهٔ سالت‌های ممکن بسازد.

تکنیک دیگری که به جلوگیری از حمله‌های پیش پردازشی کمک می‌کند، بسط دادن کلیدی (key stretching) می‌باشد. وقتی از بسط دادن استفاده می‌شود، سالت، کد و بعضی از هش ولیوهای واسطه توسط تابع درهم ساز اصولی، چندین بار به اجرا در می‌آیند تا زمان محاسبهٔ مورد نیاز را برای هش کردن (خرد کردن) هر کد افزایش دهند. برای مثال MD5-CRYPT از ۱۰۰۰ لوپ (حلقه) تکراری استفاده می‌کند که به‌طور مداوم (پشت سر هم) سالت، کد و هش ولیوی واسطه را به تابع درهم ساز MD5 اصلی خود بازمی‌گرداند. هش کد کاربری دنباله سالت ولیو (که پنهان نیست) و هش نهایی می‌باشد. این زمان اضافه برای کار مورد توجه قرار نمی‌گیرد چون آن‌ها باید فقط چندین ثانیه صبر کنند هر دفعه که وارد سیستم می‌شوند. از طرفی بسط دادن تأثیرات حملهٔ بروت فورس را نیز در تناسب با تعداد تکرارها کاهش می‌دهد، زیرا تعداد تلاش‌هایی را که یک مهاجم می‌تواند در زمان داده شده مشخصی داشته باشد کاهش می‌دهد. این ویژگی‌ها در MD5 CRYPT و BYCRYPT اجرا شده‌اند. همچنین به مقدار زیادی زمان مورد نیاز را برای ایجاد یک پیش پردازش افزایش می‌دهد، اما به دلیل عدم وجود سالت این اتفاق تنها یک بار نمی‌تواند روی دهد.

یک رویکرد متناوب به دلیل تقویت کلیدی (key strengthening)، کلید را با یک سالت تصادفی گسترش می‌دهد. اما سپس (برخلاف عملکرد بسط کلیدی) بصورتی این سالت را حذف می‌کند. این هم مهاجمین و هم کاربران را مجبور به بکاربردن یک جستجوی بروت فورس برای سالت ولیو می‌کند. اگرچه مقاله ای که بسط دادن کلید را معرفی کرده بود به این تکنیکی که پیشتر توضیح دادیم (تقویت کلیدی) نیز اشاره کرده بود، ولی نام دیگری به آن داده بود. اصطلاح تقویت کلیدی در حال حاضر گاهی (شاید بصورت غلط) برای بسط کلیدی نیز استفاده می‌شود.

جدول‌های رنگین کمانی و سایر حملات پیش پردازشی در مقابل کد (پسورد)هایی که شامل سمبل‌ها یا علامت‌هایی خارج از حلقهٔ پیش فرض هستند یا آن‌هایی که بلندتر از پیش پردازش‌های مهاجمین هستند عمل نمی‌کنند. اگرچه جدول‌ها می‌توانند با راه‌های مشترکی که کاربرها انجام می‌دهند، برای انتخاب یک پسورد ایمن تر نیز ساخته شوند، راه‌هایی مانند:اضافه کردن یک عددیا مولفهٔ مخصوص به پسورد. به دلیل سرمایه‌گذاری قابل ملاحظه در پروسهٔ محاسبه کردن، جدول‌های رنگین کمانی که بالای ۱۴ خانه در طولشان دارند هنوز رایج نیستند؛ بنابراین انتخاب یک پسوردی که بیشتر از ۱۴ مولفه دارد ممکن است مهاجم را به روش بروت فورس متوسل کند.

تلاش‌های مخصوص و متمرکزی که بر روی LM هش (LM hash) تمرکز کرده و یک الگوریتم هش قدیمی استفاده شده توسط شرکت ماکروسافت همگی در دسترس عموم قرار دارند. هش LM منحصراً آسیب‌پذیر می‌باشد، زیرا پسوردها با بیش از ۷ مولفه، به دو بخش شکسته می‌شوند؛ که هر کدام از آن‌ها بصورت جداگانه هش شده (خرد شده) اند.انتخاب یک پسوردی که دارای ۱۵ مولفه یا بیشتر می‌باشد می‌تواند ضمانت کند که در این صورت هش LM ایجاد نخواهد شد.

استفادهٔ عام

تقریباً همهٔ توزیعات (محصولات) و تغییرات یونیکس، لینوکس و BSD از سالت‌ها استفاده می‌کنند؛ گرچه بسیاری از اپلیکیشن‌ها فقط از یک هش (معمولا MD5) بدون سالت، استفاده می‌کنند. ویندوز ماکروسافت نسخهٔ NT/2000 از LAN Manager و NT LAN manager با روش هشینگ (خرد کردن) (براساس MD4) استفاده می‌کند، که سالت نشده نیز می‌باشد و این مسئله آن را به یکی از معروف‌ترین جدول‌های تولید شده تبدیل کرده‌است.

جستارهای وابسته

• A5/1
• حمله جستجوی فراگیر

منابع

• Oechslin, Philippe (2003-08-17). Making a Faster Cryptanalytical Time-Memory Trade-Off (PDF). Lecture Notes in Computer Science. Santa Barbara, California, USA: Springer. ISBN 3-540-40674-3. Archived from the original (PDF) on 26 September 2007. Retrieved 21 December 2016.

پیوند به بیرون

• Ophcrack صفحه توسط فیلیپ Oechslin اصلی رنگین کمان، جدول پژوهش
• Cryptography در کرلی