Rumo à Verificação Formal de Algoritmos de Geração de Senhas em Gestores de Senhas

1. Introdução

Os gestores de senhas (GS) são ferramentas críticas recomendadas por especialistas em segurança para mitigar vulnerabilidades associadas à autenticação por senha. Eles facilitam o uso de senhas fortes e únicas, aliviando a carga cognitiva dos utilizadores. No entanto, a adoção generalizada pelos utilizadores é dificultada pela falta de confiança nestas aplicações. Este artigo identifica a funcionalidade de geração aleatória de senhas (GAS) como um fator-chave que influencia a confiança do utilizador. Os autores argumentam que uma implementação de GAS formalmente verificada e comprovadamente segura é essencial para colmatar esta lacuna de confiança e incentivar a adoção de GS. A contribuição central do artigo é propor tal implementação de referência, com provas formais de correção funcional e propriedades de segurança utilizando o framework EasyCrypt.

2. Algoritmos Atuais de Geração de Senhas

O artigo analisa 15 gestores de senhas, focando-se em três exemplos de código aberto e amplamente utilizados: o gestor integrado do Google Chrome, o Bitwarden e o KeePass. A análise revela padrões comuns e deficiências críticas nas implementações existentes.

2.1 Políticas de Composição de Senhas

Os GS permitem que os utilizadores definam políticas que restringem as senhas geradas. Estas políticas especificam o comprimento, os conjuntos de caracteres permitidos (ex.: minúsculas, maiúsculas, números, caracteres especiais) e as ocorrências mínimas/máximas por conjunto. O artigo fornece uma tabela comparativa detalhada (Tabela 1 no PDF) que mostra as opções de políticas nos três GS estudados. Observações-chave incluem comprimentos máximos variáveis (até 30.000 no KeePass), definições diferentes de "caracteres especiais" e tratamento inconsistente de "caracteres semelhantes" (como 'l', '1', 'O', '0') para evitar ambiguidade visual. O KeePass oferece o controlo mais granular, permitindo conjuntos personalizados de inclusão/exclusão e remoção de duplicados.

2.2 Geração Aleatória de Senhas

Os algoritmos analisados seguem geralmente um processo em duas fases: 1) Gerar caracteres aleatórios para satisfazer as ocorrências mínimas exigidas para cada conjunto de caracteres especificado. 2) Preencher o comprimento restante da senha com caracteres aleatórios de qualquer conjunto que não tenha atingido o seu limite máximo de ocorrências. Finalmente, a sequência de caracteres é permutada aleatoriamente. O artigo sugere que, embora esta lógica seja simples, a sua implementação — particularmente a fonte de aleatoriedade e a aplicação de restrições complexas — raramente é formalmente especificada ou verificada, deixando margem para erros subtis que podem enfraquecer a segurança.

3. Abordagem de Verificação Formal

Os autores defendem o uso de métodos formais para eliminar erros de implementação. Eles selecionaram o EasyCrypt, um framework para construir e verificar provas criptográficas baseadas em jogos. A abordagem envolve:

1. Especificação: Definir formalmente os requisitos funcionais da GAS (política de entrada -> senha de saída que satisfaz a política).
2. Implementação: Escrever o código do algoritmo dentro do EasyCrypt.
3. Verificação: Provar que a implementação refina corretamente a especificação (correção funcional).
4. Prova de Segurança: Modelar o algoritmo como um jogo criptográfico para provar propriedades como a distribuição uniforme das saídas a partir do espaço definido (segurança).

Esta metodologia fornece certeza matemática de que o código se comporta exatamente como pretendido e possui as propriedades de segurança desejadas, assumindo que as primitivas criptográficas subjacentes (gerador de números aleatórios) são seguras.

4. Implementação de Referência Proposta

O artigo propõe um novo design modular de GAS destinado a servir como referência verificada. Embora o código completo não seja mostrado no excerto fornecido, o design separa logicamente:

• Analisador & Validador de Políticas: Garante que as políticas definidas pelo utilizador são internamente consistentes (ex.: mínimos não excedem máximos, mínimos totais não excedem o comprimento da senha).
• Amostrador com Restrições: O motor central que executa a geração em duas fases sob as restrições da política.
• Permutação Aleatória: Aplica um embaralhamento final à sequência de caracteres.

Cada módulo teria uma especificação formal e uma implementação verificada no EasyCrypt.

5. Detalhes Técnicos & Formulação Matemática

A segurança de uma GAS depende da entropia e da distribuição uniforme da sua saída. Seja $\mathcal{P}$ o conjunto de todas as senhas definidas por uma política (comprimento $l$, conjuntos de caracteres $C_1, C_2, ..., C_n$ com restrições min/max). A GAS ideal é uma função $G$ que amostra uniformemente de $\mathcal{P}$.

A probabilidade de qualquer senha específica $p \in \mathcal{P}$ ser gerada deve ser: $$Pr[G() = p] = \frac{1}{|\mathcal{P}|}$$ onde $|\mathcal{P}|$ é o tamanho do espaço de senhas. Uma falha comum em implementações ingénuas é introduzir viés, tornando algumas senhas mais prováveis do que outras. Por exemplo, se o algoritmo primeiro escolher caracteres para conjuntos obrigatórios e depois preencher o resto, as senhas com caracteres obrigatórios no início são sobre-representadas a menos que seja aplicado um embaralhamento perfeito. A verificação formal prova a ausência de tal viés.

A entropia $H$ da senha gerada (em bits) é: $$H = \log_2(|\mathcal{P}|)$$ A verificação garante que a implementação não reduz esta entropia abaixo do máximo teórico para a política.

6. Resultados Experimentais & Descrição do Gráfico

Embora o excerto do PDF fornecido não contenha resultados experimentais tradicionais ou gráficos, o seu "resultado" central é a própria prova formal. A verificação bem-sucedida no EasyCrypt serve como evidência definitiva. Poder-se-ia conceptualizar um gráfico comparando os níveis de garantia:

Gráfico Hipotético: Nível de Garantia vs. Método de Desenvolvimento

• Testes Tradicionais: Alta confiança para os casos testados, mas desconhecido para casos limite não testados (conflitos de políticas, valores de fronteira). A cobertura é limitada.
• Revisão de Código: Confiança moderada. Altamente dependente da habilidade do revisor. Pode perder erros lógicos subtis ou problemas de canais laterais.
• Verificação Formal (como proposta): A garantia mais elevada possível. Fornece prova matemática de correção para todas as entradas possíveis e propriedades de segurança explícitas. O "gráfico" mostraria isto como o ponto máximo no eixo "Garantia".

A contribuição do artigo é mover a GAS das duas primeiras categorias para a terceira.

7. Estrutura de Análise: Um Estudo de Caso Não-Código

Considere uma política: Comprimento=8, requer pelo menos 1 maiúscula, 1 número, 1 caractere especial. Um algoritmo defeituoso poderia:

1. Posição 1: Escolher uma maiúscula aleatória.
2. Posição 2: Escolher um número aleatório.
3. Posição 3: Escolher um caractere especial aleatório.
4. Posições 4-8: Preencher com caracteres aleatórios de todos os conjuntos.
5. Embaralhar todos os 8 caracteres.

Defeito: A ordenação fixa inicial (M, N, E) antes do embaralhamento cria um viés. Embora o embaralhamento aleatorize as posições finais, o processo começa a partir de uma distribuição não uniforme de estados intermédios. Um algoritmo formalmente verificado construiria a senha inteira através de um único processo de amostragem imparcial do espaço restrito $\mathcal{P}$, ou demonstraria de forma provável que o seu processo de múltiplos passos é equivalente a tal amostragem uniforme.

8. Ideia Central & Perspectiva do Analista

Ideia Central: O artigo identifica corretamente uma superfície de ataque crítica, mas frequentemente negligenciada, nos gestores de senhas: a confiabilidade do próprio gerador de senhas. Não basta ter um cofre forte; se o material de origem (as senhas) é fraco ou previsível devido a um gerador com erros, todo o sistema falha. A decisão dos autores de aplicar métodos formais — uma técnica mais comum em hardware ou software de aviação — a este problema de segurança do consumidor é ambiciosa e necessária.

Fluxo Lógico: O argumento é sólido: 1) A confiança é uma barreira à adoção de GS. 2) A GAS é um componente crítico para a confiança. 3) As GAS atuais são implementadas de forma ad-hoc sem garantias rigorosas. 4) A verificação formal fornece o mais alto nível de garantia. 5) Nós fornecemos um plano para uma GAS verificada usando o EasyCrypt. A lógica liga um problema centrado no utilizador (confiança) com uma solução técnica profunda (métodos formais).

Pontos Fortes & Fraquezas:
Pontos Fortes: O foco em GS de código aberto é pragmático. A análise comparativa de políticas é valiosa. Propor uma implementação de referência é mais útil do que apenas criticar outras; estabelece um padrão. Usar o EasyCrypt liga o trabalho à prática estabelecida de verificação criptográfica, semelhante à verificação de algoritmos como os em "The Security of Cryptographic Primitives" (M. Bellare, P. Rogaway).
Fraquezas: O excerto fornecido é um ponto de partida. O verdadeiro teste é a complexidade das provas completas do EasyCrypt para políticas do mundo real. A abordagem assume um GNA perfeito; uma vulnerabilidade aí contorna todas as garantias formais. Também não aborda ataques de canais laterais (tempo, memória) no binário compilado final, uma limitação observada noutros projetos de verificação formal como a verificação do micronúcleo seL4.

Insights Acionáveis:
1. Para Desenvolvedores de GS: Integrem este núcleo verificado, ou um semelhante, como uma biblioteca. O custo da verificação formal é elevado inicialmente, mas reduz os encargos de revisão de segurança e a responsabilidade a longo prazo.
2. Para Auditores & Investigadores: Usem este trabalho como um modelo para analisar outros GS. A tabela de comparação de políticas é uma lista de verificação pronta para avaliações de segurança.
3. Para Organismos de Normalização (ex.: NIST, FIDO): Considerem a verificação formal como um requisito para certificar módulos de geração de senhas, semelhante à forma como os Critérios Comuns exigem processos de desenvolvimento rigorosos para produtos de alta garantia.
4. Para Utilizadores: Exijam transparência. Prefiram GS que publiquem os seus algoritmos de GAS e, idealmente, as suas evidências de verificação. Este artigo fornece o vocabulário para o exigir.

Em essência, esta investigação é um apelo para elevar os padrões de engenharia de um componente de segurança fundamental. Muda o objetivo de "esperançosamente seguro" para "comprovadamente correto", que é o único padrão aceitável para ferramentas que protegem as nossas identidades digitais.

9. Aplicações Futuras & Direções de Pesquisa

As implicações estendem-se para além dos gestores de senhas:

• Tokens de API & Serviço: Serviços em nuvem e arquiteturas de microserviços frequentemente requerem tokens gerados. Um gerador verificado garante que estes segredos são criptograficamente fortes.
• Geração de Chaves Criptográficas: Os princípios aplicam-se à geração de códigos de recuperação legíveis por humanos ou frases-passe (via métodos do tipo diceware) para chaves criptográficas, onde o viés é igualmente perigoso.
• Integração com Segurança de Hardware: Trabalhos futuros poderiam verificar a interação entre o software da GAS e Geradores Verdadeiros de Números Aleatórios (GVNA) de hardware ou Ambientes de Execução Confiáveis (AEC).
• Análise Automatizada de Políticas: Construir ferramentas que analisem formalmente políticas definidas pelo utilizador em busca de fraquezas (ex.: espaços de busca efetivamente pequenos apesar da complexidade aparente) antes mesmo da geração ocorrer.
• Normalização: A maior direção futura é transformar esta implementação de referência num padrão amplamente adotado, talvez como uma biblioteca autónoma (como a libsodium para criptografia) que qualquer aplicação possa usar para geração verificada de segredos.

10. Referências

1. Grilo, M., Ferreira, J. F., & Almeida, J. B. (2021). Towards Formal Verification of Password Generation Algorithms used in Password Managers. arXiv preprint arXiv:2106.03626.
2. Bellare, M., & Rogaway, P. (2005). Introduction to Modern Cryptography. Capítulo sobre Funções e Permutações Pseudoaleatórias.
3. Klein, G., et al. (2009). seL4: Formal verification of an OS kernel. Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles.
4. National Institute of Standards and Technology (NIST). (2017). Digital Identity Guidelines (SP 800-63B).
5. Common Criteria Recognition Agreement (CCRA). Common Criteria for Information Technology Security Evaluation.
6. Chiasson, S., van Oorschot, P. C., & Biddle, R. (2006). A second look at the usability of click-based graphical passwords. Proceedings of the 3rd symposium on Usable privacy and security.
7. EasyCrypt Proof Assistant. Documentação Oficial e Tutoriais. https://easycrypt.info/