Para determinar qual a força de uma senha, é preciso analisar como os atacantes procedem ao tentar quebrar um senha. Este excelente artigo do Bruce Schneier (em inglês) descreve o estado da arte em quebra de senhas, seja de modo "cego" (i.e. quando não se sabe nada sobre o usuário em questão) ou direcionado. Também se considera o cenário em que o atacante possui acesso a dados da vítima (por exemplo, uma cópia de seu disco rígido), mas isso extrapola o escopo da pergunta.
Formas de ataque
O conjunto de senhas possíveis é virtualmente infinito, salvo caso em que exista um limite de tamanho. Entretanto, o conjunto de senhas prováveis é muitíssimo menor. Considere uma senha de 8 letras, por exemplo. É muito mais provável que o usuário escolha uma que contenha uma palavra do que simplesmente um conjunto aleatório de caracteres (tipo yrhxmmpl
). Um ataque que tentasse todas as combinações de 8 letras (208 bilhões) teria uma taxa de sucesso menor que um que tentasse, digamos, todas as palavras dos 11 idiomas mais falados (3,2 milhões).
Determinar quais são as senhas mais "prováveis" não é difícil: basta fazer uma análise estatística. Pode-se fazer isso com os usuários do seu próprio serviço, ou usar dados de algum dos diversos "vazamentos" de senhas que sempre ocorrem ao redor do mundo (muitas vezes envolvendo empresas grandes, com muitos clientes, de modo que a amostragem é significativa). A título de exemplo, algumas conclusões mencionadas no artigo:
Algumas senhas são muito comuns, apesar de sua fraqueza (password
, letmein
, 123456
, etc). Compensa testar por uma lista das, digamos, 1000 senhas mais comuns antes de qualquer outra coisa.
- Se combinado com os 100 afixos mais comuns (ver abaixo), esse conjunto de 100.000 candidatos chegam a quebrar quase 25% das senhas.
O formato mais comum de senha consiste numa "raiz" e um "afixo". Sufixos são mais comuns que prefixos. A raiz normalmente é uma palavra - talvez transformada segundo algumas regras simples (ex.: s -> $
, a -> @
, t -> 7
, etc) ou um nome próprio. O afixo em geral é um número, um símbolo especial, ou ambos.
- Estima-se que este teste é suficiente para quebrar de 55% a 65% das senhas, embora o tempo gasto seja da ordem de semanas.
Quando se usa informações pessoais da vítima em conjunto com os ataques acima (seja analisando outras senhas conhecidas da mesma, para identificar padrões comuns, seja pegando nomes, endereços, números, etc e acrescentando aos dicionários de raízes e afixos antes de efetuar o ataque) a taxa de sucesso aumenta um pouco, e o tempo gasto no ataque diminui bastante.
Por fim, quando o ataque de dicionário se mostra ineficaz, ainda é preferível testar por coisas que se pareçam com palavras do que simplesmente por strings aleatórias. Sequências aleatórias porém pronunciáveis têm mais chance de serem usadas como senhas do que aquelas que não o são.
Esta não é a única forma de ataque, naturalmente, mas é a mais eficaz. Se um "tipo" de senha torna-se muito popular, adaptar o ataque a esse tipo daria uma chance maior do que um ataque genérico. Cabe notar também que os padrões apresentados acima decorrem quase que diretamente das políticas que as empresas impõem na escolha de senhas: se todo mundo pede "uma letra, um número e um caractere especial", os usuários vão escolher a sequência mais simples que satisfaça a esses critérios mínimos, e trocar experiências e "dicas" uns com os outros - levando a um padrão que tecnicamente cumpre os requisitos mas não conferem a proteção almejada.
Senhas fortes
Uma senha forte é simplesmente uma senha que não será detectada pelo padrão usado pelo atacante, seja porque não pertence ao conjunto testado ou porque até pertence, mas será testado por último segundo as regras. Torna-se tentador simplesmente rejeitar o padrão, mas assim acaba-se por simplesmente cair em um outro padrão. Em especial porque, se seu serviço vai rejeitar senhas segundo algum critério objetivo, é muito importante informar o usuário de quais são esses critérios (para evitar por exemplo o drama do repolho... :P). E ao fazê-lo, também se informa ao atacante que tipo de senha é inútil tentar...
Mas uma razão ainda mais importante para não se criar regras arbitrárias para senhas é que é preciso levar em conta o fator humano da segurança, não só o fator "máquina". Como já satirizado no XKCD e bem debatido no security.SE, uma senha precisa ser difícil para a máquina adivinhar e fácil pro usuário lembrar. Ignorar essa segunda parte leva a práticas ainda mais prejudiciais à segurança que uma senha fraca, como por exemplo o hábito de anotar a senha num post-it e colá-lo no monitor.
Felizmente, existem maneiras de se produzir senhas que sejam relativamente simples de serem lembradas e bastante difíceis de serem adivinhadas - ainda que o padrão utilizado seja conhecido. Uma delas é o uso da primeira letra de cada palavra de uma frase [relativamente longa], pois uma senha produzida dessa forma é quase indistinguível de uma sequência aleatória[citation needed].
Entropia
Respondendo finalmente à pergunta: o método formal para se determinar a força de uma senha é a entropia (tal como definida na Teoria da Informação; não confundir com o conceito de mesmo nome na Termodinâmica). Pois como a senha consiste em um segredo que o dono conhece mas o atacante não conhece, sua segurança reside no fato de que uma tentativa de "adivinhar" essa senha (i.e. escolher a possibilidade correta num conjunto de valores possíveis) tenha uma chance negligível de sucesso. Entretanto, não basta o conjunto ser grande, se alguns candidatos ocorrem com muito mais frequência nesse conjunto do que a média, diz-se que a entropia do mesmo é baixa.
E é bom deixar isso bem claro: a entropia não é uma característica da senha em si, e sim do processo que originou aquela senha. A pergunta que se precisa fazer é: "ao se utilizar o processo X para escolher uma senha, qual a probabilidade da senha Y ser escolhida?".
Medir a entropia é algo complicado, e sujeito a muitos erros. A título de exemplo, um método comum para se estimar a força da senha é verificar a quais conjuntos de caracteres os componentes da senha pertencem, e assumir que uma senha de tamanho N pertence ao conjunto de de strings possíveis com N caracteres desse conjunto. Esse método é falho porque - assumindo uma senha como Password1$
- se estabelece que o tamanho do conjunto é 95 (letras maiúsculas, minúsculas, dígitos e símbolos ASCII) e o tamanho da senha é 10, e se estima "65 bits de entropia" (log2 9510), o que seria uma senha bastante forte! Mas se o cálculo for feito de uma outra forma - digamos uma palavra na lista das 1000 mais comuns (10 bits), com ou sem a primeira letra maiúscula (1 bit), seguida de um dígito (3.3 bits) e um símbolo especial (5 bits), numa ou outra ordem (1 bit), se chega a 20.3 bits de entropia, revelando se tratar de uma senha demasiadamente fraca...
(A propósito, qual desses dois cálculos está correto? Ora, ambos! O procedimento de se gerar uma senha aleatória com 10 caracteres ASCII vai chegar a Password1$
uma vez em 265, e o procedimento de se escolher uma palavra numa lista de 1000 [que contenha password
], capitalizar ou não, e acrescentar um dígito e um símbolo vai chegar a Password1$
uma vez em 220.3. Lembre-se: a entropia é do processo, não da senha. Se existe algo como a "força da senha", eu diria que se trata da menor entropia dentre todas as estratégias "razoáveis" que um usuário pode ter empregado para escolher sua senha. Mas isso não deixa de ser subjetivo.)
Ainda assim, pode-se estabelecer limites inferiores para a entropia. Uma senha de 8 letras minúsculas, por exemplo, terá no máximo 37 bits de entropia (log2 268). Provavelmente menos, mas nunca mais. Pois uma senha com esse formato comporta apenas 37 bits de entropia. Fala-se muito que senhas mais longas são mais seguras que senhas mais curtas, mas isso não é verdade em todas as situações (pqzrwj
é uma senha mais segura que password1
) - o que é verdade é que numa senha mais longa "cabe" mais entropia que numa senha mais curta. Escolher uma senha forte e memorável com 20 caracteres é mais fácil que fazer o mesmo com 8.
Aplicando a análise de entropia para determinar a "força" da senha
Se existem N maneiras diferentes de se calcular a entropia, qual delas é a mais "correta", ou talvez mais "útil"? Eu diria que se pode dividir a análise em dois casos: um que leva em consideração o caso médio, e outra que leva em consideração o pior caso.
Suponha que existam E
estratégias que o atacante poderia usar para tentar descobrir uma senha. Cada estratégia representa um procedimento específico de geração (escolha) de senha. Associado a cada procedimento, pode-se também associar meios de se medir/estimar a entropia do mesmo. Alguns exemplos de procedimentos, e estratégia correspondente, seriam:
P0 - Gerar uma senha aleatória de 8 caracteres.
E0 - Testar todas as sequências de 8 caracteres uma por uma.
M0 - Calcular o tamanho do menor alfabeto que contém a senha, elevado ao tamanho da senha.
P1 - Escolher uma palavra do dicionário e anexar um sufixo numérico.
E1 - Escolher um dicionário, testar todas as palavras desse dicionário combinadas com todos
os sufixos até um tamanho X.
M1 - Escolher um dicionário de frequências de palavras, verificar se a senha contém uma
palavra, qual sua probabilidade de ser escolhida dada sua frequência, e acrescentar
3.3 bits de entropia para cada dígito no sufixo.
P2 - Escolher quatro palavras do dicionário.
E2 - Escolher um dicionário, testar todas as combinações de quatro palavras.
M2 - Escolher um dicionário, calcular quantas combinações de quatro palavras existem,
verificar se a senha é composta de quatro palavras nesse dicionário.
P3 - Pensar numa frase, pegar a primeira letra de cada palavra dessa frase.
E3 - Escolher um dicionário e uma gramática, gerar todas as frases possíveis.
M3 - ???
...
Numa análise de pior caso, suporíamos que o atacante sabe qual procedimento os usuários mais utilizam, e simplesmente escolheria a estratégia En
em detrimento de todas as outras. Assim, estimaria-se a entropia de cada processo ao qual a senha se aplica, e consideraria-se o menor valor encontrado como "a força da senha".
A análise de caso médio é semelhante, só que a suposição de que o atacante vai escolher a estratégia certa toda vez não existe. Em vez disso, pode-se atribuir uma probabilidade a cada uma das estratégias consideradas, e fazer uma média ponderada de todas as estimativas obtidas em vez de escolher o menor valor encontrado. Alternativamente (e acredito eu, mais correto, embora seja só minha opinião), pode-se acrescentar bits de entropia a cada estimativa representando a chance daquela estratégia de ataque ter sido usada, combinada à chance daquela senha ter sido descoberta segundo a mesma estratégia, e continuar considerando somente o menor valor encontrado.
Uma análise do que seria mais preciso, considerar só o caso médio, o pior caso ou algo no meio do caminho seria por demais extensa para ser exposta aqui. Sugiro o estudo da Teoria dos Jogos para uma melhor compreensão da forma mais adequada de se comportar na presença de um adversário que também leva as escolhas do alvo em consideração ao adaptar sua estratégia.
Conclusão
Não há consenso na melhor forma de se escolher senhas, nem de se estimar a força de uma senha em particular. Caso você decida ser liberal nos tipos de senha que aceita, minha sugestão é manter uma lista de senhas e/ou palavras comuns e rejeitá-las de imediato, rejeitar dados conhecidos do usuário como parte da senha (como citado na própria pergunta), e rejeitar senhas cujo tamanho seja demasiadamente pequeno. Mesmo assim, receio que terá pouco sucesso em garantir um nível adequado de segurança nas senhas aceitas.
Se decidir ser draconiano, por outro lado, é possível não só assegurar uma força mínima como isso pode ser feito sem antagonizar demais o usuário. A própria sugestão do XKCD (4 palavras escolhidas aleatoriamente de uma lista de 2000), por exemplo, garante senhas com pouco menos que 44 bits de entropia, o que não é particularmente alto mas é significativamente maior do que a média das senhas escolhidas livremente pelo usuário (fala-se numa média de 40 bits, mas a realidade provavelmente é muito menor). Com um pouco de criatividade, poderia se pensar num padrão ainda mais seguro e fácil de lembrar. Nesse cenário, bastaria portanto indicar ao usuário o formato mandatório, sugerir uma senha de forma automática, e verificar se a senha final corresponde ao formato esperado (talvez deixando alguma margem).
Isso não seria necessariamente bem recebido pelos usuários (uns vão achar complicado demais, outros terão seu próprio conceito - provavelmente errado - do que é uma "senha segura" e se incomodarão por não poder usá-lo), de modo que não estou recomendando seu uso, simplesmente citando como a única forma que conheço de garantir uma certa precisão na medição da força da senha.