Understanding BruteForce — RainbowTables and Dictionary Attacks
A powerful tool for decrypting passwords.A rainbow table is a precomputed table for caching the output of cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering a key derivation function (or credit card numbers, etc.) up to a certain length consisting of a limited set of characters.
Unlike bruteforce attack, which works by calculating the hash function of every string present with them, calculating their hash value and then compare it with the one in the computer, at every step. A rainbow table attack eliminates this need by already computing hashes of the large set of available strings.
Hash Function
Some hash algorithms used in Rainbow Tables are given below.
Reduction function
RainbowTable files are very large, though. So that the required storage space doesn’t get out of hand, rainbow tables use a reduction function that change the hash value into plaintext. Important: The reduction function doesn’t reverse the hash value, so it doesn’t output the original plaintext (i.e. the password) — because this isn’t possible — but instead outputs a completely new one.
A new hash value is them generated from this text. In a rainbow table, this takes place not only one time, but many times, resulting in a chain. In the final table, however, only the first password and the last hash value of a chain appear.
WorkFlow
Some Tools
- Rainbow Crack — used for practical example
- CrackStation (Online)
- John the Ripper
Practical Example —using rainbowCrack tool
- Creating rainbow table
- Hash : md5sum
- Charset : loweralpha
- Lengthpassword: 1–7
- Chain length: 3800
- Number of Chains : 333554
2. Sorting data in the generated table. As rainbow table is searched using Binary Search.
3. Generating MD5 hash for Plaintext : Ayush
4. Using rcrack to crack hash using generated rainbow table.
See the last line of above image, cool huh. Succesfully performed rainbow table attack.
Time Memory Trade-off
A time-memory tradeoff is basically when you accept a longer runtime in favor of fewer memory requirements — or the other way around. A table, on the other hand, in which billions of passwords are presented together with their hash values, takes up an enormous amount of storage space, but can very quickly run decryptions. Rainbow tables represent a compromise of both. In principle, they also perform real-time calculations, but to a lesser extent, and so save a lot of storage space compared to complete tables.
Disadvantages
Rainbow table attacks, can be thwarted by the use of salt (you don’t have to sprinkle it. lol.) , a technique that forces the hash dictionary to be recomputed for each password sought, making precomputation infeasible, provided that the number of possible salt values is large enough.
Salts are a random token (usually used only once) that is combined with the password before hashing.It artificially increases the length of a password in the rainbow table (so to crack a 4 character password with a 4 character salt, you’d need to generate an 8 character rainbow table).
Protective Measures
- Don’t use MD5 or SHA1 in your password hashing function. MD5 and SHA1 are outdated password hashing algorithms. Consider using more modern hashing methods like SHA2.
- Use a cryptographic “Salt” in your password hashing routine.
Dictionary Attack
Overview
A Dictionary Attack as an attack vector used by the attacker to break in a system, which is password protected, by putting technically every word in a dictionary as a form of password for that system. This attack vector is a form of Brute Force Attack.
A dictionary attack is based on trying all the strings in a pre-arranged listing. Such attacks originally used words one would find in a dictionary (hence the phrase dictionary attack).
Working
A dictionary attack tries only those possibilities which are deemed most likely to succeed. Dictionary attacks often succeed because many people have a tendency to choose short passwords that are ordinary words or common passwords, or variants obtained, for example, by appending a digit or punctuation character.
Dictionary attacks are difficult to defeat, since most common password creations techniques are covered by the available lists, combined with cracking software pattern generation. A safer approach is to randomly generate a long password (15 letters or more) or a multi word passphrase, using a password manager program or a manual method.
Some Tools
- John the Ripper — used here. Yeah boyyy…
- L0phtCrack
- Metasploit Project
- Ophcrack
- Hashcat
- Mentalist — Password Manager (refer next sub-heading)
Password Manager
To boost productivity of this attack. Password manager are used which customize the list based on our requirement so more contracted and efficient list can be created for lookup.
One such tool is — mentalist. It asks various questions like name, DOB, age, phone, family, pet name, favourite food etc. and prepares a list of passwords accordingly which can be used for attack.
Protective Measures
You can protect yourself from such kind of attacks by following ways:
- Choose a mix of upper and lower case letters, numbers and specials (i.e. special characters).
- Passwords must be a long string with more characters. The longer it is, the more time consuming it is to crack (sometimes, time to crack is in years).
- Password reset should be done after a certain period of time
Dictionary attacks are not effective against systems that make use of multiple-word passwords, and also fail against systems that use random permutations of lowercase and uppercase letters combined with numerals.
Practical Example
- Creating hash for password “emerald” using md5sum and storing in password.hash.
PASSWORD: emerald HASH: 41ca53dbedb99b4eca36836dafb555e2
2. Initiating Dictionary attack using JOHN-THE-RIPPER tool. Wordlist applied is rockyou.txt, which has 14,341,564 unique passwords from 32,603,388 accounts.
Output log from john-the-ripper. For getting password use command: john <passwd file> — show
Hence Successfully performed dictionary attack. Woohoo!!
Радужные таблицы
Радужная таблица (англ. rainbow table ) — специальный вариант таблиц поиска (lookup table), использующий механизм уменьшения времени поиска за счет увеличения занимаемой памяти или time-memory tradeoff. Радужные таблицы используется для вскрытия паролей, преобразованных при помощи необратимой хеш-функции.
Содержание
Теория
Радужная таблица создается построением цепочек возможных паролей. Каждая цепочка начинается со случайного возможного пароля, затем подвергается действию хеш-функции и функции редукции. Данная функция преобразует результат хеш-функции в некоторый возможный пароль. Промежуточные пароли в цепочке отбрасываются и в таблицу записывается только первый и последний элементы цепочек. Создание таблиц требует времени и памяти (вплоть до сотен гигабайт), но они позволяют очень быстро (по сравнению с обычными методами) восстановить исходный пароль.
Для восстановления пароля данное значение хеш-функции подвергается функции редукции и ищется в таблице. Если не было найдено совпадения, то снова применяется хеш-функция и функция редукции. Данная операция продолжается, пока не будет найдено совпадение. После нахождения совпадения, цепочка содержащая его, восстанавливается для нахождения отброшенного значения, которое и будет искомым паролем.
В итоге получается таблица, которая может с высокой вероятностью восстановить пароль за небольшое время.
Таблицы могут взламывать только ту хеш-функцию, для которой они создавались, то есть таблицы для [1] как быстрый вариант time-memory tradeoff [2] . Впервые технология использована в программе Ophcrack для взлома хешей LanMan, используемых в Microsoft Windows. Позже была разработана более совершенная программа MD5, SHA1 и др. Следующим шагом было создание программы The UDC, которая позволяет строить Hybrid Rainbow таблицы не по набору символов, а по набору словарей, что позволяет восстанавливать более длинные пароли (фактически неограниченной длины).
Применение
При генерации таблиц важно найти наилучшее соотношения взаимосвязанных параметров:
- вероятность нахождения пароля по полученным таблицам
- времени генерации таблиц
- время подбора пароля по таблицам
- занимаемое место
Вышеназванные параметры зависят от настроек заданных при генерации таблиц:
- допустимый набор символов
- длина пароля
- длина цепочки
- количество таблиц
При этом время генерации зависит почти исключительно от желаемой вероятности подбора, используемого набора символов и длины пароля. Занимаемое таблицами место зависит от желаемой скорости подбора 1 пароля по готовым таблицам.
Хотя применение радужных таблиц облегчает использование метода грубой силы (bruteforce) для подбора паролей, в некоторых случаях необходимые для их генерации/использования вычислительные мощности не позволяют одиночному пользователю достичь желаемых результатов за приемлемое время. К примеру для паролей длиной не более 8 символов, состоящих из букв, цифр и специальных символов !@#$%^&*()-_+= захешированных алгоритмом MD5 могут быть сгенерированы таблицы со следующими параметрами:
- длина цепочки 1400
- количество цепочек 50 000 000
- количество таблиц 800
При этом вероятность нахождения пароля с помощью данных таблиц составит 0.7542 (75.42 %), сами таблицы займут 596 Гб, генерация их на компьютере уровня Пентиум-3 1ГГц займёт 3 года а поиск 1 пароля по готовым таблицам не более 22 минут.
Однако процесс генерации таблиц возможно распараллелить, например расчёт одной таблицы с вышеприведёнными параметрами занимает примерно 33 часа. В таком случае если в нашем распоряжении есть 100 компьютеров, все таблицы можно сгенерировать через 11 суток.
Защита от радужных таблиц
Данные таблицы невозможно использовать против необратимых хеш-функций, которые включают salt («соль», или «затравка»). Например, рассмотрим следующую функцию для создания хеша от пароля:
где + обозначает конкатенацию.
Для восстановления такого пароля взломщику необходимы таблицы для всех возможных значений затравки.
По сути, затравка увеличивает длину и возможно сложность пароля. Если таблица рассчитана на некоторую длину или на некоторый ограниченный набор символов, то затравка может предотвратить восстановление пароля.
Использование
Практически все дистрибутивы ОС Unix, GNU/Linux и PHP используют простой хеш (обычно Microsoft Windows и Windows NT используют хеши LAN Manager и NT LAN Manager, которые также не используют соль, что делает их одними из самых популярных для создания радужных таблиц.
Про MD5, радужные таблицы и то, как узнать пароль
Если каким-то образом вам удалось завладеть хэшем пароля, который был создан с помощью алгоритма MD5, то вы можете подобрать пароль с помощью специальных таблиц, которые содержат в себе сопоставления «пароль — MD5 хэш». Такие таблицы называются радужными. Существуют онлайн сервисы, которые позволяют ввести хэш, и в случаи найденного совпадения, выдать исходный пароль. Такие таблицы можно загрузить к себе на компьюетр, после чего с помощью программы «rcracki_mt» (или другой ей подобной) попытаться найти совпадение хэша с табличными значениями.
Для эскперимента я скачал таблицы «md5_mixalpha-numeric-all-space#1-6», которые позволяют подобрать пароль длиной 1-6 символов, состоящий из любых символов, включая специальные (abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVW XYZ0123456789!@#$%^&*()-_+=
Затем я воспользовался выше описанной программой (текущая стабильная версия — 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 секунд, как программа вывела мне мой хэшированный пароль.

Радужные таблицы в домашних условиях
Прошедшая неделя с точки зрения информационной безопасности выдалась исключительно «удачной»: то база хэшей LinkedIn утекла в сеть, то хэши last.fm. И во всех обсуждениях, так или иначе, упоминают о радужных таблицах.
Слышали о них почти все, но делали их своими руками очень немногие.
Думаю, не разумно рассказывать заново о том, что такое хеш и зачем в принципе нужны радужные таблицы или какие-то другие предвычисления. Для ликвидации белых пятен предлагается прочесть этот топик.
Интеллектуального прорыва в области радужных таблиц сегодня не планируется, а есть желание рассказать, что радужные таблицы – это не сложно, поэтому и писать будем на чем-то простом, а именно: PHP. Хранить таблицу в MySQL.
Весь код доступен на GoogleCode, я же опишу основные моменты, над которыми пришлось подумать и которые необходимо реализовать.
Для начала необходимо поговорить о входном алфавите. В наборе паролей участвует не все символы ASCII таблицы, а только те, которые можно без лишних хитростей набрать на клавиатуре ПК или мобильного устройства. Чем меньше входной алфавит, тем быстрее будет сгенерирована радужная таблица, но и паролей по заданным хэшам найдется меньше. В нашем случае будем использовать входной алфавит из цифр и букв латинского алфавита верхнего и нижнего регистров.
Для создания радужной таблицы используются цепочки, начало которых – это некоторый случайный пароль фиксированной длины. Очевидно, необходима функция генерация случайных паролей из символов входного алфавита:
Внутри цепочек попеременно применяется то хэш-функция, то функция редукции. С хэш-функцией все ясно – это MD5, SHA1 или любая другая (в нашем случае будем использовать MD5). С функцией редукции ясности меньше. Во-первых, функция редукции, получив на входе хэш, должна выдать некоторый пароль из символов входного алфавита. Во-вторых, функция редукции необходима не одна единственная, а упорядоченное множество функций редукции, причем мощность этого множества равна длине цепочки.
Конечно, можно было бы написать две-три функции редукции самостоятельно, но не в случае, когда длина цепочки равна 100 или 1000. Тем более, хотелось бы, чтобы длина цепочки хранилось в константе, которую можно заменить легким движением руки.
В голову приходить достаточно очевидное решение: нужно использовать Генератор псевдослучайных чисел (ГПСЧ). Для каждой конкретно взятой функции редукции инициализировать ГПСЧ определенным набором бит из хэша, поступающего на вход, а затем получать пароль с помощью вызова getWord().
В принципе действовать на уровне отдельных бит и не требуется. Инициализировать ГПСЧ нужно числом типа 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 миллионов записей ноутбук на базе i3-330UM генерировал более 8 часов. В идеале полученная таблица может обратить 2*10^9 хэшей, но это число не соизмеримо с общим количеством 6-символьных паролей, которых 56,8*10^9 на выбранном входном алфавите.
Это в очередной раз показывает, насколько важен выбор подходящего инструмента для решения конкретной задачи.
Думаю, что задачу наглядно продемонстрировать принцип реализации радужных таблиц мне на пару с PHP всё-таки удалось решить.