Цепочки – метод поиска коллизии.

Discussion in 'Криптография, расшифровка хешей' started by Red_Red1, 20 Jan 2009.

Thread Status:
Not open for further replies.
  1. Fepsis

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

    Joined:
    17 Sep 2008
    Messages:
    791
    Likes Received:
    391
    Reputations:
    72
    Интересная тема... Тоже об этом думал.. Но думаю не всё так просто. Допустим такая ситуация:
    создаём список паролей:
    ф(0)=5
    ф(5)=10
    ф(10)=0
    опаньки, вот и замыкание.. Радостные, что всего за месяц получили чудный список всевозможных (как нам кажется) паролей, идём брутить по этому списку... Брутим по нашему списку (0,5,10).. Результата нет..(((( Хны-Хны.. А всё почему..?!? Потомучто пароль, который мы пытались сбррутить "1", который в свою очередь так же имеет замыкание, только другое:
    ф(1)=6
    ф(6)=11
    ф(11)=1
    вполне может быть такое..)))
    кстати, дайте пару разных строк, у которых одинаковый мд5 хеш... не сомневаюсь что есть.. любопытно... дайте глянуть..)
     
    1 person likes this.
  2. preda1or

    preda1or Member

    Joined:
    27 Oct 2008
    Messages:
    167
    Likes Received:
    96
    Reputations:
    6
    2 Fepsis

    http://www.mscs.dal.ca/~selinger/md5collision/
     
    #22 preda1or, 20 Jan 2009
    Last edited: 20 Jan 2009
    1 person likes this.
  3. Red_Red1

    Red_Red1 Banned

    Joined:
    12 Jan 2007
    Messages:
    246
    Likes Received:
    258
    Reputations:
    83
    Приходило в голову это. Не описал специально что бы не путать.
    Я ведь и хотел обсудить идею.
    Вопрос КАК выловить что кольцо замкнулось. Ну и как выловить ВСЕ кольца. Если это сделать то мы опять получим всю цепочку-кольцо точнее несколько колец.
    Т.е. хотелось бы все это дело испытать на практике. С олдмускул это реально.
     
    1 person likes this.
  4. -=lebed=-

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

    Joined:
    21 Jun 2006
    Messages:
    3,804
    Likes Received:
    1,957
    Reputations:
    594
    Вообщем так...
    Про md5 можно пока благополучно забыть, потому как 2^128 или что тоже колличество 16^32 ну это очень много и сгенерить их все, времени при современных технологиях не хватит.
    Касательно хэшей mysql(64) - это в полне возможно попробовать реализовать.
    Следует напомнить, что высокая скорость перебора хэшей mysql(64) в реализации от xSerg на CUDA получается за счёт использования уязвимости самого алгоритма хэширования mysql(64).
    Далее, если брать в качестве входа функции именно предыдущую выходную строку, то область входных значений мы сужаем, потому как вход никак неограничен на самом деле. Если же строку подавать на вход функции в hex-виде, то можно предположить, что область входных значений будет равна области выходных. (на самом деле она будет меньше, потому как пробелы не учитываются на входе, т.е. это байты содержащие код 32 (dec) или 20 (hex)).
    Но! это возможно только в случает полного отсутствия коллизий на участке входных значений длинной при кол. 2^64, т.е. соизмеримом с областью значений. Чего скорее всего не будет и мы получим ранее упомянутое замыкание круга и множество как входных, так и выходных значений остануться за пределами этого круга!
    Отсюда следует вывод: что при замыкании в дальнейшей генерации цепочки нет смысла и для получения новой цепочки, содерж. другие значения входов и выходов, нам нужно взять другое начальное значение! Как оно должно быть связано с первой цепочкой? Каким образом вероятность возникновения замыкания (коллизии) зависит от шага? Вообщем в любом случае генерация цепочки в случае коллизии (замыкания) должна быть прервана (а это может случиться и раньше чем через 2^64 итераций)
     
    #24 -=lebed=-, 20 Jan 2009
    Last edited: 20 Jan 2009
  5. preda1or

    preda1or Member

    Joined:
    27 Oct 2008
    Messages:
    167
    Likes Received:
    96
    Reputations:
    6
    -=lebed=-
    убил мой моск, буду думать, +
     
  6. Fepsis

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

    Joined:
    17 Sep 2008
    Messages:
    791
    Likes Received:
    391
    Reputations:
    72
    На счёт места на диске пришла идея, идея о способе хранения информации о паролях и хешах...
    На примере MySQL хеша.. Представьте себе директорию, в которо находится 16 папок с именами 0,1,2,...,e,f. Заходим в любую из этих папок, в ней видим так же 16 папок 0,1,2,...,e,f. И так далее.. Глубина каждой папки - 16 вложений..
    Теперь берём произвольную стоку (пароль) и находим его MySQL хеш:
    123:773359240eb9a1d9
    в папку ...7\7\3\3\5\9\2\4\0\e\b\9\a\1\d\9\
    записывается файл НУЛЕВОЙ длины с именем "123"
    и так для любого пароля...
    Такой способ хранения не очень подойдёт для сервиса по восстановлению пароля из хеша, так как
    [​IMG]
    а пароли эти символы могут содержать, но если наша задача захешировать все числа от 0 до 2^64 или вариант когда выход пускается на вход (итерации) то вполне подойдёт..
    берём начальную строку "0000000000000000"
    файл "0000000000000000" -> в папку ...5\0\3\1\9\7\3\5\7\8\2\2\b\b\c\1\
    "503197357822bbc1" -> ...4\2\f\c\0\a\f\2\0\0\0\0\0\0\0\0\ и т.д.
    Мне кажется, написать прогу, которая данную стуктуру реализует, не очень сложная задача... И искать по такой базе очень удобно.. И если добъёмся того, что в каждой папке ...x\x\x\x\x\x\x\x\x\x\x\x\x\x\x\x\ будет лежать нулевой файл с именем "yyyyyyyyyyyyyyyy" то можео считать задачу относительно хеш функции MySQL решённой...
    Не ругайтесь, если вышенаписанное бред или баян..
    P.S. сейчас запустил на компе скрипт, создающий пустые файлы... Файлов было 100 000, винда показала, что папка с этими файлами весит 0 кб... Хотя я сомневаюсь что всё действительно по нулям.. Просветите меня..;)
     
  7. preda1or

    preda1or Member

    Joined:
    27 Oct 2008
    Messages:
    167
    Likes Received:
    96
    Reputations:
    6
    Конечно не по нулям.Таблица разметки диска, интересно, сколько будет весить? Ты сэкономишь меньше процента,если вообще сумеешь.
     
  8. Fepsis

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

    Joined:
    17 Sep 2008
    Messages:
    791
    Likes Received:
    391
    Reputations:
    72
    Эх, ну надо же.. :( а я думал америку открою..)))
     
    1 person likes this.
  9. diehard

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

    Joined:
    30 Sep 2007
    Messages:
    442
    Likes Received:
    266
    Reputations:
    15
    По-моему вывод нелогичен. Получим НЕ ВСЕ хеши на выходе, будут повторы из-за коллизий типа:
    hash(00000000000001) = 28282828282828
    hash(34583475834758) = 28282828282828

    Поэтому алгоритм обратится в вечный цикл и вот этого не произойдёт:

    "Ф(45)=46 – ненайдено.
    Ф(46)=47 – ненайдено.
    Ф(47)=48 – ненайдено.
    Ф(48)=49 – НАЙДЕНО!!!! "

    Так как например "49" отсутствует в выдаче Ф(от конечного множества), зато 2 раза присутствует "48" и 5 раз присутствует "50" например.
     
    #29 diehard, 28 Jun 2009
    Last edited: 28 Jun 2009
  10. Cthulchu

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

    Joined:
    22 Nov 2007
    Messages:
    405
    Likes Received:
    705
    Reputations:
    85
    дихард, это кольца. ред о них упоминал и тут и на сходке. давай лучше придумаем как красивее их обойти.
    Единственное, что приходит в голову это тривиальный вариант с возможностью оптимизаций:
    каждый полученый хеш прежде, чем хешировать снова - надо сопоставить с уже существующей базой нахешированых хешей... Да, это долго.
    Что делать, если мы нашли кольцо? Останавливаем хеширование замыкающего кольцо хеша, удаляем его из базы, добавляем к нему единицу и продолжаем по заданому алгоритму.
    Да, это будет долго.
    ДА нет, это будет очень долго.
    Оно того стоит.
    Да, мой набросок допускает вероятность вычесления не всех хешей.
    Ред, вместо того, что бы делить твою теоритическую базищу на сегменты по 250 миллионов хешей, оставляя лишь первый и последний - можно будет оставлять только кольца. Я, правда, не представляю сколько их там будет.
    вот и все.
     
    #30 Cthulchu, 28 Jun 2009
    Last edited: 28 Jun 2009
  11. Cthulchu

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

    Joined:
    22 Nov 2007
    Messages:
    405
    Likes Received:
    705
    Reputations:
    85
    да, что бы было понятнее - скажу, что это не кольца. это рендомно пересекающая саму себя функция, в местах пересечения оканчивая свой дальейший путь. движение функции задает, собственно, Ф() и аргумент конечно.
    нам нужен алгоритм, который сможет подставлять в Ф() такие аргументы, что бы она заполнила все возможное пространство и разделить пространство на замыкающиеся кривые.
    попробую по другому...
    символьный ряд от нула до бесконечности, где каждый следующий аргумент (входное значение) функции (алгоритма хеширования) равен предыдущему (для первого насильно зададим предыдущий), если текуший аргумент уже где-то попадался - прерываем сохранение ряда, обьявляя его петлей. Хитростью (за хакерской догадкой надо к вебхаку обратиться) находим все петли, а мы уверены, что все диапазоны рано или поздно превратятся в петлю и это уже плюс. Главный же минус в том, что петли - тоже пересекаются. Им никто не запретил. Действительно, - коллизия коллизии.
    Коллизия коллизии играет нам на руку, как мне кажется в стольк позднее время. Потому что это хороший шанс убрать лишние пароли из базы, а возможно, это является возможностью немножко регулировать размер колец для оптимизации брута конечного пароля (впадло считать какое отношение размера сегментов к их количеству будет оптимальным). Алгоритм писать под выяснение положений колец и их оптимизации - тоже впадло, так как асмового кодера под это благороднейшее дело - нету.
     
  12. BrainDeaD

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

    Joined:
    9 Jun 2005
    Messages:
    774
    Likes Received:
    292
    Reputations:
    214
    в принципе идея не нова. очень походит на ТМТО Хелльмана. буквально недавно наткнулся на статью в журнале C't за 11.2008
    к сожалению журнал весит больше 100 мб, так что заливать не стану.
    вот есть док klick
     
  13. diehard

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

    Joined:
    30 Sep 2007
    Messages:
    442
    Likes Received:
    266
    Reputations:
    15
    Нет, кольца тут не при чем, это еще хуже, попробую пояснить математическим языком -

    А - конечное множество всех значений функции хеширования F()
    Так как существуют такие a и b из множества A (a не равно b), для которых существует коллизия F(a)=F(b)=c, то с учётом того что А - конечно, то область значений F() на множестве аргументов A не равна А и является подмножеством A. Т.е. не для всякого x из А существует такое y из A, что F(y)=x
     
  14. Cthulchu

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

    Joined:
    22 Nov 2007
    Messages:
    405
    Likes Received:
    705
    Reputations:
    85
    ну да, я говорил о том, что возможно, останунтся хеши, которые сбрутить нельзя, но их мало будет... наверное мало...
    Тобишь, ты обрисовал тот случай, когда среди всевозможных хешей, найдется такой, который не будет результатом хеширования какого-либо хеша. Согласен, но мы их упускаем. Почему-то я уверен в том (иначе сама идея не имеет смысла), что количество таких вот "иррациональных" хешей будет примерно 0.1% от всех возможных хешей.
     
  15. diehard

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

    Joined:
    30 Sep 2007
    Messages:
    442
    Likes Received:
    266
    Reputations:
    15
    На первый взгляд мне тоже кажется, что их мало, ведь входное множество конечно. А ведь можно как-то оценить частоту возникновения коллизий на конечном входном множестве?
     
  16. Cthulchu

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

    Joined:
    22 Nov 2007
    Messages:
    405
    Likes Received:
    705
    Reputations:
    85
    надо хорошо знать алгоритм хеширования и держать его в "оперативной памяти" мозга. Жаль, что Лебедя опять с нами нету. Птиц бы помог. Хватит, пора спать.
     
Loading...
Thread Status:
Not open for further replies.