VEST
VEST (англ. Very Efficient Substitution Transposition, очень эффективная перестановка) — серия аппаратных поточных шифров общего назначения, которые обеспечивают однопроходное шифрование с аутентификацией и могут работать как хеш-функция, стойкая к коллизиям второго рода. Шифры VEST разработаны в Synaptic Laboratories. Все шифры этой серии поддерживают режим работы с ключами переменной длины.
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
{\displaystyle 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
{\displaystyle 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
{\displaystyle 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
{\displaystyle 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
{\displaystyle 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
{\displaystyle 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
{\displaystyle 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
{\displaystyle 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
{\displaystyle 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
{\displaystyle 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
{\displaystyle x_{0}}
,
x
1
{\displaystyle x_{1}}
,
x
2
{\displaystyle x_{2}}
,
x
3
{\displaystyle x_{3}}
,
x
4
{\displaystyle x_{4}}
преобразуются нелинейными функциями
f
0
{\displaystyle f_{0}}
,
f
1
{\displaystyle f_{1}}
,
f
2
{\displaystyle f_{2}}
,
f
3
{\displaystyle f_{3}}
,
f
4
{\displaystyle f_{4}}
, которые образуют блок подстановки. Значения этих функций линейно смешиваются с пятью выходными битами
d
0
{\displaystyle d_{0}}
,
d
1
{\displaystyle d_{1}}
,
d
2
{\displaystyle d_{2}}
,
d
3
{\displaystyle d_{3}}
,
d
4
{\displaystyle d_{4}}
счетчика-диффузора и возвращаются обратно в состояние регистра в
x
p
0
{\displaystyle x_{p0}}
,
x
p
1
{\displaystyle x_{p1}}
,
x
p
2
{\displaystyle x_{p2}}
,
x
p
3
{\displaystyle x_{p3}}
,
x
p
4
{\displaystyle x_{p4}}
соответственно. Биты
x
5
{\displaystyle x_{5}}
,
x
6
{\displaystyle x_{6}}
,
x
7
{\displaystyle x_{7}}
,
x
8
{\displaystyle x_{8}}
,
x
9
{\displaystyle x_{9}}
линейно смешивают со значениями следующих пяти функций с обратной связью
f
5
{\displaystyle f_{5}}
,
f
6
{\displaystyle f_{6}}
,
f
7
{\displaystyle f_{7}}
,
f
8
{\displaystyle f_{8}}
,
f
9
{\displaystyle f_{9}}
и с пятью битами счетчика-диффузора
d
5
{\displaystyle d_{5}}
,
d
6
{\displaystyle d_{6}}
,
d
7
{\displaystyle d_{7}}
,
d
8
{\displaystyle d_{8}}
,
d
9
{\displaystyle d_{9}}
и возвращаются в состояние регистра в
x
p
5
{\displaystyle x_{p5}}
,
x
p
6
{\displaystyle x_{p6}}
,
x
p
7
{\displaystyle x_{p7}}
,
x
p
8
{\displaystyle x_{p8}}
,
x
p
9
{\displaystyle x_{p9}}
соответственно. Биты от
x
10
{\displaystyle x_{10}}
до
x
M
+
9
{\displaystyle x_{M+9}}
линейно смешиваются с значениями функций
f
10
{\displaystyle f_{10}}
,…,
f
M
+
9
{\displaystyle 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
≤
j
<
5
{\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}
;
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
≤
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}+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
≤
j
<
W
{\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}
;
Режимы работы
[править | править код]Загрузка ключа
[править | править код]Перед генерацией ключевого потока, шифрованием данных или хешированием шифр работает в режиме загрузки ключа, состоящий из
R
0
=
F
+
16
{\displaystyle R_{0}=F+16}
раундов, где
F
{\displaystyle 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
,
{\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},}
c
i
r
+
1
1
=
0
,
i
f
r
+
i
<
15
,
{\displaystyle c_{i}{}^{r+1}{}_{1}\ =\ 0,ifr+i<15,}
c
i
r
+
1
1
=
c
i
r
0
+
k
r
+
i
−
15
,
i
f
15
≤
r
+
i
<
F
+
15
,
{\displaystyle c_{i}{}^{r+1}{}_{1}\ =\ c_{i}{}^{r}{}_{0}+k_{r+i-15},if15\leq r+i<F+15,}
c
i
r
+
1
1
=
1
,
i
f
r
+
i
=
F
+
15
,
{\displaystyle c_{i}{}^{r+1}{}_{1}\ =\ 1,ifr+i\ =\ F+15,}
c
i
r
+
1
1
=
0
,
i
f
F
+
15
<
r
+
i
,
{\displaystyle c_{i}{}^{r+1}{}_{1}\ =\ 0,ifF+15<r+i,}
c
i
r
+
1
j
=
c
i
r
+
1
j
−
1
,
2
≤
j
<
B
i
,
0
≤
i
<
16
;
{\displaystyle 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
≤
j
<
5
{\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}
;
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
≤
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}+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
≤
j
<
W
{\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}
;
0
≤
r
<
R
0
.
{\displaystyle 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
,
{\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},}
c
i
r
+
1
1
=
c
i
r
0
+
k
(
r
−
R
a
)
∗
8
+
i
,
{\displaystyle 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
≤
j
<
B
i
,
0
≤
i
<
8
;
{\displaystyle 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
,
{\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},}
c
i
r
+
1
j
=
c
i
r
j
−
1
,
2
≤
j
<
B
i
,
0
≤
i
<
16
;
{\displaystyle 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
≤
j
<
5
{\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}
;
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
≤
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}+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
≤
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}+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
≤
j
<
W
{\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}
;
R
a
≤
r
<
R
b
.
{\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
