Introdução à Introdução à CriptografiaCriptografia

Geradores pseudo-aleatóriosGeradores pseudo-aleatórios

Carlos Eduardo dos Santos Carlos Eduardo dos Santos (cesps)(cesps)René Araújo (raa2)René Araújo (raa2)

ConteúdoConteúdo

IntroduçãoIntrodução Propriedades Propriedades Geradores seguros para criptografiaGeradores seguros para criptografia Ataques a PRNGAtaques a PRNG ConclusãoConclusão

IntroduçãoIntrodução Números verdadeiramente aleatóriosNúmeros verdadeiramente aleatórios

Possuem real aleatoriedade, exemplo: Tempo Possuem real aleatoriedade, exemplo: Tempo entre desintegrações de um elemento entre desintegrações de um elemento radioativoradioativo

Números pseudo-aleatóriosNúmeros pseudo-aleatórios Possuem a aparência de aleatoriedade, mas Possuem a aparência de aleatoriedade, mas

possuindo um padrão específico repetitivo.possuindo um padrão específico repetitivo. Números calculados por um computador Números calculados por um computador

através de processos determinísticos não através de processos determinísticos não podem, por definição, serem aleatóriospodem, por definição, serem aleatórios

IntroduçãoIntrodução Conhecendo o algoritmo usado para os Conhecendo o algoritmo usado para os

números e seu estado interno (semente), números e seu estado interno (semente), pode-se prever todos os números retornados pode-se prever todos os números retornados por chamadas subsequentes ao algoritmo. por chamadas subsequentes ao algoritmo.

Para geradores verdadeiramente aleatórios, o Para geradores verdadeiramente aleatórios, o conhecimento de uma sequencia longa de bits conhecimento de uma sequencia longa de bits não é de utilidade para se prever o proximo não é de utilidade para se prever o proximo número a ser gerado.número a ser gerado. Teste do próximo bit Teste do próximo bit

Números aleatórios são gerados por Números aleatórios são gerados por algoritmos determinísticos através de algoritmos determinísticos através de geradores pseudo-aleatórios (PRNG)geradores pseudo-aleatórios (PRNG)

Propriedades desejáveis dos Propriedades desejáveis dos números pseudo-aleatóriosnúmeros pseudo-aleatórios

Sequencias sem correlação – Sequencias sem correlação – As sequencias de As sequencias de números aleatórios não devem possuir relação com as números aleatórios não devem possuir relação com as anterioresanteriores

Período longoPeríodo longo – O gerador deve possuir um período – O gerador deve possuir um período entre repetições muito longo (idealmente, o gerador entre repetições muito longo (idealmente, o gerador não deve repetir) não deve repetir)

UniformidadeUniformidade- A sequencia de números aleatórios - A sequencia de números aleatórios deve ser uniforme. Frações iguais de números deve ser uniforme. Frações iguais de números aleatórios devem cair em áreas iguais do espaço de aleatórios devem cair em áreas iguais do espaço de números. Ex: Se serão gerados números no intervalo números. Ex: Se serão gerados números no intervalo [0,1) seria uma péssima prática se mais do que [0,1) seria uma péssima prática se mais do que metade caisse no intervalo [0, 0.1) presumindo que a metade caisse no intervalo [0, 0.1) presumindo que a quantidade de números gerados é elevadaquantidade de números gerados é elevada

EficiênciaEficiência – O gerador deve ser eficiente, gerando um – O gerador deve ser eficiente, gerando um baixo overheadbaixo overhead

Quantidades físicas utilizadas Quantidades físicas utilizadas na geração de sementesna geração de sementes

Tempo entre digitações de teclas quando o usuário Tempo entre digitações de teclas quando o usuário entra com um passwordentra com um password

Medição da turbulência de ar ocasionada pelo Medição da turbulência de ar ocasionada pelo movimento das cabeças de leitura de discos rígidosmovimento das cabeças de leitura de discos rígidos

Tempo de acesso a memoria sob determinadas Tempo de acesso a memoria sob determinadas condições de sobrecargacondições de sobrecarga

Medição precisa de atrasos na CPU ou outro Medição precisa de atrasos na CPU ou outro dispositivodispositivo

Captação de interferência em ondas de rádioCaptação de interferência em ondas de rádio Tempos de desintegração de átomos radioativosTempos de desintegração de átomos radioativos

O ciclo dos números O ciclo dos números pseudo-aleatóriospseudo-aleatórios

Quase todos os PRNG possuem como base, uma Quase todos os PRNG possuem como base, uma sequencia de inteiros pseudo-aleatoriossequencia de inteiros pseudo-aleatorios

Estes inteiros são manipulados aritmeticamente Estes inteiros são manipulados aritmeticamente para gerar números de ponto flutuantepara gerar números de ponto flutuante

A natureza do cicloA natureza do ciclo A sequencia tem um numero finito de inteirosA sequencia tem um numero finito de inteiros Asequencia é percorrida em uma ordem particularAsequencia é percorrida em uma ordem particular Caso o periodo se exceda, a sequencia é repetida Caso o periodo se exceda, a sequencia é repetida Os inteiros devem ser distintos Os inteiros devem ser distintos

Geradores seguros para Geradores seguros para criptografiacriptografia

AplicaçõesAplicações Geração de chavesGeração de chaves NoncesNonces SaltsSalts One-time padsOne-time pads

Geradores seguros para Geradores seguros para criptografiacriptografia

Um bom gerador de números Um bom gerador de números aleatórios não necessariamente é aleatórios não necessariamente é adequado à criptografiaadequado à criptografia

Deve-se dificultar ao adversário a Deve-se dificultar ao adversário a previsão dos números geradosprevisão dos números gerados

Precisa passar pelo teste do próximo Precisa passar pelo teste do próximo bitbit

Teste do próximo bitTeste do próximo bit Dado um adversário Dado um adversário A A e um oráculo e um oráculo O. O. O oráculo conhece uma seqüência de bits s, e o O oráculo conhece uma seqüência de bits s, e o

adversário adversário A A é capaz de consultar o oráculo sobre o é capaz de consultar o oráculo sobre o próximo bit qualquer número de vezes, contanto próximo bit qualquer número de vezes, contanto que reste pelo menos um bit não consultado. que reste pelo menos um bit não consultado.

Depois de ter analisado os primeiros Depois de ter analisado os primeiros l l bits, bits, A A deve deve adivinhar o bit adivinhar o bit ll + 1. + 1. A A ganhará se sua adivinhação ganhará se sua adivinhação for correta. A vantagem de for correta. A vantagem de A A é definida por Advé definida por AdvA A = = [1/2 - Pa] , onde Pa é a probabilidade de [1/2 - Pa] , onde Pa é a probabilidade de A A ter ter sucesso no teste. sucesso no teste.

Um gerador pseudo-aleatório é seguro para Um gerador pseudo-aleatório é seguro para criptografia se ele passa no teste do próximo bit.criptografia se ele passa no teste do próximo bit.

O parâmetro de segurança do teste pode ser O parâmetro de segurança do teste pode ser estendido para além dos bits, muitas vezes são estendido para além dos bits, muitas vezes são utilizados números primos neste teste. utilizados números primos neste teste.

Ataques a PRNGsAtaques a PRNGs Ataque de criptoanálise diretaAtaque de criptoanálise direta

Quando um adversário pode diretamente Quando um adversário pode diretamente distinguir entre números pseudo-aleatórios e distinguir entre números pseudo-aleatórios e números aleatórios (Criptoanálise do PRNG)números aleatórios (Criptoanálise do PRNG)

Ataque baseado em entradasAtaque baseado em entradas Quando o adversário é capaz de usar seu Quando o adversário é capaz de usar seu

conhecimento e controle das entradas do conhecimento e controle das entradas do PRNG para fazer criptoanálise do mesmoPRNG para fazer criptoanálise do mesmo

Extensão de ataques:Extensão de ataques: Quando o adversário pode adivinhar alguma Quando o adversário pode adivinhar alguma

informação através de uma falha de segurança. informação através de uma falha de segurança. A vantagem de um ataque anterior é estendidaA vantagem de um ataque anterior é estendida

Ataque de criptoanálise Ataque de criptoanálise diretadireta

Quando o adversário pode usar criptoanalise Quando o adversário pode usar criptoanalise diretamente no PRNGdiretamente no PRNG

Aplicável à maioria dos PRNGsAplicável à maioria dos PRNGs

Não pode ser aplicado quando o adversário não Não pode ser aplicado quando o adversário não pode ser capaz de ver diretamente a saída do pode ser capaz de ver diretamente a saída do geradorgerador Ex: Seja um PRNG usado para gerar chaves para o Ex: Seja um PRNG usado para gerar chaves para o

triplo-DES. Neste caso, a saída do PRNG nunca é vista triplo-DES. Neste caso, a saída do PRNG nunca é vista diretamente pelo adversário.diretamente pelo adversário.

Ataque baseado em Ataque baseado em entradasentradas

Usado quando o adversário utiliza-se de Usado quando o adversário utiliza-se de conhecimento ou controle das entradas para fazer conhecimento ou controle das entradas para fazer criptoanálise da saída do PRNGcriptoanálise da saída do PRNG

Tipos:Tipos: Entrada conhecidaEntrada conhecida

Se as entradas da PRNG, que são idealizadas para serem difícil Se as entradas da PRNG, que são idealizadas para serem difícil ao usuário adivinhar, se tornam facilmente dedutíveis. Ex. ao usuário adivinhar, se tornam facilmente dedutíveis. Ex. Ltencia de disco rigido. Quando o usuário está acessando um Ltencia de disco rigido. Quando o usuário está acessando um disco da rede, o adversário pode observar a latenciadisco da rede, o adversário pode observar a latencia

Entrada escolhidaEntrada escolhida Muito utilizada contra smartcards e outras aplicações em que Muito utilizada contra smartcards e outras aplicações em que

são utilizadas informações do usuário como entropia para o são utilizadas informações do usuário como entropia para o PRNGPRNG

Entrada repetidaEntrada repetida Similar ao de entrada escolhida, a nao ser pelo fato de exigir Similar ao de entrada escolhida, a nao ser pelo fato de exigir

menos sofisticação por parte do atacante.menos sofisticação por parte do atacante.

Extensão de ataquesExtensão de ataques

Tenta extender as vantagens dos ataques se Tenta extender as vantagens dos ataques se aproveitando de brechas na segurançaaproveitando de brechas na segurança

As brechas podem ser:As brechas podem ser: Vazamento de informaçõesVazamento de informações Sucesso criptográfico anteriorSucesso criptográfico anterior

Estes ataques são bem sucedidos quando o Estes ataques são bem sucedidos quando o sistema é iniciado sem entropiasistema é iniciado sem entropia

ConclusãoConclusão Números aleatórios são a base para muitas aplicações Números aleatórios são a base para muitas aplicações

de criptografia.de criptografia.

Não existe uma função “independente” para gerar Não existe uma função “independente” para gerar números aleatórios.números aleatórios.

Os computadores atuais podem apenas aproximar os Os computadores atuais podem apenas aproximar os números aleatórios, usando os geradores de números números aleatórios, usando os geradores de números pseudo-aleatórios. pseudo-aleatórios.

Ataques à diversas aplicações criptográficas são Ataques à diversas aplicações criptográficas são possíveis através de ataques a PRNGs.possíveis através de ataques a PRNGs.

Aplicações computacionais cada vez mais utilizam-se de Aplicações computacionais cada vez mais utilizam-se de fontes físicas externas para obterem números aleatórios.fontes físicas externas para obterem números aleatórios.