☰

Você pode explicar a estimativa de entropia usada em random.c

tag-icon • tag-icon linux kernel random
Você pode explicar a estimativa de entropia usada em random.c

/dev/randomusa os tempos de interrupções do kernel para adicionar ao pool de entropia. A quantidade de entropia no pool é rastreada em uma variável chamada entropy_count.

Aqui está o trecho de código relevante de random.c. Representa o tempo (em instantes, eu acho) entre as duas últimas interrupções na variável deltae as diferenças nos deltas como delta2.

delta = time - state->last_time;
state->last_time = time;

delta2 = delta - state->last_delta;
state->last_delta = delta;

if (delta < 0) delta = -delta;
if (delta2 < 0) delta2 = -delta2;
delta = MIN(delta, delta2) >> 1;
for (nbits = 0; delta; nbits++)
  delta >>= 1;

r->entropy_count += nbits;

/* Prevent overflow */
if (r->entropy_count > POOLBITS)
  r->entropy_count = POOLBITS;

Parece que a estimativa da entropia adicionada é essencialmente o piso (não o teto por causa do deslocamento de bits inicial antes do loop) do logaritmo de base 2 do delta. Isso faz algum sentido intuitivamente, embora eu não tenha certeza de quais suposições seriam necessárias para tornar isso formalmente correto.

Então, minha primeira pergunta é"qual é o raciocínio por trás dessa estimativa?"

Minha segunda pergunta é sobre delta = MIN(delta, delta2) .... O que isso faz? Por que pegar o mínimo desse delta e o último? Não sei o que isto pretende alcançar - talvez torne a estimativa melhor, talvez apenas mais conservadora.

Editar:Eu encontrei umpapel que especifica a estimativa, mas na verdade não fornece um argumento fundamentado (embora descreva algumas condições informais que o estimador deve atender).

Outros recursos que surgiram nos comentários:

Responder1

delta2não é o anterior delta, mas odiferençaentre dois valores sucessivos de delta. É uma espécie de derivada: se deltamede a velocidade, delta2é a aceleração.

A ideia intuitiva por trás dessa estimativa é que as interrupções ocorrem em intervalos mais ou menos aleatórios, ditadas por eventos imprevisíveis do mundo físico (por exemplo, teclas digitadas ou chegada de pacotes de rede). Quanto maior o atraso, mais eventos imprevisíveis estão envolvidos. Contudo, existem sistemas físicos que disparam interrupções a uma taxa fixa; a delta2medida é um mecanismo de proteção que detecta tais ocorrências (se as interrupções ocorrerem em intervalos fixos, portanto decididamente previsíveis, todas deltaterão o mesmo valor, portanto delta2serão zero).

Eu disse “intuitivo” e não há muito mais a dizer. Na verdade, no modelo de “eventos físicos aleatórios”, contar os bits é errado; se um evento de hardware ocorrer com probabilidadeppara cada unidade de tempo, e você obtém um atraso expresso emnbits, então a contribuição de entropia deve ser contabilizada comon/2pedaços, nãonpedaços. Mas sabemos que na realidade os acontecimentos físicos não ocorrem em momentos exactamente aleatórios; o delta2mecanismo admite isso.

Então, na prática, a “estimativa de entropia” é exatamente isso: umestimativa. O seu valor de segurança não provém de uma justificação bem fundamentada e matematicamente exacta, mas da fonte habitual de segurança: ninguém parece ter encontrado uma forma de abusar dela (ainda).

Esta páginafoi escrito por alguém que se cansou dos mitos sobre /dev/randomo seu estimador de entropia, e acho que explica bem as coisas, com bastante detalhes. É importante acertar algumas ideias básicas ao lidar com RNG.

informação relacionada