VEST

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править вики-текст]

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

Применение поточных шифров[править | править вики-текст]

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

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

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

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

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

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

Аппаратная реализация[править | править вики-текст]

Общая структура[править | править вики-текст]

VEST Structure.PNG

Схема шифрования состоит из четырёх основных компонентов: нелинейный счетчик, линейный счетчик-диффузор, биективный накапливающий регистр с большим числом состояний и линейный смеситель на выходе. Ядро шифров 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

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

VEST-4 accumulator.png

Младшие пять бит 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_{p0}, x_{p1}, x_{p2}, x_{p3}, x_{p4} соответственно. Биты 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_{p5}, x_{p6}, x_{p7}, x_{p8}, x_{p9} соответственно. Биты от x_{10} до x_{M+9} линейно смешиваются с значениями функций f_{10},..., f_{M+9}, а в режиме шифрования с аутентификацией ещё и с битами шифротекста.

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

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 < 5;

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 < 10;

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 < 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,if r+i<15,

c_i{}^{r+1}{}_1 \ =\ c_i{}^r{}_0 + k_{r+i-15},if 15 \leq r+i<F+15,

c_i{}^{r+1}{}_1 \ =\ 1,if r+i \ =\ F+15,

c_i{}^{r+1}{}_1 \ =\ 0,if  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_{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 < 5;

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 < 10;

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 < 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_{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 < 5;

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 < 10;

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 < 10+M;

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 < W;

R_a \leq r < R_b.

Генерация ключевого потока[править | править вики-текст]

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

Шифрование с аутентификацией[править | править вики-текст]

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

Криптостойкость[править | править вики-текст]

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

Тест на случайность[править | править вики-текст]

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

Проверка алгебраической структуры на наличие дефектов[править | править вики-текст]

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

Применение[править | править вики-текст]

Смарт-карты[править | править вики-текст]

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

Устройства идентификации[править | править вики-текст]

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

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

Беспроводные сети[править | править вики-текст]

Источники[править | править вики-текст]