Генерация Md5 rainbow tables по маске

Радужные таблицы это для быстрого подбора пароля. Т.е. сначала они должны быть, а потом ты быстро находишь пароль. Если их ещё нет, то обзаведись хорошей видяхой и ищи пароль, т.к. генерить их долго и места надо много.

есть и хороший комп, и видяхи, и время, и друзья готовые помочь ресурсами, только вот возможно ли вообще генерить таблицы по маске?

Тк в моём случае бессмысленно генерировать возможные пароли где буквы будут стоять дальше чем на первых 6 позициях

Если генерировать обычным способом, то в мире места не хватит для всех комбинаций 16 значного пароля состоящего из алфавита в 64 символа (64^16=2^96 комбинаций)

Учитывая что каждый хэш весит 16 байт то получим как минимум 16*2^96 =2^384 байт Радужка поможет сократить размер допустим в 2000 раз (если строка таблицы быдет в 2 к), но это нчтожная малась

По этому и вопрос, возможна ли генерация по маске

Hashcat умеет подбирать по маске, но насчет генерирования радужных таблиц не скажу. Кстати, не обязательно создавать таблицы, чтобы подбирать хеши параллельно.

только вот возможно ли вообще генерить таблицы по маске?

В смысле? Кто тебе мешает вообще?

for c1, c2, c3, c4, c5, c6, n1, n2, n3, n4, n5, n6, n7, n8
   table.add_unique(md5(c1 . c2 . c3 . c4. c5 . c6 . ":" . n1 . n2 . n3 . n4 . n5 . n6 . n7 . n8), c1 . c2 . c3 . c4. c5 . c6 . ":" . n1 . n2 . n3 . n4 . n5 . n6 . n7 . n8)

или тебе прям совсем готовое решение?

Тебе не нужны ВСЕ пароли, тебе нужны все ХЕШИ. Пароли могут иметь сколько угодно комбинаций, хеш на то и хеш, что он имеет коллизии.

А есть у кого примеры коллизий хешей коротких паролей (не более 10 символов) ?
Просто академический интерес.

64 бита пока доказанные. https://stackoverflow.com/a/4371834/2932207

Не совсем понял вас

Насколько мне известно радужные таблицы тем и хороши, что они не просто все хеши в себе содержат, а беря рандомный пароль получают от него хэш к которому применяют функцию редукции прлучая новый пароль от хеша (не обязательно соответствующий ему), выполняются допустим 2000 раз и записывается только первый и последний пароли, а при поиске эти промежутки допросчитываются

Так вот и вопрос, возможно ли сгенерировать радужную таблицу только для паролей неоюходимых мне (удовлетворяющих маске)

сколько угодно комбинаций, хеш имеет коллизии

Комбинаций в моём случае ограниченное колличество, и не думаю что на нём встетится достаточно много коллизий

Если генерировать обычным способом, то в мире места не хватит для всех комбинаций 16 значного пароля состоящего из алфавита в 64 символа (64^16=2^96 комбинаций)

XXXXXX:YY.YYYYYY, где X - буква, а Y - цифра.

Если X - латинская бува из ASCII набора, то их всего 52^6 + 8^10 цифр, ":" и "." - константы. Поэтому общее число комбинаций намного меньше (порядка 20 миллиардов).

20 млрд. * 16 ~ 320 Гб., что по нынешним временам не так уж и много.

Если X - латинская бува из ASCII набора, то их всего 52^6 + 8^10 цифр, ":" и "." - константы. Поэтому общее число комбинаций намного меньше (порядка 20 миллиардов).

Сорри, немного ступил. Конечно же 52^6 * 8^10 ~ 3.3 * 10^19, а не 2 * 10^10. Но всё равно намного меньше, чем 2^96 ~ 7.9 * 10^28. Поэтому, думаю, в этом направлении и стоит смотреть.

Ну тут и я не ного ошибался, и на память не точно воссоздал маску, на деле это всё таки не 6, а 8, и не букв а символов

XXXXXXXX:YY.YY<...>Y, X - символ, их как вы правильно заметили 52 да ещё и + 9 цифр = 61. Комбинаций 61^8. Что уже будет составлять слишком много (61^8*16 байт ~ 2789 Тб)

И это увы всего для одного числового значения, которых в свою очередь тоже достаточно много 9^8

Именно по этому я и склоняюсь в сторону радужных таблиц. Насколько я помню радужная таблица содержащая все комбинации 8 значных паролей (из латинского алфавита + цифры + спец символы типа звёздочки, запятых и кавычек) весит порядка 800 Гб против 2789 Тб для полного перебора

Если я правильно понял принцип построения радужных таблиц, то мне необходимо самому написать функцию редукции для получения из хэша нового пароля, как раз удовлетворяющего моей маске (в вики например для получения 8 значного цифрового пароля предлагают просто взять первые 8 цифр хэша), но мне то нужно чтоб получалось по маске и так чтоб всё таки свести к минимуму коллизии

А длина цепочки может быть такой, что временные затраты на её восполнения не должны превышать минуты, что достаточно много миллионы а может быть и миллиарды хэшей

Да и конкретная маска взята чисто для примера

Суть вопроса не поменялась бы даже если маска была XXX:YX/YYX:XXY.XYYXX-XY

И можно было бы назвать это радужной таблицей с солью, но это не совсем так, солью в моём случае являются лишь статичные : / . -

Маска всё таки ещё и задаёт свой набор алфавита для каждого символа последовательности

Если я не ршибаюсь конкретно в моём случае вообще после : идёт не 8, а 15 значное число

не 6, а 8, и не букв а символов

после : идёт не 8, а 15 значное число

Получать мне нужно в достаточно ограниченное время

Вот и соответсвенно вопрос, возможно ли это вообще?

Боюсь, что в достаточно ограниченное время - невозможно.

Как здесь уже сказали, радужные таблицы быстрее работают, когда они уже есть. Поэтому если надо создать задел на будущее, то можно потратить не знаю сколько времени и сгенерить их. Если же работа одноразовая (сейчас надо взломать какие-то хэши), то лучше воспользоваться существующими таблицами, удовлетворяющими набору символов и длине (если таковые есть, ведь 8+15+2==25 символов - достаточно длинный пароль). Или воспользоваться брустфорсом: всяко медленно, но, думаю, быстрее, чем генерить радужные таблицы. Сколько займёт времени - не скажу, но боюсь, что неприемлемо долго. Впрочем, можно проверить на ограниченном количестве переборов, а потом умножить.

Перебор не прокатит - слишком долго

Таблиц на 25 символов - нет, очень уж большие, но у меня и не 25. У меня 8 символов и 15 цифр (это намного меньше комбинаций даёт)

По этому и спрашивал как сгенерировать самому (пусть и долго, пусть месяц буду 24/7 генерить с друзьями) таблицы по маске, то есть не для каждого из 25 символов по 52 символа алфавита, а первые 8 - все комбинации, остальные только цифры. Это и есть маска

Видимо специализированных прог для этого нет и придётся писать самому, это быдет долго, сложно, но думаю справлюсь (надо будет язык подобрать оптимально быстрый, способ хранения (мб окажется что лучше сделать миллион таблиц по 32 гига нежели одну но большую, чтоб во время поиска не построчно считывать, а загружать в 32 гига оперативы и искать в них))

Пока что в этом направление и думаю, но нужна функция редукции, и если я правильно понял, мне нужно придумать самому такую ХЭШ функцию, которая получая МД5 хэш на вход будет выдавать комбинацию удовлетворяющую моей маске, а так же чтоб коллизии встречались статистически реже чем общее кол во моих паролей

Перебор не прокатит - слишком долго

Таблицы генерируются дольше, чем брутфорсятся все твои хеши вместе взятые. Скорость генерирования хеша и записи на диск равнозначна скорости сравнения сгенерированного хеша с твоим списком хешей.

Поиск по уже имеющимся радужным таблицам - быстрый, но генерирование - нет.

Перебор не прокатит - слишком долго

Я согласен с анонимусом. По сути, генерация таблиц - это генерация из хэша всех возможных паролей (в идеале) и генерация из них всех возможных хэшей, плюс запись всего этого на диск или диски. А потом, при чтении этих таблиц, хэши и пароли генерятся повторно, хоть и в меньшем количестве. Какая тут может быть экономия? Разве что на том, что в реальности будут подобраны не все возможные пароли, а только часть. Ну так и брутфорсить можно не все варианты, а выборочно (наудачу), - результат будет таким же, только быстрее.

Другое дело, если и в будущем потребуется много раз ломать точно такие же пароли. Тогда один раз сгенерить таблицы действительно может оказаться выгоднее, чем каждый раз брутфорсить.

это намного меньше комбинаций даёт

не 6, а 8, и не букв а символов
после : идёт не 8, а 15 значное число

62^8*10^15 ~ 2.18 * 10^29

Если генерировать обычным способом, то в мире места не хватит для всех комбинаций 16 значного пароля состоящего из алфавита в 64 символа (64^16=2^96 комбинаций)

2^96 ~ 7.9 * 10^28, что меньше, чем 2.18 * 10^29, которые мы получаем за счёт оптимизации на цифровой части.

Видимо специализированных прог для этого нет

Я думаю, что проги есть, но вот готовых таблиц для заданной маски скорее всего действительно нет. Уж больно специфический случай.

надо будет язык подобрать оптимально быстрый

Главное - это быстрый алгоритм. А язык может быть любой, лишь бы компилируемый, а не интерпретатор и не байт-код. Можно си. А ещё посмотреть в сторону оптимизирующих компиляторов. В gcc не самый лучший оптимизатор. Но всё это, думаю, не спасёт. Ведь даже если генерить за секунду 2 миллиарда хэшей (что мне представляется невероятным), для полного перебора потребуется порядка 10^20 секунд, т. е. порядка 10^15 суток. Даже если создать бот-нет из 10 млрд. компов (предполагаю, что это больше, чем существует в мире), то каждый комп должен будет отработать около 250 тыс. дней или около 700 лет.

мне нужно придумать самому такую ХЭШ функцию

Да, если есть 10 млрд. компов и 700 лет времени.

Я бы дождался появления квантовых процессоров. Думаю, это произойдёт быстрее.

Да я понимаю что всё долго, но радужные таблицы они на то и радужные, что не сохраняют все хэши, они лишь способны указать промежуток на котором верный пароль.

Например есть хэш N, и тогда пройдя по РАДУЖНОЙ таблице мы получаем, что хэш N принадлежит промежутку допустим от 10000 до 20000, а дальше обычным брутфорсом перебераются комбинации 10001, 10002...19999

У меня есть строгие рамки времени, если я буду брутфорсить свой хэш дольше 80 секунд, то он становится неактуален и генерируется новый.

Получается что это бессмысленно

Мне же хочется создать некую базу, и примерно за минуту находить в ней нужные хэши, многократно.

Ну а сколько времени будет генериться это уже не столь важно. Главное чтоб жизни хватило и места на диске.

Скорость генерации на самом деле упирается именно в скорость записи на диск, как вариант - использовать SSD но они больших размеров слишком уж дороги. Мб эксперементально получится быстрее генерить на SSD а потом в другом потоке переносить на хард. Мне кажется что один большой файл будет переноситься быстрее чем запись того же файла построчно.

Один и тот же алгоритм на разных языках может занимать разное время на выполнение. Пусть разница будет в сотую миллисекунды, но на 20 миллиардах хэшей даст значительную разницу

делаешь перебор в рамках своей маски, считаешь md5, сохраняешь куда-нибудь. не?

Да я понимаю что всё долго, но радужные таблицы они на то и радужные, что не сохраняют все хэши, они лишь способны указать промежуток на котором верный пароль.

Например есть хэш N, и тогда пройдя по РАДУЖНОЙ таблице мы получаем, что хэш N принадлежит промежутку допустим от 10000 до 20000, а дальше обычным брутфорсом перебераются комбинации

Но чтобы их сгенерить, нужен тот же бутфорс + обратная функция + запись этого всего на диск, т. е. по определению дольше.

У меня есть строгие рамки времени, если я буду брутфорсить свой хэш дольше 80 секунд, то он становится неактуален

Боюсь, что даже с помощью радужной таблицы в 80 сек. тут не уложиться.

Ну а сколько времени будет генериться это уже не столь важно. Главное чтоб жизни хватило

Ну, если жить 1000 лет, то может и хватит. Иначе не уверен.

Скорость генерации на самом деле упирается именно в скорость записи на диск

Не только. Ещё и в скорость генерации кэшей md5 и их «антихэшей».

Один и тот же алгоритм на разных языках может занимать разное время на выполнение.

Скорее, откомпилированный разными компиляторами. В принципе, можно написать компилятор для паскаля ничуть не хуже, чем для си. Возможно, там не будет каких-то возможностей по созданию разных трюков в силу ограничений языка, но в данном случае, думаю, эти трюки и не понадобятся. Хотя си считается системным, поэтому, думаю, к оптимизации там подходят серьёзнее, чем в реализациях компиляторов для других языков. Однако и си-компиляторы бывают разные. Например, для процессоров x86 компилятор от Intel оптимизирует лучше, чем gcc со всеми возможными флагами оптимизации типа -O3 и т. д. Однако главный оптимизатор - программист, выбравший оптимальный алгоритм. Хотя в данном случае, думаю, никакой алгоритм не спасёт.

делаешь перебор в рамках своей маски, считаешь md5, сохраняешь куда-нибудь. не?

2.18 * 10^29 (это число вариантов) умножаем на 16 байт (размер md5-суммы).

Получаем ~ 3.5 * 10^30 байт.

Это куда же надо сохранять такое?

На 3 миллиона триллионов терабайтных дисков?

А на Земле такое количество дисков найдётся?

Ну я постараюсь что нибудь придумать) в любом случае спасибо!

Если получится - отпишусь. А после того как вероятную «уязвимость» исправят админы сервиса ещё и статью написать постараюсь)

И пусть в теории это невозможно, когда то ведь столкнулись с такой же проблемой и изобрели радужные таблицы, чем я хуже)

Тогда удачи. В любом случае, отсутствие результата - тоже результат. :-)