Seminário de Informática
Teórica
Henrique Borges Alencar Siqueira
Motivação
Geradores randômicos
Blocos fundamentais da
Segurança
Roteiro







Motivação
Algoritmos de criptografia
Geradores pseudo-randômicos
Explorando a falha
Requisitos para geradores seguros
Corrigindo a falha
Conclusão
Algoritmos de criptografia


Iludem tentativas de análise de padrões e
ataques de força-bruta
Assumem que existe uma fonte randômica
(não reproduzível) de bits para gerar:


Números primos
Chaves públicas e privadas
Algoritmos de criptografia

Falham quando não existe uma fonte
randômica segura:

Netscape implementation of SSL


I. Goldberg and D. Wagner. Randomness and the Netscape browser.
Dr Dobb’s, pages 66–70, January 1996.
Java session-ids

Z. Gutterman and D. Malkhi. Hold your sessions: An attack on Java
session-id generation. In A. J. Menezes, editor, CT-RSA, LNCS vol.
3376, pages 44–57. Springer, February 2005.
Roteiro







Motivação
Algoritmos de criptografia
Geradores pseudo-randômicos
Explorando a falha
Requisitos para geradores seguros
Corrigindo a falha
Conclusão
Geradores pseudo-randômicos


Ou “Deterministic Random Bit Generator”
Todos os geradores randômicos por
software
Geradores pseudo-randômicos
java.util.Random
Solicitação
r.nextInt()
Função
One-way
geradora
Hash
Número
“randômico”
seed = (seed * multiplier + addend) & mask
return seed >> 16
Hora
Seed:
atual
(Fontes de entropia)
Estado
interno
Geradores pseudo-randômicos


Mesmas fontes (seeds) + mesmo
algoritmo = mesma seqüência de números
java.util.Random



long seed = 0;
Random r = new Random(seed);
assert (r.nextInt() == -1155484576);
Roteiro







Motivação
Algoritmos de criptografia
Geradores pseudo-randômicos
Explorando a falha
Requisitos para geradores seguros
Corrigindo a falha
Conclusão
Explorando a falha

OpenWRT


Implementação do Linux para roteadores
wireless
Provê
SSL termination
 SSH server
 Wireless encryption


A segurança de todos estes serviços depende
do gerador pseudo-randômico
Explorando a falha

OpenWRT

Fontes de entropia (seeds) do gerador
randômico (Março de 2006)
Hora de inicialização
 Recebimento de pacotes desde a inicialização


Fontes observáveis!!!


Pacotes em rede wireless
Ambiente facilmente reproduzido
Explorando a falha
Código Java: Usando RSA com
gerador randômico ruim
Roteiro







Motivação
Algoritmos de criptografia
Geradores pseudo-randômicos
Explorando a falha
Requisitos para geradores seguros
Corrigindo a falha
Conclusão
Requisitos para geradores seguros

Pseudorandomness



A saída do gerador não pode ser prevista por
um observador externo
Provê segurança suficiente para adversários
sem acesso ao estado interno do gerador
Obtida usando fontes de entropia (seeds)
randômicas (não reproduzíveis)
Requisitos para geradores seguros

Forward security


Saber o estado interno atual não implica
descobrir saídas anteriores
Obtida usando funções one-way (injetoras)
para a geração de números randômicos
Requisitos para geradores seguros

Break-in recovery / backward security


Saber o estado interno atual não implica
descobrir saídas futuras
Obtida usando re-seed periódico (realimentação)
Roteiro







Motivação
Algoritmos de criptografia
Geradores pseudo-randômicos
Explorando a falha
Requisitos para geradores seguros
Corrigindo a falha
Conclusão
Corrigindo a falha

Usar fontes de entropia secretas e com a
segurança desejada


Usar múltiplas fontes de entropia real


Seeds com 256 bits para segurança de 256
bits
Hora atual, teclas digitadas, ruído do
microfone, giro do HD, ...
Re-seed periódico
Corrigindo a falha

OpenWRT: Fontes de entropia


Hora de inicialização
Recebimento de pacotes desde a inicialização
Corrigindo a falha

OpenWRT: Fontes de entropia


Persistir o estado do gerador randômico ao
desligar o S.O.
Re-seed
Horário de (re) inicialização
 Recebimento de pacotes

Corrigindo a falha

Código Java: Fontes de entropia

Timestamp
Corrigindo a falha

Código Java: Fontes de entropia


Usar a implementação nativa do gerador
randômico (que tem seeds melhores)
Usar re-seed periódico com outras fontes de
entropia
Roteiro







Motivação
Algoritmos de criptografia
Geradores pseudo-randômicos
Explorando a falha
Requisitos para geradores seguros
Corrigindo a falha
Conclusão
Conclusão

Um atacante sofisticado pode descobrir
ser mais fácil reproduzir o ambiente que
gerou os dados e procurar no conjunto de
possibilidades geradas do que em todo o
espaço amostral
Dúvidas?
Obrigado