Entropia de palavras-passe: o que um medidor de robustez não pode saber

A entropia pertence ao gerador, não à cadeia

Perguntar quanta entropia tem a cadeia correct-horse-battery-staple é já formular mal a pergunta. Se quatro palavras foram tiradas aos dados de uma lista publicada de 7 776 palavras, a resposta são 51,70 bits. Se alguém as leu numa banda desenhada famosa e as escreveu, a resposta é quase zero, porque as primeiríssimas tentativas de um atacante incluirão exatamente essa frase. Mesmos carateres, mesmo comprimento, mesmas classes — segurança completamente diferente, porque a entropia mede quantos resultados igualmente prováveis o processo poderia ter produzido, e a cadeia não diz qual foi o processo.

É por isso que toda a disciplina fala de palavras-passe geradas. Um gestor que retira de uma fonte aleatória criptográfica conhece R e L, logo pode declarar a entropia exata. Um humano ao teclado não tem um R bem definido, porque as escolhas humanas não são uniformes: certas letras, certas substituições, certos anos e certos padrões de teclado são muito mais prováveis do que outros, e toda a ferramenta séria de quebra é construída em torno desse enviesamento. Qualquer número colado a uma palavra-passe escolhida por um humano é uma conjetura sobre o quanto o modelo do atacante encaixa nos hábitos desse humano.

A fórmula e a condição que a acompanha

H = L x log2(R). O logaritmo converte uma contagem de possibilidades em bits, e multiplicar pelo comprimento funciona porque cada extração independente acrescenta os seus próprios bits. log2(94) = 6,5546, logo cada carácter ASCII imprimível aleatório adicional acrescenta 6,5546 bits. log2(26) = 4,7004, logo uma letra minúscula acrescenta menos. log2(7 776) = 12,9248, logo uma palavra Diceware acrescenta quase o dobro de um carácter aleatório — 7 776 é 6^5, cinco lançamentos de dado, e daí o tamanho exato da lista.

A condição é uma seleção aleatória uniforme e independente, e é ela que faz todo o trabalho. Quebre-a e a fórmula deixa silenciosamente de se aplicar enquanto continua a devolver um número confortável. Escolha uma palavra de que goste em vez de lançar os dados: R deixa de ser 7 776. Ponha maiúscula na primeira letra porque uma política o exige: essa maiúscula não acrescenta entropia nenhuma, porque toda a gente faz o mesmo. Acrescente um ponto de exclamação e um ano: esses carateres alongam o L no papel enquanto o conjunto de regras do atacante os gera de graça. A fórmula nada sabe disso. Nunca lhe disseram qual era o processo.

Há uma terceira grandeza que se enreda com estas duas e vale a pena separá-la. A entropia de Shannon de uma cadeia, aquilo que uma calculadora de entropia genérica calcula, mede a distribuição de símbolos dentro dessa cadeia concreta. Para P@ssw0rd123! dá 3,4183 bits por carácter, porque alguns carateres se repetem. Esse número é genuinamente útil para compressão e para detetar blocos cifrados, e não diz absolutamente nada sobre a dificuldade de adivinhar a palavra-passe. Três perguntas diferentes, três números diferentes, e confundi-los é a origem de imensos maus conselhos.

O que o medidor está realmente a medir

O medidor de robustez clássico conta classes de carateres. Minúscula presente, maiúscula presente, dígito presente, símbolo presente: quatro visos, R = 94, multiplica-se pelo comprimento e desenha-se uma barra tranquilizadora. Dê-lhe P@ssw0rd123! e ele calcula 12 x 6,5546 = 78,66 bits e chama excelente à palavra-passe. Dê-lhe os doze carateres genuinamente aleatórios que o seu gestor acabou de produzir e ele calcula exatamente os mesmos 78,66 bits. O medidor não os consegue distinguir, porque só olhou para que classes apareciam.

Um atacante nunca se comporta assim. A quebra real passa uma lista de palavras por um ficheiro de regras: regras que põem maiúscula, que trocam a por @, o por 0 e s por $, que acrescentam anos de dois e de quatro algarismos e um ponto de exclamação final, que invertem, duplicam e truncam. Cada transformação em P@ssw0rd123! é uma regra padrão. Pegue numa lista de dez milhões de entradas e dez mil regras: o espaço de candidatos é 10^11 — cerca de 36,5 bits, esgotado num segundo a cem mil milhões de tentativas por segundo. Perante os 78,66 bits do medidor, é uma sobrestimação de 42,11 bits, um fator de 4,76 biliões.

Existem medidores melhores e funcionam com outro princípio. Em vez de contar classes, tentam reconstruir como a palavra-passe foi provavelmente construída, confrontando-a com dicionários, nomes comuns, datas, percursos de teclado e repetições, e depois estimam quantas tentativas custaria a reconstrução mais barata. É um número muito mais honesto, e mesmo assim só vê os padrões que lhe ensinaram. A conclusão prudente é que um medidor é um filtro contra o obviamente péssimo, não uma medição. Se quer um número fiável, gere a palavra-passe e conte os bits que o gerador gastou de facto.

Mais comprida não é o mesmo que mais forte

Dois exemplos calculados deixam o ponto muito claro. Dezasseis letras minúsculas aleatórias dão 16 x 4,7004 = 75,21 bits. Doze carateres ASCII imprimíveis aleatórios dão 12 x 6,5546 = 78,66. A cadeia de dezasseis carateres é um terço mais comprida e 3,45 bits mais fraca — cerca de onze vezes mais fácil de adivinhar. Comprimento e alfabeto trocam-se um pelo outro, e só o seu produto importa.

A diferença alarga-se com as frases-passe. Uma frase Diceware de quatro palavras passa facilmente dos vinte carateres e ainda assim transporta apenas 51,70 bits, contra os 78,66 da palavra-passe aleatória de doze carateres. São 26,96 bits a menos, um fator de 130 milhões. As frases-passe não são fracas — são maravilhosamente memorizáveis, e uma de seis palavras chega a 77,55 bits, igualando na prática os doze carateres aleatórios. Mas a robustez vem do número de palavras tiradas, não do número de letras escritas, e quatro palavras não chegam para nada que lhe importe.

O tempo de quebra é o número do defensor, não o seu

Converter entropia em duração exige mais uma entrada: o ritmo a que o atacante consegue testar candidatos. Em média encontra a palavra-passe após metade do espaço de chaves, logo o tempo esperado é 2^(H-1) a dividir pelo ritmo de tentativas. Tudo depende desse ritmo, e o utilizador não o controla. Controla-o o serviço que guarda a sua palavra-passe.

Pegue na frase Diceware de quatro palavras, 51,70 bits, e varie apenas a escolha de armazenamento do defensor. Perante um hash rápido sem sal em que um bastidor de GPU consegue 10^11 tentativas por segundo, o tempo esperado é de 5,1 horas. Perante o bcrypt com custo 12, em que o mesmo bastidor consegue talvez 10^4 por segundo, é de 5 790 anos. Perante o Argon2id afinado para 64 MiB de memória, em que o requisito de memória bloqueia o paralelismo massivo e o ritmo cai para cerca de 10^3, é de 57 900 anos. Palavra-passe idêntica. Entropia idêntica. Sete ordens de grandeza de diferença, decididas inteiramente por outra pessoa.

É esse o elo entre este artigo e qualquer discussão sobre funções de hash. O MD5 e o SHA-256 foram desenhados para o débito e cumprem — mais de um gigabyte por segundo num só núcleo — o que os torna precisamente inadequados para guardar palavras-passe. O Argon2id, o bcrypt e o scrypt gastam tempo e memória reais por tentativa de propósito. Quando ler um título a afirmar que uma palavra-passe se quebra em tantas horas, a primeira pergunta é que hash a afirmação pressupunha, porque essa única premissa desloca a resposta num fator de dez milhões.

A reutilização vence a entropia sempre

Toda esta aritmética não vale nada se a palavra-passe já foi publicada. O enchimento de credenciais não adivinha coisa nenhuma: pega em pares de utilizador e palavra-passe de uma fuga e repete-os contra todos os outros serviços, e funciona porque a reutilização é comum. Uma palavra-passe de 78,66 bits reutilizada em dois sítios tem 78,66 bits naquele que a guarda bem e zero naquele que a perdeu em claro, e depois disso tem zero em todo o lado. A entropia nunca foi a falha.

Daí o teor das recomendações atuais do NIST. A SP 800-63B abandonou as antigas regras de composição — maiúscula obrigatória, símbolo obrigatório, rotação forçada de noventa em noventa dias — porque empurram as pessoas para padrões previsíveis sem comprar entropia real. O que recomenda em vez disso é um comprimento mínimo generoso, nenhum máximo arbitrário, nenhuma truncatura, e filtrar as palavras-passe candidatas contra listas de valores conhecidos como comprometidos. É esse último ponto que apanha o P@ssw0rd123!, coisa que nenhum cálculo de entropia teria feito.

O que fazer na prática

Gere, não invente. Um gestor de palavras-passe que retire de uma fonte aleatória criptográfica é a única forma de conhecer a sua entropia em vez de a esperar, e elimina ao mesmo tempo o problema da reutilização. Para o punhado de segredos que tem de escrever de memória — a palavra-passe mestra do gestor, uma frase de cifra de disco, um desbloqueio de dispositivo — use uma frase Diceware de seis palavras a 77,55 bits, memorizável e fora do alcance de um ataque por lista de palavras. Aponte a pelo menos 75 bits em tudo o que guarde outras credenciais, e tome 50 bits como o chão para uma conta corrente protegida por limitação de tentativas e um segundo fator.

E construa bem o outro lado, porque, enquanto programador, é o defensor cuja escolha decide os números da tabela acima. Guarde as palavras-passe com Argon2id onde puder, bcrypt ou scrypt onde não puder, sempre com um sal único. Não imponha comprimento máximo nem trunque em silêncio. Não force rotação periódica. Filtre as palavras-passe novas contra uma lista de palavras-passe comprometidas. Acrescente um segundo fator, que vale mais bits do que qualquer política de palavras-passe alguma vez extrairá dos seus utilizadores.

Perguntas frequentes

De quantos bits de entropia precisa uma palavra-passe?

Depende de como a outra ponta a guarda, e essa é a parte incómoda da resposta. Pegue em 51,70 bits, a entropia de uma frase Diceware de quatro palavras. Perante um hash rápido sem sal a 10^11 tentativas por segundo, o tempo esperado para a encontrar é de 5,1 horas — inútil. Perante o bcrypt com custo 12, cerca de 10^4 tentativas por segundo, a mesma palavra-passe aguenta 5 790 anos. Não há, pois, um limiar único correto em todo o lado. Alvos práticos: pelo menos 75 bits para tudo o que proteja outras credenciais, como o segredo mestre de um gestor ou uma frase de cifra de disco, pois esses têm de sobreviver a um ataque fora de linha sobre uma cópia dos dados. Cerca de 50 bits é defensável para uma conta corrente atrás de limitação de tentativas no servidor e um segundo fator, onde o atacante nunca adivinha depressa. Em termos gerados, 75 bits são doze carateres ASCII imprimíveis aleatórios (78,66) ou seis palavras Diceware (77,55); 50 bits são quatro palavras Diceware (51,70) ou oito carateres aleatórios (52,44).

Uma frase-passe é mais forte do que uma palavra-passe aleatória?

Não automaticamente, e o número de carateres é mau guia. Uma frase Diceware de quatro palavras transporta 4 x log2(7 776) = 51,70 bits mesmo que passe dos vinte carateres. Doze carateres ASCII imprimíveis aleatórios transportam 12 x log2(94) = 78,66 bits em muito menos espaço. A frase é 26,96 bits mais fraca, um fator de 130 milhões no esforço de adivinha — uma cadeia mais comprida e muitíssimo mais fácil de encontrar. Acrescente palavras e o quadro muda: seis palavras dão 77,55 bits, igualando na prática os doze carateres aleatórios, e sete dão 90,47. A verdadeira vantagem de uma frase-passe é que a guarda na cabeça, o que importa enormemente para os dois ou três segredos que escreve de memória e nada para a centena que o seu gestor preenche. Duas condições: as palavras têm de ser tiradas ao acaso de uma lista publicada, não escolhidas por si, e o tamanho da lista tem de ser conhecido para que R seja real. Escolher quatro palavras de que gosta não é Diceware e não tem entropia definida.

Porque é que o meu gestor avalia uma palavra-passe de forma diferente do site?

Porque respondem a perguntas diferentes. Um medidor de site conta tipicamente classes de carateres e multiplica pelo comprimento, o que dá a P@ssw0rd123! e a doze carateres genuinamente aleatórios os mesmos 78,66 bits — não os consegue distinguir, tendo olhado apenas para que classes apareciam. Um estimador por padrões tenta, pelo contrário, reconstruir como a palavra-passe foi provavelmente fabricada, confrontando-a com dicionários, nomes, datas, percursos de teclado e repetições, e informa quantas tentativas custaria a reconstrução mais barata. Para P@ssw0rd123! isso é muito mais baixo, porque cada transformação que contém é uma regra de quebra padrão: uma lista de dez milhões de palavras cruzada com dez mil regras são 10^11 candidatos, cerca de 36,5 bits. A diferença entre os dois veredictos é de 42,11 bits, um fator de 4,76 biliões. Acredite no pessimista. E note que nenhum consegue avaliar uma palavra-passe gerada ao acaso melhor do que a fórmula, porque para uma palavra-passe gerada a fórmula é exata — é essa toda a razão para gerar em vez de inventar.

Acrescentar um símbolo e um número ajuda mesmo?

Ajuda quando o carácter foi escolhido ao acaso e não faz nada quando foi escolhido como toda a gente o escolhe. Alargar o alfabeto aumenta de facto o rendimento por carácter: log2(26) = 4,7004 bits para minúsculas contra log2(94) = 6,5546 para todo o ASCII imprimível, pelo que cada carácter aleatório rende mais 1,85 bits. Mas uma maiúscula na primeira letra e um ponto de exclamação no fim é o que quase toda a gente faz, pelo que o conjunto de regras do atacante produz essas variantes de graça e o ganho real de entropia é quase zero. É por isso que a NIST SP 800-63B abandonou as regras de composição obrigatórias: impõem uma transformação previsível em vez de acrescentar acaso. Se quer mais bits, alongue a palavra-passe ou alargue mesmo o alfabeto ao acaso — dezasseis letras minúsculas aleatórias já chegam a 75,21 bits sem símbolo nenhum, e doze carateres aleatórios dos 94 chegam a 78,66. Ambas batem qualquer decoração de uma palavra memorável.

Em que difere a entropia de uma palavra-passe da entropia de Shannon?

Medem objetos diferentes, e uma calculadora de entropia genérica dar-lhe-á de bom grado o errado. A entropia de Shannon de uma cadeia mede a distribuição de símbolos dentro dessa cadeia: para P@ssw0rd123! dá 3,4183 bits por carácter, determinada inteiramente por que carateres se repetem. É a ferramenta certa para estimar quanto uns dados vão comprimir, ou para detetar um bloco cifrado no meio de texto simples, e nada diz sobre a facilidade de adivinha. A entropia de palavra-passe mede o processo gerador — quantas palavras-passe igualmente prováveis o procedimento poderia ter produzido — e isso é H = L x log2(R) quando a seleção foi mesmo uniforme e aleatória. As duas podem divergir enormemente: uma palavra-passe aleatória de 12 carateres e P@ssw0rd123! têm o mesmo H pela fórmula, 78,66 bits, ao passo que as suas entropias de Shannon diferem e a resistência real difere em dezenas de bits. Se está a escolher uma palavra-passe, o número que importa é o do processo gerador.

Posso apenas alongar a minha palavra-passe em vez de a tornar aleatória?

O comprimento só se converte em entropia quando os carateres acrescentados eram imprevisíveis. Alongar uma palavra memorável com um ano de nascimento e um sinal de pontuação alonga o L no papel enquanto o ficheiro de regras do atacante gera exatamente essas terminações de graça, pelo que H = L x log2(R) deixa de descrever algo real — o espaço de procura prático fica na ordem da lista de palavras vezes o conjunto de regras, cerca de 10^11 candidatos ou 36,5 bits, que é um segundo de trabalho a cem mil milhões de tentativas por segundo. O comprimento aplicado a material genuinamente aleatório é a alavanca mais eficiente que tem: cada minúscula aleatória extra acrescenta log2(26) = 4,7004 bits e cada carácter ASCII imprimível aleatório acrescenta log2(94) = 6,5546. Dezasseis minúsculas aleatórias chegam a 75,21 bits — sem símbolos, sem maiúsculas, sem substituições, e muito mais forte do que qualquer palavra de dicionário decorada. Então sim, alongue, mas só se o comprimento acrescentado for aleatório. Se tiver de a memorizar, acrescente palavras Diceware em vez de carateres: cada uma vale 12,9248 bits.