Gerador de números aleatórios de hardware - Hardware random number generator

Este cartão de computador acelerador TLS usa um gerador de número aleatório de hardware para gerar chaves criptográficas para criptografar dados enviados por redes de computadores.

Na computação , um gerador de números aleatórios de hardware ( HRNG ) ou gerador de números aleatórios verdadeiros ( TRNG ) é um dispositivo que gera números aleatórios a partir de um processo físico , em vez de por meio de um algoritmo . Tais dispositivos são muitas vezes baseados em fenómenos microscópicos que geram de baixo nível, estatisticamente aleatório " ruído " de sinais, tais como o ruído térmico , o efeito óptico , envolvendo um divisor de feixe , e outros quântica fenómenos. Esses processos estocásticos são, em teoria, completamente imprevisíveis enquanto uma equação que governa tais fenômenos é desconhecida ou incontestável, e as afirmações da teoria de imprevisibilidade estão sujeitas a teste experimental . Isso contrasta com o paradigma da geração de números pseudo-aleatórios comumente implementado em programas de computador .

Um gerador de números aleatórios de hardware normalmente consiste em um transdutor para converter alguns aspectos dos fenômenos físicos em um sinal elétrico, um amplificador e outro circuito eletrônico para aumentar a amplitude das flutuações aleatórias para um nível mensurável e algum tipo de analógico para conversor digital para converter a saída em um número digital, geralmente um dígito binário simples 0 ou 1. Ao amostrar repetidamente o sinal que varia aleatoriamente, uma série de números aleatórios é obtida.

A principal aplicação dos geradores de números aleatórios de hardware eletrônico é na criptografia , onde são usados ​​para gerar chaves criptográficas aleatórias para transmitir dados com segurança. Eles são amplamente usados ​​em protocolos de criptografia da Internet, como Transport Layer Security (TLS).

Os geradores de números aleatórios também podem ser construídos a partir de processos macroscópicos "aleatórios", usando dispositivos como lançamento de moedas , dados , rodas de roleta e máquinas de loteria . A presença de imprevisibilidade nesses fenômenos pode ser justificada pela teoria dos sistemas dinâmicos instáveis e pela teoria do caos . Embora os processos macroscópicos sejam determinísticos na mecânica newtoniana , a saída de um dispositivo bem projetado como uma roda de roleta não pode ser prevista na prática, porque depende dos micro-detalhes sensíveis das condições iniciais de cada uso.

Embora os dados tenham sido usados ​​principalmente em jogos de azar e como elementos "aleatórios" em jogos (por exemplo, jogos de RPG ), o cientista vitoriano Francis Galton descreveu uma maneira de usar dados para gerar explicitamente números aleatórios para fins científicos em 1890.

Geradores de números aleatórios de hardware geralmente produzem apenas um número limitado de bits aleatórios por segundo. Para aumentar a taxa de dados de saída disponível, eles são freqüentemente usados ​​para gerar a " semente " para um gerador de números pseudo-aleatórios criptograficamente seguro mais rápido , que então gera uma sequência de saída pseudo - aleatória a uma taxa de dados muito mais alta.

Usos

Números aleatórios imprevisíveis foram investigados pela primeira vez no contexto de jogos de azar , e muitos dispositivos de randomização, como dados , baralho de cartas e rodas de roleta , foram desenvolvidos pela primeira vez para esse uso. Números aleatórios produzidos de maneira justa são vitais para o jogo eletrônico e as formas de criá-los às vezes são regulamentadas por comissões de jogos governamentais.

Números aleatórios também são usados ​​para fins não relacionados a jogos de azar, tanto onde seu uso é matematicamente importante, como amostragem para pesquisas de opinião , quanto em situações em que a justiça é aproximada por randomização , como loterias militares e seleção de jurados .

Criptografia

O principal uso dos geradores de números aleatórios de hardware é no campo da criptografia de dados , por exemplo, para criar chaves criptográficas aleatórias e nonces necessários para criptografar e assinar dados. Eles são uma alternativa mais segura aos geradores de números pseudo - aleatórios (PRNGs), programas de software comumente usados ​​em computadores para gerar números "aleatórios". PRNGs usam um algoritmo determinístico para produzir sequências numéricas. Embora essas sequências pseudo-aleatórias passem nos testes de padrão estatístico de aleatoriedade , conhecendo o algoritmo e as condições usadas para inicializá-lo, chamadas de "semente", a saída pode ser prevista. Como a sequência de números produzida por um PRNG é, em princípio, previsível, os dados criptografados com números pseudo-aleatórios são potencialmente vulneráveis ​​à criptoanálise . Os geradores de números aleatórios de hardware produzem sequências de números que não são previsíveis e, portanto, fornecem a maior segurança quando usados ​​para criptografar dados.

Trabalho cedo

Uma das primeiras formas de produzir números aleatórios era por meio de uma variação das mesmas máquinas usadas para jogar keno ou selecionar números de loteria . Estas envolviam bolas de pingue-pongue numeradas e misturadas com ar soprado, talvez combinadas com agitação mecânica, e usavam algum método para retirar as bolas da câmara de mistura ( Patente US 4.786.056 ). Esse método dá resultados razoáveis ​​em alguns sentidos, mas os números aleatórios gerados por esse meio são caros. O método é inerentemente lento e inutilizável para a maioria dos aplicativos de computação.

Em 29 de abril de 1947, a RAND Corporation começou a gerar dígitos aleatórios com uma "roda de roleta eletrônica", consistindo em uma fonte de pulso de frequência aleatória de cerca de 100.000 pulsos por segundo com um pulso de frequência constante e alimentado em um contador binário de cinco bits . Douglas Aircraft construiu o equipamento, implementando a sugestão de Cecil Hasting (RAND P-113) para uma fonte de ruído (muito provavelmente o comportamento bem conhecido do tubo tiratron de gás em miniatura 6D4 , quando colocado em um campo magnético). Vinte dos 32 valores de contador possíveis foram mapeados nos 10 dígitos decimais e os outros 12 valores de contador foram descartados.

Os resultados de uma longa corrida da máquina RAND, filtrados e testados, foram convertidos em uma tabela, que foi publicada em 1955 no livro A Million Random Digits with 100,000 Normal Deviates . A mesa RAND foi um avanço significativo na entrega de números aleatórios porque uma mesa tão grande e cuidadosamente preparada nunca tinha estado disponível antes. Tem sido uma fonte útil para simulações, modelagem e para derivar as constantes arbitrárias em algoritmos criptográficos para demonstrar que as constantes não foram selecionadas maliciosamente. As cifras de bloco Khufu e Khafre estão entre os aplicativos que usam a tabela RAND. Veja: Nada na minha manga, números .

Fenômenos físicos com propriedades aleatórias

Propriedades aleatórias quânticas

Existem duas fontes fundamentais de aleatoriedade física da mecânica quântica prática : mecânica quântica no nível atômico ou subatômico e ruído térmico (alguns dos quais são de origem mecânica quântica). A mecânica quântica prevê que certos fenômenos físicos, como o decaimento nuclear dos átomos, são fundamentalmente aleatórios e não podem, em princípio, ser previstos (para uma discussão sobre a verificação empírica da imprevisibilidade quântica, consulte os experimentos de teste de Bell ). E, como o mundo existe a uma temperatura acima do zero absoluto , todo sistema tem alguma variação aleatória em seu estado; por exemplo, as moléculas de gases que compõem o ar estão constantemente ricocheteando umas nas outras de maneira aleatória ( veja a mecânica estatística ). Essa aleatoriedade também é um fenômeno quântico ( veja o fônon ).

Como o resultado dos eventos da mecânica quântica não pode ser previsto nem mesmo em princípio, eles são o " padrão ouro " para a geração de números aleatórios. Alguns fenômenos quânticos usados ​​para geração de números aleatórios incluem:

Propriedades aleatórias clássicas

Os fenômenos térmicos são mais fáceis de detectar. Eles são um tanto vulneráveis ​​a ataques, diminuindo a temperatura do sistema, embora a maioria dos sistemas pare de operar em temperaturas baixas o suficiente para reduzir o ruído por um fator de dois (por exemplo, ~ 150 K). Alguns dos fenômenos térmicos usados ​​incluem:

Na ausência de efeitos quânticos ou ruído térmico, outros fenômenos que tendem a ser aleatórios, embora de maneiras não facilmente caracterizadas pelas leis da física, podem ser usados. Quando várias dessas fontes são combinadas cuidadosamente (como, por exemplo, o algoritmo Yarrow ou Fortuna CSPRNGs ), entropia suficiente pode ser coletada para a criação de chaves criptográficas e nonces , embora geralmente em taxas restritas. A vantagem é que essa abordagem não precisa, em princípio, de nenhum hardware especial. A desvantagem é que um invasor com conhecimento suficiente pode modificar sub-repticiamente o software ou suas entradas, reduzindo assim a aleatoriedade da saída, talvez substancialmente. A principal fonte de aleatoriedade normalmente usada em tais abordagens é o tempo preciso das interrupções causadas por dispositivos mecânicos de entrada / saída, como teclados e unidades de disco , vários contadores de informações do sistema, etc.

Esta última abordagem deve ser implementada com cuidado e pode estar sujeita a ataques se não for. Por exemplo, a segurança direta do gerador no kernel do Linux 2.6.10 pode ser quebrada com 2 64 ou 2 96 complexidade de tempo.

Desvio do relógio

Outro fenômeno físico variável que é fácil de medir é o desvio do relógio. Existem várias maneiras de medir e usar a variação do relógio como fonte de aleatoriedade.

O chip Intel 82802 Firmware Hub (FWH) incluiu um hardware RNG usando dois osciladores de execução livre, um rápido e um lento. Uma fonte de ruído térmico (ruído de modo não comum de dois diodos) é usada para modular a frequência do oscilador lento, que então dispara uma medição do oscilador rápido. Essa saída é então desfeita usando uma etapa de decorrelação de tipo de von Neumann (veja abaixo). A taxa de saída deste dispositivo é um pouco menor que 100.000 bit / s. Este chip era um componente opcional da família de chipsets 840 que suportava um barramento Intel anterior. Não está incluído em PCs modernos.

Todos os microprocessadores VIA C3 incluem um hardware RNG no chip do processador desde 2003. Em vez de usar ruído térmico, bits brutos são gerados usando quatro osciladores de execução livre que são projetados para funcionar em taxas diferentes. A saída de dois é XORed para controlar a polarização em um terceiro oscilador, cuja saída sincroniza a saída do quarto oscilador para produzir o bit bruto. Pequenas variações na temperatura, nas características do silício e nas condições elétricas locais causam variações contínuas na velocidade do oscilador e, portanto, produzem a entropia dos bits brutos. Para garantir ainda mais a aleatoriedade, existem na verdade dois desses RNGs em cada chip, cada um posicionado em ambientes diferentes e girado no silício. A saída final é uma mistura desses dois geradores. A taxa de produção bruta é de dezenas a centenas de megabits por segundo, e a taxa branqueada é de alguns megabits por segundo. O software do usuário pode acessar o fluxo de bits aleatório gerado usando novas instruções de linguagem de máquina sem privilégios.

Uma implementação de software de uma ideia relacionada em hardware comum está incluída na CryptoLib, uma biblioteca de rotina criptográfica. O algoritmo é denominado verdadeiro . A maioria dos computadores modernos tem dois osciladores de cristal, um para o relógio em tempo real e outro para o relógio da CPU principal; verdadeiro e explora esse fato. Ele usa um serviço do sistema operacional que define um alarme, funcionando com base no relógio em tempo real. Uma sub-rotina define esse alarme para disparar em um tique do relógio (geralmente 1/60 de segundo). Outro então entra em um loop while esperando o alarme disparar. Como o alarme nem sempre dispara exatamente em um tique, os bits menos significativos de uma contagem de iterações de loop, entre a configuração do alarme e seu disparador, variam aleatoriamente, possivelmente o suficiente para alguns usos. Truerand não requer hardware adicional, mas em um sistema multitarefa, muito cuidado deve ser tomado para evitar interferência não aleatória de outros processos (por exemplo, na suspensão do processo de ciclo de contagem quando o programador do sistema operacional inicia e interrompe processos diversos )

O RDRANDopcode retornará valores de um gerador de números aleatórios de hardware integrado. Está presente nos processadores Intel Ivy Bridge e processadores AMD64 desde 2015.

Lidando com o preconceito

O fluxo de bits de tais sistemas tende a ser tendencioso, com predomínio de 1s ou 0s. Existem duas abordagens para lidar com o preconceito e outros artefatos. O primeiro é projetar o RNG para minimizar o viés inerente à operação do gerador. Um método para corrigir isso realimenta o fluxo de bits gerado, filtrado por um filtro passa-baixa, para ajustar a polarização do gerador. Pelo teorema do limite central , o ciclo de feedback tenderá a ser bem ajustado " quase o tempo todo ". Os geradores de números aleatórios de velocidade ultra-alta costumam usar esse método. Mesmo assim, os números gerados costumam ser um tanto tendenciosos.

Clareamento de software

Uma segunda abordagem para lidar com o preconceito é reduzi-lo após a geração (em software ou hardware). Existem várias técnicas para reduzir o viés e a correlação, geralmente chamados de algoritmos de " clareamento ", por analogia com o problema relacionado de produzir ruído branco a partir de um sinal correlacionado.

John von Neumann inventou um algoritmo simples para corrigir o viés simples e reduzir a correlação. Ele considera dois bits por vez (não sobrepostos), tomando uma das três ações: quando dois bits sucessivos são iguais, eles são descartados; uma sequência de 1,0 torna-se 1; e uma sequência de 0,1 torna-se zero. Portanto, representa uma borda descendente com 1 e uma borda ascendente com 0. Isso elimina a polarização simples e é fácil de implementar como um programa de computador ou em lógica digital. Essa técnica funciona independentemente de como os bits foram gerados. Não pode garantir aleatoriedade em sua saída, no entanto. O que ele pode fazer (com um número significativo de bits descartados) é transformar um fluxo de bits aleatório polarizado em um fluxo imparcial.

Outra técnica para melhorar um fluxo de bits quase aleatório é o fluxo de bits exclusivo ou com a saída de um gerador de números pseudo-aleatórios de alta qualidade criptograficamente seguro , como Blum Blum Shub ou uma cifra de fluxo forte . Isso pode melhorar a decorrelação e o viés digital a baixo custo; isso pode ser feito por hardware, como um FPGA, que é mais rápido do que por software.

Um método relacionado que reduz a polarização em um fluxo de bits quase aleatório é pegar dois ou mais fluxos de bits quase aleatórios não correlacionados e exclusivos ou juntos. Suponha que a probabilidade de um fluxo de bits produzir um 0 seja 1/2 +  e , onde −1/2 ≤  e  ≤ 1/2. Então e é a tendência do fluxo de bits. Se dois fluxos de bits não correlacionados com polarização e forem exclusivos ou unidos juntos, a polarização do resultado será 2 e 2 . Isso pode ser repetido com mais fluxos de bits (veja também o lema de empilhamento ).

Alguns projetos aplicam funções de hash criptográficas , como MD5 , SHA-1 ou RIPEMD-160 ou mesmo uma função CRC para todo ou parte do fluxo de bits e, em seguida, usam a saída como fluxo de bits aleatório. Isso é atraente, em parte porque é relativamente rápido.

Muitos fenômenos físicos podem ser usados ​​para gerar bits que são altamente polarizados, mas cada bit é independente dos outros. Um contador Geiger (com um tempo de amostra maior do que o tempo de recuperação do tubo) ou um detector de fótons de espelho semitransparente geram fluxos de bits que são principalmente "0" (silencioso ou transmissão) com o ocasional "1" (clique ou reflexão). Se cada bit for independente dos outros, a estratégia de Von Neumann gera um bit de saída imparcial aleatório para cada um dos raros bits "1" em um fluxo de bits altamente polarizado. Técnicas de branqueamento, como a Estratégia Avançada de Níveis Múltiplos (AMLS), podem extrair mais bits de saída - bits de saída que são tão aleatórios e imparciais - de um fluxo de bits altamente polarizado.

PRNG com chave aleatória atualizada periodicamente

Outros projetos usam o que se acredita serem verdadeiros bits aleatórios como a chave para um algoritmo de codificação de bloco de alta qualidade , tomando a saída criptografada como o fluxo de bits aleatório. No entanto, deve-se ter cuidado nesses casos para selecionar um modo de bloqueio apropriado . Em algumas implementações, o PRNG é executado por um número limitado de dígitos, enquanto o dispositivo gerador de hardware produz uma nova semente.

Usando eventos observados

Engenheiros de software sem verdadeiros geradores de números aleatórios freqüentemente tentam desenvolvê-los medindo eventos físicos disponíveis para o software. Um exemplo é medir o tempo entre as teclas do usuário e, em seguida, pegar o bit menos significativo (ou dois ou três) da contagem como um dígito aleatório. Uma abordagem semelhante mede o agendamento de tarefas, acessos de rede, tempos de busca de cabeçote de disco e outros eventos internos. Um projeto da Microsoft inclui uma lista muito longa de tais valores internos, uma forma de gerador de números pseudo-aleatórios criptograficamente seguro . Lâmpadas de lava também têm sido utilizadas como dispositivos físicos a serem monitorados, como no sistema Lavarand .

O método é arriscado quando usa eventos controlados por computador porque um invasor inteligente e mal-intencionado pode ser capaz de prever uma chave criptográfica controlando os eventos externos. Também é arriscado porque o suposto evento gerado pelo usuário (por exemplo, pressionamentos de tecla) pode ser falsificado por um invasor suficientemente engenhoso, permitindo o controle dos "valores aleatórios" usados ​​pela criptografia.

No entanto, com cuidado suficiente, um sistema pode ser projetado para produzir números aleatórios criptograficamente seguros a partir de fontes de aleatoriedade disponíveis em um computador moderno. O projeto básico é manter um "pool de entropia" de bits aleatórios que são considerados desconhecidos para um invasor. Uma nova aleatoriedade é adicionada sempre que disponível (por exemplo, quando o usuário pressiona uma tecla) e uma estimativa do número de bits no pool que não podem ser conhecidos por um invasor é mantida. Algumas das estratégias em uso incluem:

  • Quando bits aleatórios são solicitados, retorne aquele número de bits derivados do pool de entropia (por uma função hash criptográfica, digamos) e diminua a estimativa do número de bits aleatórios restantes no pool. Se não houver bits desconhecidos suficientes disponíveis, espere até que o suficiente esteja disponível. Este é o design de nível superior do dispositivo " / dev / random " no Linux, escrito por Theodore Ts'o e usado em muitos outros sistemas operacionais do tipo Unix. Ele fornece números aleatórios de alta qualidade, desde que as estimativas da aleatoriedade da entrada sejam suficientemente cautelosas. O dispositivo Linux "/ dev / urandom" é uma modificação simples que desconsidera as estimativas de aleatoriedade de entrada e, portanto, é menos provável que tenha alta entropia como resultado.
  • Mantenha uma cifra de fluxo com uma chave e um vetor de inicialização (IV) obtido de um pool de entropia. Quando bits suficientes de entropia forem coletados, substitua a chave e IV por novos valores aleatórios e diminua a entropia estimada restante no reservatório. Esta é a abordagem adotada pela biblioteca Yarrow . Ele oferece resistência contra alguns ataques e conserva a entropia difícil de obter.

Sistemas (des) centralizados

Um verdadeiro gerador de números aleatórios pode ser um serviço (des) central. Um exemplo de sistema centralizado onde um número aleatório pode ser adquirido é o serviço de farol de aleatoriedade do Instituto Nacional de Padrões e Tecnologia ; outro exemplo é o Random.org , um serviço que usa ruído atmosférico para gerar dígitos binários aleatórios (bits).

Como um exemplo de sistema descentralizado, a plataforma Cardano usa os participantes de seu protocolo de prova de aposta descentralizado para gerar números aleatórios.

Problemas

É muito fácil desconstruir dispositivos de hardware ou software que tentam gerar números aleatórios. Além disso, a maioria "quebra" silenciosamente, frequentemente produzindo números aleatórios decrescentes à medida que se degradam. Um exemplo físico pode ser a radioatividade decrescente rapidamente dos detectores de fumaça mencionados anteriormente, se esta fonte for usada diretamente. Os modos de falha em tais dispositivos são abundantes e complicados, lentos e difíceis de detectar. Métodos que combinam múltiplas fontes de entropia são mais robustos.

Como muitas fontes de entropia são frequentemente bastante frágeis e falham silenciosamente, os testes estatísticos em sua saída devem ser realizados continuamente. Muitos, mas não todos, esses dispositivos incluem alguns desses testes no software que lê o dispositivo.

Ataques

Assim como com outros componentes de um sistema de criptografia, um gerador de números aleatórios de software deve ser projetado para resistir a certos ataques . É difícil se defender contra esses ataques sem uma fonte de entropia de hardware.

Estimando entropia

Existem técnicas matemáticas para estimar a entropia de uma sequência de símbolos. Nenhum é tão confiável que suas estimativas possam ser totalmente confiáveis; sempre há suposições que podem ser muito difíceis de confirmar. Eles são úteis para determinar se há entropia suficiente em um pool de sementes, por exemplo, mas eles não podem, em geral, distinguir entre uma fonte aleatória verdadeira e um gerador pseudo-aleatório. Este problema é evitado pelo uso conservador de fontes de entropia de hardware.

Teste de performance

Os geradores de números aleatórios de hardware devem ser constantemente monitorados para operação adequada. RFC 4086, FIPS Pub 140-2 e NIST Special Publication 800-90b incluem testes que podem ser usados ​​para isso. Consulte também a documentação da biblioteca de software criptográfico cryptlib da Nova Zelândia .

Uma vez que muitos projetos práticos dependem de uma fonte de hardware como entrada, será útil pelo menos verificar se a fonte ainda está operando. Os testes estatísticos muitas vezes podem detectar a falha de uma fonte de ruído, como uma estação de rádio transmitindo em um canal considerado vazio, por exemplo. A saída do gerador de ruído deve ser amostrada para teste antes de ser passada por um "branqueador". Alguns designs de branqueadores podem passar em testes estatísticos sem entrada aleatória. Embora a detecção de um grande desvio da perfeição seja um sinal de que uma verdadeira fonte de ruído aleatório se degradou, pequenos desvios são normais e podem ser uma indicação de operação adequada. A correlação de polarização nas entradas para um projeto de gerador com outros parâmetros (por exemplo, temperatura interna, tensão de barramento) pode ser adicionalmente útil como uma verificação adicional. Infelizmente, com os testes atualmente disponíveis (e previstos), passar nesses testes não é suficiente para garantir que as sequências de saída sejam aleatórias. Um projeto cuidadosamente escolhido, verificação de que o dispositivo fabricado implementa esse projeto e segurança física contínua para garantir contra adulteração podem ser necessários, além de testes para usos de alto valor.

Veja também

Referências

Referências gerais

links externos