Прочитав различные ресурсы о надежности пароля, я пытаюсь создать алгоритм, который обеспечит приблизительную оценку степени энтропии пароля.
Я пытаюсь создать алгоритм как можно более полным. На данный момент у меня есть только псевдокод, но алгоритм охватывает следующее:
- длина пароля
- повторяющиеся символы
- шаблоны (логические)
- различные символьные пространства (LC, UC, Numeric, Special, Extended)
- словарные атаки
Это НЕ покрывает следующее, и ДОЛЖНО покрывать это ХОРОШО (хотя и не идеально):
- упорядочение (пароли могут быть строго упорядочены при выводе этого алгоритма)
- шаблоны (пространственные)
Кто-нибудь может дать некоторое представление о том, что этот алгоритм может быть слабым? В частности, кто-нибудь может подумать о ситуациях, когда подача пароля к алгоритму переоценила бы его силу? Недооценка является меньшей проблемой.
Алгоритм:
// the password to test
password = ?
length = length(password)
// unique character counts from password (duplicates discarded)
uqlca = number of unique lowercase alphabetic characters in password
uquca = number of uppercase alphabetic characters
uqd = number of unique digits
uqsp = number of unique special characters (anything with a key on the keyboard)
uqxc = number of unique special special characters (alt codes, extended-ascii stuff)
// algorithm parameters, total sizes of alphabet spaces
Nlca = total possible number of lowercase letters (26)
Nuca = total uppercase letters (26)
Nd = total digits (10)
Nsp = total special characters (32 or something)
Nxc = total extended ascii characters that dont fit into other categorys (idk, 50?)
// algorithm parameters, pw strength growth rates as percentages (per character)
flca = entropy growth factor for lowercase letters (.25 is probably a good value)
fuca = EGF for uppercase letters (.4 is probably good)
fd = EGF for digits (.4 is probably good)
fsp = EGF for special chars (.5 is probably good)
fxc = EGF for extended ascii chars (.75 is probably good)
// repetition factors. few unique letters == low factor, many unique == high
rflca = (1 - (1 - flca) ^ uqlca)
rfuca = (1 - (1 - fuca) ^ uquca)
rfd = (1 - (1 - fd ) ^ uqd )
rfsp = (1 - (1 - fsp ) ^ uqsp )
rfxc = (1 - (1 - fxc ) ^ uqxc )
// digit strengths
strength =
( rflca * Nlca +
rfuca * Nuca +
rfd * Nd +
rfsp * Nsp +
rfxc * Nxc ) ^ length
entropybits = log_base_2(strength)
Несколько входов и их желаемые и фактические выходы entropy_bits:
INPUT DESIRED ACTUAL
aaa very pathetic 8.1
aaaaaaaaa pathetic 24.7
abcdefghi weak 31.2
H0ley$Mol3y_ strong 72.2
s^fU¬5ü;y34G< wtf 88.9
[a^36]* pathetic 97.2
[a^20]A[a^15]* strong 146.8
xkcd1** medium 79.3
xkcd2** wtf 160.5
* these 2 passwords use shortened notation, where [a^N] expands to N a's.
** xkcd1 = "Tr0ub4dor&3", xkcd2 = "correct horse battery staple"
Алгоритм действительно понимает (правильно), что увеличение размера алфавита (даже на одну цифру) значительно усиливает длинные пароли, о чем свидетельствует разница в entropy_bits для 6-го и 7-го паролей, которые оба состоят из 36 а, а второго 21 а - капитализируются. Тем не менее, они не учитывают тот факт, что иметь 36-значный пароль не очень хорошая идея, его легко взломать слабым взломщиком паролей (и любой, кто наблюдает за вашим вводом, увидит его), и алгоритм не отражает это ,
Это, однако, отражает тот факт, что xkcd1 является слабым паролем по сравнению с xkcd2, несмотря на большую плотность сложности (это даже вещь?).
Как я могу улучшить этот алгоритм?
Приложение 1
Атаки по словарю и атаки на основе шаблонов, кажется, очень важны, поэтому я попытаюсь решить их.
Я мог бы выполнить всесторонний поиск по паролю слов из списка слов и заменить слова токенами, уникальными для слов, которые они представляют. Затем текстовые токены будут обрабатываться как символы и иметь собственную систему весов и добавлять свои собственные веса к паролю. Мне понадобятся несколько новых параметров алгоритма (я назову их lw, Nw ~ = 2 ^ 11, fw ~ = .5 и rfw), и я бы учел вес в пароле, как любой другой веса.
Этот поиск слов может быть специально изменен, чтобы соответствовать как строчным, так и прописным буквам, а также замене общих символов, например, для E с 3. Если бы я не прибавлял дополнительный вес к таким подобранным словам, алгоритм немного переоценил бы их силу. или два за слово, что нормально. В противном случае общим правилом будет то, что для каждого несовершенного совпадения символов дается слово бонусный бит.
Затем я мог бы выполнить простые проверки шаблонов, такие как поиск прогонов повторяющихся символов и производных тестов (взять разницу между каждым символом), которые бы идентифицировали шаблоны, такие как «aaaaa» и «12345», и заменять каждый обнаруженный шаблон на шаблон. жетон, уникальный по шаблону и длине. Алгоритмические параметры (в частности, энтропия для каждого шаблона) могут быть сгенерированы на лету на основе шаблона.
На этом этапе я бы взял длину пароля. Каждый жетон слова и лексема шаблона будут считаться одним символом; каждый токен заменяет символы, которые они символически представляют.
Я составил некоторую нотацию шаблона, но она включает в себя длину шаблона l, порядок шаблона o и базовый элемент b. Эта информация может быть использована для вычисления некоторого произвольного веса для каждого шаблона. Я бы сделал что-то лучше в реальном коде.
Модифицированный пример:
Password: 1234kitty$$$$$herpderp
Tokenized: 1 2 3 4 k i t t y $ $ $ $ $ h e r p d e r p
Words Filtered: 1 2 3 4 @W5783 $ $ $ $ $ @W9001 @W9002
Patterns Filtered: @P[l=4,o=1,b='1'] @W5783 @P[l=5,o=0,b='$'] @W9001 @W9002
Breakdown: 3 small, unique words and 2 patterns
Entropy: about 45 bits, as per modified algorithm
Password: correcthorsebatterystaple
Tokenized: c o r r e c t h o r s e b a t t e r y s t a p l e
Words Filtered: @W6783 @W7923 @W1535 @W2285
Breakdown: 4 small, unique words and no patterns
Entropy: 43 bits, as per modified algorithm
Точная семантика того, как энтропия рассчитывается по шаблонам, подлежит обсуждению. Я думал что-то вроде:
entropy(b) * l * (o + 1) // o will be either zero or one
Модифицированный алгоритм найдет недостатки и уменьшит надежность каждого пароля в исходной таблице, за исключением того s^fU¬5ü;y34G<
, что не содержит слов или шаблонов.
Ответы:
Приложение A на стр. 46 NIST SP 800-63 рассказывает о работе Клода Шеннона , который оценивает энтропию пароля, используя несколько битов. Действительно, это документ, который мультфильм XKCD использует для вычисления битов энтропии. В частности:
Идея состоит в том, что система аутентификации выберет определенные уровни энтропии в качестве пороговых значений. Например, 10 битов могут быть слабыми, 20 средних и 30 сильных (числа, выбранные произвольно в качестве примера, а не рекомендации). К сожалению, документ не рекомендует такие пороговые значения, возможно, потому что вычислительная мощность, доступная для перебора или угадывания паролей, увеличивается со временем:
Это может или не может быть то, что вы ищете, но это не плохой ориентир, если не что иное.
[Редактировать: Добавлено следующее.]
В статье « Тестирование метрик для политик создания паролей путем атаки на большие наборы выявленных паролей» (Мэтт Вейр, Судхир Аггарвал, Майкл Коллинз и Генри Стерн) продемонстрировано, что модель Шеннона, описанная выше, не является точной моделью энтропии для паролей, созданных человеком. Я бы порекомендовал взглянуть на «Раздел 5 Создание новых политик создания паролей» для более точных предложений.
источник
Проверьте исходный код для KeePass внизу этой страницы . В
QualityEstimation
классе реализован довольно приятный алгоритм, который, кажется, соответствует тому, что вы ищете. Мои результаты выглядят так:источник
Ты спрашиваешь
Но у вас есть пример в вопросе. Конструктивно xkcd2 имеет ~ 44 бита энтропии, но ваша оценка составляет 160,5 бита.
источник
Вы намекали на некоторые из них в преамбуле (словарные атаки и т. Д.). По сути, злоумышленник может угадать ряд общих практик, которые значительно уменьшают пространство поиска. Я уверен, что ваш алгоритм «переоценит» следующее:
Пароль довольно длинный, но его можно легко взломать, поскольку исходное слово появляется в базовом словаре, а изменения считаются достаточно общими, чтобы стать частью любой достойной атаки по словарю. Типичные буквы -> преобразования чисел (т.е. 3v3rywh3r3) также следует считать довольно слабыми, и за них следует наказать.
В гораздо меньшей степени пароли других проблем могут иметь такие же шаблоны, как:
Хотя они, вероятно, менее подвержены атакам по словарю, они страдают от тех же проблем, что и ваш "aaaaa ..." пример.
Я не уверен, что парольные фразы в настоящее время нацелены на большинство атак по словарям, но, без сомнения, по мере того, как они набирают популярность, они будут нацеливаться все больше и больше. Я думаю, что известный пример xkcd учитывает это, поскольку для каждого "общего слова" назначается только 11 битов. Ваш алгоритм также переоценивает эти типы паролей.
Подводя итог, можно сказать, что алгоритм хорошо справляется с оценкой, но в действительности он должен учитывать структуру пароля и распространенные известные шаблоны.
источник