VMPC

VMPC (англ. Variably Modified Permutation Composition) — это потоковый шифр^[1], применяющийся в некоторых системах защиты информации в компьютерных сетях. Шифр разработан криптографом Бартошем Жултаком (пол. Bartosz Żółtak,англ. Bartosz Zoltak) в качестве усиленного варианта популярного шифра RC4. Алгоритм VMPC строится как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов. Основные преимущества шифра, как и RC4 — высокая скорость работы, переменный размер ключа и вектора инициализации (от 128 до 512 бит включительно), простота реализации (буквально несколько десятков строк кода).^[2]

Основа шифра - генератор псевдослучайных чисел^[3], базой которого является односторонняя необратимая функция VMPC (англ. Variably Modified Permutation Composition):

Реализация алгоритма

Ключевое расписание

Алгоритм преобразования ключа^[2] и (дополнительно) вектора инициализации в 256-элементную перестановку P. Инициализация глобальной переменной s.

С : Длина ключа в байтах ${\displaystyle (16\leq c\leq 64)}$

K : Ключ

z : Длина вектора инициализации в байтах ${\displaystyle (16\leq z\leq 64)}$

V : Вектор инициализации

i : 8-разрядная переменная

j : 16-разрядная переменная

s : 8-разрядная глобальная переменная

P : таблица из 256 байт для хранения перестановок

1.  s = 0
2.  for i = 0 to 255: P[i] = i

3.  for j = 0 to 767 // выполнить пп. 4-6:
	4.  i = j mod 256
	5.  s = P[(s + P[i] + K[j mod c]) mod 256]
	6.  Temp = P[i]
  	    P[i] = P[s]
  	    P[s] = Temp

7.   Если используется преобразование вектора инициализации 
	for j = 0 to 767 // выполнить пп. 8-10:
8.  i = j mod 256
9.  s = P[(s + P[i] + V[j mod z]) mod 256]
10. Temp = P[i]
    P[i] = P[s]
    P[s] = Temp

Алгоритм зашифрования

Генерация выходной ключевой последовательности^[2].
Для генерации L байт выходного ключевого потока выполняются следующие операции:

L : длина ключевой последовательности в байтах

1. i = 0
2. Повтор пп. 3-6 L раз:
	3. s = P[(s + P[i]) mod 256]
	4. Output = P[(P[P[s]] + 1) mod 256]
	5. Temp = P[i]
  	   P[i] = P[s]
  	   P[s] = Temp
	6. i = (i + 1) mod 256

Реализация генератора псевдослучайных чисел

Односторонняя функция VMPC (англ. Variably Modified Permutation Composition)

Функция VMPC^[2] степени k < n над n-элементным множеством   x∈A,   A = {0,1,…n-1}:

 for x = 0 to n-1:  Qk(x) = VMPCk(P(x)) = P(Pk(Pk-1(…(P1(P(x)))…)))

Где P: A → A взаимно однозначная n-элементная перестановка
P_i (x)   n-элементная перестановка,
P_i = f_i (P(x)),   P_i(x) ≠ P(x) ≠ P_j (x),   i≠j   i,j∈{1,2…k}
f_i (x) = (x + i) mod n ,

Функция VMPC 1 степени Q₁ (x)= VMPC₁ (P(x) )=P(P(P(x))+1)

Функция VMPC 2 степени Q₂ (x)= VMPC₂ (P(x))=P(P(P(P(x))+1)+2)

Функция VMPC 3 степени Q₃ (x)= VMPC₃ (P(x))=P(P(P(P(P(x))+1)+2)+3)

Пример расчета функции VMPC 1 степени

P(x) – один из вариантов^[2] перестановки {0,1,2,3,4}

x	0	1	2	3	4
P(x)	3	0	4	1	2
VMPC1 (P(x))	4	2	1	0	3

VMPC₁ (P(x))=P(P(P(x)) + 1)

x = 0

P(0) = 3

P(P(0)) = 1

P(P(0)) + 1 = 2

P(P(P(0) + 1)) = 4

VMPC₁ (P(0)) = 4

Поиск обратного значения функции VMPC

Нахождение обратного значения функции VMPC является вычислительно сложной задачей^[2].
Например, при n = 256 для вычисления обратного значения функции VMPC₁ требуется ${\displaystyle 2^{260}}$ операций, для VMPC₂ - ${\displaystyle 2^{420}}$ , для VMPC₃ - ${\displaystyle 2^{550}}$.

Алгоритм

Восстановление n − элементной перестановки P, соответствующей значению Q(X)= VMPC_k (P(X)). 

X, Y − временные переменные 

Для элемента P(x) = y вводятся следующие обозначения: 

X − аргумент: base или parameter

Y − значение: parameter или base соответственно

Пример: для элемента P(0) = 3: если аргумент 0 – parameter, то значение 3 – base. 

Алгоритм: 

1. Для произвольного значения X ∈ {0,1,…n-1} и Y ∈ {0,1,…n-1} найти один элемент перестановки P из предположения P(X) = Y. 
   1. В случайном порядке выбирается: является ли X – parameter, Y − base, или X – base, Y − parameter элемента P(X) = Y. P(X) = Y − текущий элемент перестановки P. 
2. Найти все элементы перестановки P по алгоритму поиска.
3. Если все n  элементов перестановки найдены без противоречий, то завершить алгоритм.
4. Иначе
   1. Найти новый элемент перестановки по алгоритму отбора, P(X) = Y − текущий элемент перестановки.
   2. Сохранить parameter текущего элемента перестановки.
   3. Перейти к п. 2.
5. Если при выполнении п. 2. возникает противоречие:
   1. Удалить все найденные при выполнении п. 2. элементы перестановки P
   2. Для текущего элемента перестановки P: parameter = (parameter + 1) mod n,
   3. Если parameter принимает значение, сохраненное при выполнении п. 4.2 , то:
      1. удалить текущий элемент перестановки P.
      2. за текущий элемент перестановки принять значение, полученное при выполнении п. 1.
      3. перейти к п. 5.1.
6. Перейти к п.2.

Алгоритм поиска

Нахождение всех возможных элементов перестановки P по заданному Q и уже найденным элементам перестановки P.

D, C − временные переменные

Обозначения:

statement y − последовательность y из k + 2 элементов перестановки P, использованных для вычисления Q(y).

word x последовательности y −элемент последовательности y под номером x.

Алгоритм:

1. C = 0; D = 0;
2. Если известен элемент P:
   1. Если элемент P(D) и k других известных элементов удовлетворяют общей схеме k + 1 элементов любой последовательности statement, то найти оставшееся word этой последовательности
   2. Если найденное word не является известным элементом P
      1. Обозначить найденное word как элемент P
      2. С = 1
   3. Если найденное word противоречит какому-либо из найденных ранее элементов, сообщить об ошибке, завершить алгоритм поиска.
3. D = D + 1
4. Если D < n перейти к п.2
5. Если C = 1 перейти к п.1.

Алгоритм отбора

Выбор такого нового элемента перестановки P, вычисление которого позволит найти максимальное количество элементов P на последующих шагах алгоритма нахождения обратного значения функции VMPC_k. В результате выполнения алгоритма отбора определяется base нового элемента и произвольно выбирается его значение parameter. Данный алгоритм подходит для случая k<4.

B, R − временные переменные

T_a, T_v − временные массивы

W[j] − массив чисел

Алгоритм:

1. Инициализация переменных
   1. T_a = 0 , T_v = 0
   2. B = 0
   3. R = 1
2. Подсчет количества m известных элементов перестановки, которые являются word в последовательности statement, в которой неизвестный элемент P является word R c аргументом B. T_a = T_a + W[m]
3. Подсчет количества m известных элементов перестановки P, которые являются word в последовательности statement, в которой неизвестный элемент P является word R со значением B. T_v = T_v + W[m]
4. R = R + 1
5. Если R < n перейти к п.2.
6. B = B + 1
7. Если B < n перейти к п.1.c.
8. Выбирается значения index − любой из индексов массивов T_a или T_v, при котором значение, хранимое в ячейке массива максимально.
9. Если в п.8 выбран index массива T_a, то:
   1. X = index
   2. Случайно выбирается Y ∈ {0,1,…n-1}, такой что элемент перестановки со значением Y еще не найден.
   3. Результат: P(x) = Y X − base, Y – parameter
10. Если в п.8 выбран index массива T_v , то:
    1. Y = index
    2. Случайно выбирается X ∈ {0,1,…n-1}, такой что элемент перестановки со значением X еще не найден.
    3. Результат: P(x) = Y X – parameter, Y − base

Особенности

Вероятность получения двух последовательных одинаковых результатов при генерации ключевой последовательности при использовании шифра VMPC равна ${\displaystyle 2^{-N}}$ что совпадает с соответствующей вероятностью идеального генератора случайной последовательности^[2].  ${\displaystyle N}$ -  число разрядов внутреннего состояния генератора псевдослучайной последовательности, обычно равно ${\displaystyle 8}$. В 2005 году А. Максимов показал, что на основании ${\displaystyle 2^{40}}$ выходных бит возможно отличить последовательность генератора VMPC от случайного потока ^[4]

 Эксперименты, проведенные Б.Жултаком, показали, что не наблюдается статистически значимого отклонения вероятности появления в выходной последовательности:

• каждого из возможных ${\displaystyle 2^{8}}$   значений (${\displaystyle P=1/256}$   для ${\displaystyle 2^{41.85}}$   байт выходной последовательности);
• каждой из возможных ${\displaystyle 2^{16}}$   пар последовательных значений  (${\displaystyle P=1/65536}$   для ${\displaystyle 2^{40.1}}$   байт выходной последовательности);
• каждой из возможных ${\displaystyle 2^{24}}$   троек последовательных значений (${\displaystyle P=1/16777216}$   для ${\displaystyle 2^{41.6}}$   байт выходной последовательности)

Безопасность

Утверждается, что потоковый шифр, благодаря значительной модификации исходного RC4 с учетом его уязвимостей, более устойчив к существующим атакам на потоковые шифры и атакам на шифр RC4^[2]. В то же время, безопасность большинства потоковых шифров практически сводится к нулю при использовании одного и того же ключа для зашифрования различных открытых текстов. В таком случае потоковый шифр уже не является генератором одноразового блокнота (потока случайных бит для зашифрования открытого текста). Данная проблема шифром VMPC в некотором роде решается использованием уникального вектора инициализации для каждого зашифрованного потока.

Утверждается, что сложность атаки на шифр составляет ${\displaystyle 2^{900}}$ операций^[2]. Однако, существует метод, защищающий алгоритм от возможных уязвимостей. Данный подход заключается в повторении зависимой от ключа перестановки два раза: до и после перестановки, зависимой от вектора инициализации. Данное ключевое расписание именуется KSA3.

Ссылки

• VMPC Stream Cipher
• Спецификация VMPC
• Bartosz Zoltak VMPC One-Way Function and Stream Cipher (недоступная ссылка)

См. также

• RC4

Литература

1. Габидулин Э.М., Кшевецкий А.С., Колыбельников А.И. Защита информации (рус.). — Москва: МФТИ, 2011. — P. 225.
2. Zoltak B. VMPC One-Way Function and Stream Cipher (англ.) // Bimal R., Meier W. Fast Software Encryption. — Berlin: Springer Berlin Heidelberg, 2004. — P. 210-225. — ISBN 978-3-540-25937-4. — doi:10.1007/978-3-540-25937-4_14. Архивировано 23 апреля 2018 года.
3. Шнайер Б. Практическая криптография (рус.). — Москва: 2-е изд. — М.: Вильямс, 2005. — P. 610.
4. Goutam P., Subhamoy M. RC4 stream cipher and its variants (англ.). — Boca Raton, FL: CRC Press, 2012. — ISBN 978-1-4398-3135-9.