FAQ: Rainbow Tables

Discussion in 'Криптография, расшифровка хешей' started by Thanat0z, 14 Apr 2007.

  1. Thanat0z

    Thanat0z Негрин

    Joined:
    6 Dec 2006
    Messages:
    645
    Likes Received:
    498
    Reputations:
    311
    "Кто-нибудь другой наверняка уже высказал все твои мысли лучше тебя, так что если не можешь сказать еще лучше воруй у великих!" (с)​


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

    Оглавление
    1. Вступление
    2. Теория
    2.1 Таблицы
    2.2 Структура и поиск в rainbow table
    2.3 Создание таблиц с помощью winrtgen, наглядные характеристики таблиц
    2.4 Статистические данные из "MakingaFasterCryptanalyticTime-Memory Trade-Off" от Philippe Oechslin​
    3. Практика
    3.1 Непосредственное создание и использование таблиц
    3.2 Использование таблиц в других программах​
    4. FAQ
    5. Links


    1. Вступление

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

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

    Примеры хешей
    MD5 - 5f4dcc3b5aa765d61d8327deb882cf99
    MySQL - 5d2e19393cc5ef6
    SHA-1 - 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8

    Где MD5, MySQL, SHA-1 типы хешей. Однозначного соответствия между паролем и хешем быть не может в общем случае, и разные пароли имеют разные хеши - это криптографические особенности хеш функции.

    2.1 Таблицы

    Существует такое понятие как таблицы поиска (lookup table) - это такие таблицы, которые представляют собой массив данных, созданы они для того чтоб заменить ресурсоемкие вычисления на обычных поиск, и используются в тех случаях, когла гораздо легче извлекать эти данные из памяти, чем их создавать.

    В 1980 году Мартин Хеллман предложил использовать предварительно вычисленные таблицы, размещенные в памяти, и это было зарождением rainbow tables.

    Теперь перейдем к определению Rainbow table:
    Для ускорения генерации и поиска используются различные оптимизации и ухищрения, такие как time-memory tradeoff (компромис памяти и времени) в различных вариантах.

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

    2.2 Структура и поиск в rainbow table

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

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

    Если не ясно, постараюсь объяснить чуть более подоробно:

    1. Фиксируется рабочий алфавит, то есть задается множество Q всех возможных ключей.
    2. Фиксируется элемент q из множества Q и вычисляется значение h хэш-функции на нем.
    3. При помощи некоторой «срезающей» функции R из хэша генерируется ключ, принадлежащий множеству Q: q=R(h). Если число элементов в цепочке меньше заданного, осуществляется переход к пункту 2.


    Эти операции будут повторяться пока не будет получена цепочка длиной t ключей. Эта последовательность не размещается целиком в памяти, записывается лишь первый и последний ее элементы. Это и есть time-memory tradeoff - допустим генерим цепочку из 2000 ключей, а записывается только первый и последний элементы, получаем огромнейшую экономию, но с другой стороны время криптоанализа увеличивается.
    Далее генерируем определенное количество цепочек, которые удобно представить в виде таблицы с двумя колонками (двумерный массив), в первой из которых находится начальный ключ цепочки, а во второй - конечный. После того, как цепочки сгенерированны, можно уже осуществлять в них поиск ключа.

    Задается значение хэш-функции, для которого необходимо получить коллизию (нахождение соответствия). При помощи срезающей функции R строится значение ключа K0, из которого выводится по описанному алгоритму цепочка поиска длиной не более чем t элементов. Если в таблице есть искомый ключ, то один из сгенерированных элементов новой цепочки будет являться терминальным элементом нашей таблицы. Далее не составляет труда по известному начальному элементу вывести всю соответствующую терминалу цепочку, включая элемент, непосредственно предшествующий начальному значению K0, то есть ключ, который мы ищем. Но если же в сгенерированных таблицах нет коллизия, то нельзя дать точного ответа сколько нужно сгенерировать цепочек, чтобы они покрывали все множество возможных ключей.

    Еще не ясно? Ок, попробуем иначе

    Min Len - минимальное число букв в пароле.
    Max Len - максимальное число букв в пароле.
    K = Сумма(по i, от L1, до L2, C^i) - Число букв в чарсете и MaxLen с MinLen влияют на общее число паролей которые подлежат анализу
    Где K – кейспейс,
    L1 – минимальная длина пароля,
    L2 – максимальная длина пароля,
    C – число букв в чарсете. Чарсетом называют набор букв, к примеру ABCDEFGHIJKLMNOPQRSTUVWXYZ.

    Строка таблицы состоит из двух записей. Запись по 8 байт, то есть строка 16 байт
    При расчете записи таблицы выполняется такая последовательность действий:

    1. Скидывается случайное число от нуля до кейспейса.
    2. Находится плейнтекст пароля, соответствующий этому случайному числу.
    3. Вычисляется хэш пароля.
    4. Вычисляется R от хэша.
    5. Находится плейнтекст соотвтствующий индексу в кейспейсе полученому на предыдущем шаге.
    Дальше пункты 3-5 выполняются столько раз сколько "длина цепочки".


    Последняя запись таблицы - это R от последнего хэша, т.е. запись таблицы состоит из двух групп по 8 байт, в каждой группе из 8 байт хранится число от 0 до кейспеса. Конечно кейспейс всегда меньше чем 256^8 , именно это (и еще сортированность таблицы) дает возможность так хорошо ее паковать.

    В идеальном случае чтобы обеспечить полное покрытие множества Q, необходимо сгенерировать бесконечно большую таблицу с цепочками. Возможен вариант, при котором цепочки, начинающиеся с различных ключей, будут иметь одинаковые элементы и будут «слипаться» после определенной позиции. Это происходит из-за природы срезающей функции. Во множестве хэшей возможных элементов значительно больше, чем во множестве ключей. По этой причине нескольким хэшам соответствует только один ключ. Дело в том, что частота слипания цепей быстро увеличивается вместе с ростом таблицы. Поэтому число требуемых последовательностей характеризуется требуемой вероятностью (обозначим ее как P*) того, что произвольный ключ q из Q окажется в нашей системе подмножеств, в нашей таблице. Именно требуемая вероятность P* определяет необходимый размер таблицы с цепочками, что под «размером» таблицы понимается как число цепочек, так и их длину, оба эти параметра влияют на частоту слипания и эффективность покрытия.

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

    Вероятность успеха, объем занимаемой памяти и время поиска зависят от длины цепочек t, их количества m и числа используемых таблиц l.

    Поэтому общий объем таблицы из m цепочек составляет 16*m. Соответственно, если таблица всего одна, то они занимают 16*m*l байт.
    Что касается времени поиска хэша, то оно выражается так: t*t/(2*speed), где speed - это скорость вычисления хэшей.


    2.3 Создание таблиц с помощью winrtgen, наглядные характеристики таблиц

    Генерировать таблицы можно с помощью визуальной утилиты или стандартной rtgen, но сейчас мы запустим winrtgen для того что разобраться с параметрами таблиц. Итак, winrtgen и далее кнопка "add table"

    Еще раз повторю, что значат параметры
    Hash название хэш алгоритма. Хэшалгоритм должен поддерживаться данным билдом генератора таблиц. В winrtgen вшит ограниченный набор алгоритмов. В коммандлайный rtgen можно вкомпилировать любой свой алгоритм или любую свою собственную имплементацию, которая будет быстрее работать на вашей системе.
    Min Len минимальное число букв в пароле.
    Max Len максимальное число букв в пароле.
    K = Сумма(по i, от L1, до L2, C^i)
    Где K – кейспейс,
    L1 – минимальная длина пароля,
    L2 – максимальная длина пароля,
    C – число букв в чарсете.

    Допустим будут такие соотношениея (в случае, если C=30, L1=1, L2=8, для примера):
    - Увеличение L2 (длины пароля) на 1 увеличивает кейспейс примерно в 30 (длина чарсета) раз.
    - Увеличение чарсета на одну букву увеличивает кейспейс примерно на 30%. Примерная формула L2/C
    - Отказ от просчета паролей меньшей длины, т.е. изменение L1 так чтобы L1=L2 приводит к уменьшению кейспейса примерно на 3% т.е. на (1/C).


    От величины кейспейса прямо пропорционально (при прочих равных условиях) зависит размер таблиц, время их генерации и время криптоанализа.

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

    Index – Строго говоря, этот параметр задает некий оффесет, используемый функцией редукции. Можно называть его номером таблицы. Следует сказать, что если вы сгенерируете две таблицы с одинаковым индексом, это будут все равно две РАЗНЫЕ таблицы. Фактически это будет эквивалентно тому, что вы сгенерировали таблицу вдвое большей длины. Разница между двумя таблицами с одинаковым индексом и двумя таблицами с разным индексом состоит в том, что во втором случае КПД несколько выше, разница тем больше, чем больше длина строки таблицы (chain len). В данном случае под КПД таблицы понимается отношение числа паролей, которые могут быть вскрыты таблицей, к числу хэшей, которое было рассчитано в ходе генерации таблиц
    Еще можно добавить что индексы и суффиксы используются для того, чтобы отличать таблицы друг от друга. Вообще же, пароли в таблицы собираются не по-порядку, а случайным образом. Поэтому метод никогда не даёт 100% гарантии подбора любого пароля, но в то же время:
    1. Чем больше посчитано таблиц, тем выше вероятность нахождения пароля по данному алгоритму и ключевому пространству.
    2. Любые таблицы могут использоваться для поиска паролей из любой части ключевого пространства.
    RainbowCrack доводит каждый набор таблиц до расчётной вероятности 99,9%. Используются индексы от 0 до 7 и суффиксы от 0 до 24. Для разных ключевых пространств эти диапазоны отличаются.

    Общие правила:
    1. Кол-во индексов * Кол-во суффиксов = Кол-во таблиц для расчёта.
    2. Длина цепочки * Кол-во цепочек = Кол-во паролей в таблице.
    3. Кол-во цепочек * 16 = Размер таблицы (в байтах).

    Chain Len
    – Длина строки таблицы. Увеличение длины таблицы, к примеру вдвое, приводит (при прочих равных условиях) к увеличению времени расчетов ровно в два раза, увеличению вероятности вскрытия почти ровно в два раза, не приводит к изменению объема таблицы, приводит к увеличению времени криптоанализа по таблицам примерно в 4 раза.

    Чтобы было понятнее, сравним таблицы:
    А) chain len = 2400 chain count = 40 000 000
    [​IMG]
    Б) chain len = 4800 chain count = 20 000 000
    [​IMG]


    По идее эти две таблицы должны иметь примерно одинаковые свойства. Разница между ними состоит в:
    1. Время генерации одинаковое.
    2. Таблица Б имеет вдвое меньший размер.
    3. Вероятность вскрытия почти одинаковая, может колебаться в обе стороны, не более 0.1%.
    4. Время криптоанализа по таблице Б больше примерно в 4 раза.


    Ниже приблизительная связь вероятности успеха - КПД, рассчитанная для одного частного случая.
    0.1 - 91.4%
    0.5 - 59.7%
    0.7- 42%
    0.8 - 32.1%
    0.85 - 26.7%
    0.9 - 20.7%
    0.95 - 13.7%
    0.98 - 8.3%


    Разобравшись с тем на что влияет каждый параметр, вы уже должны выбрать для себя, чем жертвовать, свободным место или временем для криптоанализа.
    Для начала, задать желаемую вероятность успеха. Выбрав вероятность успеха, следует выбрать длину строки такую, чтобы достичь компромисса между вашим дисковым пространством и временем, необходимым на криптоанализ по получившимся таблицам. Разумной представляется величина на уровне 80% - 90%. Меньше особого смысла нет, т.к. повышать вероятность до 80% можно без особого вреда для КПД. А повышать ли выше 80% думать вам, в зависимости от объема ваших счетных ресурсов. Повышение до 90% повысит время счета и требуемое дисковое пространство в полтора раза, это еще ничего, а вот дальше уже это вряд ли оправдано.

    Вот смотрите сами, зависимость количества таблиц и success probability %:

    2.4 Статистические данные из "Making a Faster Cryptanalytic Time-Memory Trade-Off" от Philippe Oechslin
    В работе Philippe Oechslin есть сравнения поиска по обычным и rainbow таблицам, приведу лишь часть таблицы, чтоб не нагружать вас цифрами и формулами:
    [​IMG]
    Из этой таблицы видно, что rainbow выигрывают по скорости в 7 раз.
     
    #1 Thanat0z, 14 Apr 2007
    Last edited: 14 Apr 2007
    12 people like this.
  2. Thanat0z

    Thanat0z Негрин

    Joined:
    6 Dec 2006
    Messages:
    645
    Likes Received:
    498
    Reputations:
    311
    3. Практика
    3.1 Непосредственное создание и использование таблиц​

    Чем удобен winrtgen, это визуальным интерфейсом и удобным калькулятором, если же вы желаете использовать классические утилиты, то делается это так

    Code:
    rtgen lm alpha-space 1 7 0 1000 200000 test
    Данной командой мы создали тестовую табличку, для чарсета alpha-space= [ABCDEFGHIJKLMNOPQRSTUVWXYZ ].
    Кстати стоит сказать, что вы можете встретить разные модификации rtgen, вот к примеру результаты классической, и оптимизированной версий

    оптимизированная версия

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

    Code:
    rtsort lm_alpha-space#1-7_0_1000x200000_test.rt
    Для поиска пароля делаем следующее

    Code:
    rcrack *.rt -l random_lm_alpha#1-7.hash
    или
    Code:
    rcrack *.rt -h HASH
    В первом случае чтение хешей из файла, в другом один хеш.

    Продемонстрирую поиск на таблицах md5_mixalpha-numeric#1-6_0_2000x40000000, дадим ей на расшифровку 50 паролей
    mixalpha-numeric = [abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789], увидим что-то типа

    ... далее результаты по другим таблицам и в итоге статистика

    Если делать атаку через PasswordsPro к примеру, на моем компе перебор этого диапазона займет 02:40 часов, первый пароль находится только на 03:35 минуте, а за 40 минут перебора, только 13 паролей
    Обратите внимание что время для криптоанализа будет очень долгим (в сравнении с другими таблицами) только для первой таблицы.


    3.2 Использование таблиц в других программах​

    Rainbow tables можно использоваться не только с rcrack, замечательно справляются с таблицами PasswordsPro и Cain&Abel.
    На скорость не тестировал, так как нет нормального инструментария для статистических подсчетов, но лично для меня удобней rcrack. Стоит заметить что если вы создали таблицы для символов кирилицы, то при отображаении пароля вы увидеть "крякозяблы", на сколько мне известно, такого бага в программах PasswordsPro и Cain&Abel нет. Работа с этими программами выходит за рамки данной FAQ, так что на этом остановлюсь.

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

    Кстати для справки:
    Как видите, степень сжатия у 7-zip 44%, а у WinRar 50%, но затраты времени 13 и 6 минут соответственно. Обычный Zip сжимает хуже, тестировать не стал, на это надо более 17 минут.

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

    - В чем преимущество таблиц над словарями или полным перебором
    - Преимущество в скорости поиска в несколько порядков

    - Я не нашел в поставке RainbowCrack нужного алгоритма
    - Вы можете его добавить сами, имея определенный уровень в программировании, либо посмотритер утилиту winrtgen

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

    - Могу ли я создать таблицу со специфическим наборов символов?
    - Да, просто создайте в файле charset.txt строку типа my_chars = [abcABC12_+{}'] и после создавайте таблицы для этого типа

    - Не могу найти пароли, ошибка "can't open charster conf file"
    - Проверьте откуда вы запускаете rcrack, и обратите внимание на то, что чарсеты для генерации таблиц должны совпадать с теми что использует rcrack

    - Создал таблицы для русских символов, а rcrack выдает мне какие-то иероглифы
    - Для нормального отображения кирилицы, надо перекомпилить rcrack, либо используйте другие программы PasswordsPro или Cain&Abel

    - При работе с таблицами выдается ошибка "file is not sorted", но он отсортирован, в чем дело?
    - Такая ошибка может возникать, если у вас свободного места на диске меньше размер таблицы, либо вся оперативная память занята

    - При работе с файлом хешей вижу ошибку "invalid hash"
    - Хеши должны указываться в файле без логинов, только хеш. Каждый хеш с новой строки

    - Выдало ошибку "this table contains hashes with length 16 only"
    - Это значит что таблицы по которым происходит атака не совпадает по типу с вашими хешами

    - Есть ли 100% гарантия что я найду все пароли из опредленного подмножества
    - Нет, читайте про алгоритм создания таблиц

    - Если выключу программу во время генерации таблиц, мне надо будет начать с самого начала?
    - Нет, во всех программах что я встречал, можно продолжать генерацию с места остановки

    - Я стал генерить таблицы вместе с другом, и его таблица отличается от моей, а размер одинаков, в чем дело?
    - Особенность алгоритма, есть параметры которые беруться, грубо говоря рандомно, в бинарном виде все таблицы разные

    - winrtgen, как ни странно индексы сам не проставляет (у всех таблиц - 0). Есть ли смысл самому вручную прописывать эти индексы, или это не так важно?
    - Я считаю что лучший вариант это дефолтный, программе лучше знать что ставить :) Лучше не эксперементировать, не знаю что в итоге получите. Могу сказать одно, что таблицы сгенеренные разным софтом, который по своему ставят индексы отличаются хотя бы по скорости работы. Допустим мне попадались таблицы с индексами 1 и 2. Первая подгружалась очень долго, а вторая быстро проверялась, и заново, следующая пара с подобной особенностью. С таблицами без индексов такого не замечал, по крайней мере возможна долгая обработка первой таблицы, и быстрая всех следующих из сэта. Пример:

    - Не подскажите, нет ли проги для генерации Rainbow Tables в скрытом режиме, то есть невидимой для пользователя, и желательно что бы можно было выставлять приоритет программы, ну и конечно запускалась с автозагрузки. Например как это можно сделать в PasswordPro
    - Видел такой софт, но он был предназначен для расспределенного создания таблиц. Если пользоваться winrtgen, то можно создать батник запуска с низким приоритетом и кинуть в автозагузку. Смысла прятать софт от пользователя не вижу, так как загрузка при создании большая, будет все равно заметно

    5. Links
    Project RainbowCrack - __http://www.antsight.com/zsl/rainbowcrack/
    Oxid.it Projects - http://www.oxid.it/projects.html (здесь winrtgen и Cain&Abel)
    RainbowCrack Optimized - __http://rapidshare.com/files/26014582/RainbowCrack_P4optimized.rar (где взял архив сам не помню :))
    LM таблицы на wired.s6n.com - __http://wired.s6n.com/files/jathias
    Making a Faster Cryptanalytic Time-Memory Trade-Off (by Philippe Oechslin) - __http://lasecwww.epfl.ch/php_code/publications/search.php?ref=Oech03
    Ophcrack Project - __http://sourceforge.net/projects/ophcrack
    Shmoo Group - __http://rainbowtables.shmoo.com/
    Статья "Радуга в таблицах", Хакер - __http://www.xakep.ru/magazine/xa/082/050/1.asp
    Форум по безопасности www.wapbbs.com - __http://www.wapbbs.com/bbs, материалы людей с форума очень пригодились для написания статьи
    [thread=32047]Rainbow tables (md5) в инете для закачки[/thread] - тема в разделе Расшифровка паролей

    ver 09.06.2007​
     
    #2 Thanat0z, 14 Apr 2007
    Last edited: 14 Jun 2007
    2 people like this.
  3. sic57005

    sic57005 Elder - Старейшина

    Joined:
    22 Apr 2007
    Messages:
    31
    Likes Received:
    32
    Reputations:
    7
    Да вот про увеличению вероятности вскрытия почти ровно в два раза это совсем не правда. Сам ведь считал эффективность. В реальности увеличение идет очень нелинейно, и если например мы имеет 50%-ое заполнение plaintext space, увеличивая в 2 раза длину таблицы мы получим 75%-ое заполнение. Еще в 2 раза (т.е. в 4 относительно исходного) - всего 88%-ое заполнение.
     
  4. Thanat0z

    Thanat0z Негрин

    Joined:
    6 Dec 2006
    Messages:
    645
    Likes Received:
    498
    Reputations:
    311
    цифры, кпд и прочее я приводил, кому нужны детальные формулы, то всё это есть в научных работах, ссылки я привел. "Почти два" это и значит что как в 1.8 раз, так и 2.2, к примеру. Я сомневаюсь что ты можешь установить достоверно во сколько раз это увелечение будет, так что доверяю winrtgen, а он как раз показывает что увеличение будет в ~2.
     
  5. sic57005

    sic57005 Elder - Старейшина

    Joined:
    22 Apr 2007
    Messages:
    31
    Likes Received:
    32
    Reputations:
    7
    Я писал тулсу для проверки заполнения plainspace пространства (==вероятности успешного взлома), могу выложить, если интересно. Проверяет втупую - поэтому время расчета чуть больше чем время генерации таблицы. Тестил не на самых больших табличках, порядка 500мб-1гб, и выдала программа вот это:



    Т.е. в реальности, ни о каких "двух разах" говорить просто нельзя.
    Ну да, почти в два раза увеличение вероятности происходит, если количество цепочек меньше половины plainspace (т.е. success rate ~ 50%), но уже при повышении success rate до 93% нам надо в три раза больше вычислений чем для 54% ного заполнения.

    Это, кстати, все справедливо только для одной таблицы

    При увеличении числа таблиц (но никак, не объема одной таблицы) - вот тогда success rate растет почти линейно. Опять-таки весьма "почти".

    А теперь более простая (логическая) формулировка:
    Пусть success rate линейно зависит от размера таблицы.
    Возьмем таблицу из N цепочек, которая дает нам 50% success rate.
    А теперь посчитаем таблицу из 4N цепочек, и бац, такая таблица должна подбирать пароли уже с 200% вероятностью?! Но это еще что, в реальности такая таблица не обеспечит и 95% паролей, это можно проверить без тулс и довольно быстро - просто создав 1000 рандомных паролей из того же плейн спейса и поставих их на перебор по таблице.

    Спасибо за внимание.
     
    1 person likes this.
  6. sic57005

    sic57005 Elder - Старейшина

    Joined:
    22 Apr 2007
    Messages:
    31
    Likes Received:
    32
    Reputations:
    7
    Кстати, у тебя именно эти цифры в таблице вероятность - КПД отражены.

    Они как раз сходятся с моей статистикой.

    По ним видно, что для 98% success rate мы должны посчитать более чем в 10 раз больше цепочек, чем необходимо для реального накрытия plain space.

    Вот она действительность! Для однократного взлома, RT в 10-15 раз менее эффективны (по времени) нежели прямой перебор, при 100% гарантии результатов у второго метода.
     
    1 person likes this.
  7. Thanat0z

    Thanat0z Негрин

    Joined:
    6 Dec 2006
    Messages:
    645
    Likes Received:
    498
    Reputations:
    311
    Я знаю :) Просто в вопросе с таблицами есть расхождение в практике и теории :) Я поэтому не даром сказал смотреть эти циферки :)
    У меня вот правда в голове не очень укладывается твое утверждение что прямой перебор эффективней чем атака по таблицам, если брать к примеру Lowalpha на 8 или 9 символов...
     
  8. sic57005

    sic57005 Elder - Старейшина

    Joined:
    22 Apr 2007
    Messages:
    31
    Likes Received:
    32
    Reputations:
    7
    Кстати, по поводу работы Philippe Oechslin -- он сравнивает RT с таблицами, построенными по выделенным точкам (DP-Tables). Я долго не мог понять, откуда он взял цифру 7, которая показывает превосходство его метода. Может кто-нибудь лучше знает по этому вопросу?
    В реальности же таблицы с выделенными точками (DP) могут быть сделаны collision-free 100% successful что для RT вообще не возможно + время криптоанализа по DP линейно зависит от средней длины цепочки, а не квадратично, что очень значительно снижает время криптоанализа.

    P.S. А вот генерация DP таблиц до 100 раз менее эффективна.
    P.P.S. Но откуда взялось 7?! В абстракте написано 2, где-то в середине в 12...
    Может (2+12)/2 = 14/2 = 7? ;))
     
  9. Thanat0z

    Thanat0z Негрин

    Joined:
    6 Dec 2006
    Messages:
    645
    Likes Received:
    498
    Reputations:
    311
    Ну там в работе есть значение - разница в 7 раз, а что это за DP таблицы я слабо понял, какая-то специфическая таблица, но назвал ее "обычной", то есть подразумевая что рейнбоу строятся иначе :)
     
  10. sic57005

    sic57005 Elder - Старейшина

    Joined:
    22 Apr 2007
    Messages:
    31
    Likes Received:
    32
    Reputations:
    7
    Абсолютно согласен. Вот например г-н Филипп упорно пытался запрять подальше оценку на время работы криптоанализа, и предоставил только ту статистику, которая хорошо смотрелась.
    Я не то имел в виду немного.
    Т.е. время анализа по готовым таблицам до смеха мало по сравнению с прямым перебором. И это самое главное премущество табличек.
    А вот время генерации таблиц... увы оно куда больше чем время перебора по тому же диапазону.
    Однако, один раз посчитав (или скачав) таблицу - про это забываешь.
    Вот потому таблички и лучше.
     
  11. Thanat0z

    Thanat0z Негрин

    Joined:
    6 Dec 2006
    Messages:
    645
    Likes Received:
    498
    Reputations:
    311
    а ну ясное дело, я отталкиваюсь от того что у нас уже есть таблица, и не надо генерить ее. Если же сравнивать время затраченное на генерацию таблиц и перебор того же диапазона, то конечно перебор рулит. К примеру на двух компах я генерил таблицы для loweralpha8, вроде ушло 5 дней. Тот же диапазон для мд5 прямым перебором можно прогнать менее чем за 10 часов
     
    2 people like this.
  12. Rogun

    Rogun Elder - Старейшина

    Joined:
    12 Feb 2008
    Messages:
    79
    Likes Received:
    4
    Reputations:
    0
    1.в winrtgen можно ли загружать модули например sha1($username.$pass)
    PHP:
    ?или же по умолчанию sha1?

    2.Ещё там запускаеш winrtgen в адд табл в поле hash ставиш sha1 в Min Len и Max len-значения сколько символов пароль тами начинаем генеритьили ещё надо где то заполнить?

    3.чем открывать сгенерированные таблицыи пароль там найденый записывется специальноа то у меня плэер открывает таблицы а открывая ворлд падом там знаки китайские...((
     
  13. Trustno1

    Trustno1 New Member

    Joined:
    8 May 2010
    Messages:
    5
    Likes Received:
    1
    Reputations:
    0
    Чем сгенерировать RC4 таблицу?
     
Loading...