Новый тип брута (фрактальный)!

Discussion in 'Криптография, расшифровка хешей' started by -=lebed=-, 5 Apr 2012.

  1. Pirotexnik

    Pirotexnik Banned

    Joined:
    13 Oct 2010
    Messages:
    365
    Likes Received:
    68
    Reputations:
    38
    Ух ты, даже быстрее чем радужные таблицы, выходит?
    А реализация под GPU есть/будет?
     
  2. Gray_Wolf

    Gray_Wolf Active Member

    Joined:
    7 Mar 2009
    Messages:
    377
    Likes Received:
    135
    Reputations:
    10
    Это скорее никак к радужным таблицам не относится...

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

    В ближайшие пару лет мне это видится маловозможным т.к. помимо того что алгоритм ещё не до конца обдуман, остаётся проблема с внедрением. Т.к. новые вещи в данной среде появляются с неслабой задержкой.
     
  3. Pirotexnik

    Pirotexnik Banned

    Joined:
    13 Oct 2010
    Messages:
    365
    Likes Received:
    68
    Reputations:
    38
    Я имел ввиду среднюю скорость.
     
  4. -=lebed=-

    -=lebed=- хэшкрякер

    Joined:
    21 Jun 2006
    Messages:
    3,857
    Likes Received:
    1,962
    Reputations:
    594
    Можно рулить EGB по этому алгоритму, написав батник, который будет менять параметры ini-файла и запускать брут конкретных веток, необходимости реализации на низком уровне такой атаки нет.
     
  5. -=lebed=-

    -=lebed=- хэшкрякер

    Joined:
    21 Jun 2006
    Messages:
    3,857
    Likes Received:
    1,962
    Reputations:
    594
    Развитие идеи фрактального брута - вариант детерминирования прохода по ветке (маске).

    Такс, появились дальнейшие идеи по детеминированию фрактального дерева, итак:
    1. когда мы получаем совпадение словарного пароля, мы ставим ему в соответсвие определённую маску из стандартных чарсетов.
    2. Далее надо определить (посчитать) число всех возможных паролей по этой маске, чтоб определить длину ветви.
    3. Так же заносим эту маску в базу и ставим ей в соответсвие счётчик попаданий.
    4. Если длинна ветви очень велика и проход по ней составляет с учётом соответсвующей скорости V брута на GPU более чем, установленное время T, то используем следующий алгоритм соскока с ветки:
    5. Если за время похождения T ветви (атака по маске) не найдено пороговое значение паролей N то соскакиваем с ветки, если найдено, то сбрасываем счётчик и брутим ещё время T и т.д. в цикле.
    6. После того как осуществлён соскок с ветки, переходим к бруту по след. слову в словаре, если маска соответсвует уже пробрученной ранее, то переходим к след. слову, если она новая, то приступаем к п.2

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

    В алгоритме реализован не фрактал, а как бы куст с ветвями разной длинны.

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

    Попробую описать алгоритм на основе аналогии:
    Имеем дерево и имеем муравьишку способного ползать по его веткам а так же запоминать их и собирать на них пароли.
    Муравьишка выбирает понравившуюся ветку (первое словарное совпадение пароля и генерация маски) начинает ползти по ней вверх, собирая урожай пароли. Но если скорость притока паролей падает ниже некой виличины, т.е. за тот же период времени паролей собирается всё мешьше и меньше, а то и вовсе их нет, муравьишка считает что урожай весь собран и нет смысла ползти дальше по дереву вверх, либо если ветка имеет приемлемую длину он сможет всю её пройти за время t. Он спрыгиват с этой ветки к основанию куста и выбирает следующую понравившуюся (2-е совпадение со словарным паролем, при условии что маска новая и не брученная) ветку и начинает собирать урожай на новой ветке (ведь он прекрасно помнит все ветки на которые он лазил.)

    Как теперь реализовать это дело в многопоточности, в частности применительно к GPU. всё предельно просто: каждому муравью своя понравившаяся ветка. Т.е. При проходе начального словаря берётся сразу N непересекающихся веток (масок) и осуществляется проход параллельно по кадой из них.
    Можно данное и не делать ибо проход по маске - уже многопоточно реализуемая операция на GPU. Т.е. алгоритм требует минимум изменений и являет собой комбинацию атаки по словарю и маскам, только маски у нас динамически генерируемые автоматически.

    P.S. Ещё есть важное замечание! Проход по ветке (маске) должен осуществляться с опред. приоритетом! Т.е. некоторые чарсеты на опред знакоместе имеют больший приоритет чем другие, поэтому проход по маске должен быть не абы как а в соответствии с матожиданием конкретного символа в конкретном чарсете и в зависимости от знакоместа.

    Т.е. Я вообще предлагаю сделать возможность задания пользовательских чарсетов сразу на начальном этапе.
    т.е. в случае стандартных получим:
    ?1=?n
    ?2=?l
    ?3=?u
    ?4=?s


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

    P.P.S. В случае с пользовательскими чарсетами при повторении символов в чарсете возможно пересечение (сплетение веток и последующее разветвление) что может снизить эффективность прохода по всему кусту из-за повторов, однако если символы в пользовательских чарсетах размещенны в соответсвии со статисчическим матожданием то наоборот может прибавить эффективности при проходе всего куста.

    UP: Если договорюсь с InsidePro, возможно он реализует такую атаку в будущих версиях EGB.
     
    #25 -=lebed=-, 22 Oct 2012
    Last edited: 22 Oct 2012
    1 person likes this.
  6. -=Cerberus=-

    -=Cerberus=- κρυπτός γράφω

    Joined:
    29 Apr 2012
    Messages:
    1,320
    Likes Received:
    919
    Reputations:
    391
    -=lebed=- идея конечно крайне интересная, но не особо понял её реальную ценность на примере скажем реал дампа паролей.

    к примеру:
    в нашем дампе 25 процентов паролей числа, 35 буквы в нижнем регистре, и т д по степени уменьшения процента и увеличения сложности пароля, например, 3% это пароли более 8 имеющие в себе разные регистры числа и буквы и не имеющие смысловой нагрузки.

    получается, что "ухватив" числа будут пробручены все их диапазоны скажем 1-14, дальше новый чарсет с новым приоритетом, и это я как понимаю будет ?l, потом ?u, потом пойдут миксы.

    по логике событий все подобные действия укладываются в факты собранной статистики по другим дампам паролей.

    Отсюда у меня вопрос: а в чем тогда смысл данного метода, если он описывает статистику? или я чего-то не понял, тогда заранее извеняюсь! :)
     
  7. -=lebed=-

    -=lebed=- хэшкрякер

    Joined:
    21 Jun 2006
    Messages:
    3,857
    Likes Received:
    1,962
    Reputations:
    594
    Теперь для увеличения начальной скорости выхлопа паролей нужно сделать следующее:
    1. Сгенерировать все маски из входного словаря и привязать к каждой счётчик попаданий.
    2. Сортируем маски по популярности (сначала более популярные - больше счётчик попаданий).
    3. Проход осуществляем начиная с ветки (маски) наиболее ожидаемой.
    4. Соскакиваем с ветки (маски) по описанному выше алгоритму.

    P.S. Таким образом мы изменяем ускорение брута т.е. вначале брута скорость выхлопа максимальна, а к концу брута всё меньше и меньше, при этом дастаются ВСЕ! наиболее популярные и распростанённые пароли, если нужны более сложные и редкие просто ждём окончания брута, либо увеличиваем пороговые значения N и Т.
     
  8. Alexandr II

    Alexandr II -=ImperatoR=-

    Joined:
    28 Dec 2007
    Messages:
    1,073
    Likes Received:
    642
    Reputations:
    87
    молодец лебедь! ты фанат-мастер своего дела!!! сколько уже хешами занимаешься?!!
     
  9. -=Cerberus=-

    -=Cerberus=- κρυπτός γράφω

    Joined:
    29 Apr 2012
    Messages:
    1,320
    Likes Received:
    919
    Reputations:
    391
    А все понял! спасибо! я просто не с той стороны зашел! :)
     
  10. -=lebed=-

    -=lebed=- хэшкрякер

    Joined:
    21 Jun 2006
    Messages:
    3,857
    Likes Received:
    1,962
    Reputations:
    594
    Это брут на основе статистики. Она может быть различна в конкретном дампе - это раз.
    Второе ухватив маску из чисел, скажем ?n?n?n?n?n?n?n?n?n?n (10 знаков) не факт что она будет пробручена вся! Соскок может произойти в том случае, если выхлоп прекратился, либо опустился ниже опред. значения.

    Ну и третье! Самое важное! Кто мешает собрать словарь реалпассов из словарей реалпассов от дампов удалив повторы слов? В него войдут менее распространённые маски и пароли.

    Смысл в общем-то в автоматизации атаки, то что хэшкрякер делает ручками (интеллектуальный выбор видов атак, диапазонов, масок и т.д.) берёт на себя софт. Ну и скорость нелинейна: сначала всё брутится быстро простое, а более сложное уже медленнее, но всё равно эффективно!

    Ещё есть один плюс этой техники нащупывания: есть базы, сайты, где не пользователь выбрает пароль, а сайт автоматом генерирует его по маске - так вот задача нащупать эту маску а там уже дело техники - и софт это осуществит автоматом.
     
    2 people like this.
  11. -=lebed=-

    -=lebed=- хэшкрякер

    Joined:
    21 Jun 2006
    Messages:
    3,857
    Likes Received:
    1,962
    Reputations:
    594
    Угу - речь о масках, на основе стандартных чарсетов и пользовательских.

    Т.е. ветки это маски: ?l?l?l?l?n?n?n?n (из стандартных наборов символов) или ?1?1?1?2?2?2?2?2 (из пользовательских наборов, сгенерированных в соответсвии с матожиданием символа на конкретном знакоместе по входному словарю реалпассов).
     
    #31 -=lebed=-, 22 Oct 2012
    Last edited: 22 Oct 2012
  12. Саранча

    Joined:
    30 May 2011
    Messages:
    9
    Likes Received:
    1
    Reputations:
    -5
    Спасиб. Полезная штука. Но понять трудно.
     
  13. -=lebed=-

    -=lebed=- хэшкрякер

    Joined:
    21 Jun 2006
    Messages:
    3,857
    Likes Received:
    1,962
    Reputations:
    594
    Хэшкрякеры поймут... ;-)

    Теперь немного про аддаптивность:
    Аддаптивность возможна только при использовании пользовательских чарсетов. Каким образом её реализовать?
    1. Безусловно надо динамически отслеживать матожидание каждого символа на конкретном знакоместе в ВЫХОДНОМ словаре.
    2. Задаться его пороговым значением (скажем 1%).
    3. Если матожидание символа падает ниже порогового значения - требуется выкинуть символ из чарсета и наоборот ввести символ в чарсет если матожидание превысило 1%.
    4. Изменить пользовательский чарсет на этапе прохода по маске из него очень проблематично.
    5. Когда менять? Менять(подстраивать) чарсет(ы) нужно каждый раз после соскока с ветки (пересчитывая матожидание во ВЫХОДНОМ словаре).
    Вот примерный упрощённый вариант аддаптивности в выше описанном алгоритме.

    Но тут (в реализации аддаптивности/подстройки) у нас масса вариантов для манёвра, поэтому этот блок можно так же реализовать модулем и подключать требуемый, либо менять его настройки.
    6. В любом случае требуется его настройка на практике, т.е. его надо изначально делать настраиваемым и иметь возможность включать/выключать чтоб оценить эффективность. Блок аддаптивности по идее должен ввести третью производную, т.е. добавить скорость ускорения брута, в ущерб нахождению релевантных паролей в начале брута.
    7. Иногда полезно реверснуть, т.е. наоборот взять и составить редкие маски из символом с малым матожиданием и найти мало, но очень редких паролей из них.
     
    #33 -=lebed=-, 22 Oct 2012
    Last edited: 22 Oct 2012
  14. SC0RPI0

    SC0RPI0 Decrypt Hashes

    Joined:
    21 Apr 2010
    Messages:
    1,460
    Likes Received:
    804
    Reputations:
    378
    Спасибо! идея вполне понятна.
     
Loading...