Статистика - великая сила! (или Атака на хэши часть II)

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

[собираем статистику]

Где взять статистические данные и каковы они должны быть для последующего эффективного использования?
Ну конечно это должны быть реально используемые пароли в интернете - именно база таких паролей может дать хороший статистический результат, который мы в дальнейшем используем для брута, кроме того колличество таких паролей должно быть велико - от нескольких. млн. и более...
Возьмём к примеру словарь сервиса hashcracking.info - он содержит в своей базе в основном реальные пароли (более 3 млн.), которые когда-то использовались, используются и вполне будут использоваться в интернете в будущем. А именно: общий Ачатовски сборник passwordspro.dic + пароли, пропарсенные с соответсвующих тем форума + расшифрованные участниками пароли с реальных хэшей, взятых из дампов баз и т.п. Берём оттуда только словарь, фильтруем убирая хэши в качестве пароля (которые являются исходным паролем для двойного мд5).
Далее нам потребуется написать скрипт собирающий статистику с файла паролей, хотя можно воспользоваться готовым. Стату по словарю hashcracking.info любезно предоставил мне Basurman, за что ему отдельное спасибо. Для получения статы он использовал скрипт некоего [вырезано цензурой]...
Смотрим, что же у нас на выходе:
1 Часть - статистика по используемым символам в пароле. (вопреки распрастранённому мнению чаще встречающаяся буква оказалась не "а", а "е")
2 Часть - статистика по используемым маскам. (как видим лидирующую позицию занимают пароли из 8 символов из набора символов lowalpha).
3 Часть - статистика по использованию символов, относительно местоположения конкретного символа в пароле.

[Анализ статистических данных]

В статье я привёл конечно не полные статистические данные, а только самые верхние, но и даже на основании их уже можно разработать стратегию для атаки на большие списки хэшей (очереди сервисов типа 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:
Я думаю все заметили ощутимую разницу, когда я выбросил из полного lowalpha всего лишь 12 редко встречающихся символов.
Т.е. мы видим тот факт, что атака грубой силой становится уже не приемлимой для пароля длинной 10 символов из диапазона lowalpha. Ещё раз взглянем на статистику (часть 2) таких паролей оказалось не много-не мало, а более 50К в нашем словаре. Прибавим сюда число паролей длинной 9 символов (78817) и получим 131361 паролей против 990550 (общее количество паролей длинной 8 символов из диапазона lowalpha). Наверно многие уже поняли к чему я клоню... (9-ти и 10-ти значные lowalpha занимают 5 и 7 места в рейтинге их общая доля более 4 %)
Как же использовать все эти выкладки, спросите Вы? Читайте дальше (а кто догадался может не читать, а идти брутить по этой методе)...

[Атака по маске - универсальная Атака]

Если мы хотим сократить стандартные наборы символов в программе PasswordsPro то мы должны создать свой пользовательский набор(ы) символов.
Конечно глупо было бы взять и тупо резануть набор lowalpha до 20 шт. не обратив внимания на положение символа в пароле. Ведь скорее всего может получится так, что как раз нужного символа и нехватит в нашем пользовательском наборе. Поэтому смотрим на третью часть нашей статы! Именно эта информация и поможет нам создать свои пользовательские наборы символов для каждой позиции в пароле. Смотрим 3 часть статы и собираем свои наборы символов, для примера я сделал это уже за Вас (для себя). Я брал по 20 самых часто используемых символов для каждой позиции. Вот что у меня получилось:
наборы символов:
Проанализируем получившиеся наборы символов, как видим, уже на 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=- для бруттеров Ачата