Como um sistema operacional cria entropia para sementes aleatórias?

No Linux, os arquivos /dev/randome os/dev/urandom arquivos são as fontes de bloqueio e não bloqueio (respectivamente) de bytes pseudo-aleatórios.

Eles podem ser lidos como arquivos normais:

$ hexdump /dev/random
0000000 28eb d9e7 44bb 1ac9 d06f b943 f904 8ffa
0000010 5652 1f08 ccb8 9ee2 d85c 7c6b ddb2 bcbe
0000020 f841 bd90 9e7c 5be2 eecc e395 5971 ab7f
0000030 864f d402 74dd 1aa8 925d 8a80 de75 a0e3
0000040 cb64 4422 02f7 0c50 6174 f725 0653 2444
...

Muitas outras variantes unix fornecem /dev/randome /dev/urandomtambém, sem a distinção de bloqueio / não bloqueio.

O equivalente do Windows é a CryptGenRandom()função .

Como o sistema operacional gera pseudo-aleatoriedade?

O título e o corpo da sua pergunta fazem duas perguntas diferentes: como o sistema operacional cria entropia (isso realmente deve ser obtido entropia) e como gera pseudo-aleatoriedade a partir dessa entropia. Vou começar explicando a diferença.

De onde vem a aleatoriedade?

Os geradores de números aleatórios (RNG) vêm em dois tipos:

• Os geradores de números pseudo-aleatórios (PRNG), também chamados de geradores de bits aleatórios determinísticos (DRBG) ou combinações dos mesmos, são algoritmos determinísticos que mantêm um estado interno variável de tamanho fixo e calculam sua saída desse estado.
• O gerador de números aleatórios de hardware (HRNG), também chamado de gerador de números aleatórios "true", é baseado em fenômenos físicos. “Verdadeiro” é um pouco impróprio, porque não há fontes de informações conhecidas como verdadeiramente aleatórias , apenas fontes de informações que não são conhecidas por serem previsíveis.

Algumas aplicações, como simulações de fenômenos físicos, podem se contentar com números aleatórios que passam nos testes estatísticos. Outras aplicações, como a geração de chaves criptográficas, exigem uma propriedade mais forte: imprevisibilidade . A imprevisibilidade é uma propriedade de segurança, não (apenas) uma propriedade estatística: significa que um adversário não pode adivinhar a saída do gerador de números aleatórios. (Mais precisamente, você pode medir a qualidade do RNG medindo a probabilidade de um adversário adivinhar cada bit da saída RNG. Se a probabilidade for mensurável diferente de 1/2, o RNG será ruim.)

Existem fenômenos físicos que produzem dados aleatórios com boas propriedades estatísticas - por exemplo, decaimento radioativo ou algumas observações astronômicas de ruído de fundo ou flutuações do mercado de ações. Tais medidas físicas precisam de condicionamento ( clareamento ), para transformar distribuições de probabilidade enviesadas em uma distribuição de probabilidade uniforme. Uma medida física conhecida por todos não é boa para criptografia: as flutuações do mercado de ações podem ser boas para geohashing , mas você não pode usá-las para gerar chaves secretas .

A criptografia requer sigilo : um adversário não deve ser capaz de descobrir os dados que foram condicionados. Existem geradores de números pseudo-aleatórios criptograficamente seguros (CSPRNG): algoritmos PRNG cuja saída é adequada para uso em aplicações criptográficas, além de ter boas propriedades estatísticas . Uma das propriedades que tornam um CSPRNG criptograficamente seguro é que sua saída não permite que um adversário reconstrua o estado interno (conhecer todos os bits, exceto um produzido por um CSPRNG, não ajuda a encontrar o bit que falta). Não vou falar sobre como criar um CSPRNG, porque essa é a parte mais fácil - você pode seguir receitas dadas por criptografistas profissionais (use um padrãoalgoritmo, como Hash_DRBG, HMAC_DRBG ou CTR_DRBG do NIST SP 800-90A ) ou o ANSI X9.31 PRNG . O CSPRNG requer duas propriedades de seu estado para ser seguro:

• O estado deve ser mantido em segredo desde o início e em todos os momentos (embora a exposição do estado não revele resultados passados).
• O estado deve ser linear: o RNG nunca deve ser iniciado duas vezes a partir do mesmo estado.

Arquitetura de um gerador de números aleatórios

Na prática, quase todos os bons geradores de números aleatórios combinam um CSPRNG com uma ou mais fontes de entropia . Em outras palavras, a entropia é uma medida da imprevisibilidade de uma fonte de dados. Basear um gerador de números aleatórios puramente em um RNG de hardware é difícil:

• É provável que os dados físicos brutos precisem ser condicionados de qualquer maneira, para transformar os dados probabilísticos em uma distribuição uniforme.
• A saída da fonte da aleatoriedade deve ser mantida em segredo.
• As fontes de entropia geralmente são lentas em comparação com a demanda.

Assim, o RNG em um sistema operacional quase sempre funciona assim :

1. Acumule entropia suficiente para criar um estado interno imprevisível.
2. Execute um CSPRNG , usando a entropia acumulada como a semente, ou seja, como o valor inicial do estado interno.
3. Opcionalmente, misture periodicamente entropia adicional no estado interno. (Isso não é estritamente necessário, pois a entropia não é "consumida" a uma taxa mensurável . Ajuda contra certas ameaças que vazam no estado RNG sem comprometer todo o sistema.)

Um serviço de geração de números aleatórios faz parte do trabalho de um sistema operacional, porque a coleta de entropia requer acesso ao hardware, e as fontes de entropia constituem um recurso compartilhado: o sistema operacional deve montá-las e obter a saída delas para atender às aplicações. O condicionamento pseudo-aleatório das fontes de entropia é necessário no sistema operacional; também pode ser criptograficamente seguro, porque isso não é fundamentalmente mais difícil (e é necessário em sistemas operacionais em que os aplicativos não confiam um no outro; em sistemas totalmente cooperativos, cada aplicativo precisaria executar seu próprio CSPRNG internamente se o sistema operacional de qualquer maneira).

A maioria dos sistemas com armazenamento persistente carrega uma semente RNG do disco (usarei "disco" como uma abreviação para qualquer tipo de armazenamento persistente) quando eles inicializarem e sobrescreverão a semente com alguns dados pseudo-aleatórios frescos gerados a partir dessa semente, ou, se disponível, com dados aleatórios gerados a partir dessa semente mais outra fonte de entropia. Dessa forma, mesmo que a entropia não esteja disponível após uma reinicialização, a entropia de uma sessão anterior é reutilizada.

Alguns cuidados devem ser tomados sobre o estado salvo. Lembra como eu disse que o estado deve ser linear? Se você inicializar duas vezes no mesmo estado do disco, obterá as mesmas saídas RNG. Se isso for possível no seu ambiente, você precisará de outra fonte de entropia. Tome cuidado ao restaurar a partir de backups ou ao clonar uma máquina virtual . Uma técnica de clonagem é misturar a entropia armazenada com alguns dados ambientais previsíveis, mas únicos (por exemplo, horário e endereço MAC); tenha cuidado para que, se os dados ambientais forem previsíveis, qualquer pessoa que possua o estado de VM armazenado possa reconstruir a semente de uma instância de VM bifurcada.

Fontes de entropia

Encontrar (e usar corretamente) fontes de entropia é a parte mais desafiadora da geração de números aleatórios em um sistema operacional. As fontes de entropia disponíveis dependerão necessariamente do hardware e do ambiente em que o hardware é executado.

Se você tiver sorte, o seu hardware fornece um periférico que pode ser usado como uma fonte de entropia: um gerador de números aleatórios de hardware , dedicado ou com finalidade secundária. Por exemplo:

• ruído térmico
• ruído avalanche de um ruído avalanche
• vários tipos de (combinações de) osciladores , como osciladores de anel
• decaimento radioativo
• vários fenômenos quânticos que eu não conseguia explicar
• ruído acústico
• ruído da câmera

O NIST SP800-90B fornece diretrizes de design para RNG de hardware. Avaliar um hardware RNG é difícil . Normalmente, os RNG de hardware são bestas delicadas, que precisam ser usadas com cuidado: muitos tipos requerem algum tempo após a inicialização e algum tempo entre as leituras para desestabilizar, geralmente são sensíveis a condições ambientais como temperatura, etc.

Os processadores Intel x86-64 baseados na arquitetura Ivy Bridge fornecem as RdRandinstruções que fornecem a saída de um CSPRNG semeado por ruído térmico . A maioria dos processadores de smartphones inclui uma fonte de entropia de hardware, embora o Android nem sempre a use.

Os sistemas que não possuem uma fonte de entropia forte têm a ver com a combinação de fontes de entropia fracas e com a esperança ( garantindo uma palavra muito forte) de que serão suficientes. Os movimentos aleatórios do mouse são populares para as máquinas clientes, e você pode ter visto a segurança de certos programas de criptografia que solicitam que você mova o mouse (mesmo que em qualquer sistema operacional para PC do século XXI, o sistema operacional tenha acumulado entropia sem que o aplicativo precise se preocupar. )

Se você quiser ver um exemplo, pode ver o Linux, embora tenha cuidado para não ser perfeito . Em particular, /dev/randombloqueia com muita frequência (porque bloqueia até que entropia suficiente esteja disponível, com uma noção excessivamente conservadora de entropia), enquanto que /dev/urandomquase sempre é bom, exceto na primeira inicialização, mas não dá indicação quando não há entropia suficiente. O Linux possui drivers para muitos dispositivos HRNG e acumula entropia de vários dispositivos (incluindo dispositivos de entrada ) e tempos de disco .

Se você tiver armazenamento persistente (confidencial), poderá usá-lo para salvar a entropia de uma inicialização para a seguinte, conforme indicado acima. A primeira inicialização é um momento delicado: o sistema pode estar em um estado bastante previsível nesse ponto, especialmente em dispositivos produzidos em massa que essencialmente operam fora da fábrica da mesma maneira. Alguns dispositivos incorporados que possuem armazenamento persistente são provisionados com uma semente inicial na fábrica (produzida por um RNG em execução em um computador na fábrica). Em ambientes de servidor virtualizado, a entropia inicial pode ser provisionada ao instanciar uma máquina virtual do host ou de um servidor de entropia.

Dispositivos mal-propagados são um problema generalizado na prática - um estudo de chaves públicas RSA descobriu que muitos servidores e dispositivos tinham chaves que foram geradas com um RNG ruim, provavelmente um bom PRNG que foi insuficientemente semeado. Como projetista de SO, você não pode resolver esse problema por conta própria: é o trabalho da entidade que controla a cadeia de implantação garantir que o RNG seja propagado corretamente na primeira inicialização. Sua tarefa como projetista de sistema operacional é fornecer um RNG adequado, incluindo uma interface para fornecer a primeira semente e garantir a sinalização de erro adequada se o RNG for usado antes de ser propriamente propagado.

Além da resposta de Gilles, interrupções também podem ser usadas para estabelecer entropia. No Linux, por exemplo, ao adicionar um manipulador de interrupções, você pode definir se a ocorrência dessa interrupção deve ser usada como uma contribuição ao pool de entropia do kernel.

Obviamente, isso nunca deve ser o caso de interrupções que um invasor possa determinar. Por exemplo, à primeira vista, o tráfego de rede (ou seja, suas interrupções resultantes) parece ser uma boa fonte de aleatoriedade. No entanto, um invasor pode ser capaz de manipular seu tráfego de forma a prever a aleatoriedade necessária para alguma operação.