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

Статистика - великая сила! (или Атака на хэши часть 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=- для бруттеров Ачата

 

хотелось бы взглянуть на все результаты статистики...

 

Все будет. и проги, и полная статистика,и все остальное

P.S. я этот момент описывать тогда не буду снова

 

См. ответ постом выше от Basurman
по hashcracking.info - полная стата - стратегическая приватная информация
ЗЫ В пользовательских наборах - конечная стата для паролей до 10 символов - оптимизируй их.

 

[Оптимизация наборов символов, мой вариант]​

Исходный вариант:

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. Удачного брута, х.е.з. чем Вас ещё заинтересовать...

 

Если всё таки продолжить анализ дальше (лучше отсортировать символы в наборах по алфавиту), то мы увидим в них минимальные отличия (на 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 пользовательских набора ещё в запасе!

 

Так-с! Слушаем сюда

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

Теперь предположим, что нам надо сбрутить пароль из 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. Лебедь, на этот раз честно заслуженный плюсик=) Первую часть статьи можешь смело задвинуть подальше

 

desTiny ты немного не прав.
Из того, что на первой позиции самые популярные символы s, c, b а на второй а е о далеко не вытекает то, что самые популярные сочетания на 1 и 2 позиции из них. Может получиться так, что их сочетания, наоборот, самые не популярные. Так что предложенной схемой руководствоваться не стоит.
Другое дело, собрать статистические данные о самых популярных двухбуквенных комбинациях и обозначив каждую из ник, например уникальным id, потом брутить используя, в зависимости от местоположения такой пары по своему набору id, вот тогда будет толк, тут можно и 12-ти символьные попробовать (т.е.) брут сводится к 6-ти символьному перебору, где каждый символ - самые популярные пары символов, в зависимости от местоположения в пароле.
ЗЫ Слухайте Лебедя...

 

Не факт. Зависит от статистических данных. Тут вообще можно долго размышлять о прелестях (И НЕДОСТАТКАХ!!) обоих методов, а можно посчитать, имея всю статистику (и, желательно, базу=))