NLSv2

NLSv2 — синхронный потоковый шифр, разработанный для секретного ключа, длина которого может достигать 128 бит

Шифр выводит ключевой поток в 32-битных блоках. Генератор потока ключей NLS состоит из нелинейного сдвига с обратной связью регистра (NFSR) и нелинейного фильтра (NLF) со счётчиком. Структура NLSv2 является точно такой же, как у NLS, за исключением периодически обновляемой Konst (зависящее от ключа слово инициализирующееся из секретного ключа при загрузке ключа).

NLSv2 — это программно-ориентированный шифр на основе простых 32-битных операций (таких как 32-битная XOR и сложение по модулю $2^{32}$). Следовательно, NLSv2 может использоваться во многих вычислительных средах: от смарт-карт до компьютеров. Исходный код для NLSv2 находится в свободном доступе и использование этого исходного кода или независимой реализации разрешено бесплатно для любых целей.

История: Семейство потоковых шифров SOBER

NLSv2 был разработан на основе SOBER, предложенном Роузом в 1998 году. Алгоритм SOBER основан на 8-битных операциях в отличие от 32-битных операций, используемых в NLSv2. SOBER был заменён SOBER-II, когда были обнаружены различные недостатки в оригинальном дизайне.

S16 был предложен как 16-битовое расширение SOBER-II: S16 копирует структуру SOBER-II и использует 16-битные операции. Тем не менее, были возможности для усиления SOBER-II и S16, которые нельзя было игнорировать. Поэтому SOBER-II и S16 были заменены. Эти замены называются т-классом шифров SOBER.

T-класс содержит три шифра на основе 8-битных, 16-битных и 32-битных операций. Шифры SOBER-t16 и SOBER-t32 были представлены в программе NESSIE; SOBER-t16 в качестве потокового шифра с 128-битным ключом и SOBER-t32 в качестве потокового шифра с 256-битным. SOBER-t16 и SOBER-t32 оказались одними из самых сильных потоковых шифров представленных в NESSIE. Тем не менее, оба шифра, как было установлено, не соответствуют строгим требованиям NESSIE. SOBER-128 был разработан как очень консервативный потоковый шифр, но с инновационной функциональностью целостности сообщений. Mundja был разработан для устранения недостатков целостности сообщений SOBER-128. NLS является улучшенной версией SOBER-128, которая включает в себя Mundja. Функциональность целостности сообщения не изменилась, а функциональность потокового шифра поменялась, поскольку она основана на регистре сдвига нелинейной обратной связи вместо LFSR. NLSv2 — это усовершенствованная версия NLS, в которой единственным изменением является периодическое обновление переменной Konst (в NLS Konst является зависимой от ключа переменной, которая остаётся постоянной в течение всего потока ключей поколения). Это изменение было мотивировано исследованиями, которые обнаружили отличительную атаку на NLS.

Модель использования

NLSv2 предлагает шифрование сообщений или защиту целостности сообщений или и то, и другое. NLSv2 также поддерживает модель использования, когда в приложениях желательно обеспечить целостность сообщения и конфиденциальность для всего или части сообщения. NLSv2 включает в себя средство для простой повторной синхронизации без установки отправителем и получателем новых секретных ключей с использованием одноразового номера (число, используемое только один раз). Это средство не всегда нужно использовать. Например, NLSv2 может использоваться для генерации одного потока ключей шифрования произвольной длины. В этом режиме можно было бы использовать NLSv2 в качестве замены широко используемого шифра RC4, например, в SSL / TLS. В этом режиме одноразовый номер не требуется.

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

NLSv2 предназначен для обеспечения безопасности при условии, что никакие одноразовые номера никогда не используются повторно с одним ключом, что не более $2^{80}$ слов обрабатываются одним ключом и что не более $2^{48}$ слов обрабатываются одним ключом / одноразовым номером. Не требуется, чтобы одноразовые номера были случайными - это позволяет использовать счётчик и значительно упрощает гарантирование уникальности.

Краткое описание

⊕, ⊗ — операции сложения и умножения в указанном поле Галуа;

+ сложение по модулю $2^{32}$.

^ является побитовым «и» 32-битных слов.

~ является побитовым дополнением 32-битного слова.

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

Преобразование между 4-байтовыми блоками и 32-битными словами выполняется в «little-endian» независимо от порядка следования байтов базовой машины.

Генератор потока NLSv2 построен из регистра сдвига нелинейной обратной связи (NLFSR) и нелинейного фильтра (NLF) при помощи счётчика. Примитив основан на 32-битных операциях и 32-битовых блоках: каждый 32-битный блок называется словом.

NLFSR

Вектор $\sigma _{t}=(r_{t}[0],...,r_{t}[16])$ слов известен как состояние регистра в момент времени t, а состояние $\sigma _{0}=(r_{0}[0],...,r_{0}[16])$ называется начальным состоянием. Состояние ключа и 32-разрядное зависящее от ключа слово, называемое Konst, инициализируются из секретного ключа путём загрузки ключа. Если используется одноразовый номер, то состояние ключа дополнительно возмущается процессом загрузки одноразового номера, чтобы сформировать начальное состояние, в противном случае состояние ключа используется непосредственно в качестве исходного состояния. Во время загрузки генератор потока выполняет новое вычисление Konst. После инициализации генератор потока создаёт 32-битные ключевые слова, обозначенные как $v_{j}$, которые объединяются для формирования.

NLFSR преобразует состояние $\sigma _{t}$ в состояние $\sigma _{t+1}$. Последовательные состояния $\sigma _{t}$ от NLFSR пропускаются через фильтр для получения 32-разрядных выходных слов, обозначенных как $out_{t}$. Каждое выходное слово $out_{t}$ получается с использованием NLF как

$out_{t}=NLF(\sigma _{t})=(r_{t}[0]+r_{t}[16])\oplus (r_{t}[1]+r_{t}[13])\oplus (r_{t}[6]+Konst)$

Когда t ≡ 0 (по модулю f16), тогда $out_{t}$ используется в качестве нового значения для Konst, и значение $out_{t}$ не выводится в качестве ключевого потока. В противном случае $out_{t}$ используется непосредственно в качестве ключевого потока. Отображение в ключевые слова потока {$v_{j}$} из выходных слов имеет вид $v_{j}=out_{j-(j\,div\,f16)}$, где (j div f16) обозначает целую часть (j ÷ f16).

NLFSR преобразует состояние $\sigma _{t}$ в состояние $\sigma _{t+1}$ следующим образом:

1. $r_{t+1}[i]=r_{t}[i+1]$, для i = 0..15

2. $r_{t+1}[16]=f((r_{t}[0]^{<<<19})+(r_{t}[15]^{<<<9})+Konst)\oplus r_{t}[4]$

3. $r_{t}[0]$ заброшен

4. если t ≡ 0 (по модулю f16), то применяются три специальных действия; $r_{t+1}[2]$модифицируется добавлением t (по модулю $2^{32}$); Konst изменяется на результирующее значение $out_{t+1}$; и вычисляется состояние $out_{t+2}$ как в шагах с 1 по 3.

f16 — постоянное целое число $2^{16}$ + 1 = 65537

Функция f определяется как f (ω) = S-box ($\omega _{(H)}$) ⊕ ω, где $\omega _{(H)}$ — это старшие 8 битов 32-битного слова ω. Основной S-блок состоит из двух независимых S-блоков меньшего размера:

S-блок Skipjack (с 8-битным входом и 8-битным выходом) и специально разработанный S-блок QUT (с 8-битным входом и 24-битным выходом). Выход основного S-блока в NLSv2 определяется как объединение выходов двух меньших S-блоков. Обратите внимание, что вход S-блока Skipjack (то есть$\omega _{(H)}$) заранее добавляется к выходу S-блока Skipjack для быстрой реализации. Поскольку выход основного S-блока снова добавляется в ω, исходный выход Skipjack S-box восстановлен.

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

NLF

Каждое выходное слово ключевого потока $v_{t}$ NLF генерируется согласно следующему уравнению

$v_{t}=NLF(\sigma _{t})=(r_{t}[0]\boxplus r_{t}[16])\oplus (r_{t}[1]\boxplus r_{t}[13])\oplus (r_{t}[6]\boxplus Konst)$

Обратите внимание, что при t = 0 по модулю f16 нет выходного слова.

Требования безопасности NLSv2

NLSv2 предназначен для обеспечения 128-битной безопасности. Базовая атака на NLSv2 — это исчерпывающий поиск ключа, который имеет вычислительную сложность, эквивалентную генерации $2^{128}$слов потока ключей. Во всех атаках предполагается, что злоумышленник наблюдает за определённым количеством потока ключей, созданного одним или несколькими секретными ключами, и злоумышленник, как предполагается, знает соответствующий открытый текст и одноразовые номера. Считается, что NLSv2 противостоит атаке, если для атаки требуется, чтобы владелец секретного ключа (ключей) сгенерировал более $2^{80}$ слов потока ключей, или вычислительная сложность атаки эквивалентна тому, что злоумышленник повторно проверяет шифр $2^{128}$ раз и генерирует по крайней мере 5 слов выходных данных каждый раз. Что касается функциональности потока ключей, утверждается, что NLSv2 удовлетворяет следующим требованиям безопасности при условии, что никакая пара ключ / одноразовый номер никогда не используется повторно, и с одним ключом обрабатывается не более $2^{80}$ слов:

1. NLSv2 должен противостоять атакам, которые либо определяют секретный ключ, либо определяют значения Konst и состояния шифра в любое указанное время

2. NLSv2 должен противостоять атакам, которые точно предсказывают неизвестные значения потока ключей без определения информации о состоянии NLFSR или секретного ключа.

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

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

Отдельный набор требований безопасности применяется к необязательности MAC. Сначала рассмотрим свойства безопасности, требуемые для функции MAC.

Функция MAC — это криптографический алгоритм, который генерирует тег TAG = $MAC_{K}(M)$ длины d из сообщения M произвольной длины и секретного ключа K длины n. Пара сообщение-тег (M, TAG) передаётся получателю (сообщение может быть зашифровано, полностью или частично, перед передачей).

Предположим, что полученная пара сообщение-тег (RM, RTAG). Получатель вычисляет ожидаемый тег XTAG = $MAC_{K}(RM)$. Если XTAG = RTAG, то получатель имеет некоторую уверенность в том, что пара сообщение-тег была сформирована стороной, которая знает ключ K. В некоторых случаях сообщение включает данные последовательности (например, одноразовый номер), чтобы предотвратить воспроизведение сообщения-тега.

Длина n ключа и длина d тега формируют параметры безопасности алгоритма MAC, поскольку эти значения определяют степень, в которой получатель может быть уверен в том, что пара сообщение-тег была сформирована стороной, которая знает ключ K. Функция MAC с параметрами безопасности (n, d) должна обеспечивать устойчивость к четырём классам атак:

1. При атаке столкновением злоумышленник находит любые два разных сообщения M, M ’, такие что $MAC_{K}(M)=MAC_{K}({\acute {M}})$. Функция MAC противостоит атаке столкновения, если сложность атаки составляет $O(2^{\min(n,d/2)})$ (Коллизионная атака)

2. Первая предварительная атака. В первой атаке перед изображением злоумышленнику указывается значение тега TAG, и злоумышленник должен найти сообщение M, для которого $MAC_{K}(M)=TAG$. Функция MAC противостоит первой атаке перед изображением, если сложность атаки составляет $O(2^{\min(n,d)})$

3. Вторая атака перед изображением. Во второй атаке перед изображением для ttacker указывается сообщение M, и злоумышленник генерирует новое сообщение M ’, такое, что $MAC_{K}(M)=MAC_{K}({\acute {M}})$. Функция MAC противостоит второй атаке перед изображением, если сложность атаки составляет$O(2^{\min(n,d)})$

4. Подделка MAC. При подделке MAC злоумышленник генерирует новую пару сообщение-тег (M ’, y’), такую что y ’= $MAC_{K}({\acute {M}})$. Функция MAC противостоит подделке MAC, если сложность атаки составляет $O(2^{\min(n,d)})$. Во всех этих атаках предполагается, что злоумышленник не знает о значении ключа K. Однако мы предполагаем, что (до атаки) злоумышленник может указать сообщения M (i), для которых они будут предоставлены с соответствующими тегами TAG (i) = $MAC_{K}(M(i))$. Mundja в NLSv2 предназначен для использования в качестве функции MAC с параметрами безопасности n = 128 и d ≤ 128. То есть мы утверждаем, что Mundja противостоит вышеуказанным атакам при использовании 128-битных ключей и выводе тегов длиной до 128 бит

NLSv2 будет считаться нарушенным, если злоумышленник может выполнить любую из этих атак. Атаки восстановления потока ключей кажутся маловероятными, поскольку выходная последовательность в значительной степени зависит от состояния регистра, поэтому любая вероятная атака восстановления потока ключей, вероятно, также позволит провести более сильную атаку восстановления ключа / состояния. Большинство атак концентрируется на первом варианте определения значений Konst и состояния. Атаки по связанным ключам менее важны, так как большинство систем безопасности гарантируют, что злоумышленники не смогут предсказать отношения между секретными ключами. Однако все ещё предпочтительно, чтобы NLSv2 сопротивлялся таким атакам.

Сильные стороны и преимущества NLSv2

• Скорость

• Требуется небольшой объём памяти.

• Гибкость в размерах процессора и реализации.

• Конструкция позволяет использовать секретный ключ и не секретный одноразовый номер.

• Включает функциональность MAC

Ссылки

• P. Hawkes and G. Rose. The t-class of SOBER stream ciphers. Technical report, QUALCOMM Australia, 1999 Архивная копия от 22 марта 2015 на Wayback Machine (англ.)
• NIST. SKIPJACK and KEA algorithm specifications May 1998 (англ.)
• ECRYPT NoE. eSTREAM — the ECRYPT stream cipher project Архивировано 16 мая 2012 года., 2005 (англ.)
• J. Y. Cho and J. Pieprzyk. Linear distinguishing attack on NLS. SASC 2006 workshop, 2006 Архивная копия от 22 января 2022 на Wayback Machine (англ.)