Прочитал сегодня на хабре перевод статьи Распределение символов в паролях. Захотелось провести свой небольшой анализ. Интерес для меня представляют длины паролей, первые символы паролей и используемые в паролях биграммы (пар смежных символов). А также в статье будет рассмотрен алгоритм улучшенного полного перебора паролей.
Скачал архив с паролями отсюда: http://thepiratebay.org/torrent/6443601
Использовал для анализа только 1 файл: Sony_Pictures_International_BEAUTY_USERS.txt
Количество паролей: 20 921
Картинки в статье кликабельны.
![](https://habrastorage.org/r/w1560/storage/b03e15c1/a6a9458c/a079ffab/d58ca9bf.png)
Видно, что пароли пользователей имеют различные длины. Удивляет, что у пользователей встречаются пароли короче 6-ти символов. Странно, что система регистрации вообще позволяет использовать такие пароли. Количество паролей такой длины составляет менее 2,5% от всех общего числа паролей. Имеется 2 пароля длиной 35 — очень похоже, что они получены какой-нибудь программой для генерации паролей.
![](https://habrastorage.org/r/w1560/storage/cc025f85/6da0fc58/f74dafcb/c17f5b27.png)
Как и ожидалось, гласные по популярности на первом месте, за ними идут согласные с цифрами. Символы в верхнем регистре используются на порядок реже. Число символов в верхнем регистре составляют менее 2,8% от числа всех символов.
![](https://habrastorage.org/r/w1560/storage/897b3cb0/bdb4687a/bb4ac6e7/aef6dc7e.png)
Чаще всего пароли начинаются с символов s,m,b,c. Следующими по популярности являются символы p,t,d,a,j,l,r. Менее популярна группа символов g,k,1,h,f,w,n,e. Все остальные символы менее популярны в данном смысле.
![](https://habrastorage.org/r/w1560/storage/41efd3b8/1ea98c9e/cbfb661c/3ac91ac8.png)
Как видно из диаграммы, распределение биграмм весьма не случайное. Пять самых встречающихся биграмм в порядке уменьшения популярности:
ar(1367), le(1315), on(1239), ie(1136), es(1134).
Теперь рассмотрим алгоритм линеаризации перебора комбинаций слов из двух символов. Символы принадлежат счётному алгоритму (не обязательно конечному).
![](https://habrastorage.org/r/w1560/storage/63e99e39/19811e10/4288f99c/59c3a4d3.png)
Что делать, если у необходимо организовать перебор слов из трёх символов счётного алфавита? Придумывать формулы для обхода трёхмерного куба не хочется. Можно организовать обход квадрата, а один из символов интерпретировать как номер в последовательности обхода двухсимвольных слов. Таким образом можно организовать обход слов любой заданной длины.
Отдельное внимание следует уделить обходу слов разной длины. Необходимо дополнительно линеаризовать обход «длины слова» и самого слова. Таким образом будут перебираться слова всех длин, символы которых принадлежат счётному множеству.
По сути теперь перед нами стоит задача перебора слов всех длин и с бесконечным алфавитом. Алфавит на самом деле конечный, но в общем случае задачу так решать проще.
Теперь составим следующие линейные списки:
— Длины паролей
— Первые символы паролей
— Вторые символы биграмм
Составим перечень длин паролей по их популярности:
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,…
…
Теперь можно организовать линейный перебор паролей, начиная с самых популярных вариантов. И возможно решить обратную задачу. Из конкретного пароля вывести его номер в перебираемой последовательности. Это, правда, немного трудновато из-за того что список букв алфавита выбирается на основе предыдущей буквы.
Если тема окажется интересной сообществу, постараюсь получить номер пароля в последовательности паролей в одной из своих следующих статей.
Скачал архив с паролями отсюда: http://thepiratebay.org/torrent/6443601
Использовал для анализа только 1 файл: Sony_Pictures_International_BEAUTY_USERS.txt
Количество паролей: 20 921
Картинки в статье кликабельны.
Какие длины паролей самые популярные?
![](https://habrastorage.org/storage/b03e15c1/a6a9458c/a079ffab/d58ca9bf.png)
Видно, что пароли пользователей имеют различные длины. Удивляет, что у пользователей встречаются пароли короче 6-ти символов. Странно, что система регистрации вообще позволяет использовать такие пароли. Количество паролей такой длины составляет менее 2,5% от всех общего числа паролей. Имеется 2 пароля длиной 35 — очень похоже, что они получены какой-нибудь программой для генерации паролей.
Какие символы преобладают в паролях?
![](https://habrastorage.org/storage/cc025f85/6da0fc58/f74dafcb/c17f5b27.png)
Как и ожидалось, гласные по популярности на первом месте, за ними идут согласные с цифрами. Символы в верхнем регистре используются на порядок реже. Число символов в верхнем регистре составляют менее 2,8% от числа всех символов.
С каких символов чаще всего начинаются пароли?
![](https://habrastorage.org/storage/897b3cb0/bdb4687a/bb4ac6e7/aef6dc7e.png)
Чаще всего пароли начинаются с символов s,m,b,c. Следующими по популярности являются символы p,t,d,a,j,l,r. Менее популярна группа символов g,k,1,h,f,w,n,e. Все остальные символы менее популярны в данном смысле.
Какие биграммы (пары соседних символов) в паролях встречаются чаще других?
![](https://habrastorage.org/storage/41efd3b8/1ea98c9e/cbfb661c/3ac91ac8.png)
Как видно из диаграммы, распределение биграмм весьма не случайное. Пять самых встречающихся биграмм в порядке уменьшения популярности:
ar(1367), le(1315), on(1239), ie(1136), es(1134).
Алгоритм линеаризации перебора слов разной длины, символы которых принадлежат счётному алфавиту.
Теперь рассмотрим алгоритм линеаризации перебора комбинаций слов из двух символов. Символы принадлежат счётному алгоритму (не обязательно конечному).
![](https://habrastorage.org/storage/63e99e39/19811e10/4288f99c/59c3a4d3.png)
Что делать, если у необходимо организовать перебор слов из трёх символов счётного алфавита? Придумывать формулы для обхода трёхмерного куба не хочется. Можно организовать обход квадрата, а один из символов интерпретировать как номер в последовательности обхода двухсимвольных слов. Таким образом можно организовать обход слов любой заданной длины.
Отдельное внимание следует уделить обходу слов разной длины. Необходимо дополнительно линеаризовать обход «длины слова» и самого слова. Таким образом будут перебираться слова всех длин, символы которых принадлежат счётному множеству.
По сути теперь перед нами стоит задача перебора слов всех длин и с бесконечным алфавитом. Алфавит на самом деле конечный, но в общем случае задачу так решать проще.
Для чего может потребоваться вся это информация?
Теперь составим следующие линейные списки:
— Длины паролей
— Первые символы паролей
— Вторые символы биграмм
Составим перечень длин паролей по их популярности:
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,…
…
Теперь можно организовать линейный перебор паролей, начиная с самых популярных вариантов. И возможно решить обратную задачу. Из конкретного пароля вывести его номер в перебираемой последовательности. Это, правда, немного трудновато из-за того что список букв алфавита выбирается на основе предыдущей буквы.
Если тема окажется интересной сообществу, постараюсь получить номер пароля в последовательности паролей в одной из своих следующих статей.