Анализ реальных паролей пользователей и улучшенный полный перебор

    Прочитал сегодня на хабре перевод статьи Распределение символов в паролях. Захотелось провести свой небольшой анализ. Интерес для меня представляют длины паролей, первые символы паролей и используемые в паролях биграммы (пар смежных символов). А также в статье будет рассмотрен алгоритм улучшенного полного перебора паролей.

    Скачал архив с паролями отсюда: http://thepiratebay.org/torrent/6443601
    Использовал для анализа только 1 файл: Sony_Pictures_International_BEAUTY_USERS.txt
    Количество паролей: 20 921

    Картинки в статье кликабельны.

    Какие длины паролей самые популярные?




    Видно, что пароли пользователей имеют различные длины. Удивляет, что у пользователей встречаются пароли короче 6-ти символов. Странно, что система регистрации вообще позволяет использовать такие пароли. Количество паролей такой длины составляет менее 2,5% от всех общего числа паролей. Имеется 2 пароля длиной 35 — очень похоже, что они получены какой-нибудь программой для генерации паролей.

    Какие символы преобладают в паролях?




    Как и ожидалось, гласные по популярности на первом месте, за ними идут согласные с цифрами. Символы в верхнем регистре используются на порядок реже. Число символов в верхнем регистре составляют менее 2,8% от числа всех символов.

    С каких символов чаще всего начинаются пароли?




    Чаще всего пароли начинаются с символов s,m,b,c. Следующими по популярности являются символы p,t,d,a,j,l,r. Менее популярна группа символов g,k,1,h,f,w,n,e. Все остальные символы менее популярны в данном смысле.

    Какие биграммы (пары соседних символов) в паролях встречаются чаще других?




    Как видно из диаграммы, распределение биграмм весьма не случайное. Пять самых встречающихся биграмм в порядке уменьшения популярности:
    ar(1367), le(1315), on(1239), ie(1136), es(1134).

    Алгоритм линеаризации перебора слов разной длины, символы которых принадлежат счётному алфавиту.


    Теперь рассмотрим алгоритм линеаризации перебора комбинаций слов из двух символов. Символы принадлежат счётному алгоритму (не обязательно конечному).



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

    Отдельное внимание следует уделить обходу слов разной длины. Необходимо дополнительно линеаризовать обход «длины слова» и самого слова. Таким образом будут перебираться слова всех длин, символы которых принадлежат счётному множеству.

    По сути теперь перед нами стоит задача перебора слов всех длин и с бесконечным алфавитом. Алфавит на самом деле конечный, но в общем случае задачу так решать проще.

    Для чего может потребоваться вся это информация?


    Теперь составим следующие линейные списки:
    — Длины паролей
    — Первые символы паролей
    — Вторые символы биграмм

    Составим перечень длин паролей по их популярности:
    6, 8, 7, 9, 10, 11, 12, 13, 14, 16,15

    Составим перечень первых символов в паролях по их популярности:
    s,m,b,c,p,t,d,a,j,l,r,g,k,1,h,f,w,n,e,0,o,i,2,y,v,S,M,4,B,3,C,P,5,T,D,z,…

    Составим списки вторых символов из биграмм по популярности для заданных первых букв биграмм:
    e: s,l,n,e,y,t,1,b,r,c,w,2,v,x,f,3,4,a,7,5,k,6,9,j,h,u,d,m,8,z,p,o,…
    a: r,t,s,l,m,c,d,b,i,y,g,p,k,u,h,v,w,x,2,f,0,j,4,9,3,7,1,6,n,z,e,o,…
    o: n,o,r,l,m,u,s,g,v,k,b,d,c,1,2,x,i,w,p,t,0,3,6,j,z,5,9,7,e,y,a,8,…
    r: a,i,o,l,d,t,1,r,k,n,e,g,b,c,4,5,7,8,s,v,3,6,u,9,w,y,h,j,2,p,m,z,…


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

    Если тема окажется интересной сообществу, постараюсь получить номер пароля в последовательности паролей в одной из своих следующих статей.
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 44

      +6
      Вот еще анализ 62k паролей добытых LulzSec, но там информация совсем скудная.
        +1
        Зато там автор пытался классифицировать пароли по тем или иным признакам. Например, 12к паролей из 62к полностью состоят из цифр — это значительный процент. Все остальные обобщения плавают на уровне 3-5%. С точки зрения перебора по словарю они представляют интерес. С точки зрения брута я думаю столь малые доли не имеет смысла рассматривать.
        +21
        Судя по вашему анализу, мои пароли не пользуются популярностью, и это радует)
          +1
          Научный подход.
            0
            Можно существенно ускорить перебор паролей брутфорсом, хотя… с таким бэкграундом брутфорсом этот метод уже не назовешь)
              +8
              Можно назвать статфорсом. На основе статистик же))
                0
                в свое время, когда занимался UDC тоже использовал статистические методы. Считал декомпозицию паролей из большой базы (20 миллионов) на комбинации символов, идущие подряд, в зависимости от позиций, грубо — в начале, в середине, в конце.
                затем перебирал словарь_начальных_комбинаций x словарь_средних_комбинаций^n x словарь_конечных_комбинаций. какие-то оптимизации, чтобы выкидывать повторные проверки не проводил, но в целом это позволяло «восстанавливать» до 75% паролей меньше чем за час.
                  0
                  Если я правильно понял за час перебора вы получали 75% исходных паролей? Или нет? Это на одной персоналке?
                    0
                    да, перебирал на одной машине (причем лет 5 назад было, так что мощности соответствующие), а проценты от слитой, например с форума базы хешей. причем половина паролей подбирались буквально за пару минут.
                  0
                  смартфорс
                –1
                Тема интересна, развивайте. Еще бы увидеть алгоритм на языке программирования.
                  0
                  Тема очень интересная, но возник иной вопрос: чем анализировали базу паролей и чем создавали графики? Как раз ищу удобный инструмент для последнего.
                    +2
                    Не знаю, что использовал автор, но в любом случае рекомендую посмотреть в сторону R.
                      +1
                      Извините, но аббревиатура слишком коротка, чтобы искать её в интернете))
                        +4
                        Эмм… в википедии поиск отрабатывает на раз.
                        «R — язык программирования для статистической обработки данных и работы с графикой, а также свободная программная среда вычислений с открытым исходным кодом в рамках проекта GNU.»

                        Сайт проекта тут
                      0
                      Анализ производил самописной программой на плюсах. Графики их MS Excel.
                        0
                        хех, давно видно я в Excel не заглядывал, раз у них уже такие неплохие графики отрисовываются.

                        Ну а я бы тогда порекомендовал использовать матлаб, тк он как раз под эти задачи, а R для новика мозгодробителен.
                      +1
                      ага, научный подход :)
                      а нормализовать по частотам для обычного языка? и что-то мне подсказывает что после нормализации будет более случайное распределение. А следовательно перебор по словарю будет гораздо успешней.
                        +1
                        Сегодня вечером просто для интереса прогоню обычный текст и построю графики. Всё-таки пароли пользователей мне кажется более специфичны, чем просто текст. Чаще используются звонкие слова, например.
                          0
                          Не обычный текст, а только существительные и имена :)
                            0
                            Где такой взять?) Словарь туда загнать?
                              0
                              Собственно да, подвергнуть статистике словарный поиск паролей.
                          +1
                          Тут вопрос более глубокий. Если использовать полученные статистические данные для атаки на пользователей из приблизительно той же языковой и социальной группы, то никакая нормализация не нужна и использование результатов статистики даст выигрыш при переборе. Но вот если есть желание воспользоваться данной статистикой, как универсальной — то тут можно уже говорить о нормализации, но при этом полученные данные скорее всего приведут к мысли, что статистика бесполезна, что Вы и утверждаете. Следовательно, не стоит пользоваться конкретными результатами как неким плацебо, а нужно взять на вооружение сам механизм анализа и применять его к конкретным ситуациям. Но в любом случае практика — критерий истины, так что хорошо бы теперь посмотреть статистику получения выигрыша от использования буквенно-частотной статистики =)
                          +3
                          Судя по количественному анализу букв, у многих пароль должно быть: reason :) И кстати, биграммы интересные получились.
                            +1
                            Что-то мне подсказывает что существует 2 принципиально разных варианта:

                            1) Осмысленный пароль (фраза, комбинация, или еще что-то)
                            2) Сгенерированный пароль

                            Для сгенерированных паролей частотные анализы — заведомо ересь, потому как они случайны. Для осмысленных же перебор слов по словарю будет гораздо эффективней чем попытка эти слова сгенерировать.
                              0
                              Я думаю сгенерированных паролей не так много, чтобы они значительно повлияли на статистику.
                                +6
                                Есть пароли осмысленные для создающего, но случайные на первый взгляд — генерируемые не по случайному алгоритму.
                                  +1
                                  Есть не осмысленные «случайные» пароли и при этом не сгенерированные программами. Лично мне проще запомнить последовательность символов, которую я придумал сам, чем ту, которую выдала какая-то программа.
                                  +2
                                  Простите за занудство, но я уже не первый раз в топиках подобного содержания встречаю утверждения вроде «как видим, биграммы совсем не случайны».

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

                                  Далее, каждая случайная величина (возвращаясь к нашим баран биграммам, случайной величиной будет являться дискретная случайная величина со значениями в виде всевозможных биграмм) обладает своим законом распределения! И то, что очень и очень многие тут называют «случайно» на самом деле приравнивают по смыслу к «равновероятно». Закон распределения может быть каким угодно, вообще любым, и величина от этого случайной быть не перестанет. Закон распределения (для дискретной величины) есть множество значений величины и соответствующие им вероятности. Равномерный закон распределения — это очень частный случай! Давайте будем грамотнее.

                                  P.S.: пока писал комментарий, увидел, что тоже относится и к комментарию выше от товарища alexey_uzhva. Конечно, сгенерированные пароли случайны, однако закон распределения символов по их местам в пароле нам неизвестен. Ведь очевидно, что генератор вряд ли допустит последовательности «ааа» или «111», значит он уже не равномерный для каждой позиции. А проведенные в этом и предыдущем (а он как раз рассматривал только пароли, не подобравшиеся по словарю!) топиках исследования показывают, что он довольно интересный и может облегчить брут.
                                    +1
                                    Конечно, сгенерированные пароли случайны, однако закон распределения символов по их местам в пароле нам неизвестен. Ведь очевидно, что генератор вряд ли допустит последовательности «ааа» или «111», значит он уже не равномерный для каждой позиции.
                                    Однажды, когда военный генератор пароля случайно выдал осмысленную фразу, подтверждая древний тезис об обезьяне, которая способна сочинить «Войну и мир», паника поднялась на весь бывший СССР...
                                      +3
                                      Почему же не допустит последовательности «ааа» или «111»? Они могут сгенерироваться случайно.
                                        +1
                                        я думаю практически все на хабре знакомы с основами основ теории вероятности, и знают хотябы приблизительно, что такое функция распределения
                                          0
                                          Всё дело в том, что я проводил анализ не с точки зрения теории вероятности, а с точки зрения математической логики, дискретной математики и комбинаторики.
                                          –2
                                          Прочитал как «Анализ анальных паролей...». Не понял. Прочитал повторно — «Ректальный анализ паролей». Нажал на ссылку. Прочитал в третий раз. Окончательно проснулся.
                                          Мне пора к доктору, да?
                                            +1
                                            Воскресенье. 9 утра.
                                            • НЛО прилетело и опубликовало эту надпись здесь
                                              +1
                                              Это все конечно мило и познавательно, но неплохо было бы посмотреть на реальные оценки и испытания. Ведь нерабочие часы тоже показывают два раза в день правильное время
                                                0
                                                В следующей статье будет и код и результаты и оценки ускорения перебора.
                                                  +1
                                                  может с кодом поможет, реализация переборщика и генератора rainbow tables по частотным таблицам,
                                                    0
                                                      0
                                                      Не найдется у вас ссылки на описание этой техники. Было бы интересно почитать.
                                                +12
                                                – Учитель, я подобрал хороший пароль, которого не может быть в словарях.
                                                Инь Фу Во кивнул.
                                                – Я ввёл его в Гугле, – продолжал Сисадмин, – и убедился, что в Сети такого сочетания нет.
                                                – Теперь есть.

                                                  +1
                                                  Коллеги, может я не в теме, но о каких атаках идет речь? И какая практическая польза от словарей?

                                                  а) после неправильного ввода добавляем задержку (0.1 секунды, 0.2 секунды, 0.4 секунды, 0.8 секунда, 1.6, 3.2)
                                                  б) на 3-й неправильный ввод присылаем каптчу на вход
                                                  в) на 10-й неправльный вход блокируем вход в аккаунт.

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

                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                  Самое читаемое