Variably Modified Permutation Composition

VMPC (Variably Modified Permutation Composition) is a stream cipher technology designed by Bartosz Zoltak, presented in 2004 at the Fast Software Encryption conference. VMPC is a modification of the RC4 cipher.

The core of the cipher is the VMPC function, a transformation of n-element permutations defined as:

for x from 0 do n-1:  g(x) = VMPC(f)(x) = f(f(f(x))+1)

Inverting the function, i.e. obtaining f from g appears to be a complex problem. According to computer simulations the average number of operations required to recover f from g for a 16-element permutation is about 2¹¹, for 64-element permutation - about 2⁵³ and for a 256-element permutation - about 2²⁶⁰.

Theoretically speaking - if these results were possible to be proved - it would imply that VMPC is a true one way function, which would solve the famous P vs NP problem.

In 2006 at Cambridge University Kamil Kulesza published a paper that investigates the problem of inverting VMPC. The paper concluded that "results indicate that VMPC is not a good candidate for a cryptographic one-way function".

The VMPC function is used in an encryption algorithm - the VMPC stream cipher. The algorithm allows for efficient in software implementations; to encrypt L bytes of plaintext do:

1. n = 0
2. Repeat steps 3-6 L times:
3. s = P[ (s + P[n]) mod 256 ]
4. Output = P[ (P[P[s]]+1) mod 256 ]
5. Temp = P[n]
   P[n] = P[s]
   P[s] = Temp
6. n = (n + 1) mod 256

Where 256-element permutation P and integer value s are obtained from the encryption password using the VMPC-KSA (Key Scheduling Algorithm), which can be found at the VMPC Homepage along with the VMPC-MAC (Message Authentication Code) allowing to authenticate messages encrypted with the VMPC Stream Cipher.

External links

• VMPC Homepage
• Original conference paper on VMPC from okna wrocław (PDF)
• Kamil Kulesza: On inverting the VMPC one-way function
• Unofficial C implementation of VMPC Stream cipher
• Unofficial Delphi implementation of VMPC Stream cipher