Рейтинг:3

Skipping first outputs of the stream cipher

флаг tf
Tom

I remember reading somewhere that sometimes in some stream ciphers it is necessary to skip the first values they produce. I can't find any information on this right now.

But it seems to make sense. Just as a hash function needs to do many rounds before it returns a random result, the CSPRNG needs some number of iterations so that seed and key information cannot be obtained from the first results.

How do you determine how many iterations this must be? Or are there other ways to solve this problem? For the results to be random from the first iterations it would be enough to have proper initialization with a random key and seed (which can also be treated as a key). But I don't think this solves the problem of first generator results. You can still read some key properties from those first results, exactly as if you didn't do enough rounds in the hash function.

PS My idea to test how many iterations we have to skip is to treat the CSPRNG as a hash function with a key and feed it by numbers $1,2,3,...$ as a seed with some keys, especially specially selected to make them appear weak (but also with random keys). Then see if such a hash function passes statistical tests, such as PractRand. This would be a minimum condition. It still does not preclude that there will be methods of sophisticated cryptographic attacks that will pick out bits of the key from the numbers looking for PractRand as random numbers.

Maarten Bodewes avatar
флаг in
Хороший поточный шифр не должен обладать такими свойствами. Старые/не очень хорошие потоковые шифры, такие как RC4, имеют отличительные свойства в своем выходном ключевом потоке. Некоторые из них указывают на проблему с выходными байтами в целом, но другие зависят от связи с внутренним состоянием алгоритма, и тогда они, конечно, зависят от алгоритма. Вот в чем проблема: во-первых, некоторые возможные проблемы могут быть не обнаружены с помощью «простого» анализа вывода. Для других атака полностью зависит от алгоритма. Так что количество итераций зависит.
Рейтинг:3
флаг cn

Помнится, я где-то читал, что иногда в некоторых потоковых шифрах необходимо пропускать первые значения, которые они выдают.

Не какие-то потоковые шифры, а один конкретный шифр: RC4. RC4 относится к более ранней эпохе, когда криптографические примитивы не подвергались тщательному изучению — фактически, изначально это был секретный алгоритм. После того, как дизайн RC4 был обнародован, был обнаружен ряд слабых мест. Основная слабость заключалась в том, что смещение в начале ключевого потока. RC4 был популярен в то время, когда была впервые обнаружена атака, основанная на этой предвзятости, и контрмерой было отбрасывание первых нескольких байтов. Со временем анализ смещения был улучшен, что сделало отбросы недостаточными, и RC4 постепенно терял популярность.

RC4 имеет очень простую структуру: каждый раунд состоит из простого скремблирования внутреннего состояния и выдает один байт вывода. Получается, что пока не набралось достаточно раундов, результат несколько предсказуем.

Большинство шифров выполняют несколько раундов скремблирования, прежде чем выдать какой-либо вывод. И общеупотребительные шифры были подтверждены годами исследований в криптографическом исследовательском сообществе.

Точно так же, как хеш-функция должна сделать много раундов, прежде чем она вернет случайный результат, CSPRNG требуется некоторое количество итераций, чтобы начальное число и ключевая информация не могли быть получены из первых результатов.

Да и нет. Это правда, что CSPRNG требует достаточного скремблирования из семени.Но это скремблирование встроено в основные составляющие алгоритма. Типичные современные CSPRNG основаны либо на хеше (в котором уже много раундов), либо на блочном или потоковом шифре (в котором уже много раундов).

Моя идея проверить, сколько итераций нам нужно пропустить, состоит в том, чтобы рассматривать CSPRNG как хеш-функцию с ключом и кормить ее числами 1,2,3,... как начальное число с некоторыми ключами.

Это действенный и популярный подход для ключевые производные функции - детерминированное генерирование псевдослучайного материала из начального числа. (Обратите внимание, что я говорю о получении ключа из материала с высокой энтропией, а не о получении ключа на основе пароля, также известном как растяжение ключа, которое имеет другие требования.) Примеры алгоритмов получения ключа, которые следуют этой парадигме: NIST SP 800-108 KDF в режиме счетчика и ХКДФ.

Однако в качестве генератора случайных чисел этому подходу чего-то не хватает — чего, кстати, не хватает и RC4 (что делает его плохим выбором для CSPRNG, несмотря на его популярность). Не хватает сопротивление возврату: свойство, согласно которому, если состояние скомпрометировано, это скомпрометирует будущие выходные данные RNG, но не прошлые выходные данные. Сопротивление обратному отслеживанию требует одностороннего преобразования состояния ГСЧ каждый раз, когда он выдает выходные данные. Любая конструкция, использующая постоянный секрет и общедоступную переменную для генерирования выходных данных, не обладает устойчивостью к возврату.

kelalaka avatar
флаг in
Вам нужна коррекция. Смотрите [здесь] (https://chat.stackexchange.com/transcript/message/61198977#61198977)
Gilles 'SO- stop being evil' avatar
флаг cn
@kelalaka Можете ли вы (ну, Squeamish Ossifrage), пожалуйста, расширить или предоставить ссылки? AFAIK ARC4 был опубликован в 1994 году, и о статистических аномалиях стало известно довольно быстро, но не в течение 24 часов, но атаки не появлялись до начала 2000-х годов (особенно https://www.mattblaze.org/papers/others/rc4_ksaproc.pdf). в 2001 г. — чей раздел «предыдущие атаки» цитирует документы 1997 и 1998 годов, которые 1. не привели к практической атаке и 2. появились после того, как RC4 стал популярным, например, он использовался в SSL).
kelalaka avatar
флаг in
[Боб Дженкинс, 15 сентября 1994 г., 18:51:50] (https://groups.google.com/g/sci.crypt/c/JsO3xEATGFA/m/-wO4ttv7BCYJ) рассказывает о предвзятости в отношении Sci.Crypt. .
Gilles 'SO- stop being evil' avatar
флаг cn
@kelalaka А, спасибо.Понятно, да, я писал о предвзятости, но имел в виду (практические) атаки, основанные на этой предвзятости, на которые ушло несколько лет.
Рейтинг:1
флаг sa

Большинство традиционных потоковых шифров имеют состояние $S=(s_1,\ldots,s_n)$ размера $n$ биты, функция обновления состояния $\фи:S\стрелка вправо S$, который инициализируется случайным материалом ключа, скажем $S_0=(k_1,\ldots,k_n)$ и итерация состояния $S_{t+1}=\фи(S_t),$ за $t=1,2,\ldots.$ Они также имеют функцию вывода $f:S\стрелка вправо\{0,1\}^\ell,$ который выводит $\ell$ биты сразу. Обычно мы можем иметь $\ell=1,$ или же $\ell=8.$

Таким образом, требуется определенное количество итераций, чтобы любые легко вычисляемые корреляции из ключевого материала рассеялись в наблюдаемой последовательности ключевого потока. $f(S_t),f(S_{t+1}),\ldots$ (при условии известного зашифрованного текста или известного открытого текста и аддитивного шифра, в котором открытый текст подвергается операции XOR с потоком ключей).

Традиционно отображение $\фи$ был в форме $$ \phi(s_1,\ldots,s_n)=(s_2,\ldots,s_n,s_{n+1}),\quad s_{n+1}=g(s_1,\ldots,s_n) $$

из соображений эффективности, как в сдвиговых регистрах. Таким образом, вам понадобится постоянное кратное $n$ итераций перед фактическим использованием ключевого потока.

Как и в комментариях, в современных потоковых шифрах ряд мер, таких как использование IV или Nonce, или использование различных режимов работы потоковых шифров, позволяет использовать ключевой поток сразу, ничего из него не выбрасывая. Например, если IV является случайным и независимым от ключа и имеет ту же длину в битах, что и состояние, и оно подвергается операции XOR в начальном состоянии (при этом будучи общедоступным), это имеет эффект отбеливания и делает ключевой поток независимым от ключа.

Tom avatar
флаг tf
Tom
Спасибо, этот ответ делает эту тему еще более понятной для меня.

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

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