HC-256

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

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

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

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

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

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

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

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

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

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

${{f_{1}}(x)=(x>>>7)\oplus (x>>>18)\oplus (x>>3)}$
${{f_{2}}(x)=(x>>>17)\oplus (x>>>19)\oplus (x>>10)}$
${{g_{1}}(x,y)=((x>>>10)\oplus (y>>>23))+Q[(x\oplus y)mod~1024]}$
${{g_{2}}(x,y)=((x>>>10)\oplus (y>>>23))+P[(x\oplus y)mod~1024]}$
${{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}}]}$

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

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

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

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

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

 ${{K_{i}},~0\leq i\leq 7}$ 

 ${{V_{i-8}},~8\leq i\leq 15}$ 

 ${{f_{2}}({W_{i-2}})+W_{i-7}+f_{1}(W_{i-15})+W_{i-16}+i,~16\leq i\leq 2559}$ 

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

${{P[i]}={W_{i+512}},~0\leq i\leq 1023}$
${{Q[i]}={W_{i+1536}},~0\leq i\leq 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 $\boxminus$ 10] + $g_{1}$(P[j $\boxminus$ 3], P[j $\boxminus$ 1023]); 

     $S_{i}=h_{1}$(P[j $\boxminus$ 12]) $\oplus$ P[j]; 

  }
  else 

  {
     Q[j] = Q[j] + Q[j $\boxminus$ 10] + $g_{2}$(Q[j $\boxminus$ 3], Q[j $\boxminus$ 1023]); 

     $S_{i}=h_{2}$(Q[j $\boxminus$ 12]) $\oplus$ Q[j]; 

  }
  end-if 

  i = i + 1; 

}
end-repeat


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

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

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

Период

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

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

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

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

Для ${~2048*\alpha \leq i<j<2048*\alpha +1024~}$ из условия ${~{S_{i}}={S_{j}}~}$ следует, что ${~h_{1}(x)(P[i\boxminus 12])\oplus P[i]=h_{1}(x)(P[j\boxminus 12])\oplus P[j]~}$. Так как ${~h_{1}(x)(P[i\boxminus 12])=h_{1}(x)(P[j\boxminus 12])~}$ с вероятностью примерно ${2^{-31}}$, вероятность того, что ${~P[i]=P[j]~}$, также равна примерно ${2^{-31}}$. Это означает, что при каждом совпадении(collision) утекает примерно ${2^{-26.1}}$ бит информации. Всего ${\approx 2^{-12}~}$ совпадений. Для восстановления P необходимо ${~{\frac {1024*32}{2^{-12}*2^{-26.1}}}*1024\approx 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}$ ключей. Следует вывод, что в теории HC-256 уязвим для атак по времени.

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

Заключение

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

Ссылки

• Stream Cipher HC-256
• HC-256
• eSTREAM
• Improved Distinguishing Attacks on HC-256
• Cache Timing Analysis of eStream Finalists(Extended Abstract)
• A Cache Timing Analysis of HC-256