Электромонтаж Ремонт и отделка Укладка напольных покрытий, теплые полы Тепловодоснабжение

HC-256


HC-256 — система потокового шифрования, разработанная криптографом У Хунцзюнем (Hongjun Wu) из сингапурского Института инфокоммуникационных исследований. Впервые опубликован в 2004 году. 128-битный вариант был представлен на конкурсе eSTREAM, целью которого было создание европейских стандартов для поточных систем шифрования. Алгоритм стал одним из четырёх финалистов конкурса в первом профиле (поточные шифры для программного применения с большой пропускной способностью). [1] (англ.)

Описание алгоритма

Потоковый шифр HC-256 генерирует ключевую последовательность (keystream) длиной до 2 128 {displaystyle 2^{128}} бит с помощью 256-битового ключа (secret key) и 256-битного вектора инициализации (initialization vector).

НС-256 содержит две секретные таблицы, в каждой из которых 1024 32-битных элемента. При каждом шаге обновляется один элемент из таблицы при помощи нелинейном функции обратной связи(feedback function). Через каждые 2048 шагов все элементы двух таблиц будут обновлены.

Операции, функции, переменные

В алгоритме используются следующие операции:

+ {displaystyle +} : x+y означает x+y mod 2 32 {displaystyle 2^{32}} , где 0 ≤ {displaystyle leq } x < {displaystyle <} 2 32 {displaystyle 2^{32}} и 0 ≤ {displaystyle leq } y < {displaystyle <} 2 32 {displaystyle 2^{32}}
⊟ {displaystyle oxminus } : x ⊟ {displaystyle oxminus } y означает x — y mod 1024
⊕ {displaystyle oplus } : побитовое исключающее ИЛИ
| | {displaystyle ||} : конкатенация
≫ {displaystyle gg } : оператор сдвига вправо на указанное количество бит
≪ {displaystyle ll } : оператор сдвига влево на указанное количество бит
⋙ {displaystyle ggg } : циклический сдвиг вправо, x ⋙ {displaystyle ggg } n означает ((x ≫ {displaystyle gg } n) + {displaystyle +} (x ≪ {displaystyle ll } (32 — n)), где 0 ≤ {displaystyle leq } n < {displaystyle <} 32 и 0 ≤ {displaystyle leq } x < {displaystyle <} 2 32 {displaystyle 2^{32}}

В HC-256 используются две таблицы P и Q. Ключ и вектор инициализации обозначаются K и V соответственно. Ключевая последовательность обозначается S.

P {displaystyle P} : таблица из 1024 32-битных элементов. Каждый элемент обозначается P[i], где 0 ≤ {displaystyle leq } i ≤ {displaystyle leq } 1023.
Q {displaystyle Q} : таблица из 1024 32-битных элементов. Каждый элемент обозначается P[i], где 0 ≤ {displaystyle leq } i ≤ {displaystyle leq } 1023.
K {displaystyle K} : 256-битный ключ алгоритма HC-256.
V {displaystyle V} : 256-битный вектор инициализации алгоритма HC-256.
S {displaystyle S} : ключевая последовательность, созданная алгоритмом HC-256. 32-битный элемент на выходе i-го шага обозначается S i {displaystyle S_{i}} . S= S 0 {displaystyle S_{0}} || S 1 {displaystyle S_{1}} || S 2 {displaystyle S_{2}} || …

В HC-256 используется шесть функций:

f 1 ( x ) = ( x >>> 7 ) ⊕ ( x >>> 18 ) ⊕ ( x >> 3 ) {displaystyle {{f_{1}}(x)=(x>>>7)oplus (x>>>18)oplus (x>>3)}}
f 2 ( x ) = ( x >>> 17 ) ⊕ ( x >>> 19 ) ⊕ ( x >> 10 ) {displaystyle {{f_{2}}(x)=(x>>>17)oplus (x>>>19)oplus (x>>10)}}
g 1 ( x , y ) = ( ( x >>> 10 ) ⊕ ( y >>> 23 ) ) + Q [ ( x ⊕ y ) m o d   1024 ] {displaystyle {{g_{1}}(x,y)=((x>>>10)oplus (y>>>23))+Q[(xoplus y)mod~1024]}}
g 2 ( x , y ) = ( ( x >>> 10 ) ⊕ ( y >>> 23 ) ) + P [ ( x ⊕ y ) m o d   1024 ] {displaystyle {{g_{2}}(x,y)=((x>>>10)oplus (y>>>23))+P[(xoplus y)mod~1024]}}
h 1 ( x ) = Q [ x 0 ] + Q [ 256 + x 1 ] + Q [ 512 + x 2 ] + Q [ 768 + x 3 ] {displaystyle {{h_{1}}(x)=Q[{x_{0}}]+Q[256+{x_{1}}]+Q[512+{x_{2}}]+Q[768+{x_{3}}]}}
h 2 ( x ) = P [ x 0 ] + P [ 256 + x 1 ] + P [ 512 + x 2 ] + P [ 768 + x 3 ] {displaystyle {{h_{2}}(x)=P[{x_{0}}]+P[256+{x_{1}}]+P[512+{x_{2}}]+P[768+{x_{3}}]}}

Здесь x = x 3 {displaystyle x_{3}} || x 2 {displaystyle x_{2}} || x 1 {displaystyle x_{1}} || x 0 {displaystyle x_{0}} — 32-битное слово. x 0 {displaystyle x_{0}} , x 1 {displaystyle x_{1}} , x 2 {displaystyle x_{2}} , x 3 {displaystyle x_{3}} состоят из 1 байта каждый, причем x 0 {displaystyle x_{0}} , x 3 {displaystyle x_{3}} — младший и старший байты соответственно.

Процесс инициализации

Процесс инициализации (Initialization process) в HC-256 состоит из преобразования P и Q с помощью ключа и вектора инициализации и запуска шифрования 4096 раз без генерации выходного результата (output).

1. Составление K = K 0 {displaystyle K_{0}} || K 1 {displaystyle K_{1}} || … || K 7 {displaystyle K_{7}} и V = V 0 {displaystyle V_{0}} || V 1 {displaystyle V_{1}} || … || V 7 {displaystyle V_{7}} , где K i {displaystyle K_{i}} и V i {displaystyle V_{i}} состоят из 32 битов. Ключ и вектор инициализации расширяются в массив W i {displaystyle W_{i}} (0 ≤ {displaystyle leq } i ≤ {displaystyle leq } 2559).

W i {displaystyle {W_{i}}} принимает следующие значения:

K i ,   0 ≤ i ≤ 7 {displaystyle {{K_{i}},~0leq ileq 7}}
V i − 8 ,   8 ≤ i ≤ 15 {displaystyle {{V_{i-8}},~8leq ileq 15}}
f 2 ( W i − 2 ) + W i − 7 + f 1 ( W i − 15 ) + W i − 16 + i ,   16 ≤ i ≤ 2559 {displaystyle {{f_{2}}({W_{i-2}})+W_{i-7}+f_{1}(W_{i-15})+W_{i-16}+i,~16leq ileq 2559}}

2. Обновление таблиц P и Q с помощью W:

P [ i ] = W i + 512 ,   0 ≤ i ≤ 1023 {displaystyle {{P[i]}={W_{i+512}},~0leq ileq 1023}}
Q [ i ] = W i + 1536 ,   0 ≤ i ≤ 1023 {displaystyle {{Q[i]}={W_{i+1536}},~0leq ileq 1023}}

3. Запуск шифрования (алгоритм генерации ключевой последовательности) 4096 раз без генерации выходного результата.

Процесс инициализации завершен и шифр готов к генерации ключевой последовательности.

Алгоритм генерации ключевой последовательности

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

i=0;
repeat until enough keystream bits are generated.
{

j = i mod 1024;
if (i mod 2048) < 1024
{ P[j] = P[j] + P[j ⊟ {displaystyle oxminus } 10] + g 1 {displaystyle g_{1}} (P[j ⊟ {displaystyle oxminus } 3], P[j ⊟ {displaystyle oxminus } 1023]);
S i = h 1 {displaystyle S_{i}=h_{1}} (P[j ⊟ {displaystyle oxminus } 12]) ⊕ {displaystyle oplus } P[j];
} else
{ Q[j] = Q[j] + Q[j ⊟ {displaystyle oxminus } 10] + g 2 {displaystyle g_{2}} (Q[j ⊟ {displaystyle oxminus } 3], Q[j ⊟ {displaystyle oxminus } 1023]);
S i = h 2 {displaystyle S_{i}=h_{2}} (Q[j ⊟ {displaystyle oxminus } 12]) ⊕ {displaystyle oplus } Q[j];
} end-if
i = i + 1;

}
end-repeat

Безопасность шифрования HC-256

Авторы сформулировали следующие утверждения о безопасности HC-256:

  • В HC-256 нет скрытых дефектов.
  • Ожидается, что наименьший период не будет намного больше чем 2 256 {displaystyle 2^{256}} .
  • Восстановление секретного ключа так же тяжело, как и полный перебор ключей.
  • Для результативной атаки требуется более чем 2 128 {displaystyle 2^{128}} бит ключевой последовательности.
  • В HC-256 нет слабых ключей.

    • Период

    Алгоритм HC-256 гарантирует, что период ключевой последовательности очень большой. Но точно определить его тяжело. По оценкам средний период ключевой последовательности около 2 65546 {displaystyle 2^{65546}} .

    Безопасность секретного ключа

    Функции выхода (output function) и функции обратной связи (feedback function) в HC-256 в высокой степени нелинейна. Нелинейная функция выхода допускает очень малую утечку информации на каждом шаге. Нелинейная функция обратной связи гарантирует, что секретный ключ не может быть определён из этой утечки.

    Из анализа значений функций h 1 ( x ) {displaystyle h_{1}(x)} и h 2 ( x ) {displaystyle h_{2}(x)} следует:

    Для   2048 ∗ α ≤ i < j < 2048 ∗ α + 1024   {displaystyle {~2048*alpha leq i<j<2048*alpha +1024~}} из условия   S i = S j   {displaystyle {~{S_{i}}={S_{j}}~}} следует, что   h 1 ( x ) ( P [ i ⊟ 12 ] ) ⊕ P [ i ] = h 1 ( x ) ( P [ j ⊟ 12 ] ) ⊕ P [ j ]   {displaystyle {~h_{1}(x)(P[ioxminus 12])oplus P[i]=h_{1}(x)(P[joxminus 12])oplus P[j]~}} . Так как   h 1 ( x ) ( P [ i ⊟ 12 ] ) = h 1 ( x ) ( P [ j ⊟ 12 ] )   {displaystyle {~h_{1}(x)(P[ioxminus 12])=h_{1}(x)(P[joxminus 12])~}} с вероятностью примерно 2 − 31 {displaystyle {2^{-31}}} , вероятность того, что   P [ i ] = P [ j ]   {displaystyle {~P[i]=P[j]~}} , также равна примерно 2 − 31 {displaystyle {2^{-31}}} . Это означает, что при каждом совпадении(collision) утекает примерно 2 − 26.1 {displaystyle {2^{-26.1}}} бит информации. Всего ≈ 2 − 12   {displaystyle {approx 2^{-12}~}} совпадений. Для восстановления P необходимо   1024 ∗ 32 2 − 12 ∗ 2 − 26.1 ∗ 1024 ≈ 2 53.1   {displaystyle {~{frac {1024*32}{2^{-12}*2^{-26.1}}}*1024approx 2^{53.1}~}} выходных результатов. Итак, можно сделать вывод, что ключ для HC-256 безопасен, и что его нельзя определить быстрее, чем полным перебором ключей.

    Безопасность процесса инициализации

    Процесс инициализации HC-256 состоит из двух этапов (см. выше). P и Q преобразуются с помощью ключа K и вектора инициализации V. Каждый бит K и V влияет на все биты двух таблиц, и каждое изменение в них приводит к неконтролируемым изменениям в таблицах. Шифрование запускается 4096 раз без генерирования выходного результата, так что таблицы P и Q становятся более случайными. После процесса инициализации изменение в K и V не приводят к изменениям в ключевой последовательности.

    Атаки на HC-256

    В 2008 году Эриком Зеннером (Erik Zenner) был предложен способ атаки на шифр HC-256. Предложенная атака по времени позволяет восстановить и внутреннее состояние (inner state), представляющее собой 2 таблицы из 1024 32-битовых элементов, а также ключ. Атака требует 8 килобайт известной ключевой последовательности, 6148 точных измерений времени чтения из кэша, время на вычисление, соответствующее времени тестирования 2 55 {displaystyle 2^{55}} ключей. Следует вывод, что в теории HC-256 уязвим для атак по времени.

    Также следует обратить внимание на публикацию Г.Секара (Gautham Sekar) и Барта Пренеля (Bart Preneel), предлагающую класс идентификаторов (class of distinguishers), каждый из которых требует тестирование около 2 276.8 {displaystyle 2^{276.8}} линейных функций. Каждое уравнение включает в себя 8 бит ключевой последовательности. Вероятность успешного исхода 0.9772. Для сравнения, известный до этого и предложенный самим автором HC-256 аналогичный способ требовал 2 280 {displaystyle 2^{280}} функций, каждый из которых включало в себя 10 бит ключевой последовательности.

    Заключение

    HC-256 удобен для современных микропроцессоров. Зависимость между операциями в HC-256 сведена у минимуму: три последовательных шага алгоритма могут быть вычислены параллельно. Возможность распараллеливания позволяет HC-256 быть эффективным в современных процессорах. Авторы реализовали HC-256 на языке программирования С и протестировали его эффективность на процессоре Pentium 4. Скорость шифрования HC-256 достигает 1.93 бит/цикл. HC-256 не запатентован и находится в свободном доступе.


    Имя:*
    E-Mail:
    Комментарий: