# CSPRNG

Um gerador de número pseudo-aleatório criptograficamente seguro (CSPRNG, na sigla em inglês) ou gerador de números pseudoaleatórios criptográfico (CPRNG, na sigla em inglês) é um gerador de números pseudoaleatórios (PRNG) com propriedades que o torna adequado para o uso na criptografia.
Muitos aspectos da criptografia requerem números aleatórios, como por exemplo:
* geração de chave
* nonces
* cifras de uso único
* sais em certos esquemas de assinatura, como ECDSA, RSASSA-PSS
A "qualidade" da aleatoriedade necessária para essas aplicações varia. Por exemplo, criar uma nonce para algum protocolo requer apenas singularidade. Por outro lado, a geração de uma chave mestre requer mais qualidade, tal como entropia. E no caso de cifras de uso único, a garantia da teoria da informação de sigilo perfeito apenas se mantém caso a geração da chave utilizar uma fonte verdadeiramente aleatória com alta entropia.
Idealmente, a geração de números aleatórios em CSPRNGs usa entropia para obter fontes de alta qualidade, que podem ser um hardware ou um processo de sistema imprevisível; apesar de correlações inesperadas terem sido encontradas em tais diversos processos ostensivamente independentes. Do ponto de vista da informação teórica, a quantidade de aleatoriedade, a entropia que pode ser gerada, é igual a entropia fornecida pelo sistema. Porém, às vezes, em situações práticas, é necessário mais números aleatórios do que há entropia disponível. Além disso, o processo de extrair aleatoriedade de um sistema em execução pode ser lento na prática. Em tais casos, um CSPRNG pode ser utilizado. Um CSPRNG pode "ampliar" a entropia disponível sobre mais bits.

## Requisitos

Os requisitos de um PRNG padrão também são satisfeitos por um PRNG criptograficamente seguro, porém, não se pode dizer o mesmo do inverso. Os requisitos do CSPRNG podem ser divididos em dois grupos: primeiramente, eles devem passar por testes de aleatoriedade estatísticos; e segundo, eles devem ser resistentes a ataques, mesmo quando parte de seu estado inicial ou em execução chegue ao conhecimento do atacante.
* Todo CSPRNG deve satisfazer o teste do próximo bit. Isto é, dados os primeiros k bits de uma sequência aleatória, não há algoritmo de tempo polinomial capaz de predizer o (k+1)-ésimo bit com probabilidade de sucesso maior que 50%. Andrew Yao provou em 1982 que um gerador que passe nesse teste, passará em qualquer outro teste estatístico de tempo polinomial para aleatoriedade.
* Todo CSPRNG deve resistir a "extensões de compromisso de estado". Caso parte ou o todo de seus estados seja revelado (ou predito corretamente), deve ser impossível de reconstruir o fluxo de números aleatórios antes dessa revelação. Além disso, caso haja uma entrada de entropia em execução, deve ser inviável utilizar-se de qualquer conhecimento sobre o estado da entrada para predizer condições futuras sobre o estado do CSPRNG.
       Exemplo: Se o CSPRNG sob consideração produzir uma saída computando bits de π em sequência, começando de alguém ponto desconhecido dessa expansão binária, ele pode satisfazer o teste do próximo e ser considerado estatisticamente aleatório, já que π aparenta ser uma sequência aleatória. (Isso poderia ser garantido caso π seja um número normal, por exemplo.) Entretanto, esse algoritmo não é criptograficamente seguro; um atacante pode determinar em qual bit de π (i.e. o estado do algoritmo) ele se encontra e será capaz de calcular todos os bits anteriores também.
A maioria dos PRNGs não são adequados para uso como CSPRNGs e não irão satisfazer ambos requisitos. Primeiro, enquanto muitos PRNGs dão saídas aparentemente aleatórias para alguns testes estatísticos, eles não são capazes de resistir a determinados métodos de engenharia reversa. Testes estatísticos especializados podem ser especialmente melhorados para mostrar que esses números aleatórios não são verdadeiramente aleatórios. Segundo, para a maioria dos PRNGs, quando o seu estado atual é revelado, todos os números aleatórios passados podem ser calculados, permitindo a um atacante ler todas as mensagens passadas, bem como as futuras.
CSPRNGs são projetados intencionalmente para resistir a esse tipo de criptoanálise.

## Algumas informações básicas

Santha e Vazirani provaram que vários fluxos de bit com baixa aleatoriedade podem ser combinados para produzir um fluxo de bit quase-aleatório de melhor qualidade. Antes ainda, John von Neumann provou que um simples algoritmo é capaz de remover quantidade considerável de viés em qualquer fluxo de bits, que pode ser aplicado em cada fluxo de bit antes de usar qualquer variante do projeto de Santha-Vazirani. Essa área de atuação é chamada de extração de entropia e é objeto de pesquisas em atividade (e.g., N Nisan, S Safra, R Shaltiel, A Ta-Shma, C Umans, D Zuckerman).

## Projetos

Na discussão abaixo, os projetos de CSPRNG são divididos em três classes: 1) as baseadas em primitivas criptográficas como cifras e hashes criptográficos, 2) as baseadas em problemas matemáticos considerados difíceis, e 3) projetos de propósito-especial. Esse último, por muitas vezes introduz entropia adicional quando disponível e , a rigor, não são geradores de números aleatórios "puro", pois suas saídas não são determinadas pelo seus estados iniciais. Essa adição pode prevenir ataques mesmo que o estado inicial seja comprometido.

### Projetos baseados em primitivas criptográficas

* Uma cifra de bloco segura pode ser transformado em um CSPRNG executando-o em modo contador. Isso pode ser feito, escolhendo uma chave aleatória e encriptando-a junto com 0, depois com 1, depois com 2, etc. O contador também pode começar em um número arbitrário diferente de 0. Assumindo que uma cifra de bloco de n-bit, a saída pode ser distinguida de um dado aleatório após, aproximadamente, 2$^{n/2}$ blocos desde, seguindo o paradoxo do aniversário, blocos em colisão devem se tornar mais prováveis a partir desse ponto, onde uma cifra de blocos em modo CTR nunca dará como saída blocos idênticos. Para cifras de bloco de 64 bits, isso limita o tamanho da saída segura para alguns gigabytes, com blocos de 128 bits, a limitação é grande o suficiente para não afetar aplicações típicas.
* Um hash criptograficamente seguro de um contador também pode atuar como um bom CSPRNG em alguns casos. Nesse caso, é necessário que o valor inicial do contador seja aleatório e secreto. Entretanto, há poucos estudos desses algoritmos utilizados dessa maneira, e pelo menos alguns autores alertam contra este uso.
* A maioria das cifras de fluxo funcionam através da geração de fluxo de bits pseudoaleatórios que são combinados (quase sempre com uma operação XOR) com o purotexto; executando a cifra em modo contador irá retornar um novo fluxo pseudoaleatório, possivelmente com um período mais longo. A cifra só pode ser segura se o fluxo original for um bom CSPRNG, apesar desse nem sempre ser o caso (veja a cifra RC4). Novamente, o estado inicial deve ser mantido em segredo.

### Projetos em teoria dos números

* O algoritmo Blum Blum Shub possui uma prova de segurança baseado na dificuldade do problema dos resíduos quadráticos (veja lei da reciprocidade quadrática). Como a única maneira conhecida de resolver esse problema é através da fatoração dos módulos, e, geralmente, é considerado que a dificuldade da fatoração de inteiros fornece uma prova segura condicional para o algoritmo Blum Blum Shub. Entretanto, esse algoritmo é muito ineficiente e por isso, impraticável, exceto quando medidas de extrema segurança são necessárias.
* O algoritmo Blum-Micali possui uma prova de segurança incondicional baseada na dificuldade do problema do logaritmo discreto, que também é muito ineficiente.
* Daniel Brown da Certicom escreveu em 2006 uma prova de segurança para Dual_EC_DRBG, baseada na suposta dificuldade do problema decisional Diffie-Hellman, o problema do logaritmo-x, e o problema do ponto truncado. A prova de 2006 assume, explicitamente, um outlen menor que o do Dual_EC_DRBG padrão, e que o P e o Q no Dual_EC_DRBG padrão (que, em 2013, foi revelado que a NSA teria introduzido um backdoor nesse sistema) são substituídos por valores que não possuem essa falha de backdoor.

### Projetos especiais

Há diversos PRNGs práticos que foram projetados para ser criptograficamente seguros, como:
* o algoritmo Yarrow que tenta avaliar a qualidade entrópica de suas entradas. Yarrow é utilizado em FreeBSD, OpenBSD e Mac OS X (e também em /dev/random).
* o algoritmo Fortuna, o sucessor do Yarrow, que não tenta avaliar a qualidade entrópica de suas entradas.
* a função CryptGenRandom fornecida pela CryptoAPI da Microsoft.
* ISAAC baseado em uma variante da cifra RC4.
* Algoritmo evolutivo baseado no Statistical Test Suite da NIST.
* arc4random, uma API, originária do OpenBSD, que fornece acesso a diversos geradores de números aleatórios baseados em RC4.
* o DRBG da AES-CTR é frequentemente utilizado como um gerador de números aleatórios em sistemas que utilizam a encriptação AES.
* o padrão ANSI X9.17 (Financial Institution Key Management (atacado)), que foi adotado como um padrão FIPS também. Ele recebe como entrada um pacote de chaves k numa variação do 3DES (ao invés de utilizar três chaves distintas, a terceira é igual a primeira) e (o valor inicial) de uma semente aleatória s de 64 bits. Toda vez que um número aleatório é requisitado, ele:
** Obtém a data/hora atual D com a precisão máxima possível.
** Computa um valor temporário t = TDEA$_k$(D)
** Computa um valor aleatório x = TDEA$_k$(s ⊕ t), onde ⊕ denota ou exclusivo bit a bit.
** Atualiza a semente s = TDEA$_k$(x ⊕ t)
    Obviamente, essa técnica é facilmente generalizada por qualquer bloco de cifra; AES tem sido sugerido (Young and Yung, op cit, sect 3.5.1).

## Padrões

Diversos CSPRNGs foram padronizados. Por exemplo,
* FIPS 186-2
* NIST SP 800-90A: Esse padrão possui três CSPRNGs incontroversas chamadas Hash_DRBG, HMAC_DRBG, e CTR_DRBG; e uma PRNG chamada Dual_EC_DRBG que foi mostrada não ser criptograficamente segura e provavelmente possui uma backdoor cleptográfica da NSA.
* ANSI X9.17-1985 Appendix C
* ANSI X9.31-1998 Appendix A.2.4
* ANSI X9.62-1998 Annex A.4, obsoleta pelo ANSI X9.62-2005, Annex D (HMAC_DRBG)
Uma boa referência é mantida pela NIST.
Existem, também, diversos padrões para testes estatísticos de novos projetos de CSPRNG:
* A Statistical Test Suite for Random and Pseudorandom Number Generators, NIST Special Publication 800-22.

## Backdoor da NSA no PRNG Dual_EC_DRBG

The Guardian e The New York Times relataram que a National Security Agency (NSA) inseriu uma PRNG no NIST SP 800-90A que teria um backdoor que permitiria a NSA decriptar qualquer material prontamente, que teria sido encriptado com a ajuda do Dual_EC_DRBG. Ambas as reportagens relataram que, que como especialistas em segurança já suspeitavam, a NSA tem introduzido fraquezas no CSPRNG padrão 800-90; isso foi confirmado pela primeira vez por um dos documentos confidenciais vazados pelo The Guardian por Edward Snowden. A NSA trabalhou secretamente para ter a sua própria versão do projeto da norma de segurança da NIST, aprovada em todo mundo para uso em 2006. O documento vazado afirma que "eventualmente, a NSA tornou-se seu único editor." Apesar do conhecido potencial de um backdoor e outras deficiências significativas com o Dual_EC_DRBG, diversas empresas como a RSA Security continuaram a utilizar o Dual_EC_DRBG, até a backdoor ser confirmada em 2013. RSA Security recebeu da NSA U$10 milhões como pagamento para continuar a utilizar o CSPRNG comprometido.