☰

Можете ли вы объяснить оценку энтропии, используемую в random.c?

tag-icon • tag-icon linux kernel random
Можете ли вы объяснить оценку энтропии, используемую в random.c?

/dev/randomиспользует тайминги прерываний ядра для добавления в пул энтропии. Количество энтропии в пуле отслеживается в переменной с именем entropy_count.

Вот соответствующий фрагмент кода из random.c. Он представляет время (в мгновениях, я думаю) между двумя последними прерываниями в переменной deltaи разницей в дельтах как 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;

Похоже, что оценка добавленной энтропии по сути является полом (а не потолком из-за начального битового сдвига перед циклом) логарифма дельты по основанию 2. Это имеет некоторый интуитивный смысл, хотя я не уверен, какие предположения потребуются, чтобы сделать это формально правильным.

Итак, мой первый вопрос:«Каковы основания для этой оценки?»

Мой второй вопрос о delta = MIN(delta, delta2) .... Что это делает? Зачем брать минимум этой дельты и последней? Я не знаю, чего это должно достичь — возможно, это делает оценку лучше, может быть, просто более консервативной.

Редактировать:Я нашелдокумент, в котором указана оценка, но на самом деле он не дает обоснованного аргумента в пользу этого (хотя и описывает некоторые неформальные условия, которым должна соответствовать оценщица).

Другие ресурсы, упомянутые в комментариях:

решение1

delta2не предыдущий delta, аразницамежду двумя последовательными значениями delta. Это своего рода производная: если deltaизмеряет скорость, delta2то - ускорение.

Интуитивная идея, лежащая в основе этой оценки, заключается в том, что прерывания происходят с более или менее случайными интервалами, продиктованными непредсказуемыми событиями из физического мира (например, нажатиями клавиш или прибытием сетевых пакетов). Чем больше задержка, тем больше непредсказуемых событий происходит. Однако существуют физические системы, которые запускают прерывания с фиксированной частотой; мера delta2представляет собой защитный механизм, который обнаруживает такие события (если прерывания происходят с фиксированными интервалами, следовательно, определенно предсказуемы, все deltaбудут иметь одинаковое значение, следовательно, delta2будут равны нулю).

Я сказал "интуитивно", и больше нечего сказать. На самом деле, в модели "случайных физических событий" подсчет битов неверен; если аппаратное событие происходит с вероятностьюпдля каждой единицы времени, и вы получаете задержку, выраженную черезнбит, то вклад энтропии следует учитывать какн/2биты, ненбиты. Но мы знаем, что в реальности физические события не происходят в абсолютно случайные моменты; delta2механизм это допускает.

Итак, на практике «оценка энтропии» выглядит именно так:оцениватьЕго ценность с точки зрения безопасности исходит не из хорошо обоснованного, математически точного обоснования, а из обычного источника безопасности: никто, кажется, не нашел способа злоупотребить им (пока).

Эта страницабыл написан кем-то, кто устал от мифов о /dev/randomи его оценщике энтропии, и я думаю, что он хорошо объясняет вещи, с достаточным количеством деталей. Важно правильно понимать некоторые базовые идеи, когда имеешь дело с ГСЧ.

Связанный контент