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, como senhas fracas e reutilização de senhas. Eles permitem o uso de senhas fortes e únicas, tratando do armazenamento e da geração. No entanto, a adoção pelos utilizadores é dificultada pela falta de confiança nestas aplicações. Este artigo identifica a funcionalidade de geração de senhas aleatórias (GSA) como um fator-chave que influencia tanto a confiança como a utilização. Para resolver isto, os autores propõem o desenvolvimento e a verificação formal de uma implementação de referência para um algoritmo de GSA, com o objetivo de fornecer uma base criptograficamente sólida e comprovadamente segura em que utilizadores e programadores possam confiar.

O problema central é que, embora os GS promovam a segurança, os seus mecanismos internos — especialmente a geração de senhas — são frequentemente caixas negras opacas. Sem garantias verificáveis, os utilizadores mantêm-se céticos. A via de solução envolve o uso de métodos formais, especificamente o enquadramento EasyCrypt, para especificar matematicamente o algoritmo e provar as suas propriedades de correção e segurança face a um modelo adversário bem definido.

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 diferenças críticas nas suas abordagens para gerar senhas aleatórias.

3. Implementação Formalmente Verificada Proposta

A contribuição central do artigo é a proposta de construir uma implementação de referência de GSA com provas verificadas por máquina das suas propriedades.

4. Resultados Experimentais & Análise

Embora o PDF fornecido seja um trabalho preliminar e não contenha resultados experimentais completos, ele prepara o terreno para os mesmos. A verificação proposta produziria os seguintes resultados tangíveis:

• Relatório de Verificação: Um certificado de prova gerado por máquina a partir do EasyCrypt, confirmando que o código do algoritmo adere à sua especificação formal e aos teoremas de segurança.
• Análise Comparativa: O algoritmo verificado poderia ser comparado com as implementações existentes no Chrome, Bitwarden e KeePass. Os testes envolveriam gerar grandes lotes de senhas (ex.: 1 milhão) sob políticas idênticas e analisar estatisticamente a distribuição.
• Métrica: Uma métrica chave seria a Divergência de Kullback-Leibler (KL) ou o teste do Qui-quadrado entre a distribuição empírica das senhas geradas e a distribuição uniforme teórica sobre o espaço definido pela política. Um algoritmo formalmente verificado deveria mostrar uma divergência estatisticamente indistinguível de zero, enquanto implementações não verificadas poderiam revelar enviesamentos subtis.
• Descrição do Gráfico: Um gráfico de barras comparando a entropia (em bits) da distribuição de senhas geradas para o algoritmo de cada GS contra a entropia máxima teórica para a política dada. A barra da implementação de referência verificada deveria alinhar-se perfeitamente com a barra "Máximo Teórico".

5. Detalhes Técnicos & Enquadramento Matemático

A verificação formal baseia-se na modelação matemática precisa. Vamos definir os conceitos centrais:

Espaço de Senhas: Dada uma política com comprimento $L$ e conjuntos de caracteres permitidos $S_1, ..., S_n$, o conjunto total de senhas conformes $\mathcal{P}$ é um subconjunto do produto cartesiano $\mathcal{C}^L$, onde $\mathcal{C} = \bigcup_{i=1}^n S_i$. O tamanho de $\mathcal{P}$ é restringido pelas regras de mínimo e máximo.

Distribuição Uniforme: O objetivo de segurança é que o algoritmo $\mathcal{A}$ implemente uma função indistinguível de um verdadeiro amostrador uniforme $\mathcal{U}_{\mathcal{P}}$. Para qualquer senha $p \in \mathcal{P}$, a probabilidade deve ser: $$\Pr[\mathcal{A}(policy) = p] = \frac{1}{|\mathcal{P}|}$$ onde $|\mathcal{P}|$ é a cardinalidade do conjunto de senhas válidas.

Esboço da Prova Baseada em Jogos: A segurança é enquadrada como um jogo "Real-ou-Aleatório" (RoR).

1. O desafiante lança uma moeda secreta $b \xleftarrow{\$} \{0,1\}$.
2. O adversário $\mathcal{D}$ pode consultar o desafiante com políticas de senha.
3. Se $b=0$ (Real), o desafiante executa o algoritmo real $\mathcal{A}$.
4. Se $b=1$ (Aleatório), o desafiante amostra uniformemente de $\mathcal{P}$ usando $\mathcal{U}_{\mathcal{P}}$.
5. $\mathcal{D}$ produz um palpite $b'$.

6. Enquadramento de Análise: Um Exemplo Sem Código

Como o PDF não inclui código real, aqui está um enquadramento de análise conceptual para avaliar um algoritmo de GSA, apresentado como uma lista de verificação:

7. Aplicações Futuras & Direções de Investigação

O trabalho abre várias vias promissoras:

• Padronização: Um GSA formalmente verificado poderia tornar-se um componente padrão (como uma biblioteca) integrado em GS em toda a indústria, semelhante à forma como o libsodium fornece primitivas criptográficas verificadas.
• Integração no Navegador e SO: Sistemas operativos (ex.: Windows Hello, macOS Keychain) e navegadores poderiam adotar o gerador verificado para as suas funcionalidades integradas de sugestão de senhas, elevando o nível de segurança base para todos os utilizadores.
• Geração Suportada por Hardware: O algoritmo verificado poderia ser implementado em elementos de hardware seguro (TPM, Secure Enclave) para uma geração que é tanto fisicamente como logicamente segura.
• Considerações Pós-Quânticas: Investigação futura poderia explorar políticas de geração de senhas que produzam senhas resistentes a ataques de força bruta clássicos e quânticos, com provas formais adaptadas a novos modelos de ameaça.
• Verificação do Compromisso Usabilidade-Segurança: Estender o modelo formal para provar propriedades sobre a memorabilidade ou facilidade de digitação das senhas geradas, colmatando o fosso entre criptografia pura e interação humano-computador.
• Análise Automática de Políticas: Desenvolver ferramentas que usem o modelo formal para analisar automaticamente uma política definida pelo utilizador e reportar a sua entropia efetiva e quaisquer restrições não intencionais que enfraqueçam o espaço de senhas.

8. 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. (2006). The security of triple encryption and a framework for code-based game-playing proofs. In Advances in Cryptology-EUROCRYPT 2006 (pp. 409-426). Springer.
3. Barthe, G., Dupressoir, F., Grégoire, B., Kunz, C., Schmidt, B., & Strub, P. Y. (2016). EasyCrypt: A computer-aided cryptography toolset. Lecture Notes in Computer Science, 9573, 3-32.
4. National Institute of Standards and Technology (NIST). (2020). Digital Identity Guidelines: Authentication and Lifecycle Management (SP 800-63B).
5. Shannon, C. E. (1948). A mathematical theory of communication. The Bell System Technical Journal, 27(3), 379-423. (Trabalho fundamental sobre entropia e teoria da informação).
6. Florêncio, D., Herley, C., & Van Oorschot, P. C. (2014). An administrator's guide to internet password research. In 28th Large Installation System Administration Conference (LISA14) (pp. 44-61).

9. Perspetiva do Analista: Ideia Central & Crítica