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

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

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

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

Алгоритм преобразования ключа и (дополнительно) вектора инициализации в 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

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

Генерация выходной ключевой последовательности .
Для генерации 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 степени 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) – один из вариантов перестановки {0,1,2,3,4}

x	0	1	2	3	4
P(x)	3	0	4	1	2
VMPC 1 (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 является вычислительно сложной задачей .
Например, при 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}}$ что совпадает с соответствующей вероятностью идеального генератора случайной последовательности . ${\displaystyle N}$ -  число разрядов внутреннего состояния генератора псевдослучайной последовательности, обычно равно ${\displaystyle 8}$ . В 2005 году А. Максимов показал, что на основании ${\displaystyle 2^{40}}$ выходных бит возможно отличить последовательность генератора VMPC от случайного потока

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

• каждого из возможных ${\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 . В то же время, безопасность большинства потоковых шифров практически сводится к нулю при использовании одного и того же ключа для зашифрования различных открытых текстов. В таком случае потоковый шифр уже не является генератором одноразового блокнота (потока случайных бит для зашифрования открытого текста). Данная проблема шифром VMPC в некотором роде решается использованием уникального вектора инициализации для каждого зашифрованного потока.

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

Ссылки

• Bartosz Zoltak (недоступная ссылка)

См. также

• RC4

Литература