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-битовых линейных смесителей.

Счетчик-диффузор

Биты, поступившие на вход счетчика-диффузора, смешиваются перед подачей их на вход накапливающего регистра по следующему правилу: [math]\displaystyle{ d_0^{r+1}\ =\ d_1^{r} + c_1^{r} + c_4^{r} + c_5^{r} + c_{11}^{r} + c_{13}^{r} + 1 }[/math]
[math]\displaystyle{ d_1^{r+1}\ =\ d_2^{r} + c_0^{r} + c_2^{r} + c_6^{r} + c_{8}^{r} + c_{14}^{r} }[/math]
[math]\displaystyle{ d_2^{r+1}\ =\ d_3^{r} + c_3^{r} + c_4^{r} + c_7^{r} + c_{10}^{r} + c_{15}^{r} }[/math]
[math]\displaystyle{ d_3^{r+1}\ =\ d_4^{r} + c_0^{r} + c_3^{r} + c_5^{r} + c_{9}^{r} + c_{12}^{r} }[/math]
[math]\displaystyle{ d_4^{r+1}\ =\ d_5^{r} + c_1^{r} + c_4^{r} + c_6^{r} + c_{12}^{r} + c_{15}^{r} + 1 }[/math]
[math]\displaystyle{ d_5^{r+1}\ =\ d_6^{r} + c_0^{r} + c_7^{r} + c_9^{r} + c_{13}^{r} + c_{14}^{r} }[/math]
[math]\displaystyle{ d_6^{r+1}\ =\ d_7^{r} + c_1^{r} + c_8^{r} + c_{11}^{r} + c_{14}^{r} + c_{15}^{r} }[/math]
[math]\displaystyle{ d_7^{r+1}\ =\ d_8^{r} + c_2^{r} + c_5^{r} + c_6^{r} + c_{10}^{r} + c_{12}^{r} + 1 }[/math]
[math]\displaystyle{ d_8^{r+1}\ =\ d_0^{r} + c_0^{r} + c_3^{r} + c_7^{r} + c_{8}^{r} + c_{9}^{r} + 1 }[/math]
[math]\displaystyle{ d_9^{r+1}\ =\ d_9^{r} + c_8^{r} + c_{10}^{r} + c_{12}^{r} + c_{13}^{r} + c_{15}^{r} + 1 }[/math]

Накапливающий регистр

Младшие пять бит [math]\displaystyle{ x_0 }[/math], [math]\displaystyle{ x_1 }[/math], [math]\displaystyle{ x_2 }[/math], [math]\displaystyle{ x_3 }[/math], [math]\displaystyle{ x_4 }[/math] преобразуются нелинейными функциями [math]\displaystyle{ f_0 }[/math], [math]\displaystyle{ f_1 }[/math], [math]\displaystyle{ f_2 }[/math], [math]\displaystyle{ f_3 }[/math], [math]\displaystyle{ f_4 }[/math], которые образуют блок подстановки. Значения этих функций линейно смешиваются с пятью выходными битами [math]\displaystyle{ d_0 }[/math], [math]\displaystyle{ d_1 }[/math], [math]\displaystyle{ d_2 }[/math], [math]\displaystyle{ d_3 }[/math], [math]\displaystyle{ d_4 }[/math] счетчика-диффузора и возвращаются обратно в состояние регистра в [math]\displaystyle{ x_{p0} }[/math], [math]\displaystyle{ x_{p1} }[/math], [math]\displaystyle{ x_{p2} }[/math], [math]\displaystyle{ x_{p3} }[/math], [math]\displaystyle{ x_{p4} }[/math] соответственно. Биты [math]\displaystyle{ x_5 }[/math], [math]\displaystyle{ x_6 }[/math], [math]\displaystyle{ x_7 }[/math], [math]\displaystyle{ x_8 }[/math], [math]\displaystyle{ x_9 }[/math] линейно смешивают со значениями следующих пяти функций с обратной связью [math]\displaystyle{ f_5 }[/math], [math]\displaystyle{ f_6 }[/math], [math]\displaystyle{ f_7 }[/math], [math]\displaystyle{ f_8 }[/math], [math]\displaystyle{ f_9 }[/math] и с пятью битами счетчика-диффузора [math]\displaystyle{ d_5 }[/math], [math]\displaystyle{ d_6 }[/math], [math]\displaystyle{ d_7 }[/math], [math]\displaystyle{ d_8 }[/math], [math]\displaystyle{ d_9 }[/math] и возвращаются в состояние регистра в [math]\displaystyle{ x_{p5} }[/math], [math]\displaystyle{ x_{p6} }[/math], [math]\displaystyle{ x_{p7} }[/math], [math]\displaystyle{ x_{p8} }[/math], [math]\displaystyle{ x_{p9} }[/math] соответственно. Биты от [math]\displaystyle{ x_{10} }[/math] до [math]\displaystyle{ x_{M+9} }[/math] линейно смешиваются с значениями функций [math]\displaystyle{ f_{10} }[/math],…, [math]\displaystyle{ f_{M+9} }[/math], а в режиме шифрования с аутентификацией ещё и с битами шифротекста.

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

[math]\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 \le j \lt 5 }[/math];

[math]\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 \le j \lt 10 }[/math];

[math]\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 \le j \lt W }[/math];

Режимы работы

Загрузка ключа

Перед генерацией ключевого потока, шифрованием данных или хешированием шифр работает в режиме загрузки ключа, состоящий из [math]\displaystyle{ R_0 = F + 16 }[/math] раундов, где [math]\displaystyle{ F }[/math] — длина ключа в битах. Формируется последовательность битов, состоящая из 15 нулей, ключа, единичного бита и ещё 15 нулей. Эта последовательность загружается с регистры начиная с младшего бита по 16 бит до тех пор, пока единичный бит не окажется в первом регистре. Далее происходят следующие операции: [math]\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}, }[/math]

[math]\displaystyle{ c_i{}^{r+1}{}_1 \ =\ 0,if r+i\lt 15, }[/math]

[math]\displaystyle{ c_i{}^{r+1}{}_1 \ =\ c_i{}^r{}_0 + k_{r+i-15},if 15 \leq r+i\lt F+15, }[/math]

[math]\displaystyle{ c_i{}^{r+1}{}_1 \ =\ 1,if r+i \ =\ F+15, }[/math]

[math]\displaystyle{ c_i{}^{r+1}{}_1 \ =\ 0,if F+15\lt r+i, }[/math]

[math]\displaystyle{ c_i{}^{r+1}{}_j \ =\ c_i{}^{r+1}{}_{j-1},2 \leq j\lt B_i,0 \leq i\lt 16; }[/math]

[math]\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 \le j \lt 5 }[/math];

[math]\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 \le j \lt 10 }[/math];

[math]\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 \le j \lt W }[/math];

[math]\displaystyle{ 0 \leq r \lt R_0. }[/math]

Хеширование

Этот режим используется для хеширования данных и для загрузки вектора инициализации. Входные данные хешируются по 8 бит за раунд: [math]\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}, }[/math]

[math]\displaystyle{ c_i{}^{r+1}{}_1 \ =\ c_i{}^r{}_0+k_{(r-R_a)*8+i}, }[/math]

[math]\displaystyle{ c_i{}^{r+1}{}_j \ =\ c_i{}^{r}{}_{j-1},2 \leq j\lt B_i,0 \leq i\lt 8; }[/math]

[math]\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}, }[/math]

[math]\displaystyle{ c_i{}^{r+1}{}_j \ =\ c_i{}^{r}{}_{j-1},2 \leq j\lt B_i,0 \leq i\lt 16; }[/math]

[math]\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 \le j \lt 5 }[/math];

[math]\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 \le j \lt 10 }[/math];

[math]\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 \le j \lt 10+M }[/math];

[math]\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 \le j \lt W }[/math];

[math]\displaystyle{ R_a \leq r \lt R_b. }[/math]

Генерация ключевого потока

В этом режиме на вход не подаются никакие данные. А биты с выхода складываются с открытым текстом по модулю 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