Variably Modified Permutation Composition

VMPC (Variably Modified Permutation Composition) for cryptography is a stream cipher similar to the well known and popular cipher RC4 designed by Ron Rivest.^[1] It was designed by Bartosz Żółtak, presented in 2004 at the Fast Software Encryption conference.

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

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

The function was designed such that inverting it, i.e. obtaining f from g, would 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²⁶⁰.^{[citation needed]}

In 2006 at Cambridge University, Kamil Kulesza investigated the problem of inverting VMPC and concluded "results indicate that VMPC is not a good candidate for a cryptographic one-way function".^[2]

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:

All arithmetic is performed modulo 256.
i := 0
while GeneratingOutput:
    j := S[j + S[i]]
    
    output S[S[S[j]] + 1]
    swap S[i] and S[j]          (b := S[j]; S[j] := S[i]; S[i] := b))
    
    i := i + 1
endwhile

Where 256-element permutation P and integer value s are obtained from the encryption password using the VMPC-KSA (Key Scheduling Algorithm).

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

• https://eprint.iacr.org/2013/768.pdf VMPC-R: Cryptographically Secure Pseudo-Random Number Generator Alternative to RC4
• https://eprint.iacr.org/2014/985.pdf Statistical weakness in Spritz against VMPC-R: in search for the RC4 replacement
• https://eprint.iacr.org/2014/315.pdf Statistical weaknesses in 20 RC4-like algorithms and (probably) the simplest algorithm free from these weaknesses - VMPC-R
• https://eprint.iacr.org/2019/041.pdf Message Authentication (MAC) Algorithm For The VMPC-R (RC4-like) Stream Cipher