Рейтинг:4

Использование скремблера LFSR для выделения случайности полуслучайного источника

флаг us

Я использую сдвиговый регистр с линейной обратной связью (LFSR) в скремблер конфигурация как экстрактор случайности для слабослучайного источника. Этот источник является полуслучайным (он же. Источник Санта-Вазирани): биты коррелированные и предвзятые (с мин-энтропией ~0,5 на бит). Вот пример LFSR в конфигурации скремблера (это 12-битный, а я использую 32-битный регистр) с понижающей дискретизацией:

скремблер LFSR

Слабослучайный источник энтропии напрямую подает сигнал на скремблер LFSR, а на выходе сильно понижается дискретизация (один выходной бит берется, например, для каждых 1000 слабых бит). Этот метод был предложено здесь. Однако я не нашел примеров, когда скремблеры LFSR используются в качестве экстракторов случайности. Отсюда у меня следующие вопросы:

  1. Является ли использование скремблера для случайного извлечения полуслучайных данных допустимым? Чем он отличается от других экстракторов? Например, экстрактор фон Неймана подходит только для смещенного, независимого (не коррелированного) ввода и является линейным по времени.
  2. Как вычислить, сколько требуется субдискретизации/прореживания на выходе LSFR, чтобы результат был пригоден для криптографического использования (учитывая оценку входной минимальной энтропии)?
  3. Какие последствия имеет сразу весь регистр (например, вывод 32 бита каждые 32000 слабых входных данных), а не 1 бит на каждые 1000 входных данных?

контекст: LFSR используется в следующих TRNG:

TRNG

Paul Uszak avatar
флаг cn
Что вы примеряете?
DurandA avatar
флаг us
@PaulUszak XORed вывод нескольких кольцевых генераторов.
Fractalice avatar
флаг in
Не знаком с аппаратной частью, в чем слабость кольцевых генераторов? Зависимость последовательных выборок или отклонение от 50%?
DurandA avatar
флаг us
@Fractalice Выборочный сигнал от осцилляторов имеет как сильную периодичность, так и характеристики смещения. Вы можете увидеть оба в [этих шумовых изображениях](https://docs.google.com/document/d/1srb3rwd-MhxEhMsq1V8GMYIejlq99ZZWdcyAHJvAths/edit?usp=sharing), которые я создал. На изображении 4x3 этапа мы можем различить некоторые узоры линий, что является прямым следствием периодичности/отсутствия джиттера. По сравнению с истинными случайными данными осцилляторы производят больше белых пикселей, что означает смещение в сторону 1.
Paul Uszak avatar
флаг cn
@DurandA Вы не можете этого сделать. Глаз не может различить автокорреляцию (R) $R \leqslant 10^{-3}$ и $R > 10^{-3}$. Это общепринятые пределы корреляции.
DurandA avatar
флаг us
@PaulUszak Я думаю, что эти шумовые изображения могут помочь развить интуицию, когда закономерность очень очевидна. Конечно, обратное неверно, и это нельзя использовать ни для какой оценки энтропии.
b degnan avatar
флаг ca
@DurandA, поскольку вы можете доказать, что джиттер в кольцевом генераторе является функцией двустороннего дробового шума канала (не Джонсона) для каждого переключателя. Вам нужен только один RO со значительно более медленным семплом (в пределах допустимого уровня шума). В кремнии это нормально, и если вы выполняете моделирование методом Монте-Карло, вы можете увидеть такое поведение, но вы всегда можете его измерить.
Рейтинг:0
флаг cn

ТРНГ: нет.

  1. Скремблирование ~ перестановка. Это не безопасность, это обфускация.

  2. Это суть вашего вопроса, и он полностью субъективен. Большинство здесь знают, что я ярый сторонник одноразовых блокнотов, но. Поделитесь своими данными о вашем TNRG. 50 МГц? Нет. Никакой коммерческий TRNG не делает этого, поскольку вы столкнетесь с автокорреляцией. Делиться...

  3. Не имеющий отношения :-).


Мы можем работать над этим, но $H_{\infty}$ сильно сократится.

DurandA avatar
флаг us
Я обновлю вопрос с дизайном TRNG (в основном [это] (https://crypto.stackexchange.com/q/89709/39499), но с 32-битным LFSR в конфигурации скремблера).Однако мне не понятна ваша негативная реакция по поводу частоты дискретизации 50 МГц от источника слабой энтропии. Как эта частота связана с безопасностью системы, если экстрактор случайности собирает достаточно энтропии?
Paul Uszak avatar
флаг cn
Отрицательная реакция: опыт. Кольцевые осиллоторы известны своей стабильностью. Я видел скорость прореживания 1024. Единственная причина, по которой мы их делаем, заключается в том, что это легко для кремния.
DurandA avatar
флаг us
«Это не безопасность, это обфускация»: безопасность системы не зависит от знания конфигурации LFSR. Как показал @fgrieu [здесь] (https://crypto.stackexchange.com/a/89712/39499), добавление еще одного LFSR в конфигурацию дескремблера покажет первоначальный ввод — чье смещение можно использовать для прогнозирования будущего вывода. Вместо этого система полагается на прореживание на выходе LFSR для извлечения случайности.Учитывая, что вы знаете полный дизайн системы и последние сгенерированные значения, есть ли у вас шанс предсказать будущие значения больше, чем случайный?
Paul Uszak avatar
флаг cn
@DurandA Безопасность TRNG не зависит от «скрытого» дизайна. Это происходит из-за какого-то внутреннего физического свойства, которое вы используете. Дрожание/задержка распространения кольцевого генератора могут быть описаны статистически только на макроуровне. Если нет смещения (равномерное распределение, а не гауссовское), вы будете в безопасности.
Paul Uszak avatar
флаг cn
Вы измеряли энтропию на тик в Sampler? Это решающее измерение.
DurandA avatar
флаг us
«_Это происходит из-за некоторого внутреннего физического свойства, которое вы используете._» Поскольку кольцевой осциллятор является слабо случайным, требуется «извлечь» энтропию с помощью экстрактора случайности, который даст гораздо меньший результат. В моем случае я накапливаю 1000 слабо случайных битов от кольцевых генераторов, чтобы получить 1 бит. Вопрос в том, подходит ли LFSR для этой задачи и как он сравнивается, например, с безопасная хэш-функция.
DurandA avatar
флаг us
Да, минимальная энтропия составляет ~0,54/бит (отредактировано) согласно ea_non_iid из SP800-90B. Я знаю, что есть [некоторые противоречия] (https://crypto.stackexchange.com/questions/83882/whats-wrong-with-nist-sp-800-90b) по поводу этого теста, но я не знаю лучшего метода для оцените минимальную энтропию без дорогого осциллографа, чтобы охарактеризовать джиттер.
DurandA avatar
флаг us
Я четко понимаю, как можно использовать дизайн `[предвзятый независимый источник] -> [LFSR]`. Как насчет `[смещенный коррелированный источник] -> [LFSR] -(в основном однородно коррелированный)-> [дециматор]`, как было предложено?

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.