NLSv2
NLSv2 — синхронный потоковый шифр, разработанный для секретного ключа, длина которого может достигать 128 бит
Шифр выводит ключевой поток в 32-битных блоках. Генератор потока ключей NLS состоит из нелинейного сдвига с обратной связью регистра (NFSR) и нелинейного фильтра (NLF) со счётчиком. Структура NLSv2 является точно такой же, как у NLS, за исключением периодически обновляемой Konst (зависящее от ключа слово инициализирующееся из секретного ключа при загрузке ключа).
NLSv2 — это программно-ориентированный шифр на основе простых 32-битных операций (таких как 32-битная XOR и сложение по модулю 2 32 {displaystyle 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 {displaystyle 2^{80}} слов обрабатываются одним ключом и что не более 2 48 {displaystyle 2^{48}} слов обрабатываются одним ключом / одноразовым номером. Не требуется, чтобы одноразовые номера были случайными - это позволяет использовать счётчик и значительно упрощает гарантирование уникальности.
Краткое описание
⊕, ⊗ — операции сложения и умножения в указанном поле Галуа;
+ сложение по модулю 2 32 {displaystyle 2^{32}} .
^ является побитовым «и» 32-битных слов.
~ является побитовым дополнением 32-битного слова.
NLSv2 полностью основан на внутренних операциях 32-разрядных слов, но внешний интерфейс указан в условиях массивов байтов.
Преобразование между 4-байтовыми блоками и 32-битными словами выполняется в «little-endian» независимо от порядка следования байтов базовой машины.
Генератор потока NLSv2 построен из регистра сдвига нелинейной обратной связи (NLFSR) и нелинейного фильтра (NLF) при помощи счётчика. Примитив основан на 32-битных операциях и 32-битовых блоках: каждый 32-битный блок называется словом.
NLFSR
Вектор σ t = ( r t [ 0 ] , . . . , r t [ 16 ] ) {displaystyle sigma _{t}=(r_{t}[0],...,r_{t}[16])} слов известен как состояние регистра в момент времени t, а состояние σ 0 = ( r 0 [ 0 ] , . . . , r 0 [ 16 ] ) {displaystyle sigma _{0}=(r_{0}[0],...,r_{0}[16])} называется начальным состоянием. Состояние ключа и 32-разрядное зависящее от ключа слово, называемое Konst, инициализируются из секретного ключа путём загрузки ключа. Если используется одноразовый номер, то состояние ключа дополнительно возмущается процессом загрузки одноразового номера, чтобы сформировать начальное состояние, в противном случае состояние ключа используется непосредственно в качестве исходного состояния. Во время загрузки генератор потока выполняет новое вычисление Konst. После инициализации генератор потока создаёт 32-битные ключевые слова, обозначенные как v j {displaystyle v_{j}} , которые объединяются для формирования.
NLFSR преобразует состояние σ t {displaystyle sigma _{t}} в состояние σ t + 1 {displaystyle sigma _{t+1}} . Последовательные состояния σ t {displaystyle sigma _{t}} от NLFSR пропускаются через фильтр для получения 32-разрядных выходных слов, обозначенных как o u t t {displaystyle out_{t}} . Каждое выходное слово o u t t {displaystyle out_{t}} получается с использованием NLF как
o u t t = N L F ( σ t ) = ( r t [ 0 ] + r t [ 16 ] ) ⊕ ( r t [ 1 ] + r t [ 13 ] ) ⊕ ( r t [ 6 ] + K o n s t ) {displaystyle 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), тогда o u t t {displaystyle out_{t}} используется в качестве нового значения для Konst, и значение o u t t {displaystyle out_{t}} не выводится в качестве ключевого потока. В противном случае o u t t {displaystyle out_{t}} используется непосредственно в качестве ключевого потока. Отображение в ключевые слова потока { v j {displaystyle v_{j}} } из выходных слов имеет вид v j = o u t j − ( j d i v f 16 ) {displaystyle v_{j}=out_{j-(j,div,f16)}} , где (j div f16) обозначает целую часть (j ÷ f16).
NLFSR преобразует состояние σ t {displaystyle sigma _{t}} в состояние σ t + 1 {displaystyle sigma _{t+1}} следующим образом:
1. r t + 1 [ i ] = r t [ i + 1 ] {displaystyle 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 ) + K o n s t ) ⊕ r t [ 4 ] {displaystyle r_{t+1}[16]=f((r_{t}[0]^{<<<19})+(r_{t}[15]^{<<<9})+Konst)oplus r_{t}[4]}
3. r t [ 0 ] {displaystyle r_{t}[0]} заброшен
4. если t ≡ 0 (по модулю f16), то применяются три специальных действия; r t + 1 [ 2 ] {displaystyle r_{t+1}[2]} модифицируется добавлением t (по модулю 2 32 {displaystyle 2^{32}} ); Konst изменяется на результирующее значение o u t t + 1 {displaystyle out_{t+1}} ; и вычисляется состояние o u t t + 2 {displaystyle out_{t+2}} как в шагах с 1 по 3.
f16 — постоянное целое число 2 16 {displaystyle 2^{16}} + 1 = 65537
Функция f определяется как f (ω) = S-box ( ω ( H ) {displaystyle omega _{(H)}} ) ⊕ ω, где ω ( H ) {displaystyle omega _{(H)}} — это старшие 8 битов 32-битного слова ω. Основной S-блок состоит из двух независимых S-блоков меньшего размера:
S-блок Skipjack (с 8-битным входом и 8-битным выходом) и специально разработанный S-блок QUT (с 8-битным входом и 24-битным выходом). Выход основного S-блока в NLSv2 определяется как объединение выходов двух меньших S-блоков. Обратите внимание, что вход S-блока Skipjack (то есть ω ( H ) {displaystyle omega _{(H)}} ) заранее добавляется к выходу S-блока Skipjack для быстрой реализации. Поскольку выход основного S-блока снова добавляется в ω, исходный выход Skipjack S-box восстановлен.
NLSv2 допускает шифрование любой части открытого текста при формировании сообщения передачи. Когда отправитель формирует сообщение передачи, биты, которые содержат зашифрованный открытый текст, формируются путём XOR соответствующих битов открытого текста с соответствующими битами потока ключей. Точно так же, когда получатель извлекает открытый текст из сообщения передачи, биты, которые содержат зашифрованный открытый текст, дешифруются в открытый текст посредством XOR соответствующих битов сообщения передачи с соответствующими битами потока ключей. NLSv2 допускает шифрование / дешифрование и аутентификацию открытого текста любой длины, но большинство операций предназначены для работы с 32-битными блоками открытого текста или передачи сообщения.
NLF
Каждое выходное слово ключевого потока v t {displaystyle v_{t}} NLF генерируется согласно следующему уравнению
v t = N L F ( σ t ) = ( r t [ 0 ] ⊞ r t [ 16 ] ) ⊕ ( r t [ 1 ] ⊞ r t [ 13 ] ) ⊕ ( r t [ 6 ] ⊞ K o n s t ) {displaystyle v_{t}=NLF(sigma _{t})=(r_{t}[0]oxplus r_{t}[16])oplus (r_{t}[1]oxplus r_{t}[13])oplus (r_{t}[6]oxplus Konst)}
Обратите внимание, что при t = 0 по модулю f16 нет выходного слова.
Требования безопасности NLSv2
NLSv2 предназначен для обеспечения 128-битной безопасности. Базовая атака на NLSv2 — это исчерпывающий поиск ключа, который имеет вычислительную сложность, эквивалентную генерации 2 128 {displaystyle 2^{128}} слов потока ключей. Во всех атаках предполагается, что злоумышленник наблюдает за определённым количеством потока ключей, созданного одним или несколькими секретными ключами, и злоумышленник, как предполагается, знает соответствующий открытый текст и одноразовые номера. Считается, что NLSv2 противостоит атаке, если для атаки требуется, чтобы владелец секретного ключа (ключей) сгенерировал более 2 80 {displaystyle 2^{80}} слов потока ключей, или вычислительная сложность атаки эквивалентна тому, что злоумышленник повторно проверяет шифр 2 128 {displaystyle 2^{128}} раз и генерирует по крайней мере 5 слов выходных данных каждый раз. Что касается функциональности потока ключей, утверждается, что NLSv2 удовлетворяет следующим требованиям безопасности при условии, что никакая пара ключ / одноразовый номер никогда не используется повторно, и с одним ключом обрабатывается не более 2 80 {displaystyle 2^{80}} слов:
1. NLSv2 должен противостоять атакам, которые либо определяют секретный ключ, либо определяют значения Konst и состояния шифра в любое указанное время
2. NLSv2 должен противостоять атакам, которые точно предсказывают неизвестные значения потока ключей без определения информации о состоянии NLFSR или секретного ключа.
3. NLSv2 должен противостоять атакам, которые отличают поток ключей NLSv2 от случайного потока битов
4. NLSv2 должен противостоять атакам описанной выше формы, которые используют поток ключей, сгенерированный из нескольких пар ключ / одноразовый номер, которые связаны каким-либо образом, известным атакующему
Отдельный набор требований безопасности применяется к необязательности MAC. Сначала рассмотрим свойства безопасности, требуемые для функции MAC.
Функция MAC — это криптографический алгоритм, который генерирует тег TAG = M A C K ( M ) {displaystyle MAC_{K}(M)} длины d из сообщения M произвольной длины и секретного ключа K длины n. Пара сообщение-тег (M, TAG) передаётся получателю (сообщение может быть зашифровано, полностью или частично, перед передачей).
Предположим, что полученная пара сообщение-тег (RM, RTAG). Получатель вычисляет ожидаемый тег XTAG = M A C K ( R M ) {displaystyle MAC_{K}(RM)} . Если XTAG = RTAG, то получатель имеет некоторую уверенность в том, что пара сообщение-тег была сформирована стороной, которая знает ключ K. В некоторых случаях сообщение включает данные последовательности (например, одноразовый номер), чтобы предотвратить воспроизведение сообщения-тега.
Длина n ключа и длина d тега формируют параметры безопасности алгоритма MAC, поскольку эти значения определяют степень, в которой получатель может быть уверен в том, что пара сообщение-тег была сформирована стороной, которая знает ключ K. Функция MAC с параметрами безопасности (n, d) должна обеспечивать устойчивость к четырём классам атак:
1. При атаке столкновением злоумышленник находит любые два разных сообщения M, M ’, такие что M A C K ( M ) = M A C K ( M ´ ) {displaystyle MAC_{K}(M)=MAC_{K}({acute {M}})} . Функция MAC противостоит атаке столкновения, если сложность атаки составляет O ( 2 min ( n , d / 2 ) ) {displaystyle O(2^{min(n,d/2)})}
2. Первая предварительная атака. В первой атаке перед изображением злоумышленнику указывается значение тега TAG, и злоумышленник должен найти сообщение M, для которого M A C K ( M ) = T A G {displaystyle MAC_{K}(M)=TAG} . Функция MAC противостоит первой атаке перед изображением, если сложность атаки составляет O ( 2 min ( n , d ) ) {displaystyle O(2^{min(n,d)})}
3. Вторая атака перед изображением. Во второй атаке перед изображением для ttacker указывается сообщение M, и злоумышленник генерирует новое сообщение M ’, такое, что M A C K ( M ) = M A C K ( M ´ ) {displaystyle MAC_{K}(M)=MAC_{K}({acute {M}})} . Функция MAC противостоит второй атаке перед изображением, если сложность атаки составляет O ( 2 min ( n , d ) ) {displaystyle O(2^{min(n,d)})}
4. Подделка MAC. При подделке MAC злоумышленник генерирует новую пару сообщение-тег (M ’, y’), такую что y ’= M A C K ( M ´ ) {displaystyle MAC_{K}({acute {M}})} . Функция MAC противостоит подделке MAC, если сложность атаки составляет O ( 2 min ( n , d ) ) {displaystyle O(2^{min(n,d)})} . Во всех этих атаках предполагается, что злоумышленник не знает о значении ключа K. Однако мы предполагаем, что (до атаки) злоумышленник может указать сообщения M (i), для которых они будут предоставлены с соответствующими тегами TAG (i) = M A C K ( M ( i ) ) {displaystyle MAC_{K}(M(i))} . Mundja в NLSv2 предназначен для использования в качестве функции MAC с параметрами безопасности n = 128 и d ≤ 128. То есть мы утверждаем, что Mundja противостоит вышеуказанным атакам при использовании 128-битных ключей и выводе тегов длиной до 128 бит
NLSv2 будет считаться нарушенным, если злоумышленник может выполнить любую из этих атак. Атаки восстановления потока ключей кажутся маловероятными, поскольку выходная последовательность в значительной степени зависит от состояния регистра, поэтому любая вероятная атака восстановления потока ключей, вероятно, также позволит провести более сильную атаку восстановления ключа / состояния. Большинство атак концентрируется на первом варианте определения значений Konst и состояния. Атаки по связанным ключам менее важны, так как большинство систем безопасности гарантируют, что злоумышленники не смогут предсказать отношения между секретными ключами. Однако все ещё предпочтительно, чтобы NLSv2 сопротивлялся таким атакам.
Сильные стороны и преимущества NLSv2
• Скорость
• Требуется небольшой объём памяти.
• Гибкость в размерах процессора и реализации.
• Конструкция позволяет использовать секретный ключ и не секретный одноразовый номер.
• Включает функциональность MAC