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

Question

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

Aqui está o snippet de código relevante de random.c . Ele representa o tempo (em termos que eu acho) entre as duas últimas interupções na variável delta e as diferenças em 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 ceil por causa do desvio inicial de bits antes do loop) do logaritmo de base 2 do delta. Isso faz algum sentido intuitivo, 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 levar o mínimo deste delta e o último? Eu não sei o que isso deve conseguir - talvez isso torne a estimativa melhor, talvez apenas mais conservadora.

Editar: encontrei um artigo que especifica a estimativa , mas ele não fornece um argumento fundamentado para isso (embora elabore algumas condições informais que o estimador deve cumprir).

Outros recursos que surgiram nos comentários:

• Wikipedia sobre /dev/random e /dev/urandom
• Um documento que tenta explicá-lo (sou cético sobre isso, ver comentários)
• Uma postagem no blog sobre /dev/random com comentários do cara que escreveu o código acima.
• Uma resposta secutity.SE sobre o pool de entropia /dev/random .

Answer 1

delta2 não é o delta anterior, mas a diferença entre dois valores sucessivos de delta . É um tipo de derivada: se delta mede 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, toques de tecla ou chegada de pacotes de rede). Quanto maior o atraso, mais imprevisíveis estarão envolvidos. No entanto, existem sistemas físicos que disparam interrupções a uma taxa fixa; a medida delta2 é um mecanismo de proteção que detecta tais ocorrências (se as interrupções ocorrem em intervalos fixos, portanto, decididamente previsíveis, todo delta terá o mesmo valor, portanto delta2 será zero).

Eu disse "intuitivo" e não há muito mais a dizer. De fato, no modelo "eventos físicos aleatórios", a contagem dos bits está errada; se ocorrer um evento de hardware com probabilidade p para cada unidade de tempo e você obtiver um atraso expresso sobre n bits, a contribuição de entropia deverá ser contabilizada como n / 2 bits, não n bits. Mas sabemos que, na realidade, os eventos físicos não ocorrem em momentos exatamente aleatórios; o mecanismo delta2 admite isso.

Então, na prática, a "estimativa de entropia" é exatamente isso: uma estimativa . Seu valor de segurança não vem de uma justificativa bem fundamentada, matematicamente exata, mas da fonte usual de segurança: ninguém parece ter encontrado uma maneira de abusar dela (ainda).

Esta página foi escrita por alguém que se cansou dos mitos sobre /dev/random e sua entropia estimador, e eu acho que explica bem as coisas, com detalhes suficientes. É importante ter algumas ideias básicas ao lidar com o RNG.