Атака на хэши (часть вторая)

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

  1. -=lebed=-

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

    Joined:
    21 Jun 2006
    Messages:
    3,858
    Likes Received:
    1,962
    Reputations:
    594
    Статистика - великая сила! (или Атака на хэши часть II)

    [intro]
    Ну вот я и решил написать небольшое продолжение к Атака на хэши (практическое руководство)
    Статистика действительно вещь нужная и сильная в жизни, не даром существуют там всякие статуправления, аналитические агенства и т.п. Они собирают информацию, котороя может быть полезной во многих случаях.
    Вот и в плане брута хэшей, она может сыграть определённую положительную роль, о чём ещё писал Tanatoz в своём многостраничном труде. (Hybrid Rainbow - Введение в новый метод восстановления паролей.
    Вообщем так, допустим распределённым перебором или прогами на основе CUDA вы пробрутили весь диапазон паролей длинной 1-8 символов. И соответствие нужному хэшу так и не найдено. Ясное дело - пароль более чем 8 символов...

    [собираем статистику]
    Где взять статистические данные и каковы они должны быть для последующего эффективного использования?
    Ну конечно это должны быть реально используемые пароли в интернете - именно база таких паролей может дать хороший статистический результат, который мы в дальнейшем используем для брута, кроме того колличество таких паролей должно быть велико - от нескольких. млн. и более...
    Возьмём к примеру словарь сервиса hashcracking.info - он содержит в своей базе в основном реальные пароли (более 3 млн.), которые когда-то использовались, используются и вполне будут использоваться в интернете в будущем. А именно: общий Ачатовски сборник passwordspro.dic + пароли, пропарсенные с соответсвующих тем форума + расшифрованные участниками пароли с реальных хэшей, взятых из дампов баз и т.п. Берём оттуда только словарь, фильтруем убирая хэши в качестве пароля (которые являются исходным паролем для двойного мд5).
    Далее нам потребуется написать скрипт собирающий статистику с файла паролей, хотя можно воспользоваться готовым. Стату по словарю hashcracking.info любезно предоставил мне Basurman, за что ему отдельное спасибо. Для получения статы он использовал скрипт некоего [вырезано цензурой]... ;)
    Смотрим, что же у нас на выходе:
    1 Часть - статистика по используемым символам в пароле. (вопреки распрастранённому мнению чаще встречающаяся буква оказалась не "а", а "е")
    Code:
    3088368 words analyzed
    
    217 symbols' charset
    (chr	qty)
    (символ	 колличество)
    e - 	2081164
    a - 	1784381
    r - 	1324441
    i - 	1311775
    o - 	1277592
    s - 	1208981
    t - 	1140845
    n - 	1110775
    l - 	994024
    c - 	838318
    ---------------
    
    2 Часть - статистика по используемым маскам. (как видим лидирующую позицию занимают пароли из 8 символов из набора символов lowalpha).
    Code:
    65608 masks in this passfile
    (mask	qty	power)
    (маска	колличество - число возм. комбинаций)
    llllllll - 	990550 - 	208827064576
    llllll - 	729318 - 	308915776
    lllllll - 	273290 - 	8031810176
    lllll - 	183331 - 	11881376
    lllllllll - 	78817 - 	5429503678976
    llll - 	67685 - 	456976
    llllllllll - 	52544 - 	141167095653376
    lllllllllll - 	34111 - 	3.67034448698778e+015
    llllllllllll - 	26344 - 	9.54289566616822e+016
    lllllllllllll - 	18640 - 	2.48115287320374e+018
    dddddddd - 	15398 - 	100000000
    ddddddd - 	15285 - 	10000000
    -------------------------------------------------
    
    3 Часть - статистика по использованию символов, относительно местоположения конкретного символа в пароле.
    Code:
    Position 1:
    s - 	258621
    c - 	184198
    b - 	173505
    t - 	173252
    p - 	153434
    a - 	151506
    d - 	146465
    --------------
    Position 2:
    a - 	412252
    e - 	367070
    o - 	331805
    i - 	286756
    r - 	207614
    u - 	202239
    l - 	140165
    h - 	135627
    
    и т.д.
    
    [Анализ статистических данных]
    В статье я привёл конечно не полные статистические данные, а только самые верхние, но и даже на основании их уже можно разработать стратегию для атаки на большие списки хэшей (очереди сервисов типа hashcracking.info, md5.xek.cc, insidepro.com и т.п.)
    Посмотрим на вторую часть статистики, как мы видим, основное большинство паролей сосредоточено в диапазоне lowalpha, к чему бы это? Ответ прост: всё таки большинство пользователей используют в качестве пароля либо обычные английские слова, либо их сочетания, либо набирают в транслите пароль. С паролями <=7 символов в слове, нам не представит труда разделаться с ними атакой грубая сила (простой перебор по этому диапазону). В этом случае мы вытащим все, даже не имеющего никакого смысла слова, но встаёт вопрос, что делать с паролями 8 и более символов? Ведь перебор займёт уже более продолжительное время и оно при увеличении длинны пароля будет стремиться к тысячалетиям... Тут поступить можно так: Обратимся к первой части статистики и посмотрим, какие у нас самые часто используемые символы. Возьмём например не все 32 символа, а обрежем до 20 наш возможный набор символов. Вычислим колличество возможных комбинаций по формуле A^n (где A - число символов в наборе, n - длинна пароля)
    A=32 (lowalpha) n=8 (длиннна пароля 8) A^n=1 099 511 627 776 (колличество возможных паролей). Возьмём стандартную для современных компьютеров скорость перебора одного хэша 5 000 000 пасс/сек получаем t=219902сек (61,08 часов ~ 2,54 суток) расчётное время перебора этого диапазона.
    Для А=20 (lowalpha-12 символов, реже всех встречающихся) n=8 (длиннна пароля 8) A^n=25600000000, расчётное время перебора 5120 сек (1,42 часа)
    Как видим, сокращение диапазона возможных символов в наборе существенно сужает диапазон и требуемое время перебора. Для сравнения приведу аналогичные данные для паролей длинной 9 и 10 символов из всё того диапазона lowalpha:
    Code:
    [COLOR=White]А=32 n=9 A^n=35184372088832 t=7036875 сек ~ 1955 часов ~ 81,5 суток
    А=20 n=9 A^n=512000000000 t=102400 сек ~ 28,5 часов ~ 1,2 суток[/COLOR]
    
    [COLOR=White]А=32 n=10 A^n=1125899906842624 t=225179981 сек ~ 62550 часов ~ 2606 суток ~ более 7 лет!
    А=20 n=10 A^n=10240000000000 t=2048000 сек ~ 569 часов ~ 23,7 суток ~ менее месяца![/COLOR]
    
    Я думаю все заметили ощутимую разницу, когда я выбросил из полного lowalpha всего лишь 12 редко встречающихся символов.
    Т.е. мы видим тот факт, что атака грубой силой становится уже не приемлимой для пароля длинной 10 символов из диапазона lowalpha. Ещё раз взглянем на статистику (часть 2) таких паролей оказалось не много-не мало, а более 50К в нашем словаре. Прибавим сюда число паролей длинной 9 символов (78817) и получим 131361 паролей против 990550 (общее количество паролей длинной 8 символов из диапазона lowalpha). Наверно многие уже поняли к чему я клоню... (9-ти и 10-ти значные lowalpha занимают 5 и 7 места в рейтинге их общая доля более 4 %)
    Как же использовать все эти выкладки, спросите Вы? Читайте дальше (а кто догадался может не читать, а идти брутить по этой методе)...

    [Атака по маске - универсальная Атака]
    Если мы хотим сократить стандартные наборы символов в программе PasswordsPro то мы должны создать свой пользовательский набор(ы) символов.
    Конечно глупо было бы взять и тупо резануть набор lowalpha до 20 шт. не обратив внимания на положение символа в пароле. Ведь скорее всего может получится так, что как раз нужного символа и нехватит в нашем пользовательском наборе. Поэтому смотрим на третью часть нашей статы! Именно эта информация и поможет нам создать свои пользовательские наборы символов для каждой позиции в пароле. Смотрим 3 часть статы и собираем свои наборы символов, для примера я сделал это уже за Вас (для себя). Я брал по 20 самых часто используемых символов для каждой позиции. Вот что у меня получилось:
    наборы символов:
    Code:
    ?1 scbtpadmgrlfhenkwvji
    ?2 aeoirulhtncpysmbdfwk
    ?3 aerinosltucmdgpbhykf
    ?4 etsanrlidcompghkbufv
    ?5 easiotrlnhcdupmbgkfy
    ?6 eaoirnlstuchdmpgybkf
    ?7 eaiornstlucdhmgpkybf
    ?8 esatnrioldcghupmkbyf
    ?9 enrtsaidlo1gk02c3h9m
    ?0 enrtsidalgo1k023c956
    
    Проанализируем получившиеся наборы символов, как видим, уже на 9-ой позиции у нас полезли циферки из диапазона numeric. Проверим по статистике количество вхождений для маски lllllllldd - количество таких паролей всего 2381 (из выборки 3 млн.), у маски dddddddddd - 3829 шт. Вообщем смысл в том, что на 9 и 10 позиции в пароле уже на равне со строчными латинскими английскими могут играть и цифры, если мы просуммируем все возможные комбинации где на 9 и/или на 10 позиции цифры. В принципе мы можем оставить 9 и 10 наборы такими как есть, а можем и смело выбросить цифры, раз мы брутим только lowalpha длинной 6-10. Кому как нравится. Идём забивать получившиеся наборы в пользовательские и обнаруживаем что таких у нас всего может быть 8 шт. а не 10. Как быть?

    [Оптимизация наборов символов]
    Если взглянуть на наборы символов, то опытный глаз сразу скажет что тут, что-то не так! Конечно не так, в разных наборах присутствуют одни и теже символы, что не есть гуд! Визаульно набор наборов символов (простите за тафталогию) должны выглядеть не как квадратик, а как треугольник (учитывая то, что цифры в 9 и 10 позициях мы должны выкинуть и кое-что куда-нибудь перекинуть). Как привеcти данную матрицу к треугольному виду? Размерность [20,10]->[20,8] Это я оставляю Вам на домашнее задание...

    [заключение]

    Пример найденных паролей по данной методе:
    Вопрос брута хэшей всегда будет открыт. Эффективные статистические алгоритмы и математический анализ могут в конце концов вообще свести на нет стойкость осмысленного длинного пароля, состоящего из релевантных комбинаций символов. И останется только один путь защиты - использование длинного, труднозапоминаемого, сгенерированного самим компьютером пароля.
    Отдельное спасибо Basurman за предоставленную статистику по словарю hashcracking.info
    Это статья - лишь ещё одно руководство по эффективному бруту хэшей, для тех энтузиастов, кто этим занимается, для кого это своеобразное хобби и/или заработок.
    Жду Ваши Варианты оптимизации набора наборов пользовательских символов, можете выкладывать тут.
    Жду также статью от Basurman на аналогичную тему (более обзорную по той же тематике) в разделе Наши статьи (я думаю он меня простит за это очередное руководство...)
    (с) -=lebed=- для бруттеров Ачата
     
    #1 -=lebed=-, 3 Jun 2008
    Last edited: 3 Jun 2008
    12 people like this.
  2. [Paran0ik]

    [Paran0ik] Elder - Старейшина

    Joined:
    22 Dec 2006
    Messages:
    219
    Likes Received:
    145
    Reputations:
    16
    хотелось бы взглянуть на все результаты статистики...
     
  3. Basurman

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

    Joined:
    10 Nov 2006
    Messages:
    364
    Likes Received:
    271
    Reputations:
    29
    Все будет. и проги, и полная статистика,и все остальное :)

    P.S. я этот момент описывать тогда не буду снова
     
    #3 Basurman, 3 Jun 2008
    Last edited: 3 Jun 2008
    1 person likes this.
  4. -=lebed=-

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

    Joined:
    21 Jun 2006
    Messages:
    3,858
    Likes Received:
    1,962
    Reputations:
    594
    См. ответ постом выше от Basurman
    по hashcracking.info - полная стата - стратегическая приватная информация ;)
    ЗЫ В пользовательских наборах - конечная стата для паролей до 10 символов - оптимизируй их.
     
  5. -=lebed=-

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

    Joined:
    21 Jun 2006
    Messages:
    3,858
    Likes Received:
    1,962
    Reputations:
    594
    [Оптимизация наборов символов, мой вариант]
    Исходный вариант:
    Code:
    [/COLOR]
    ?1 scbtpadmgrlfhenkwvji
    ?2 aeoirulhtncpysmbdfwk
    ?3 aerinosltucmdgpbhykf
    ?4 etsanrlidcompghkbufv
    ?5 easiotrlnhcdupmbgkfy
    ?6 eaoirnlstuchdmpgybkf
    ?7 eaiornstlucdhmgpkybf
    ?8 esatnrioldcghupmkbyf
    ?9 enrtsaidlo1gk02c3h9m
    ?0 enrtsidalgo1k023c956
    
    начинаем попарно сравниваем наборы символов:

    1 vs 2
    ?1&?2 scbtpadmrlfhenkwi (есть в обоих наборах)
    ?1 gvJ (есть только в 1 наборе)
    ?2 oyu (есть только в 2 наборе)

    2 vs 3
    ?2&?3 aeoirulhtncpysmbdfk
    ?2 w (есть только в 2 наборе)
    ?3 g (есть только в 3 наборе)

    3 vs 4
    ?3&?4 aerinoslucmdgpbhkf
    ?3 y (есть только в 2 наборе)
    ?4 v (есть только в 3 наборе)

    4 vs 5
    ?4+?5 etsanrlidcompghkbufv
    Оказывается 4 и 5 наборы идентичны! Это удача, различие в порядке, а он для нас не имеет значения.
    Т.е. 4 и 5 - это фактически один и тот же набор символов. (Итого 10-1=9 наборов)

    5 vs 6
    ?5&?6 easiotrlnhcdupmbgkfy
    Упс! 5 и 6 наборы так же идентичны! -> 4-й идентичен и 6-му.
    Т.е. 4,5,6 - это фактически один и тот же набор символов. (Итого 10-1-1=8 наборов)

    Простой проверкой мы достигли нужного количества наборов символов (конечно можно и продолжить далее анализировать и сравнивать наборы) но мне этого уже достаточно, что мы имеем в итоге:

    Вычёркиваем 5 и 6 наборы, остальные переименовываем, далее убираем цифры из последних наборов, теперь оптимизированные наборы выглядят так:
    Конечный вариант
    Code:
    ?1 scbtpadmgrlfhenkwvji
    ?2 aeoirulhtncpysmbdfwk
    ?3 aerinosltucmdgpbhykf
    ?4 etsanrlidcompghkbufv
    ?5 eaiornstlucdhmgpkybf
    ?6 esatnrioldcghupmkbyf
    ?7 enrtsaidlogkchm
    ?8 enrtsidalgokc
    
    Вбиваем (копипастим отсюда) в пользовательские наборы в прогу PasswordsPro, ставим маску ?1?2?3?4?4?4?5?6?7?8 и брутим пароли до 10 символов!
    P.S. Удачного брута, х.е.з. чем Вас ещё заинтересовать... ;)
     
    #5 -=lebed=-, 4 Jun 2008
    Last edited: 4 Jun 2008
    Immune and Jes like this.
  6. -=lebed=-

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

    Joined:
    21 Jun 2006
    Messages:
    3,858
    Likes Received:
    1,962
    Reputations:
    594
    Если всё таки продолжить анализ дальше (лучше отсортировать символы в наборах по алфавиту), то мы увидим в них минимальные отличия (на 1-2 символа) а так же заметим что наборы 3,5,6 у нас снова идентичны (т.е. можно заменить одним).
    Code:
    1	2	3	4	5	6	7	8
    a	a	a	a	a	a	a	a
    b	b	b	b	b	b	c	c
    c	c	c	c	c	c	d	d
    d	d	d	d	d	d	e	e
    e	e	e	e	e	e	g	g
    f	f	f	f	f	f	h	i
    g	h	g	g	g	g	i	k
    h	i	h	h	h	h	k	l
    i	k	i	i	i	i	l	n
    j	l	k	k	k	k	m	o
    k	m	l	l	l	l	n	r
    l	n	m	m	m	m	o	s
    m	o	n	n	n	n	r	t
    n	p	o	o	o	o	s	
    p	r	p	p	p	p	t	
    r	s	r	r	r	r		
    s	t	s	s	s	s		
    t	u	t	t	t	t		
    v	w	u	u	u	u		
    w	y	y	v	y	y
    
    Тогда Конечный результат (вычёркиваем 5 и 6 наборы, 7 и 8 переименовываем):
    Code:
    ?1 scbtpadmgrlfhenkwvji
    ?2 aeoirulhtncpysmbdfwk
    ?3 aerinosltucmdgpbhykf
    ?4 etsanrlidcompghkbufv
    ?5 enrtsaidlogkc3hm
    ?6 enrtsidalgokc
    
    Маска примет вид ?1?2?3?4?4?4?3?3?5?6
    В итоге 2 пользовательских набора ещё в запасе!
     
    1 person likes this.
  7. desTiny

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

    Joined:
    4 Feb 2007
    Messages:
    1,005
    Likes Received:
    444
    Reputations:
    94
    Так-с! Слушаем сюда :)

    После прочтения родилась у меня ещё одна идейка.
    Итак, посмотрим сюда:

    Теперь предположим, что нам надо сбрутить пароль из 9 символов. Долго, однако...

    Но! используя данную статистику можно свести этот перебор к НЕМНОГОКРАТНОМУ перебору семи символов!

    Что для этого надо?
    Генерим сочетания (AB) из двух частых первых символов, как то:
    A|B
    s|a
    s|e
    s|o
    c|a
    c|e
    c|o
    b|a
    b|e
    b|o

    и брутим 9 раз по маске
    AB???????,
    где A и B - первый и второй символ.

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


    P.S. Лебедь, на этот раз честно заслуженный плюсик=) Первую часть статьи можешь смело задвинуть подальше;)
     
    1 person likes this.
  8. -=lebed=-

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

    Joined:
    21 Jun 2006
    Messages:
    3,858
    Likes Received:
    1,962
    Reputations:
    594
    desTiny ты немного не прав.
    Из того, что на первой позиции самые популярные символы s, c, b а на второй а е о далеко не вытекает то, что самые популярные сочетания на 1 и 2 позиции из них. Может получиться так, что их сочетания, наоборот, самые не популярные. Так что предложенной схемой руководствоваться не стоит.
    Другое дело, собрать статистические данные о самых популярных двухбуквенных комбинациях и обозначив каждую из ник, например уникальным id, потом брутить используя, в зависимости от местоположения такой пары по своему набору id, вот тогда будет толк, тут можно и 12-ти символьные попробовать (т.е.) брут сводится к 6-ти символьному перебору, где каждый символ - самые популярные пары символов, в зависимости от местоположения в пароле.
    ЗЫ Слухайте Лебедя... :D
     
    1 person likes this.
  9. desTiny

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

    Joined:
    4 Feb 2007
    Messages:
    1,005
    Likes Received:
    444
    Reputations:
    94
    Не факт. Зависит от статистических данных. Тут вообще можно долго размышлять о прелестях (И НЕДОСТАТКАХ!!) обоих методов, а можно посчитать, имея всю статистику (и, желательно, базу=))
     
Loading...