Rainbow маси у дома
Изминалата седмица беше изключително „успешна“ по отношение на информационната сигурност: или хеш базата данни на LinkedIn беше изтекла в мрежата, или last.fm хешовете. И във всички дискусии по един или друг начин се споменаваттаблици на дъгата. Почти всеки е чувал за тях, но много малко са ги правили със собствените си ръце. Мисля, че не е разумно да се преразказва какво е хеш и защо по принцип са нужни дъгови таблици или някакви други предварителни изчисления. За премахване на бели петна се предлага да прочетете тази тема.
Днес не се планира интелектуален пробив в областта на дъговите таблици, но има желание да се каже, че дъговите таблици не са трудни, така че ще напишем нещо просто, а именно: PHP. Съхранявайте таблица в MySQL.
Целият код е наличен в GoogleCode, но ще опиша основните моменти, върху които трябваше да помисля и които трябва да бъдат внедрени.
Първо трябва да поговорим за азбуката за въвеждане. Не всички ASCII знаци от таблицата са включени в набора от пароли, а само тези, които могат да бъдат въведени без излишни трикове на клавиатурата на компютър или мобилно устройство. Колкото по-малка е въведената азбука, толкова по-бързо ще се генерира дъговата таблица, но ще има по-малко пароли за дадени хешове. В нашия случай ще използваме въведената азбука от цифри и букви от латинската азбука от главни и малки букви.
За създаване на дъгова таблица се използват вериги, чието начало е произволна парола с фиксирана дължина. Очевидно е необходима функция за генериране на произволни пароли от знаците на въведената азбука:
Във веригите последователно се прилага или функцията за хеширане, или функцията за намаляване. С хеш функцията всичко е ясно - това е MD5, SHA1 или всяка друга (в нашия случай ще използваме MD5). С функцията за намаляване има по-малко яснота. Първо, функциятаредукция, след като получи хеш на входа, трябва да издаде някаква парола от символите на входната азбука. Второ, редукционната функция изисква не само една, а подреден набор от редукционни функции и мощността на този набор е равна на дължината на веригата.
Разбира се, можете сами да напишете две или три редукционни функции, но не и в случая, когато дължината на веригата е 100 или 1000. Освен това бих искал дължината на веригата да се съхранява в константа, която може да бъде заменена с леко движение на ръката.
Едно доста очевидно решение идва на ум: трябва да използвате генератор на псевдослучайни числа (PRNG). За всяка конкретна редукционна функция инициализирайте PRNG с определен набор от битове от входния хеш и след това вземете паролата с помощта на извикването getWord().
По принцип не се изисква да се действа на ниво отделни битове. Трябва да инициализирате PRNG с int число, за моята платформа е 32 бита или 4 байта. MD5 се състои от 16 байта (вижте втория параметър на функцията md5 на PHP), тогава броят на възможните разпределения е 16! / (16 - 4)! = 43680 - дори за дължина на веригата от 1000 достатъчно с марж.
Тогава действителната редукционна функция, която приема хеш и номера на текущата стъпка във веригата като вход, ще изглежда така:
Като се вземе предвид всичко по-горе, функцията за изчисляване на края на веригата от нейното начало е тривиална:
Поздравления, свършихме много работа и има само един аспект от намирането на парола с хеш, който трябва да се каже.
В класическата версия се взема последната n-та редукционна функция от хеша и получената парола се търси в таблицата на дъгата, ако не се намери нищо, се взема n-1 редукция, след това се изчислява хешът, след това n-тата редукция се търси в таблицата и така нататък, докато се намери паролата. ИзползвайкиMySQL, това може да доведе до n SELECT от един и същи тип (в най-лошия случай) - дори начинаещ уеб програмист знае какво можете да получите за това! Разбира се, един SELECT е достатъчен за търсене на една парола, но за това е необходимо да генерирате всички пароли за търсене наведнъж:
Всички други манипулации с MySQL не са пряко свързани с таблиците на дъгата, а други части от изходния код според мен са ясни без обяснение.
И накрая, муха в мехлема. PHP и MySQL са страхотни за бързо създаване на прототипи, но PHP наистина не е най-бързият език и съхраняването на дъгова таблица в релационна СУБД с общо предназначение не е най-ефективното решение. Генерирането на дъгова таблица MD5 за 6-символни пароли с дължина на веригата 1000 от 2 милиона записа отне над 8 часа. В идеалния случай получената таблица може да обърне 2*10^9 хешове, но това число не е съизмеримо с общия брой 6-символни пароли, които са 56,8*10^9 в избраната азбука за въвеждане.
Това още веднъж показва колко е важно да изберете правилния инструмент за конкретна задача. Мисля, че успях да реша задачата за визуална демонстрация на принципа на внедряване на дъгови таблици заедно с PHP.
Благодаря за вниманието.
И тук можете да получите грант за тестов период на Yandex.Cloud. Необходимо е само да въведете "Habr" в полето "секретна парола".