Как сделать радужную таблицу

Добавил пользователь Skiper
Обновлено: 04.10.2024

Windows Password Recovery - атака по таблицам Passcape

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

Принцип действия простых радужных таблиц

Принцип действия простых радужных таблиц состоит в задании диапазона символов (например, a..z) и максимальной длины пароля. Затем просчитываются все возможные варианты и создаются миллионы цепочек. Каждая цепочка вычисляется по следующей формуле:

P0 -> hash(P0) -> H1 -> R(H1) ->
P1 -> hash(P1) -> H2 -> R(H2) ->
P2 .

где P - пароль, hash - функция хэширования, R - функция редукции. Таким образом из первоначального пароля с помощью функции хэширования получается хэш, из которого на выходе функции редукции получается следующий пароль и процесс повторяется сначала, что ведет к созданию цепочек. В каждой такой цепочке сохраняется только первоначальное и конечное значение. Хранение только первого и последнего элементов является операцией, ведущей к компромиссу, сохраняя память за счет временных затрат на криптоанализ.

Для восстановления искомого пароля, он подвергается хэшированию и функции редукции, а затем ищется в таблице. Для этого создается цепочка ключей, начиная с R(Hn) до максимальной длины цепочки. Если Hn окажется полученным с помощью пароля, использованного при создании таблицы, то мы в итоге получим ключ, соответствующий последнему ключу соответствующей цепочки. Этот последний ключ был сохранен в таблице вместе с первым ключом цепочки. Используя первый ключ цепочки, возможно восстановить всю цепочку – в частности, значение, стоящее перед R(Hn). Это и есть тот ключ, который использовался для генерации Hn, т.е. наш искомый пароль.

Принцип действия радужных таблиц Passcape

Поиск с использованием радужных таблица Passcape во многом схож с поиском по простым таблицам. Но в отличие от последних, он является чем-то вроде гибрида идентификационной и простой табличной атаки, где проверка паролей производится не в заданном диапазоне символов, а в диапазоне т.н. отпечатков слов. Суть идентификационной атаки, разработанной в Passcape, сводится к тому что из исходного словаря создается банк отпечатков слов, необходимых для проверки пароля, а во время атаки производится поиск всех возможных вариантов слов, состоящих из двух таких отпечатков.

Подобно идентификационной атаке, в радужных таблицах Passcape в начале происходит создание банка отпечатков слов из заданного пользователем словаря. Банк отпечатков слов является аналогом диапазона символов в простых радужных таблицах. Он используется как при генерации Passcape таблиц, так и при проверке пароля. Таким образом, радужная таблица Passcape состоит из одной или нескольких файлов *.prt (непосредственно самих таблиц) и банка отпечатков (*.prti), который может быть задействован только с созданными с помощью него таблицами.

Использование отпечатков слов вместо диапазона символов при создании таблиц имеет ряд преимуществ:

Длина проверяемых паролей в таблицах Passcape практически неограничена. В отличие от простых радужных таблиц, создание которых для паролей длиной более 9 символов на практике не представляется возможным, в таблицах Passcape с одинаковой долей вероятности можно найти как односимвольный, так и 50-символьный пароль.
Диапазон символов в обычной таблице сильно влияет на ее критические параметры: чем шире диапазон символов, тем больше должна быть длина цепочки или общее количество цепочек для сохранения success rate (процент успеха при поиске пароля) этой таблицы. В таблице Passcape диапазон символов не влияет на критические параметры таблицы.
В обычных таблицах имеются определенные сложности при создании таблиц для проверки паролей в национальных кодировках: не все программы корректно работают с такими таблицами, не все могут их создавать. В радужных таблицах Passcape при создании таблиц, например, для русских паролей, достаточно задать исходный словарь на русском языке.
Поиск паролей в Passcape таблицах осуществляется по более осмысленным комбинациям, однако это в значительной степени зависит от исходного словаря.

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

Настройки атаки по радужным таблицам Passcape

Опции атаки по радужным таблицам Passcape довольно тривиальны. Необходимо указать один или несколько *.prt таблиц в одном каталоге с которыми должен находиться банк отпечатков (*.prti файл). Поскольку данная атака потребляет больше памяти, чем атака с использованием обычных радужных таблиц, рекомендуется ограничить объем потребляемой памяти, выставив соответствующую опцию.

Для создания своих собственных таблиц, воспользуйтесь соответствующим инструментом.

С нашего сайта можно скачать несколько Passcape таблиц для данной атаки.

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

Радужная таблица (англ. rainbow table) — специальный вариант таблиц поиска (англ. lookup table) для обращения криптографических хеш-функций, использующий механизм разумного компромисса между временем поиска по таблице и занимаемой памятью (англ. time-memory tradeoff). Радужные таблицы используются для вскрытия паролей, преобразованных при помощи сложнообратимой хеш-функции, а также для атак на симметричные шифры на основе известного открытого текста. Использование функции формирования ключа с применением соли делает эту атаку неосуществимой.
Радужные таблицы являются развитием более раннего и простого алгоритма, предложенного Мартином Хеллманом.

Предпосылки к появлению

Компьютерные системы, которые используют пароли для аутентификации, должны каким-то образом определять правильность введённого пароля. Самым простым способом решения данной проблемы является хранение списка всех допустимых паролей для каждого пользователя. Минусом данного метода является то, что в случае несанкционированного доступа к списку злоумышленник узнаёт все пользовательские пароли. Более распространённый подход заключается в хранении значений криптографической хеш-функции от парольной фразы. Однако большинство хешей быстро вычисляется, поэтому злоумышленник, получивший доступ к хешам, может быстро проверить список возможных паролей на валидность. Чтобы избежать этого, нужно использовать более длинные пароли, тем самым увеличивая список паролей, которые должен проверить злоумышленник. Для простых паролей, не содержащих соли, взломщик может заранее подсчитать значения хешей для всех распространённых и коротких паролей и сохранить их в таблице. Теперь можно быстро найти совпадение в заранее полученной таблице. Но чем длиннее пароль, тем больше таблица, и тем больше памяти необходимо для её хранения. Альтернативным вариантом является хранение только первых элементов цепочек хешей. Это потребует больше вычислений для поиска пароля, но значительно уменьшит количество требуемой памяти. А радужные таблицы являются улучшенным вариантом данного метода, которые позволяют избежать коллизий.

Предрассчитанные цепочки хешей

Цепочки хешей, описанные в этой статье, отличаются от описанных в статье Цепочка хешей.

Пусть у нас есть хеш-функция H с длиной хеша n и конечное множество паролей P. Наша цель — создать структуру данных, которая для любого значения хеша h может либо найти такой элемент p из P, что H(p)=h, либо определить, что такого элемента не существует. Простейший способ сделать это — вычислить H(p) для всех p из P, но для хранения такой таблицы потребуется Θ(|P|n) памяти, что слишком много.

Цепочки хешей — метод для уменьшения этого требования к объёму памяти. Главная идея — определение функции редукции R, которая сопоставляет значениям хеша значения из P. Заметим, что R не является обращением хеш-функции. Начиная с исходного пароля и попеременно применяя к каждому полученному значению H и R, мы получим цепочку перемежающихся паролей и хешей. Например, для набора паролей длиной в 6 символов и хеш-функции, выдающей 32-битные значения, цепочка может выглядеть так:

К функции редукции предъявляется единственное требование: возвращать значения из того же алфавита, что и пароли.

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

Для каждого хеша h, значение которого мы хотим обратить (найти соответствующий ему пароль), вычисляем последовательность R(…R(H(R(h)))…). Если какое-то из промежуточных значений совпадёт с каким-нибудь концом какой-либо цепочки, мы берём начало этой цепочки и восстанавливаем её полностью. С высокой вероятностью полная цепочка будет содержать значение хеша h, а предшествующий ему пароль будет искомым.

Для примера, указанного выше, если у нас изначально есть хеш 920ECF10, он породит следующую последовательность:

Поскольку kiebgt является концом цепочки из нашей таблицы, мы берём соответствующий начальный пароль aaaaaa и вычисляем цепочку, пока не найдём хеш 920ECF10:

Таким образом, искомый пароль — sgfnyd.

Стоит заметить, что восстановленная цепочка не всегда содержит искомое значение хеша h. Такое возможно при возникновении коллизии функции H или R. Например, пусть дан хеш FB107E70, который на определенном этапе порождает пароль kiebgt:

Но FB107E70 не появляется в цепочке, порождённой паролем aaaaaa. Это называется ложным срабатыванием. В этом случае мы игнорируем совпадение и продолжаем вычислять последовательность, порождённую h. Если сгенерированная последовательность достигает длины k без хороших совпадений, это означает, что искомый пароль никогда не встречался в предвычисленных цепочках.

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

Простые цепочки хешей имеют несколько недостатков. Самый серьёзный — возможность слияния двух цепочек в одну (генерация одного и того же значения в разных цепочках). Все значения, сгенерированные после слияния, будут одинаковыми в обеих цепочках, что сужает количество покрываемых паролей. Поскольку прегенерированные цепочки сохраняются не целиком, невозможно эффективно сравнивать все сгенерированные значения между собой. Как правило, об отсутствии коллизий в хеш-функции H заботится сторона, обеспечивающая шифрование паролей, поэтому основная проблема кроется в функции редукции R.

Другая серьёзная проблема — подбор такой функции R, которая будет генерировать пароли с требуемым покрытием и распределением. Ограничение выходного алфавита является серьёзным ограничением для выбора такой функции.

Радужные таблицы

Радужные таблицы являются развитием идеи таблицы хеш-цепочек. Они эффективно решают проблему коллизий путём введения последовательности функций редукции R1, R2, …, Rk. Функции редукции применяются по очереди, перемежаясь с функцией хеширования: H, R1, H, R2, …, H, Rk. При таком подходе две цепочки могут слиться только при совпадении значений на одной и той же итерации. Следовательно, достаточно проверять на коллизии только конечные значения цепочек, что не требует дополнительной памяти. На конечном этапе составления таблицы можно найти все слившиеся цепочки, оставить из них только одну и сгенерировать новые, чтобы заполнить таблицу необходимым количеством различных цепочек. Полученные цепочки не являются полностью свободными от коллизий, тем не менее, они не сольются полностью.

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

первая цепочка строится в предположении, что искомый хеш встретится на последней позиции в табличной цепочке, поэтому состоит из единственного значения Rk(h);
вторая цепочка строится в предположении, что искомый хеш встретится на предпоследней позиции в табличной цепочке, поэтому выглядит так: Rk(H(Rk−1(h)));
аналогично, наращивая длину цепочки и применяя функции редукции с меньшими номерами, получаем остальные цепочки. Последняя цепочка будет иметь длину k и содержать все функции редукции: Rk(H(Rk−1(H(…H(R1(h))…))))

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

Пример

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

Время и память

Радужная таблица создаётся построением цепочек возможных паролей. Создание таких таблиц требует больше времени, чем нужно для создания обычных таблиц поиска, но значительно меньше памяти (вплоть до сотен гигабайт, при объёме для обычных таблиц в N слов для радужных нужно всего порядка N2/3). При этом они требуют хоть и больше времени (по сравнению с простыми методами вроде атаки по словарю) на восстановление исходного пароля, но на практике более реализуемы (для построения обычной таблицы для 6-символьного пароля с байтовыми символами потребуется 2566 = 281 474 976 710 656 блоков памяти, в то время как для радужной — всего 2566·⅔ = 4 294 967 296 блоков).

Таблицы могут взламывать только ту хеш-функцию, для которой они создавались, то есть таблицы для MD5 могут взломать только хеш MD5. Теория данной технологии была разработана Philippe Oechslin как быстрый вариант time-memory tradeoff. Впервые технология использована в программе Ophcrack для взлома хешей LanMan (LM-хеш), используемых в Microsoft Windows. Позже была разработана более совершенная программа RainbowCrack, которая может работать с большим количеством хешей, например, LanMan, MD5, SHA1 и другими.

Следующим шагом было создание программы The UDC, которая позволяет строить Hybrid Rainbow таблицы не по набору символов, а по набору словарей, что позволяет восстанавливать более длинные пароли (фактически неограниченной длины).

Применение

При генерации таблиц важно найти наилучшее соотношения взаимосвязанных параметров:

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

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

допустимый набор символов;
длина пароля;
длина цепочки;
количество таблиц.

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

длина цепочки — 1400
количество цепочек — 50 000 000
количество таблиц — 800

При этом вероятность нахождения пароля с помощью данных таблиц составит 0,7542 (75,42 %), сами таблицы займут 596 ГиБ, генерация их на компьютере уровня Пентиум-3 1 ГГц займёт 3 года, а поиск 1 пароля по готовым таблицам — не более 22 минут.

Однако процесс генерации таблиц возможно распараллелить, например, расчёт одной таблицы с вышеприведёнными параметрами занимает примерно 33 часа. В таком случае, если в нашем распоряжении есть 100 компьютеров, все таблицы можно сгенерировать через 11 суток.

Защита от радужных таблиц

хеш = MD5( пароль + соль )

Для восстановления такого пароля взломщику необходимы таблицы для всех возможных значений соли. При использовании такой схемы, соль должна быть достаточно длинной (6‒8 символов), иначе злоумышленник может вычислить таблицы для каждого значения соли, случайной и различной для каждого пароля. Таким образом два одинаковых пароля будут иметь разные значения хешей, если только не будет использоваться одинаковая соль.

По сути, соль увеличивает длину и, возможно, сложность пароля. Если таблица рассчитана на некоторую длину или на некоторый ограниченный набор символов, то соль может предотвратить восстановление пароля. Например, в старых Unix-паролях использовалась соль, размер которой составлял всего лишь 12 бит. Для взлома таких паролей злоумышленнику нужно было посчитать всего 4096 таблиц, которые можно свободно хранить на терабайтных жёстких дисках. Поэтому в современных приложениях стараются использовать более длинную соль. Например, в алгоритме хеширования bcrypt используется соль размером 128 бит. Подобная длина соли делает предварительные вычисления просто бессмысленными. Другим возможным способом борьбы против атак, использующих предварительные вычисления, является растяжение ключа (англ. key stretching). Например:

ключ = хеш(пароль + соль) for 1 to 65536 do ключ = хеш(ключ + пароль + соль)

Использование

Мне необходимо имея md5 хэш получить его значение, причём это не просто там обычный пароль, а построенный по некой структуре: 6 случайных символов англ алфавита после него двоеточие и десятичное число от 0 до 100, но с 6 знаками после запятой.

Получать мне нужно в достаточно ограниченное время, по этому решил использовать именно радужные таблицы, но сгенерировать мне их надо по некой маске XXXXXX:YY.YYYYYY, где X - буква, а Y - цифра.

Вот и соответсвенно вопрос, возможно ли это вообще? И если да, то какими способами? И если не сложно ссылки где можно почитать

Если нет, то каким образом это дело лучше реализовать?

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

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

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

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

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

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

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

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

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

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

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

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

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

Насколько мне известно радужные таблицы тем и хороши, что они не просто все хеши в себе содержат, а беря рандомный пароль получают от него хэш к которому применяют функцию редукции прлучая новый пароль от хеша (не обязательно соответствующий ему), выполняются допустим 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 значное число

после : идёт не 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 лет, то может и хватит. Иначе не уверен.

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

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

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

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

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

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

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

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

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

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

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

Схема упрощенной радужной таблицы с длиной цепочек равной трем. R1 R2 R3 - функции редукции, H - функция хеширования.

Радужная таблица (англ. rainbow table ) — специальный вариант таблиц поиска (англ. lookup table ), использующий механизм разумного компромисса между временем поиска по таблице и занимаемой памятью (time-memory tradeoff). Радужные таблицы используются для вскрытия паролей, преобразованных при помощи сложнообратимой хеш-функции, а также для атак на симметричные шифры на основе известного открытого текста.

Содержание

Предпосылки к появлению

Компьютерные системы, которые используют пароли для аутентификации, должны каким-то образом определять правильность введенного пароля. Самым простым способом решения данной проблемы является хранение списка всех допустимых паролей для каждого пользователя. Минусом данного метода является то, что в случае несанкционированного доступа к списку злоумышленник узнает все пользовательские пароли. Более распространенный подход заключается в хранении значений криптографической хеш-функции от парольной фразы. Однако большинство хешей быстро вычисляются, поэтому злоумышленник, получивший доступ к хешам, может быстро проверить список возможных паролей на валидность. Чтобы избежать этого, нужно использовать более длинные пароли, тем самым увеличивая список паролей, которые должен проверить злоумышленник. Для простых паролей, не содержащих соль, взломщик может заранее подсчитать значения хешей для всех распространенных и коротких паролей и сохранить их в таблице. Теперь можно быстро найти совпадение в заранее полученной таблице. Но чем длиннее пароль, тем больше таблица, и необходимо больше памяти для её хранения. Альтернативным вариантом является хранение только первых элементов цепочек хэшей. Это потребует больше вычислений для поиска пароля, но значительно уменьшит количество требуемой памяти. А радужные таблицы являются улучшенным вариантом данного метода, которые позволяют избежать коллизий.

Теория

Радужная таблица создается построением цепочек возможных паролей. Каждая цепочка начинается со случайного возможного пароля, затем подвергается действию хеш-функции и функции редукции. Данная функция преобразует результат хеш-функции в некоторый возможный пароль (например, если мы предполагаем, что пароль имеет длину 64 бита, то функцией редукции может быть взятие первых 64 бит хеша, побитовое сложение всех 64-битных блоков хеша и т. п.). Промежуточные пароли в цепочке отбрасываются и в таблицу записываются только первый и последний элементы цепочек. Создание таких таблиц требует больше времени, чем нужно для создания обычных таблиц поиска, но значительно меньше памяти (вплоть до сотен гигабайт, при объёме для обычных таблиц в N слов для радужных нужно всего порядка N 2/3 ). При этом они требуют хоть и больше времени (по сравнению с обычными методами) на восстановление исходного пароля, но на практике более реализуемы (для построения обычной таблицы для 6-символьного пароля с байтовыми символами потребуется 256 6 = 281 474 976 710 656 блоков памяти, в то время как для радужной — всего 256 6·⅔ = 4 294 967 296 блоков).

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

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

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

Таблицы могут взламывать только ту хеш-функцию, для которой они создавались, то есть таблицы для MD5 могут взломать только хеш MD5. Теория данной технологии была разработана Philippe Oechslin [1] как быстрый вариант time-memory tradeoff [2] . Впервые технология использована в программе Ophcrack для взлома хешей LanMan (LM-хеш), используемых в Microsoft Windows. Позже была разработана более совершенная программа RainbowCrack, которая может работать с большим количеством хешей, например LanMan, MD5, SHA1 и др.

Применение

При генерации таблиц важно найти наилучшее соотношения взаимосвязанных параметров:

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

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

допустимый набор символов;
длина пароля;
длина цепочки;
количество таблиц.

длина цепочки 1400
количество цепочек 50 000 000
количество таблиц 800

При этом вероятность нахождения пароля с помощью данных таблиц составит 0.7542 (75.42 %), сами таблицы займут 596 Гб, генерация их на компьютере уровня Пентиум-3 1ГГц займёт 3 года, а поиск 1 пароля по готовым таблицам не более 22 минут.

Однако процесс генерации таблиц возможно распараллелить, например расчёт одной таблицы с вышеприведёнными параметрами занимает примерно 33 часа. В таком случае если в нашем распоряжении есть 100 компьютеров, все таблицы можно сгенерировать через 11 суток.

Защита от радужных таблиц

Для восстановления такого пароля взломщику необходимы таблицы для всех возможных значений затравки. При использовании такой схемы, затравка должна быть достаточно длинной (6-8 символов), иначе злоумышленник может вычислить таблицы для каждого значения затравки, случайной и различной для каждого пароля. Таким образом два одинаковых пароля будут иметь разные значения хешей, если только не будет использоваться одинаковая затравка.

По сути, затравка увеличивает длину и, возможно, сложность пароля. Если таблица рассчитана на некоторую длину или на некоторый ограниченный набор символов, то затравка может предотвратить восстановление пароля.Например, в старых Unix паролях использовалась затравка, размер которой составлял всего лишь 12 бит. Для взлома таких паролей злоумышленнику нужно было посчитать 4096 таблиц, что можно свободно хранить на терабайтных жестких дисках. Такие же алгоритмы хеширования, как MD5 и bcrypt используют затравку размером 48 и 128 бит соответственно. [3] Такие большие длины затравки делают предварительные вычисления просто бессмысленными. Другим возможным способом борьбы против атак, использующие предварительные вычисления, является растяжение ключа(англ. key stretching ).Например:

Этот способ снижает эффективность применения предварительных вычислений, так как использование промежуточных значений увеличивает время, которое необходимо для вычисления одного пароля, и тем самым уменьшает количество вычислений, которые злоумышленник может произвести в установленные временные рамки. [4] Данный метод применяется в следующих алгоритмах хеширования: MD5, в котором используется 1000 повторений, и bcrypt. [5] Альтернативным вариантом является использование усиление ключа(англ. key strengthening ), который часто принимают за растяжение ключа. Применяя данный метод, мы увеличиваем размер ключа за счет добавки случайной затравки, которая затем спокойно удаляется, в отличие от растяжения ключа, когда затравка сохраняется и используется в следующих итерациях. [6] Также рассмотрим LM-хеш – это старый алгоритм хеширования, который используется в Microsoft. Он чрезвычайно уязвим, так пароль, состоящий больше, чем из 7 символов, но меньше, чем из 15 символов, разбивается на две части, которые хешируютя независимо друг от друга. Поэтому, чтобы избежать создания LM-хеша, необходимо использовать пароли из 15 символов и более. [7]

Использование

Практически все дистрибутивы ОС Unix, GNU/Linux и BSD используют хеши с солью для хранения системных паролей, хотя многие приложения, например, интернет-скрипты используют простой хеш (обычно MD5) без "соли". ОС Microsoft Windows и Windows NT используют хеши LM-хеш и NTLM, которые также не используют "соль", что делает их самыми популярными для создания радужных таблиц.

Затем я воспользовался выше описанной программой (текущая стабильная версия — 0.6.6), создав крохотный bat-файл:

:: Здесь лежат радужные таблицы
set RainbowTables=C:\RainbowTables\RainbowTables
:: Здесь лежат файлы hash.txt (должен содержать хэши, к которым нужно подобрать праоль) и pass.txt (файл, куда будут записываться найденные пароли)
set Path=C:\RainbowTables\
:: Путь до программы
set rcracki_mt=C:\RainbowTables\rcracki_mt_0.6\rcracki_mt.exe

:: Команда запуска программы (подробное описание параметров программы можно посмотреть в файле README.txt)
%rcracki_mt% -l %Path%\hash.txt %RainbowTables% -t 2 -o %Path%\pass.txt

В файл hash.txt я поместил всего одну хэш-запись от известного мне пароля. Я был поражен быстротой поиска пароля по известному хэшу с помощью радужных таблиц — не прошло и 20 секунд, как программа вывела мне мой хэшированный пароль.

Результат нахождения пароля, используя радужные таблицы

Читайте также: