VEST

VEST (англ. Very Efficient Substitution Transposition, очень эффективная перестановка) — серия аппаратных поточных шифров общего назначения, которые обеспечивают однопроходное шифрование с аутентификацией и могут работать как хеш-функция, стойкая к коллизиям второго рода. Шифры VEST разработаны в Synaptic Laboratories. Все шифры этой серии поддерживают режим работы с ключами переменной длины.

Шифры VEST были разработаны Шоном О’Нейлом (Sean O’Neil). Впервые были представлены на турнире eStream в 2005 году, прошли во второй отборочный тур, но не попали в третий и, соответственно, не прошли в финал.

Поточные шифры начали активно использовать в годы войны, ещё до появления электроники.

Преимущества поточных шифров:

• Простота проектирования;
• Простота аппаратной реализации;
• Высокая скорость шифрования (важно при магистральном шифровании больших потоков информации);
• Отсутствие эффекта размножения ошибок, который присутствует в блочных шифрах;
• Обеспечивают высокую криптостойкость

Поточные шифры и их применение:

• RC4 (системы защиты информации в компьютерных сетях, например в протоколах SSL и TSL);
• A3 (процесс аутентификации в глобальном цифровом стандарте для мобильной сотовой связи GSM);
• A5 (обеспечения конфиденциальности передаваемых данных между телефоном и базовой станцией в европейской системе мобильной цифровой связи GSM);
• SEAL (криптографический алгоритм)(является одним из самых быстрых шифров)
• Также поточные шифры используются в:
  • смарт-картах
  • RFID-метках
  • Беспроводных сетях

Одним из примеров поточных шифров является шифр VEST

Схема шифрования состоит из четырёх основных компонентов: нелинейный счетчик, линейный счетчик-диффузор, биективный накапливающий регистр с большим числом состояний и линейный смеситель на выходе. Ядро шифров VEST можно представить как взаимно-однозначные регистры сдвига с нелинейной обратной связью (NLFSRs) с множеством параллельных обратных связей, работающие вместе с системой нелинейных модульных счетчиков (RNS) с очень длинным периодом. Модульный счетчик состоит из 16 регистров сдвига с нелинейной обратной связью с взаимно простыми длинами периодов. Счетчик-диффузор — это набор 6-битовых линейных смесителей с обратной связью, сжимающий выходные данные с 16 счетчиков в 10 бит. Ядро накапливающего регистра — регистр сдвига с нелинейной параллельной обратной связью, на вход которого подаются выходные 10 бит от счетчика-диффузора. Выходной смеситель — набор 6-битовых линейных смесителей.

Биты, поступившие на вход счетчика-диффузора, смешиваются перед подачей их на вход накапливающего регистра по следующему правилу: ${\displaystyle d_{0}^{r+1}\ =\ d_{1}^{r}+c_{1}^{r}+c_{4}^{r}+c_{5}^{r}+c_{11}^{r}+c_{13}^{r}+1}$
${\displaystyle d_{1}^{r+1}\ =\ d_{2}^{r}+c_{0}^{r}+c_{2}^{r}+c_{6}^{r}+c_{8}^{r}+c_{14}^{r}}$
${\displaystyle d_{2}^{r+1}\ =\ d_{3}^{r}+c_{3}^{r}+c_{4}^{r}+c_{7}^{r}+c_{10}^{r}+c_{15}^{r}}$
${\displaystyle d_{3}^{r+1}\ =\ d_{4}^{r}+c_{0}^{r}+c_{3}^{r}+c_{5}^{r}+c_{9}^{r}+c_{12}^{r}}$
${\displaystyle d_{4}^{r+1}\ =\ d_{5}^{r}+c_{1}^{r}+c_{4}^{r}+c_{6}^{r}+c_{12}^{r}+c_{15}^{r}+1}$
${\displaystyle d_{5}^{r+1}\ =\ d_{6}^{r}+c_{0}^{r}+c_{7}^{r}+c_{9}^{r}+c_{13}^{r}+c_{14}^{r}}$
${\displaystyle d_{6}^{r+1}\ =\ d_{7}^{r}+c_{1}^{r}+c_{8}^{r}+c_{11}^{r}+c_{14}^{r}+c_{15}^{r}}$
${\displaystyle d_{7}^{r+1}\ =\ d_{8}^{r}+c_{2}^{r}+c_{5}^{r}+c_{6}^{r}+c_{10}^{r}+c_{12}^{r}+1}$
${\displaystyle d_{8}^{r+1}\ =\ d_{0}^{r}+c_{0}^{r}+c_{3}^{r}+c_{7}^{r}+c_{8}^{r}+c_{9}^{r}+1}$
${\displaystyle d_{9}^{r+1}\ =\ d_{9}^{r}+c_{8}^{r}+c_{10}^{r}+c_{12}^{r}+c_{13}^{r}+c_{15}^{r}+1}$

Младшие пять бит ${\displaystyle x_{0}}$, ${\displaystyle x_{1}}$, ${\displaystyle x_{2}}$, ${\displaystyle x_{3}}$, ${\displaystyle x_{4}}$ преобразуются нелинейными функциями ${\displaystyle f_{0}}$, ${\displaystyle f_{1}}$, ${\displaystyle f_{2}}$, ${\displaystyle f_{3}}$, ${\displaystyle f_{4}}$, которые образуют блок подстановки. Значения этих функций линейно смешиваются с пятью выходными битами ${\displaystyle d_{0}}$, ${\displaystyle d_{1}}$, ${\displaystyle d_{2}}$, ${\displaystyle d_{3}}$, ${\displaystyle d_{4}}$ счетчика-диффузора и возвращаются обратно в состояние регистра в ${\displaystyle x_{p0}}$, ${\displaystyle x_{p1}}$, ${\displaystyle x_{p2}}$, ${\displaystyle x_{p3}}$, ${\displaystyle x_{p4}}$ соответственно. Биты ${\displaystyle x_{5}}$, ${\displaystyle x_{6}}$, ${\displaystyle x_{7}}$, ${\displaystyle x_{8}}$, ${\displaystyle x_{9}}$ линейно смешивают со значениями следующих пяти функций с обратной связью ${\displaystyle f_{5}}$, ${\displaystyle f_{6}}$, ${\displaystyle f_{7}}$, ${\displaystyle f_{8}}$, ${\displaystyle f_{9}}$ и с пятью битами счетчика-диффузора ${\displaystyle d_{5}}$, ${\displaystyle d_{6}}$, ${\displaystyle d_{7}}$, ${\displaystyle d_{8}}$, ${\displaystyle d_{9}}$ и возвращаются в состояние регистра в ${\displaystyle x_{p5}}$, ${\displaystyle x_{p6}}$, ${\displaystyle x_{p7}}$, ${\displaystyle x_{p8}}$, ${\displaystyle x_{p9}}$ соответственно. Биты от ${\displaystyle x_{10}}$ до ${\displaystyle x_{M+9}}$ линейно смешиваются с значениями функций ${\displaystyle f_{10}}$,…, ${\displaystyle f_{M+9}}$, а в режиме шифрования с аутентификацией ещё и с битами шифротекста.

Работу ядра накапливающего регистра (в режиме без аутентификации) можно изобразить с следующем виде:

${\displaystyle x_{pj[5]}^{r+1}\ =\ f_{j}(x_{0}^{r},x_{1}^{r},x_{2}^{r},x_{3}^{r},x_{4}^{r})+d_{j}^{r},0\leq j<5}$;

${\displaystyle x_{pj[5]}^{r+1}\ =\ f_{j}(x_{pj[0]}^{r},x_{pj[1]}^{r},x_{pj[2]}^{r},x_{pj[3]}^{r},x_{pj[4]}^{r})+x_{j}^{r}+d_{j}^{r},5\leq j<10}$;

${\displaystyle x_{pj[5]}^{r+1}\ =\ f_{j}(x_{pj[0]}^{r},x_{pj[1]}^{r},x_{pj[2]}^{r},x_{pj[3]}^{r},x_{pj[4]}^{r})+x_{j}^{r},10\leq j<W}$;

Перед генерацией ключевого потока, шифрованием данных или хешированием шифр работает в режиме загрузки ключа, состоящий из ${\displaystyle R_{0}=F+16}$ раундов, где ${\displaystyle F}$ — длина ключа в битах. Формируется последовательность битов, состоящая из 15 нулей, ключа, единичного бита и ещё 15 нулей. Эта последовательность загружается с регистры начиная с младшего бита по 16 бит до тех пор, пока единичный бит не окажется в первом регистре. Далее происходят следующие операции: ${\displaystyle c_{i}{}^{r+1}{}_{0}\ =\ g_{i}(c_{i}{}^{r}{}_{0},c_{i}{}^{r}{}_{1},c_{i}{}^{r}{}_{2},c_{i}{}^{r}{}_{6},c_{i}{}^{r}{}_{7})+c_{i}{}^{r}{}_{B[i]-1},}$

${\displaystyle c_{i}{}^{r+1}{}_{1}\ =\ 0,ifr+i<15,}$

${\displaystyle c_{i}{}^{r+1}{}_{1}\ =\ c_{i}{}^{r}{}_{0}+k_{r+i-15},if15\leq r+i<F+15,}$

${\displaystyle c_{i}{}^{r+1}{}_{1}\ =\ 1,ifr+i\ =\ F+15,}$

${\displaystyle c_{i}{}^{r+1}{}_{1}\ =\ 0,ifF+15<r+i,}$

${\displaystyle c_{i}{}^{r+1}{}_{j}\ =\ c_{i}{}^{r+1}{}_{j-1},2\leq j<B_{i},0\leq i<16;}$

${\displaystyle x_{pj[5]}^{r+1}\ =\ f_{j}(x_{0}^{r},x_{1}^{r},x_{2}^{r},x_{3}^{r},x_{4}^{r})+d_{j}^{r},0\leq j<5}$;

${\displaystyle x_{pj[5]}^{r+1}\ =\ f_{j}(x_{pj[0]}^{r},x_{pj[1]}^{r},x_{pj[2]}^{r},x_{pj[3]}^{r},x_{pj[4]}^{r})+x_{j}^{r}+d_{j}^{r},5\leq j<10}$;

${\displaystyle x_{pj[5]}^{r+1}\ =\ f_{j}(x_{pj[0]}^{r},x_{pj[1]}^{r},x_{pj[2]}^{r},x_{pj[3]}^{r},x_{pj[4]}^{r})+x_{j}^{r},10\leq j<W}$;

${\displaystyle 0\leq r<R_{0}.}$

Этот режим используется для хеширования данных и для загрузки вектора инициализации. Входные данные хешируются по 8 бит за раунд: ${\displaystyle c_{i}{}^{r+1}{}_{0}\ =\ g_{i}(c_{i}{}^{r}{}_{0},c_{i}{}^{r}{}_{1},c_{i}{}^{r}{}_{2},c_{i}{}^{r}{}_{6},c_{i}{}^{r}{}_{7})+c_{i}{}^{r}{}_{B[i]-1},}$

${\displaystyle c_{i}{}^{r+1}{}_{1}\ =\ c_{i}{}^{r}{}_{0}+k_{(r-R_{a})*8+i},}$

${\displaystyle c_{i}{}^{r+1}{}_{j}\ =\ c_{i}{}^{r}{}_{j-1},2\leq j<B_{i},0\leq i<8;}$

${\displaystyle c_{i}{}^{r+1}{}_{0}\ =\ g_{i}(c_{i}{}^{r}{}_{0},c_{i}{}^{r}{}_{1},c_{i}{}^{r}{}_{2},c_{i}{}^{r}{}_{6},c_{i}{}^{r}{}_{7})+c_{i}{}^{r}{}_{B[i]-1},}$

${\displaystyle c_{i}{}^{r+1}{}_{j}\ =\ c_{i}{}^{r}{}_{j-1},2\leq j<B_{i},0\leq i<16;}$

${\displaystyle x_{pj[5]}^{r+1}\ =\ f_{j}(x_{0}^{r},x_{1}^{r},x_{2}^{r},x_{3}^{r},x_{4}^{r})+d_{j}^{r},0\leq j<5}$;

${\displaystyle x_{pj[5]}^{r+1}\ =\ f_{j}(x_{pj[0]}^{r},x_{pj[1]}^{r},x_{pj[2]}^{r},x_{pj[3]}^{r},x_{pj[4]}^{r})+x_{j}^{r}+d_{j}^{r},5\leq j<10}$;

${\displaystyle x_{pj[5]}^{r+1}\ =\ f_{j}(x_{pj[0]}^{r},x_{pj[1]}^{r},x_{pj[2]}^{r},x_{pj[3]}^{r},x_{pj[4]}^{r})+x_{j}^{r}+e^{(r-R_{i}-1)*M+j-10},10\leq j<10+M}$;

${\displaystyle x_{pj[5]}^{r+1}\ =\ f_{j}(x_{pj[0]}^{r},x_{pj[1]}^{r},x_{pj[2]}^{r},x_{pj[3]}^{r},x_{pj[4]}^{r})+x_{j}^{r},10+M\leq j<W}$;

${\displaystyle R_{a}\leq r<R_{b}.}$

В этом режиме на вход не подаются никакие данные. А биты с выхода складываются с открытым текстом по модулю 2.

В этом режиме биты зашифрованного сообщения попадают обратно в регистр.

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

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

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

Смарт-карты часто используют как защищённый способ предоставления услуг. Использование сильного, быстрого, малоэнергозатратного шифрования в таких системах — необходимое условие. Программное шифрование недостаточно быстрое и сильно энергозатратное, и его не всегда удобно использовать на уровне «железа».

Шифр VEST-4 удовлетворяет необходимым требованиям радиочастотной идентификации:

• шифрование с аутентификацией;
• низкая стоимость;
• массовый параллелизм;
• высокая надежность;
• низкие энергозатраты.

• VEST eStream Phase II specification Архивная копия от 27 мая 2011 на Wayback Machine
• The official Synaptic Laboratories VEST website
• eSTREAM page on VEST Архивная копия от 4 марта 2016 на Wayback Machine