VMPC () — это потоковый шифр, применяющийся в некоторых системах защиты информации в компьютерных сетях. Шифр разработан криптографом Бартошем Жултаком (,) в качестве усиленного варианта популярного шифра RC4. Алгоритм VMPC строится как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов. Основные преимущества шифра, как и RC4 — высокая скорость работы, переменный размер ключа и вектора инициализации (от 128 до 512 бит включительно), простота реализации (буквально несколько десятков строк кода).
Основа шифра - генератор псевдослучайных чисел, базой которого является односторонняя необратимая функция VMPC ():
Реализация алгоритма
Ключевое расписание Алгоритм преобразования ключа и (дополнительно) вектора инициализации в 256-элементную перестановку P. Инициализация глобальной переменной s.
С : Длина ключа в байтах
K : Ключ
z : Длина вектора инициализации в байтах
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} x 0 1 2 3 4 P(x) 3 0 4 1 2 VMPC1 (P(x)) 4 2 1 0 3
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 требуется операций, для VMPC2 - , для VMPC3 - .
Алгоритм
Восстановление 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 равна что совпадает с соответствующей вероятностью идеального генератора случайной последовательности. - число разрядов внутреннего состояния генератора псевдослучайной последовательности, обычно равно . В 2005 году А. Максимов показал, что на основании выходных бит возможно отличить последовательность генератора VMPC от случайного потока
Эксперименты, проведенные Б.Жултаком, показали, что не наблюдается статистически значимого отклонения вероятности появления в выходной последовательности:
каждого из возможных значений ( для байт выходной последовательности); каждой из возможных пар последовательных значений ( для байт выходной последовательности); каждой из возможных троек последовательных значений ( для байт выходной последовательности)
Безопасность Утверждается, что потоковый шифр, благодаря значительной модификации исходного RC4 с учетом его уязвимостей, более устойчив к существующим атакам на потоковые шифры и атакам на шифр RC4. В то же время, безопасность большинства потоковых шифров практически сводится к нулю при использовании одного и того же ключа для зашифрования различных открытых текстов. В таком случае потоковый шифр уже не является генератором одноразового блокнота (потока случайных бит для зашифрования открытого текста). Данная проблема шифром VMPC в некотором роде решается использованием уникального вектора инициализации для каждого зашифрованного потока.
Утверждается, что сложность атаки на шифр составляет операций. Однако, существует метод, защищающий алгоритм от возможных уязвимостей. Данный подход заключается в повторении зависимой от ключа перестановки два раза: до и после перестановки, зависимой от вектора инициализации. Данное ключевое расписание именуется KSA3.
Ссылки VMPC Stream Cipher Спецификация VMPC Bartosz Zoltak VMPC One-Way Function and Stream Cipher
См. также RC4
Литература
Категория:Потоковые шифры