Esgotamento de entropia e erros de chaves fracas

A exaustão de entropia ocorre quando um sistema não tem entrada imprevisível suficiente para inicializar seu CSPRNG. Isso acontece em dispositivos embarcados recém-inicializados, servidores virtualizados ou sistemas sem entrada do usuário. A saída do RNG se torna previsível.

Em 2006, um desenvolvedor do Debian removeu uma linha sinalizada pelo Valgrind: MD_Update(&m, buf, j). Essa linha era a fonte de entropia. O resultado: o OpenSSL no Debian era inicializado apenas com o PID (no máximo 32.768 valores). Todas as chaves geradas entre 2006 e 2008 pertencem a um conjunto de 32.768 possibilidades.

Chaves RSA, DSA e ECDSA, chaves de host do SSH, certificados TLS e chaves de VPN SSL gerados em sistemas Debian/Ubuntu entre 2006 e 2008 foram comprometidos. Sistemas afetados: Debian Etch, Debian Lenny, Ubuntu 7.04-8.04. Listas de bloqueio foram publicadas; certificados foram revogados.

Máquinas virtuais podem ser clonadas com estado de disco idêntico. Se duas máquinas virtuais gerarem chaves a partir do mesmo estado do CSPRNG, produzirão as mesmas chaves. Atualmente, os hipervisores injetam entropia por meio de tabelas VirtIO RNG ou ACPI, mas máquinas virtuais mal configuradas ainda enfrentam esse risco durante a inicialização.

Dispositivos de IoT (roteadores, câmeras) frequentemente geram chaves SSH/TLS na primeira inicialização, antes de acumular entropia. Estudos descobriram milhões de dispositivos compartilhando alguns milhares de pares de chaves RSA, porque todos eram inicializados a partir do mesmo estado de inicialização com baixa entropia.

Lenstra e outros (2012) coletaram 11,7 milhões de certificados TLS e calcularam os GCDs de cada par. Encontraram 12.720 chaves RSA que compartilhavam um fator primo — o que significa que ambas as chaves poderiam ser completamente fatoradas. 0,2% de todas as chaves públicas estavam quebradas. A causa foi a entropia insuficiente na inicialização.

O ECDSA exige um nonce aleatório k exclusivo para cada assinatura. Se k for reutilizado (ou for fraco), a chave privada poderá ser recuperada imediatamente: d = (s1-s2)^{-1} * (z1-z2) * k / (r1-r2) mod n. O PS3 da Sony usava k=constant — todos os jogos poderiam ser assinados com a chave recuperada.

O Java SecureRandom no Android 4.x era inicializado com o horário do sistema em determinadas condições. Vários aplicativos de carteira de Bitcoin geraram assinaturas com o mesmo nonce k, expondo as chaves privadas. Milhões de dólares foram roubados. O Google corrigiu a implementação do SecureRandom.

Ferramentas: ssh-vulnkey (verifica a lista de bloqueio de chaves fracas do Debian), badkeys (verifica certificados TLS em busca de primos reconhecidamente fracos) e o algoritmo GCD-batch para auditoria em massa de chaves RSA. Os registros de Certificate Transparency permitem análises em escala populacional.

Use getrandom(GRND_RANDOM) na primeira geração de chaves. Leia de /dev/urandom após aguardar a inicialização inicial (verifique se /proc/sys/kernel/random/entropy_avail > 128). Use um RNG de hardware (RDRAND) como entropia suplementar. Nunca gere chaves na primeira inicialização sem um atraso.

Preserve o estado do CSPRNG entre reinicializações: salve 32 bytes de /dev/urandom em um arquivo de semente durante o desligamento; leia-os e reinsira-os durante a inicialização. Isso proporciona continuidade da entropia entre inicializações a frio. O Linux faz isso automaticamente; sistemas embarcados frequentemente não fazem.

A exaustão de entropia causa chaves previsíveis. Quebras reais: OpenSSL no Debian (semente baseada apenas no PID), ataques de GCD contra dispositivos de IoT, reutilização de nonce em ECDSA no PS3 e carteira de Bitcoin do Android. Sempre inicialize a partir da entropia do OS; audite cuidadosamente a geração de chaves em sistemas embarcados. A seguir: geração segura de chaves, nonces e IVs.