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

Счетчик-диффузор[править]

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

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

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

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

$x_{p j [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$ ;

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

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

Режимы работы[править]

Загрузка ключа[править]

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

$c_{i}^{r + 1}_{1} = 0, i f r + i < 15,$

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

$c_{i}^{r + 1}_{1} = 1, i f r + i = F + 15,$

$c_{i}^{r + 1}_{1} = 0, i f F + 15 < r + i,$

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

$x_{p j [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$ ;

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

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

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

Хеширование[править]

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

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

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

$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},$

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

$x_{p j [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$ ;

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

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

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

$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