Depois de ler vários recursos sobre a força da senha, estou tentando criar um algoritmo que fornecerá uma estimativa aproximada de quanta entropia uma senha possui.

Estou tentando criar um algoritmo o mais abrangente possível. Neste ponto, só tenho pseudocódigo, mas o algoritmo cobre o seguinte:

• comprimento da senha
• caracteres repetidos
• padrões (lógicos)
• espaços de caracteres diferentes (LC, UC, Numérico, Especial, Estendido)
• ataques de dicionário

NÃO cobre o seguinte, e DEVE ABRIR BEM (embora não perfeitamente):

• ordenação (as senhas podem ser estritamente ordenadas pela saída desse algoritmo)
• padrões (espaciais)

Alguém pode fornecer algumas dicas sobre o que esse algoritmo pode ser fraco? Especificamente, alguém pode pensar em situações em que a alimentação de uma senha ao algoritmo superestima sua força? Subestimações são menos um problema.

O algoritmo:

// 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)

Algumas entradas e suas saídas entropy_bits desejadas e reais:

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"

O algoritmo percebe (corretamente) que aumentar o tamanho do alfabeto (mesmo em um dígito) fortalece muito as senhas longas, como mostra a diferença entre entropy_bits das 6ª e 7ª senhas, que consistem em 36 a, mas no segundo 21 é capitalizado. No entanto, eles não levam em conta o fato de que ter uma senha de 36 a não é uma boa idéia, é facilmente quebrada com um cracker de senha fraco (e qualquer pessoa que assiste a digitar o verá) e o algoritmo não reflete isso. .

No entanto, reflete o fato de que xkcd1 é uma senha fraca em comparação com o xkcd2, apesar de ter maior densidade de complexidade (isso é mesmo uma coisa?).

Como posso melhorar esse algoritmo?

Adenda 1

Ataques de dicionário e ataques baseados em padrões parecem ser a grande coisa, então vou tentar resolver esses problemas.

Eu poderia realizar uma pesquisa abrangente na senha por palavras de uma lista de palavras e substituir palavras por tokens exclusivos das palavras que elas representam. Os tokens de palavras seriam tratados como caracteres e teriam seu próprio sistema de ponderação e adicionariam seus próprios pesos à senha. Eu precisaria de alguns novos parâmetros de algoritmo (os chamarei lw, Nw ~ = 2 ^ 11, fw ~ = .5 e rfw) e fatoraria o peso na senha como faria com qualquer outro pesos.

Essa pesquisa de palavras pode ser modificada especialmente para combinar letras minúsculas e maiúsculas, bem como substituições de caracteres comuns, como a de E com 3. Se eu não adicionasse um peso extra a essas palavras correspondentes, o algoritmo subestimaria um pouco sua força. ou dois por palavra, o que é bom. Caso contrário, uma regra geral seria, para cada combinação de caracteres não perfeita, atribuir um pouco de bônus à palavra.

Eu poderia, então, executar verificações simples de padrões, como pesquisas por execuções de caracteres repetidos e testes derivativos (faça a diferença entre cada caractere), que identificariam padrões como 'aaaaa' e '12345' e substituir cada padrão detectado por um padrão token, exclusivo para o padrão e o comprimento. Os parâmetros algorítmicos (especificamente, entropia por padrão) podem ser gerados em tempo real com base no padrão.

Nesse ponto, eu pegaria o comprimento da senha. Cada símbolo de palavra e símbolo de padrão contaria como um caractere; cada token substituiria os caracteres que eles representavam simbolicamente.

Criei algum tipo de notação de padrão, mas inclui o comprimento do padrão l, a ordem do padrão o e o elemento base b. Esta informação pode ser usada para calcular algum peso arbitrário para cada padrão. Eu faria algo melhor no código real.

Exemplo modificado:

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

A semântica exata de como a entropia é calculada a partir de padrões está em discussão. Eu estava pensando em algo como:

entropy(b) * l * (o + 1) // o will be either zero or one

O algoritmo modificado encontraria falhas e reduziria a força de cada senha na tabela original, com exceção de s^fU¬5ü;y34G<, que não contém palavras ou padrões.

O Apêndice A na página 46 do NIST SP 800-63 fala sobre o trabalho de Claude Shannon , que estima a entropia de senha usando um número de bits. De fato, este é o documento que o desenho animado XKCD usa para calcular os bits de entropia. Especificamente:

• a entropia do primeiro caractere é considerada de 4 bits;
• a entropia dos próximos 7 caracteres é de 2 bits por caractere; isso é mais ou menos consistente com a estimativa de Shannon de que "quando efeitos estatísticos que se estendem por mais de 8 letras são considerados, a entropia é de aproximadamente 2,3 bits por caractere";
• para os caracteres de 9 a 20, a entropia é de 1,5 bits por caractere;
• para os caracteres 21 e acima, a entropia é considerada como 1 bit por caractere;
• Um "bônus" de 6 bits de entropia é designado para uma regra de composição que requer caracteres maiúsculos e não alfabéticos. Isso força o uso desses caracteres, mas em muitos casos, esses caracteres ocorrerão apenas no início ou no final da senha, e reduz um pouco o espaço total de pesquisa, de modo que o benefício é provavelmente modesto e quase independente do tamanho da senha. senha;
• Um bônus de até 6 bits de entropia é adicionado para uma verificação abrangente do dicionário. Se o invasor conhece o dicionário, ele pode evitar testar essas senhas e, de qualquer forma, conseguir adivinhar grande parte do dicionário, que, no entanto, serão as senhas selecionadas mais prováveis ​​na ausência de uma regra de dicionário. O pressuposto é que a maioria dos benefícios da entropia de adivinhação para um teste de dicionário se acumula em senhas relativamente curtas, porque qualquer senha longa que possa ser lembrada deve necessariamente ser uma "frase secreta" composta de palavras do dicionário, portanto o bônus diminui para zero em 20 personagens.

A ideia é que um sistema de autenticação escolha certos níveis de entropia como limites. Por exemplo, 10 bits podem ser fracos, 20 médios e 30 fortes (números escolhidos arbitrariamente como exemplo, não como recomendação). Infelizmente, o documento não recomenda esses limites, provavelmente porque o poder computacional disponível para força bruta ou adivinhar senhas aumenta com o tempo:

Como alternativa à imposição de um conjunto específico de regras arbitrárias, um sistema de autenticação pode classificar as senhas dos usuários, usando as regras descritas acima, e aceitar as que atendam a algum padrão mínimo de entropia. Por exemplo, suponha que senhas com pelo menos 24 bits de entropia sejam necessárias. Podemos calcular a estimativa de entropia de "Iamthe CapitanoftPina4" observando que a string possui 23 caracteres e satisfaria uma regra de composição que requer caracteres maiúsculos e não alfabéticos.

Isso pode ou não ser o que você está procurando, mas não é um ponto de referência ruim, se nada mais.

[Editar: adicionado o seguinte.]

O artigo Métricas de teste para políticas de criação de senhas atacando grandes conjuntos de senhas reveladas (por Matt Weir, Sudhir Aggarwal, Michael Collins e Henry Stern) demonstrou que o modelo de Shannon, descrito acima, não é um modelo preciso de entropia para senhas geradas por seres humanos. Eu recomendaria consultar a "Seção 5 Gerando novas políticas de criação de senha" para obter propostas mais precisas.

Confira o código fonte do KeePass na parte inferior desta página . A QualityEstimationclasse implementa um algoritmo bastante agradável, que parece estar alinhado com o que você deseja implementar. Meus resultados têm a seguinte aparência:

aaa                              8
aaaaaaaaa                        9
abcdefghi                       18
H0ley$Mol3y_                    73
s^fU¬5ü;y34G<                   99
[a^36]*                         10
[a^20]A[a^15]*                  18
Tr0ub4dor&3                     66
correct horse battery staple    98

Você pergunta

Especificamente, alguém pode pensar em situações em que alimentar uma senha com o algoritmo superestima sua força?

Mas você tem um exemplo na pergunta. Por padrão, o xkcd2 possui ~ 44 bits de entropia, mas sua estimativa é de 160,5 bits.

Alguém pode fornecer algumas dicas sobre o que esse algoritmo pode ser fraco? Especificamente, alguém pode pensar em situações em que alimentar uma senha com o algoritmo superestima sua força?

Você sugeriu alguns no preâmbulo (ataques de dicionário, etc). Essencialmente, há várias práticas comuns que podem ser adivinhadas pelo invasor, o que reduz muito o espaço de pesquisa. Tenho certeza de que seu algoritmo "superestima" o seguinte:

• em toda parte
• Em toda parte
• Everywhere1

A senha é bastante longa, mas é trivialmente quebrável, pois a palavra original aparece em um dicionário básico e as modificações são consideradas comuns o suficiente para fazer parte de qualquer ataque decente ao dicionário. As conversões típicas de letra -> número (ou seja, 3v3rywh3r3) também devem ser consideradas muito fracas e você deve penalizar por isso.

Em um grau muito menor, outras senhas com problemas podem ser aquelas que possuem padrões óbvios, como:

• abcdefghijklmnop
• abcde12345

Embora estes provavelmente sejam menos propensos a serem direcionados em ataques reais de dicionário, eles sofrem de problemas semelhantes ao exemplo "aaaaa ...".

Não tenho certeza se as frases de senha são atualmente segmentadas na maioria dos ataques de dicionário, mas sem dúvida, à medida que ganham popularidade, elas serão segmentadas cada vez mais. Eu acho que o famoso exemplo xkcd leva isso em consideração, uma vez que apenas 11 bits são atribuídos para cada "palavra comum". Seu algoritmo superestima esses tipos de senhas também.

Portanto, para resumir, o algoritmo faz um bom trabalho na estimativa, mas realmente deve levar em consideração a estrutura da senha e os padrões conhecidos e comuns.