Рейтинг:1

Какие существуют инструменты для обратного проектирования LFSR помимо BMA?

флаг cn

У меня есть определенный тайм-код, который я не могу понять. Мы привели успешно декодированные другие коды для той же цели с помощью алгоритма Берлекэмпа-Масси, но этот код, похоже, имеет линейную сложность 110, что никоим образом непрактично. Его также нельзя восстановить с помощью 110-битного неприводимого полинома, который находит BMA. Только первые несколько битов соответствуют ожиданиям, а затем кажется, что биты перевернуты, то есть они обратны ожидаемым битам.

Я новичок в криптографии и понятия не имею, как действовать дальше. Существуют ли другие алгоритмы для анализа LFSR (или подобных псевдослучайных последовательностей)? Или кто-нибудь знает, при каких условиях BMA обнаруживает такой чрезвычайно длинный полином?

kodlu avatar
флаг sa
если он имеет линейную сложность 110, через BMA должно хватить только 220 бит (если это не ошибка). Я предполагаю, что это двоичная последовательность, вы этого не указали.
neolith avatar
флаг cn
Да, это двоичная последовательность или GF(2), как говорят математики. Ну, на самом деле мы не знаем, но я проанализировал последовательность в соответствии с этим предположением, потому что другие последовательности, которые мы успешно расшифровали, также были двоичными.
Рейтинг:2
флаг us

Не совсем понятно, что такое "определенный временной код", но я буду понимать его как последовательность конечной длины. $s_0, s_1, \ldots, s_{N-1}$ из $N$ биты. Сама последовательность может быть или не быть сгенерирована LFSR — мы не знаем — но мы хотели бы найти (Fibonacci) LFSR, который генерирует последовательность.

Давайте немного подготовим сцену. LFSR Фибоначчи длины $n$ представляет собой массив $n$ биты с начальным значением $$(s_0, \quad s_1,\quad \ldots, \quad s_{n-2}, \quad s_{n-1})$$ и последовательные значения $$(s_0, \quad s_1, \quad \ldots, \quad s_{n-2}, \quad s_{n-1})\ \Кнопка "Стрелка вниз\ (s_1, \quad s_2, \quad \ldots, \quad s_{n-1}, \quad s_n)\ \Кнопка "Стрелка вниз\ (s_2, \quad s_3, \quad \ldots, \quad s_n, \quad \quad s_{n+1})\ \Кнопка "Стрелка вниз\ \cdots\quad \cdots$$ где содержимое массива сдвигается влево на каждом шаге (тактовый цикл) так что биты падают с левого конца (LFSR вывод) — заданная последовательность, а биты показаны как въезд в ЛФСР справа находятся вычисляется как линейная комбинация (также известная как сумма исключающего ИЛИ) некоторый ЛССР содержимое на предыдущем шаге. В частности, для $i\geq 0$, в переход состояния можно выразить как $$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+n-2}, \quad s_{i+n-1}\biggr)\ \Кнопка "Стрелка вниз\ \biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+n-1}, \quad {\Large{\oplus}}_{j=0}^ {n-1}c_{n-j} s_{i+j}\biggr),$$ где $c_i$имеют значение $0$ или же $1$, таким образом линейный комбинация $c_ns_i\oplus c_{n-1}s_{i+1} \oplus \cdots \oplus c_1s_{i+n-1}$ предыдущего Содержимое LFSR вернули в правый конец LFSR как $s_{n+i}$ на самом деле является суммой исключающего ИЛИ нескольких выбранных битов предыдущего содержимого (тех, для которых соответствующие $c_i$ иметь значение $1$). Отсюда и название сдвигового регистра с линейной обратной связью, который инициализируется в LFSR.

Имея в виду приведенное выше описание, один ответ на вопрос о LFSR тривиален в одном смысле: $N$ ступень LFSR с коэффициентами обратной связи $(c_N,c_{N-1}, \cdots, c_1) = (1,0,0,\cdots, 0)$ и начальная загрузка $\big(s_0, s_1, \ldots, s_{N-1}\big)$ будет производить бесконечные повторения $$s_0, s_1, \ldots, s_{N-1},s_0, s_1, \ldots, s_{N-1}, s_0, s_1, \ldots, s_{N-1}, \cdots$$ заданного временного кода $s_0, s_1, \ldots, s_{N-1}$ на всю вечность. Альтернативно, Любые другой выбор $(c_N,c_{N-1}, \cdots, c_1)$ заполнит сдвиговый регистр чем-то другим, но первым $N$ биты все равно будут $s_0, s_1, \ldots, s_{N-1}$ и то, что последует за этим, будет другим. Это явно не то, что нам нужно, и поэтому мы ищем лучший критерий: находим самый короткий LFSR (и его начальная загрузка), который будет генерировать $s_0, s_1, \ldots, s_{N-1}$, и это именно то, что находит алгоритм Берлекэмпа-Месси.

Алгоритм Берлекэмпа-Месси представляет собой итеративный процесс, состоящий из поиска кратчайшего LFSR, который генерирует первый $t$ биты $s_0, s_1, \ldots s_{t-1}$ и проверка, если LFSR находит $s_t$ правильно. Если так, $s_{t+1}$ проверено, а если нет, то $c_i$обновлены так, что пересмотренный LFSR генерирует $s_t$. Часто, но не всегда длина LFSR увеличивается. Итеративный процесс продолжается до последнего доступного бита. $s_{N-1}$ была обработана, так что, когда алгоритм Берлекэмпа-Масси завершает работу, синтезированный LFSR создает всю последовательность $s_0, s_1, \ldots, s_{N-1}$ на его выходе. Если синтезированный LFSR имеет $n\leq N$ стадий, то его первоначальная загрузка $\big(s_0, s_1, \ldots, s_{n-1}\big)$ (которые первые $n$ выходных битов), и LFSR правильно вычисляет $s_n, s_{n+1}, \cdots, s_{N-1}$ (то есть остальная часть данной последовательности). Длина LFSR, синтезированного алгоритмом Берлекэмпа-Месси, гарантированно равна минимальный: нет LFSR, который генерирует $s_0, s_1, \ldots, s_{N-1}$ может иметь короче длина. Однако, есть нет утверждают, что $n$ гарантированно меньше, чем $N$; вполне может оказаться, что тривиальные решения, описанные выше, являются минимальными решениями. Действительно, я утверждаю, что это действительно так для наиболее последовательности; LFSR имеет длину $N$. Колмогоровская теория сложности говорит, что самая короткая программа для вывода большинства строк длины $N$ имеет длину $N+c$, или, в просторечии, для большинства строк можно сделать немногим лучше, чем просто сохранить строку и распечатать ее; "$с$" - это просто длина команды "Распечатать следующую строку". В контексте сдвиговых регистров для большинства последовательностей длины $N$, кратчайший регистр сдвига, выход которого представляет собой заданную последовательность длины $N$ это просто сдвиговый регистр длины $N$ инициализируется заданной последовательностью. Какая обратная связь (если она вообще есть) не имеет значения.

  • Если последовательность действительно была создана $n$-стадия LFSR, как описано выше, где $n \leq \frac N2$, затем Берлекамп-Месси алгоритм находит все $n$ коэффициенты $c_i$ после изучение $s_0, s_1, \ldots, s_{2n-1}$. Начальная загрузка синтезированного LFSR, конечно же, всего лишь $\big(s_0, s_1, \ldots, s_{n-1}\big)$. Из этого далее алгоритм Берлекампа-Месси может продолжайте проверять остальную часть последовательности (если это так желательно), но не требует обновления $c_i$х потому что каждая проверка следующего символа просто сообщает назад, что все в порядке; текущий LFSR также генерирует следующий бит. Однако, в общем, у криптоаналитика есть нет представление о том, был ли временной код вообще сгенерирован LFSR; это просто последовательность $N$ биты неизвестного происхождения, поэтому для целей криптоаналитика все $N$ биты должны быть проверены, чтобы найти самый короткий LFSR, который может генерировать $s_0, s_1, \ldots, s_{N-1}$. Если дополнительные биты $s_N, s_{N+1}, \ldots$ доступны, то нет гарантии, что LFSR обнаружит после проверки $N$ биты также будут генерировать эти дополнительные биты. На самом деле, вся идея алгоритма Берлекэмпа-Месси заключается в том, что если тест «Генерирует ли текущий LFSR также $s_n$?" не удается, алгоритм синтезирует модифицированный LFSR из текущего LFSR, так что модифицированный LFSR генерирует $s_0, s_1, \ldots, s_{n-1},s_n$. В этом процессе длина LFSR может (а может и нет) увеличиться.
  • Если последовательность действительно была создана $n$-стадия LFSR, как описано выше, где $\frac N2 < n \leq N$, то алгоритм Берлекэмпа-Месси находит кратчайший LFSR, который генерирует $s_0, s_1, \ldots, s_{N-1}$. Он может генерировать, а может и не генерировать одинаковые значения для $s_N, s_{N+1}, \cdots, s_{2n-1}$ как это делает настоящий LFSR.

Имея в виду вышеупомянутую длинную обличительную речь, давайте ответим на вопросы ОП. В заголовке ОП спрашивает

Какие инструменты доступны для обратного проектирования LFSR помимо BMA?

Ну, расширенный алгоритм Евклида для многочленов можно использовать наибольшие общие делители, но в некотором смысле это эквивалентно алгоритму Берлекэмпа-Месси; это можно рассматривать как обработку последовательности в обратном порядке $s_{N-1}, s_{N-2}, \cdots, s_1, s_0$ по сравнению с заказом $s_0, s_1, \cdots, s_{N-2}, s_{N-1}$ используется алгоритмом Берлекампа-Месси.

В теле вопроса ОП жалуется

этот код, кажется, имеет линейную сложность 110, что никоим образом не практично.Его также нельзя восстановить с помощью 110-битного неприводимого полинома, который находит BMA. Как и ожидалось, только первые несколько битов, а затем биты, кажется, переворачиваются.

Вполне вероятно, что эта проблема связана с ошибками в реализации BMA. «Ни в коем случае не практично» предполагает, что, возможно, было выделено недостаточно памяти для хранения различных полиномов, используемых внутри BMA, или что буферы переполнились и т. д. Как указывает @kodlu, если временной код имеет длину $220$ биты, затем проверяя все $220$ битов может привести к LFSR длины $110$. В противном случае, как обсуждалось выше, если временной код имеет длину $110$ или более (возможно $128$ биты $= 16$ байт?), BMA вполне может синтезировать LFSR длины $110$. Наконец, у меня нет другого объяснения, кроме ошибки программиста, для наблюдения ОП о том, что в синтезированном выводе LFSR «первые несколько битов» верны, а остальные перевернуты.

Кто-нибудь знает, при каких условиях BMA обнаруживает такой чрезвычайно длинный полином?

См. материал над пунктирной линией в этом ответе.

neolith avatar
флаг cn
Прежде всего, спасибо за этот обширный ответ. У меня есть несколько вопросов. «Часто, но не всегда длина LFSR увеличивается». Я смотрел подробный пример BMA в статье. Я помню, что иногда добавленные биты в регистр снова отбрасываются. Могут ли 110 бит также уменьшиться, учитывая, что имеется достаточно безошибочных битов последовательности, подаваемой в BMA? В противном случае, в случае нехватки памяти, это означало бы, что линейная сложность может только увеличиться, что все еще нецелесообразно.
neolith avatar
флаг cn
Профессор моего универа предположил, что он может быть сжимающим генератором, и предложил атаку в статье Голича. Я еще не уверен, стоит ли идти по этому пути. Думаю сначала проверим алгоритм на ошибки. Это из 32-битной эпохи, и это действительно может быть так. Следующим шагом будет реализация алгоритма в NumPy, где все ошибки памяти невозможны. Если все это терпит неудачу, может ли быть так, что BMA ложно обнаруживает неприводимый полином, или это невозможно, учитывая, что реализация правильная?
Рейтинг:0
флаг ng

Все LFSR могут быть реконструированы с правильным, достаточно длинным примером вывода и правильной реализацией Berlekamp-Massey.

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

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

neolith avatar
флаг cn
Да, к этому выводу мы тоже пришли. Если код зашифрован — что нецелесообразно с точки зрения производительности, но у разработчика были бы веские причины для этого — невозможно найти производящий полином или LFSR без огромного количества работы и опыта. В этом случае я бы сдался, но пока не готов к этому.

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

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