Você pode explicar a estimativa da entropia usada aleatoriamente.c

12

/dev/randomusa os tempos das 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. Ele 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 devido ao deslocamento de bits inicial antes do loop) do logaritmo base 2 do delta. Isso faz algum sentido intuitivo, embora 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 tirar o mínimo desse delta e o último? Não sei o que isso deve alcançar - talvez melhore a estimativa, talvez apenas mais conservador.

Edit: Encontrei um artigo que especifica a estimativa , mas não fornece um argumento fundamentado para ela (embora ele delineie algumas condições informais que o estimador deve atender).

Outros recursos que surgiram nos comentários:

Lucas
fonte
1
Observe que o valor da estimativa de entropia no Linux /dev/randomestá em uma base instável - consulte Feeding / dev / random entropy pool? . Liguei para Thomas na esperança de que ele respondesse sua pergunta.
Gilles 'SO- stop be evil'
Se alguém estiver interessado neste tópico, o tratamento sobre ele na Wikipedia é um bom ponto de partida: en.wikipedia.org/wiki//dev/random
slm
1
@ Lucas - dê uma olhada também neste artigo: [Uma interpretação do estimador de entropia do Linux] ( eprint.iacr.org/2012/487.pdf )
slm
@slm Interessante, embora não tenha certeza de que está correto - a etapa de justificar a função mínima usando a complexidade de Kolmogorov é um grande salto no raciocínio e não está claro para mim que isso soa conceitualmente.
Lucas
@Lucas - Pensei em passar adiante, estou fora da minha liga com este Q 8-)
slm

Respostas:

5

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

A idéia intuitiva por trás dessa estimativa é que as interrupções ocorrem em intervalos mais ou menos aleatórios, ditados por eventos imprevisíveis do mundo físico (por exemplo, pressionamentos de teclas ou chegada de pacotes de rede). Quanto maior o atraso, mais eventos imprevisíveis estão envolvidos. No entanto, 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 e, portanto delta2, serão zero).

Eu disse "intuitivo" e não há muito mais a dizer. De fato, no modelo "eventos físicos aleatórios", contar os bits está errado; se ocorrer um evento de hardware com probabilidade p para cada unidade de tempo e você receber um atraso expresso em n bits, a contribuição da entropia deve 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 delta2mecanismo 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 matematicamente exata e bem fundamentada, mas da fonte usual de segurança: ninguém parece ter encontrado uma maneira de abusar (ainda).


Esta página foi escrita por alguém que se cansou dos mitos sobre /dev/randome seu estimador de entropia, e acho que explica bem as coisas, com detalhes suficientes. É importante acertar algumas idéias básicas ao lidar com a RNG.

Thomas Pornin
fonte
Opa, eu errei, eu deveria ter dito mudança nos deltas. Eu tenho que dizer que a maioria das estimativas têm uma "bem-fundamentado, a justificação matematicamente exata", que é o que os diferencia de suposições - e se ele funciona em tudo isso deve ter alguma justificação formal. É totalmente bom não se importar com essas coisas e se preocupar apenas com a pragmática da segurança, mas isso não é verdade para todos. Não concordar com o que é interessante não é uma questão de "acertar as idéias básicas".
Lucas
Não estou dizendo que você está errado em ser uma estimativa prática para os fins a que foi projetada.
Lucas