VMPC

19.12.2020

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

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

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

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

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

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

K : Ключ

z : Длина вектора инициализации в байтах ( 16 ≤ z ≤ 64 ) {displaystyle (16leq zleq 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-элементная перестановка
Pi (x) n-элементная перестановка,
Pi = fi (P(x)), Pi(x) ≠ P(x) ≠ Pj (x), i≠j i,j∈{1,2…k}
fi (x) = (x + i) mod n ,

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

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

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

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

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

VMPC1 (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

VMPC1 (P(0)) = 4

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

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

Алгоритм

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

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

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

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

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

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

Алгоритм:

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

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

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

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

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

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

    Алгоритм:

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

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

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

    Ta, Tv − временные массивы

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

    Алгоритм:

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

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

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

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

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

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

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


    Имя:*
    E-Mail:
    Комментарий: