Распределение символов в паролях

http://csgillespie.wordpress.com/2011/06/16/character-occurrence-in-passwords/
  • Перевод
Намедни наткнулся на интересные выводы анализа недавно утекших учеток с серверов Sony. Думаю эти выводы будут интересны и актуальны.

Как известно, в последнее время Sony выступает мальчиком для битья среди хакеров. Благодаря Sony, много учетных записей и паролей циркулируют в интернете. Недавно, Трой Хант провел небольшой анализ этих паролей. Вот выдержка его поста:
  • Из примерно сорока тысяч паролей, треть подвержена простой атаке по словарю.
  • Только один процент паролей содержал небуквенно-цифровые символы.
  • 93 процента паролей содержали от 6 до 10 символов.


В этом посте, мы исследуем остальные 24 тысячи паролей, которые выдержали атаку словарем.

Распределение символов

Как отмечает Трой, абсолютное большинство паролей содержало только один тип символов — или все в нижнем регистре, или все в верхнем. Однако, всё даже хуже, если мы рассмотрим частоту символов.

В базе паролей существуют 78 уникальных символов. Если эти пароли были бы по настоящему случайными, каждый символ должен встречаться с вероятностью 1/78 = 0,013. Но, когда мы посчитаем реальную частоту символов, мы явно увидим, что распределение не случайное. Следующий график показывает топ 20-ти парольных символов, а красная линия показывает ожидаемое 1/78 распределение.

image


Неудивительно, что гласные «e», «a» и «o» очень популярны, а также цифры «1», «2» и «0» (в этом порядке). Заглавные буквы не входят в топ двадцатку. Мы также можем построить график суммарной вероятности для символов. В этом графике, красные точки показывают ожидаемый паттерн при использовании настоящих случайных паролей (ссылка на график побольше).
image

Ясно, что пароли не так случайны как бы хотелось.

Порядок символов

Давайте рассмотрим порядок символов в пароле. Для простоты возьмем только 8-символьные пароли. Самая популярная цифра в пароле это «1». Если бы её расположение было случайным, то мы бы ожидали равномерное распределение. Но вместо этого мы получаем:
##Distribution of "1" over eight character passwords
0.06 0.03 0.04 0.04 0.13 0.13 0.22 0.34

Из этого следует, что из 84 процентов паролей, которые содержат цифру «1», эта цифра случается только во второй половине пароля. Ясно, что люди любят ставить единицу в конце пароля.

Та же картина с цифрой «2»:
0.05 0.05 0.04 0.05 0.13 0.11 0.30 0.27
И с "!"
#Small sample size here
0.00 0.00 0.00 0.00 0.00 0.11 0.16 0.74

Мы наблюдаем похожие паттерны и с остальными буквенно-цифровыми символами.

Число символов необходимых для угадывания пароля

Предположим, мы соберем все возможные пароли используя первые N самых популярных символов. Сколько паролей мы покроем в нашей выборке? Следующий график показывает пропорцию паролей покрытых в нашем списке используя первые N символов:
image
Для покрытия 50% паролей в списке, нам понадобилось 27 первых символов. Собственно, использование только 20 символов покрывает около 25% паролей, а использование 31 символа покрывает 80% паролей. Помните, что эти пароли не поддались атаке по словарю.

Итог

Обычно, когда мы подсчитываем вероятность угадывания пароля, мы предполагаем, что каждый символ выбирается с одинаковой вероятностью, то есть вероятность выбора «e» равна выбору «Z». Это явно неверно. Также, в последнее время много систем заставляют пользователей выбирать различные типы символов в паролях. А это так просто добавить циферку в конец. Я не хочу рассматривать эффективные техники подбора паролей, но понятно, что брутфорс не тот метод.

Лично, я забросил попытки запомнить пароли давным давно и просто использую менеджер паролей. Например мой Wordpress пароль длинее 12-ти символов и состоит из совершенно случайных цифр, букв и спец. символов. Конечно, вам лишь нужно держать свой менеджер паролей защищенным…

От переводчика: Да, я таки попал в категорию людей приписывающих единички и восклицательные знаки для обхода настырных сайтов. Sad but true.
Поделиться публикацией
Комментарии 50
    0
    Задумывался раньше об этом, но руки не доходили поискать информацию о частоте и распределении символов, очень познавательно.
      0
      Скорее всего предположение, что символы встречаются независимо друг от друга тоже не верно. Возможно, 2 следует сразу за 1, более часто, чем скажем 6.
        +3
        если пароль «неслучаен», то что все ожидали? частотное распределение букв еще никто не отменял! E!=Z по частоте, а наша А != Щ
        когда пароль придумывает пользователь, к нему так же применяется частотный анализ как и к другому тексту, несмотря на то что пароль «короткий текст».
          –2
          Закон Бенфорда в действии… забавно.
            +4
            А яндекс тем временем все еще запрещает использовать спец. символы в паролях… (как минимум в платежном пароле ЯД)
              0
              Его же все равно не зафорсить. Наверное это сделано для того, чтобы меньше людей внезапно забывали мудреный пароль (так как мало использовали Я.Деньги), что в случае отсутствия привязки мобильного и проживания не в Москве фактически означает потерю доступа к сервису.
                0
                Хм, у меня спецсимволы и в основном, и в платёжном. Они этот запрет давно ввели?
                –1
                Один мой товарищ (нет, не я сам) любил использовать МД5-хэши в качестве паролей. Выглядели они по-настоящему зубодробильными: тут тебе и буквы, и цифры, и длина большая. Однако при первом включении мозга стало понятно, что алфавит символов ограничен (0-9, A-F), а длина фиксированная, что сильно уменьшает диапазон символов для перебора злоумышленнику, знающему принцип формирования пароля.
                  –1
                  диапазон вариантов, а не символов
                  +1
                  По сути, md5 дает 128 бит, которые принято представлять в таком виде. Естественно, что перебирать всевозможные строки из 32 символов из этого диапазона — это примерно то же самое, что и 128-битные числа. Их все перебрать нереально…
                  Другое дело, что, если кто-то знает этот метод, то его применение ничем не поможет: можно подбирать не хеш, а сам пароль.
                    +1
                    использование в качестве пароля md5 хэша равносильно усложнению задачи брутеру, увеличив его временные затраты на величину, равную времени вычисления одного md5 умноженному на количество перебираемых паролей. Перебор действительно будет снова по обычному читабельному словарю. С учетом того, что современные алгоритмы вычисления хэша по паролю усиливаются десятками сотен дополнительных хэширований, добавление одного лишнего md5 погоды не делает
                      0
                      Согласен, что выручает длина. Но произвольный 32-символьный пароль был бы более стойким.
                      0
                      надо не в виде hex-цифр записывать, а кодировать в Base64
                        0
                        Обоснуйте, что это даст? Помимо уменьшения длины с 32 до 21-22 символов?
                          0
                          Слишком длинные пароли тоже не все сервисы/системы принимают, в принципе, ничего больше не даст.
                      +1
                      Исходя из первого графика, если прикинуть на глаз сумму вероятностей встречи топовых 20 символов, на оставшиеся 58 остается около 20 % (т.е. 0,2 так как сумма всех вероятностей должна давать единицу). Следовательно совсем не ясно с чем связаны выводы по третьему графику по поводу 27 первых символов и 50 % паролей…
                        0
                        То, что первые 20 символов составляют 80% всех символов, встреченных в паролях, не означает, что 80% паролей состоят только из них.
                          0
                          конечно не означает, но все же числа должны быть поближе, мне кажется. В статье определенно не хватает формул
                            0
                            Каких формул? По списку паролей все утверждения статьи легко проверяются.
                            При этом они более-менее независимы.
                            Пример. Рассматривается всего один пароль: 11111111111...11112 (100500 единичек и потом двойка). Тогда «1» составляет 99.999...% символов, встречающихся в паролях, и 0% паролей целиком состоят из единичек.
                        0
                        Интересно, есть ли ресурсы с бинарными паролями, а то всë символы да цифры
                          0
                          Alt+NumPad ;)
                            0
                            Я как-то использовал односимвольный пароль в одной игрушке: √
                            +2
                            Вот где сами пароли: thepiratebay.org/torrent/6443601
                            Можно провести свой собственный анализ, если хочется))
                            0
                            Постоянно встречаются рекомендации использовать разные символы в разных регистрах, или даже русские слова латинскими заместителями. Вроде бы это выглядит правильным. Но что показывает практика? Рассмотрим два случая. В обоих — пароли, сгенерированные KeePass, случайные и стойкие до безобразия 20 символов. Запомнить их, естественно, нельзя, надо где-то хранить. В случае с доступом через браузер с персоналки всё прекрасно — KeePass даёт возможность и в клипбоард положить пароль, и автоввод запустить.

                            Вариант 1) — у нас есть сотовый телефон. Так как раскладка русских букв на нём не соответствует раскладке на клавиатуре компьютера, запомнить куда нажимать при вводе паролей с русскими буквами малореально. Так как скорость переключения регистров и цифровой/буквенной клавиатур маленькая, ошибок при вводе много, ввод пароля из рекомендованных 20-ти символов становится приключением.

                            Вариант 2) — мы входим на удалённый сервер через IP KVM, проброс клипбоарда не работает => сложный пароль вводится долго, так долго, что можно не уложиться в отведённое для ввода время.

                            И что делать в таких ситуациях? Кроме уменьшения длины пароля и использование простого набора символов решения мне не видится.
                              0
                              Использую пароли с заменой русских символов английскими (правда не слова, но тут это значения не имеет) длиной 10 символов. Где-то за полгода использования экранной клавиатуры на планшете привык набирать стилусом символы английскими без временного переключения на русский, правда сами символы наизусть не помню, нужна кверти-клавиатура — помню взаимное расположение клавиш с нужными символами. Думаю, если буду постоянно пользоваться телефонной клавиатурой, то тоже запомню.
                                +4
                                Меня ещё при использовании менеджера паролей смущает зависимость от базы с паролями: её можно потерять, её может не оказаться под рукой в нужный момент, и т.п.

                                Для себя решил так:
                                — запоминаю только 1 сложный и длинный мастер-пароль;
                                — для каждого сайта (ресурса) составляю пароль в виде md5(сайт+мастер-пароль) в привычном 32-символьном виде.

                                Плюсы:
                                — помнить нужно немного;
                                — для каждого сайта автоматически получается уникальный и стойкий к перебору пароль;
                                — нет зависимости от хранилища паролей и конкретного менеджера;
                                — пароль можно сгенерировать на любом компьютере, не устанавливая спец. ПО, либо посчитать онлайн (я для удобства себе сайтик сделал);
                                — используются стандартные символы 0-9a-f, т.е. нет проблем с вводом на нестандартных клавиатурах и операционных системах.

                                Минусы:
                                — теоретически злоумышленник может узнать один мой md5-пароль, и, зная алгоритм, попытаться через brute force на мощной машине или кластере вычислить мастер-пароль и получить доступ ко всем паролям сразу. Но т.к. мастер-пароль длинный, то на практике нереально.

                                P.S. Про «уязвимости» MD5 знаю, они относятся к другим сферам применения хэшей, и для данной задачи криптостойкость не снижают.
                                  0
                                  Ну такой метод вообще не криптостойкий — подсмотреть мастер пароль, который постоянно набирается, просто. Это во-первых, а во-вторых для вычисления пароля для каждого сайта надо привлекать какую-то программу — так почему бы ей не быть тем же KeePass?

                                  У KeePass есть только один недостаток — если к нему получить доступ, все пароли улетают. И при нынешнем беспорядке с android market это совсем не фантастика.
                                    0
                                    Подсмотреть — это типа через плечо? Ну так и пароль к KeePass можно подсмотреть, а пока Вы отлучитесь за кофе стянуть базу.
                                    Программу для удобства я использую, но она не является необходимостью. MD5 можно и в терминале посчитать, и онлайн. И база с собой не нужна.

                                    Я не агитирую, но для меня этот способ удобнее.
                                  0
                                  Именно поэтому и надо выбирать KeePass, а не «Мега-супер-пароле-хранилку» — потому что KeePass есть для всех платформ, включая мобильные телефоны.
                                  0
                                  Обычно, когда мы подсчитываем вероятность угадывания пароля, мы предполагаем, что каждый символ выбирается с одинаковой вероятностью, то есть вероятность выбора «e» равна выбору «Z». Это явно неверно.

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

                                  Радует, что если кто будет использовать результаты этого исследования для брутфорса 99% паролей (согласно вторму графику), то подобрать мои основные не сможет :) Не радует, что цифры в конце будут прежде всего подбирать :( В начало их что ли во всех паролях перенести ;)
                                    0
                                    | «это очевидно для тех, кто понимает, что буквы
                                    | в словах естественного языка распределяются
                                    | неравномерно и что подавляющее большинство
                                    | паролей являются не рандомной последовательностью
                                    | символов из допустимого алфавита, а чем-то
                                    | осмысленным, мнемоничным и так или иначе
                                    | коррелирует с естественными языками»

                                    Это справедливо без исключений для пользователей, набирающих пароль в раскладке своего родного языка.
                                    Конечно, это существенно облегчает вскрытие.

                                    Для остальных пользователей, у которых установлено >1 раскладки клавиатуры, набор pronouneable-пароля в другой раскладке, уже давно стал одним из способов его усложнения.
                                    Надеюсь, в алгоритмах взлома паролей это можно учесть и использовать.
                                    0
                                    По сути, эта информация может помочь при атаке брутфорсом. То есть если со словарём — пролёт, выставляем параметры длина от 6 до 10. Символы — будет достаточно тех, что на втором графике до буквы j
                                    + можно еще как то учесть, что цифры, в основном — в конце.

                                    Правда всё равно, время это не сильно сэкономит. Единственное, странно, что пароли хранились в открытом виде, а не в виде хэша. Если храняться в виде хэша — можем еще и на коллизию нарваться.
                                      0
                                      Шансы случайно нарваться на коллизию пренебрежимо малы (естественно, полагая хеш-функцию хорошей).
                                      При брутфорсе это сильно облегчит жизнь. Например, если мы будем перебирать пароли, пользуясь алфавитом в 27 символов, а не в 56, то, скажем для длины 8 мы получим ускорение в (56/27)^8 ~ 342 раза.
                                      0
                                      Система, которой нужен пароль больше 5-6 символов (то есть подверженная брутфорсу) — ошибочна по-определению и должна использовать нормальную крифтографию (сертификаты, открыте/закрытые ключи), а не пароли в цать символов юникода.
                                        0
                                        ИМХО вы смешиваете криптографию с аутентификацией.
                                          0
                                          Я не смешиваю, я говорю, что если система не выдерживает атаки на 4-5 символьный пароль, значит эта система напрасно хочет пароль, она должна использовать другие средства аутоидентификации.
                                            0
                                            Можете привести пример любой системы выдерживающей атаку брутфорсом на 4 символа?
                                              +1
                                              Сим-карта? Security token? Любая железка, уходящая в несознанку при бруте.
                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                  0
                                                  А без железки, какие варианты?
                                                • НЛО прилетело и опубликовало эту надпись здесь
                                            0
                                            интересно, а если сделать такой же анализ, только в отношении хешей? типа для ускорения подбора.
                                              +1
                                              Вообще-то благодаря лавинному эффекту в криптографических хэш-функциях распределение бит в выходном множестве должно быть равномерным.
                                              +1
                                              Скажите пожалуйста, не является ли буфер обмена слабым местом, при использовании супер сложных паролей с менеджером паролей? Ведь как я понимаю, сложный пароль никто не запоминает и вручную не переписывает.
                                              Могут ли зловреды и сайт втихую съесть ваш буфер обмена?
                                              И на сколько буфер обмена вообще защищен?

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

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