CSPRNG

Categorias de números aleatórios e respectivos geradores (chinês simplificado).

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.

Ligações externas

• RFC 4086, Randomness Requirements for Security
• Java "entropy pool" for cryptographically secure unpredictable random numbers.
• Java standard class providing a cryptographically strong pseudo-random number generator (PRNG).
• Cryptographically Secure Random number on Windows without using CryptoAPI
• Conjectured Security of the ANSI-NIST Elliptic Curve RNG, Daniel R. L. Brown, IACR ePrint 2006/117.
• A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator, Daniel R. L. Brown and Kristian Gjosteen, IACR ePrint 2007/048. Aparece em CRYPTO 2007.
• Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/190.
• Efficient Pseudorandom Generators Based on the DDH Assumption, Reza Rezaeian Farashahi and Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/321.
• Analysis of the Linux Random Number Generator, Zvi Gutterman and Benny Pinkas and Tzachy Reinman.
• An implementation of a cryptographically safe shrinking pseudorandom number generator.