Gerador de números pseudo-aleatórios criptograficamente seguro - Cryptographically-secure pseudorandom number generator

Um gerador de número pseudo-aleatório criptograficamente seguro ( CSPRNG ) ou gerador de número pseudo-aleatório criptográfico ( CPRNG ) é um gerador de número pseudo - aleatório (PRNG) com propriedades que o tornam adequado para uso em criptografia . Ele também é vagamente conhecido como gerador de números aleatórios criptográficos ( CRNG ) (consulte Geração de números aleatórios § "Verdadeiro" vs. números pseudo-aleatórios ).

A maioria dos aplicativos criptográficos requer números aleatórios , por exemplo:

geração de chave
nonces
sais em certos esquemas de assinatura, incluindo ECDSA , RSASSA-PSS

A "qualidade" da aleatoriedade necessária para esses aplicativos varia. Por exemplo, a criação de um nonce em alguns protocolos precisa apenas de exclusividade. Por outro lado, a geração de uma chave mestra requer uma qualidade superior, como mais entropia . E no caso de blocos únicos , a garantia teórica da informação de sigilo perfeito só é válida se o material da chave vier de uma fonte aleatória verdadeira com alta entropia e, portanto, qualquer tipo de gerador de número pseudo-aleatório é insuficiente.

Idealmente, a geração de números aleatórios em CSPRNGs usa entropia obtida de uma fonte de alta qualidade, geralmente a API de aleatoriedade do sistema operacional. No entanto, correlações inesperadas foram encontradas em vários desses processos aparentemente independentes. Do ponto de vista da teoria da informação, a quantidade de aleatoriedade, a entropia que pode ser gerada, é igual à entropia fornecida pelo sistema. Mas às vezes, em situações práticas, são necessários mais números aleatórios do que a entropia disponível. Além disso, os processos para extrair aleatoriedade de um sistema em execução são lentos na prática. Em tais casos, às vezes pode ser usado um CSPRNG. Um CSPRNG pode "esticar" a entropia disponível por mais bits.

Requisitos

Os requisitos de um PRNG comum também são satisfeitos por um PRNG criptograficamente seguro, mas o inverso não é verdadeiro. Os requisitos do CSPRNG se enquadram em dois grupos: primeiro, que eles sejam aprovados em testes estatísticos de aleatoriedade ; e, em segundo lugar, resistem bem a ataques sérios, mesmo quando parte de seu estado inicial ou de execução fica disponível para um invasor.

Cada CSPRNG deve satisfazer o teste do próximo bit . Ou seja, dados os primeiros k bits de uma sequência aleatória, não há algoritmo de tempo polinomial que pode prever o ( k +1) o bit com probabilidade de sucesso não desprezível melhor que 50%. Andrew Yao provou em 1982 que um gerador aprovado no teste do próximo bit passará em todos os outros testes estatísticos de tempo polinomial para aleatoriedade.
Cada CSPRNG deve suportar "extensões de compromisso de estado". No caso de parte ou todo o seu estado ter sido revelado (ou adivinhado corretamente), deveria ser impossível reconstruir o fluxo de números aleatórios antes da revelação. Além disso, se houver uma entrada de entropia durante a execução, deve ser inviável usar o conhecimento do estado da entrada para prever as condições futuras do estado CSPRNG.

Exemplo: Se o CSPRNG em consideração produz saída computando bits de π em sequência, começando de algum ponto desconhecido na expansão binária, ele pode muito bem satisfazer o teste do próximo bit e, portanto, ser estatisticamente aleatório, já que π parece ser uma sequência aleatória . (Isso seria garantido se π fosse um número normal , por exemplo.) No entanto, esse algoritmo não é criptograficamente seguro; um invasor que determina qual bit de pi (ou seja, o estado do algoritmo) está em uso no momento também será capaz de calcular todos os bits anteriores.

A maioria dos PRNGs não é adequada para uso como CSPRNGs e falhará em ambas as contagens. Em primeiro lugar, embora a maioria das saídas PRNGs pareça aleatória para diversos testes estatísticos, eles não resistem à engenharia reversa determinada. Testes estatísticos especializados podem ser encontrados especialmente ajustados para tal PRNG que mostra que os números aleatórios não são verdadeiramente aleatórios. Em segundo lugar, para a maioria dos PRNGs, quando seu estado é revelado, todos os números aleatórios anteriores podem ser retroduzidos, permitindo que um invasor leia todas as mensagens anteriores, bem como as futuras.

Os CSPRNGs são projetados explicitamente para resistir a esse tipo de criptoanálise .

Definições

No cenário assintótico , uma família de funções computáveis de tempo polinomial determinísticas para algum polinômio $p$ , é um gerador de número pseudo - aleatório ( PRNG , ou PRG em algumas referências), se estende o comprimento de sua entrada ( para qualquer $k$ ), e se seu a saída é computacionalmente indistinguível da verdadeira aleatoriedade, ou seja, para qualquer algoritmo de tempo polinomial probabilístico $A$ , que produz 1 ou 0 como um distinguidor, ${\ displaystyle G_ {k} \ dois pontos \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {p (k)}}$ ${\ displaystyle p (k)> k}$

{\ displaystyle \ left | \ Pr _ {x \ gets \ {0,1 \} ^ {k}} [A (G (x)) = 1] - \ Pr _ {r \ gets \ {0,1 \ } ^ {p (k)}} [A (r) = 1] \ right | <\ mu (k)}

para alguma função insignificante . (A notação significa que $x$ é escolhido uniformemente ao acaso a partir do conjunto $X.$ ) ${\ displaystyle \ mu}$ ${\ displaystyle x \ gets X}$

Há uma caracterização equivalente: para qualquer família de funções , $G$ é um PRNG se e somente se o próximo bit de saída de $G$ não puder ser previsto por um algoritmo de tempo polinomial. ${\ displaystyle G_ {k} \ dois pontos \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {p (k)}}$

Um PRNG forward-secure com comprimento de bloco é um PRNG , onde a string de entrada com comprimento $k$ é o estado atual no período $i$ , e a saída ( , ) consiste no próximo estado e no bloco de saída pseudo-aleatório do período $i$ , que resiste ao estado comprometer extensões no seguinte sentido. Se o estado inicial é escolhido uniformemente ao acaso , então para qualquer $i$ , a sequência deve ser computacionalmente indistinguível de , em que são escolhidos uniformemente ao acaso . ${\ displaystyle t (k)}$ ${\ displaystyle G_ {k} \ dois pontos \ {0,1 \} ^ {k} \ a \ {0,1 \} ^ {k} \ times \ {0,1 \} ^ {t (k)}}$ ${\ displaystyle s_ {i}}$ ${\ displaystyle s_ {i + 1}}$ ${\ displaystyle y_ {i}}$ ${\ displaystyle s_ {i + 1}}$ ${\ displaystyle y_ {i}}$ ${\ displaystyle s_ {1}}$ ${\ displaystyle \ {0,1 \} ^ {k}}$ ${\ displaystyle (y_ {1}, y_ {2}, \ dots, y_ {i}, s_ {i + 1})}$ ${\ displaystyle (r_ {1}, r_ {2}, \ dots, r_ {i}, s_ {i + 1})}$ ${\ displaystyle r_ {i}}$ ${\ displaystyle \ {0,1 \} ^ {t (k)}}$

Qualquer PRNG pode ser transformado em um PRNG seguro direto com comprimento de bloco , dividindo sua saída no próximo estado e na saída real. Isso é feito definindo , em que e ; então $G$ é um PRNG seguro direto com o próximo estado e como o bloco de saída pseudo-aleatório do período atual. ${\ displaystyle G \ dois pontos \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {p (k)}}$ ${\ displaystyle p (k) -k}$ ${\ displaystyle G (s) = G_ {0} (s) \ Vert G_ {1} (s)}$ ${\ displaystyle | G_ {0} (s) | = | s | = k}$ ${\ displaystyle | G_ {1} (s) | = p (k) -k}$ ${\ displaystyle G_ {0}}$ ${\ displaystyle G_ {1}}$

Extração de entropia

Santha e Vazirani provaram que vários fluxos de bits com aleatoriedade fraca podem ser combinados para produzir um fluxo de bits quase aleatório de maior qualidade. Ainda antes, John von Neumann provou que um algoritmo simples pode remover uma quantidade considerável de polarização em qualquer fluxo de bits, o que deve ser aplicado a cada fluxo de bits antes de usar qualquer variação do projeto de Santha-Vazirani.

Desenhos

Na discussão abaixo, os projetos CSPRNG são divididos em três classes:

aqueles baseados em primitivas criptográficas, como cifras e hashes criptográficos ,
aqueles baseados em problemas matemáticos considerados difíceis, e
projetos para fins especiais.

O último freqüentemente introduz entropia adicional quando disponível e, estritamente falando, não são geradores de números pseudo-aleatórios "puros", já que sua saída não é completamente determinada por seu estado inicial. Essa adição pode evitar ataques, mesmo se o estado inicial estiver comprometido.

Projetos baseados em primitivas criptográficas

Uma cifra de bloco seguro pode ser convertida em um CSPRNG executando-o no modo contador . Isso é feito escolhendo uma chave aleatória e criptografando um 0, em seguida criptografando um 1 e, em seguida, criptografando um 2, etc. O contador também pode ser iniciado em um número arbitrário diferente de zero. Assumindo uma cifra de bloco de n bits, a saída pode ser distinguida dos dados aleatórios após cerca de 2 ^{n / 2} blocos, uma vez que, após o problema do aniversário , blocos em colisão devem se tornar prováveis nesse ponto, enquanto uma cifra de bloco no modo CTR nunca produzirá blocos idênticos . Para cifras de bloco de 64 bits, isso limita o tamanho de saída seguro a alguns gigabytes, com blocos de 128 bits a limitação é grande o suficiente para não afetar os aplicativos típicos. No entanto, quando usado sozinho, não atende a todos os critérios de um CSPRNG (conforme declarado acima), uma vez que não é forte contra "extensões de compromisso de estado": com o conhecimento do estado (neste caso, um contador e uma chave), você pode prever todas as saídas anteriores.
Um hash criptograficamente seguro de um contador também pode atuar como um bom CSPRNG em alguns casos. Nesse caso, também é necessário que o valor inicial desse contador seja aleatório e secreto. No entanto, existem poucos estudos sobre esses algoritmos para uso dessa maneira, e pelo menos alguns autores alertam contra esse uso.

A maioria das cifras de fluxo funciona gerando um fluxo pseudo-aleatório de bits que são combinados (quase sempre com XOR ) com o texto simples ; executar a cifra em um contador retornará um novo fluxo pseudo-aleatório, possivelmente com um período mais longo. A cifra só pode ser segura se o fluxo original for um bom CSPRNG, embora esse não seja necessariamente o caso (consulte a cifra RC4 ). Novamente, o estado inicial deve ser mantido em segredo.

Projetos teóricos dos números

O algoritmo Blum Blum Shub possui uma prova de segurança baseada na dificuldade do problema de residuosidade quadrática . Como a única maneira conhecida de resolver esse problema é fatorar o módulo, geralmente considera-se que a dificuldade da fatoração de inteiros fornece uma prova de segurança condicional para o algoritmo Blum Blum Shub. No entanto, o algoritmo é muito ineficiente e, portanto, impraticável, a menos que extrema segurança seja necessária.
O algoritmo Blum-Micali tem uma prova de segurança baseada na dificuldade do problema do logaritmo discreto, mas também é muito ineficiente.
Daniel Brown da Certicom escreveu uma prova de segurança de 2006 para Dual_EC_DRBG , com base na dureza assumida da suposição Diffie-Hellman Decisional , o problema do logaritmo x e o problema do ponto truncado . A prova de 2006 assume explicitamente um outlen mais baixo do que no padrão Dual_EC_DRBG, e que P e Q no padrão Dual_EC_DRBG (que foi revelado em 2013 como provavelmente backdoored pela NSA) são substituídos por valores não backdoored.

Designs especiais

Há uma série de PRNGs práticos que foram projetados para serem criptograficamente seguros, incluindo

o algoritmo de Yarrow que tenta avaliar a qualidade entrópica de suas entradas. Yarrow é usado no macOS e em outros sistemas operacionais da Apple até cerca de dezembro de 2019. A Apple mudou para o Fortuna desde então. (Veja / dev / random ).
o algoritmo ChaCha20 substituiu o RC4 no OpenBSD (versão 5.4), NetBSD (versão 7.0) e FreeBSD (versão 12.0).
ChaCha20 também substituiu SHA-1 no Linux na versão 4.8.
o algoritmo Fortuna , sucessor do Yarrow, que não tenta avaliar a qualidade entrópica de suas entradas. Fortuna é usado no FreeBSD. A Apple mudou para o Fortuna para a maioria ou todos os sistemas operacionais da Apple a partir de dezembro de 2019.
a função CryptGenRandom previsto no Microsoft 's criptográfica Application Programming Interface
ISAAC baseado em uma variante da cifra RC4
Registro de deslocamento de feedback linear ajustado com algoritmo evolutivo baseado no NIST Statistical Test Suite.
arc4random
AES - CTR DRBG é frequentemente usado como um gerador de números aleatórios em sistemas que usam criptografia AES.
Padrão ANSI
X9.17 ( Financial Institution Key Management (wholesale) ), que também foi adotado como um padrão FIPS . Ele toma como entrada um TDEA ( keying opção 2 ) chave feixe k e (o valor inicial) de 64 bits semente aleatória s . Cada vez que um número aleatório é necessário:
- Obtém a data / hora atual D com a resolução máxima possível.
- Calcula um valor temporário $t = TDEA k (D)$
- Calcula o valor aleatório $x = TDEA k (s \oplus t)$ , onde ⊕ denota ou exclusivo bit a bit .
- Atualiza a semente $s = TDEA k (x \oplus t)$

Obviamente, a técnica é facilmente generalizada para qualquer cifra de bloco; AES foi sugerido.

Padrões

Vários CSPRNGs foram padronizados. Por exemplo,

Este padrão retirado tem quatro PRNGs. Dois deles são incontroversos e comprovados: CSPRNGs chamados Hash_DRBG e HMAC_DRBG.

O terceiro PRNG neste padrão, CTR DRBG , é baseado em uma cifra de bloco em execução no modo contador . Ele tem um design incontroverso, mas provou ser mais fraco em termos de ataque de distinção do que o nível de segurança da cifra de bloco subjacente quando o número de bits de saída deste PRNG é maior que dois à potência do tamanho do bloco da cifra de bloco subjacente em bits.

Quando o número máximo de bits de saída deste PRNG é igual ao ^{tamanho de} 2 ^blocos , a saída resultante fornece o nível de segurança matematicamente esperado que o tamanho da chave deveria gerar, mas a saída é mostrada como não indistinguível de um número aleatório verdadeiro gerador. Quando o número máximo de bits de saída deste PRNG é menor do que isso, o nível de segurança esperado é entregue e a saída parece ser indistinguível de um gerador de número aleatório verdadeiro.

É observado na próxima revisão que a força de segurança reivindicada para CTR_DRBG depende da limitação do número total de solicitações de geração e dos bits fornecidos por solicitação de geração.

O quarto e último PRNG neste padrão é denominado Dual_EC_DRBG . Ele demonstrou não ser criptograficamente seguro e acredita-se que ele tenha uma porta dos fundos cleptográfica NSA.

NIST SP 800-90A Rev.1: Este é essencialmente NIST SP 800-90A com Dual_EC_DRBG removido e é o substituto do padrão retirado.
ANSI X9.17-1985 Apêndice C
ANSI X9.31-1998 Apêndice A.2.4
ANSI X9.62-1998 Anexo A.4, obsoleto por ANSI X9.62-2005, Anexo D (HMAC_DRBG)

Uma boa referência é mantida pelo NIST .

Existem também padrões para testes estatísticos de novos designs CSPRNG:

A Statistical Test Suite for Random and Pseudorandom Number Generators , NIST Special Publication 800-22 .

NSA cleptographic backdoor no Dual_EC_DRBG PRNG

O Guardian e o The New York Times relataram em 2013 que a National Security Agency (NSA) inseriu uma porta dos fundos em um gerador de números pseudo - aleatórios (PRNG) do NIST SP 800-90A, que permite à NSA descriptografar prontamente o material que foi criptografado com o auxílio de Dual_EC_DRBG . Ambos os documentos relatam que, como especialistas independentes em segurança há muito suspeitavam, a NSA tem introduzido fraquezas no padrão CSPRNG 800-90; isso foi confirmado pela primeira vez por um dos documentos ultrassecretos vazados para o Guardian por Edward Snowden . A NSA trabalhou secretamente para obter sua própria versão do esboço do padrão de segurança do NIST aprovado para uso mundial em 2006. O documento vazado afirma que "eventualmente, a NSA se tornou o único editor." Apesar do potencial conhecido para umbackdoor cleptográfico e outras deficiências significativas conhecidas com Dual_EC_DRBG, várias empresas como a RSA Security continuaram usando Dual_EC_DRBG até que o backdoor foi confirmado em 2013. RSA Security recebeu um pagamento de $ 10 milhões da NSA para fazer isso.

Falhas de segurança

Ataque DUHK

Em 23 de outubro de 2017, Shaanan Cohney , Matthew Green e Nadia Heninger , criptógrafos da Universidade da Pensilvânia e da Universidade Johns Hopkins, divulgaram detalhes do ataque DUHK (Don't Use Hard-coded Keys) em WPA2, onde fornecedores de hardware usam um hardcoded chave semente para o algoritmo ANSI X9.31 RNG, afirmando que "um invasor pode usar dados criptografados de força bruta para descobrir o resto dos parâmetros de criptografia e deduzir a chave mestra de criptografia usada para criptografar sessões da web ou conexões de rede privada virtual (VPN)".

Máquina de cifragem ROXA japonesa

Durante a Segunda Guerra Mundial , o Japão usou uma máquina de criptografia para comunicações diplomáticas; os Estados Unidos conseguiram decifrá-lo e ler suas mensagens , principalmente porque os "valores-chave" usados não eram suficientemente aleatórios.

Referências

links externos

RFC 4086 , Requisitos de aleatoriedade para segurança
Java "pool de entropia" para números aleatórios imprevisíveis criptograficamente seguros.
Classe padrão Java que fornece um gerador de números pseudo-aleatórios (PRNG) criptograficamente forte.
Número aleatório criptograficamente seguro no Windows sem usar CryptoAPI
Segurança conjecturada da curva elíptica ANSI-NIST RNG , Daniel RL Brown, IACR ePrint 2006/117.
Uma análise de segurança do gerador de números aleatórios da curva elíptica NIST SP 800-90 , Daniel RL Brown e Kristian Gjosteen, IACR ePrint 2007/048. Para aparecer no CRYPTO 2007.
Criptoanálise do gerador pseudo-aleatório da curva elíptica dupla , Berry Schoenmakers e Andrey Sidorenko, IACR ePrint 2006/190.
Geradores Pseudo- Aleatórios Eficientes com Base na Suposição DDH , Reza Rezaeian Farashahi e Berry Schoenmakers e Andrey Sidorenko, IACR ePrint 2006/321.
Análise do gerador de números aleatórios do Linux , Zvi Gutterman e Benny Pinkas e Tzachy Reinman.
Documentação do NIST Statistical Test Suite e download do software.

Languages

In other projects