Variably Modified Permutation Composition: Difference between revisions

Revision as of 11:27, 12 December 2010

Latest revision as of 10:22, 8 October 2024

(45 intermediate revisions by 33 users not shown)

Line 1:

{{Short description|Stream cipher}}

{{Multiple issues|orphan =February 2009|context =October 2009|unreferenced =May 2007}}

'''VMPC''' ('''Variably Modified Permutation Composition''') for [[cryptography]] is a [[stream cipher]] similar to the

{{mergeto|Variably modified permutation composition}}

well known and popular cipher [[RC4]] designed by [[Ron Rivest]]. It was designed by Bartosz Żółtak, presented in 2004 at the [[Fast Software Encryption]] conference. VMPC is a modification of the [[RC4]] cipher.<ref name=maximov>{{cite journal |title=Two Linear Distinguishing Attacks on VMPC and RC4A and Weakness of RC4 Family of Stream Ciphers (Corrected) |author=Alexander Maximov |journal=Cryptology ePrint Archive |date=2007-02-22 |url=https://eprint.iacr.org/2007/070 }} (originally presented at FSE 2006 conference)</ref>

The VMPCcore functionof the cipher is the VMPC function, a transformation of ''n''-element [[permutation]]s defined as:

'''VMPC''' ("Variably Modified Permutation Composition") is [[encryption]] technology designed by Bartosz Zoltak, publicly presented in 2004 at an international [[cryptography]] conference Fast Software Encryption in [[Delhi, India]].

'''for''' x '''from''' 0 '''to''' n-1:

The core of the technology is the VMPC one-way function, applied in an encryption [[algorithm]] - the VMPC stream cipher.

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

InterestinglyThe invertingfunction thewas functiondesigned such that inverting it, i.e. obtaining {{mono|f}} from {{mono|g}}, appears towould be a complex problem. According to computer simulations the average number of operations required to recover {{mono|f}} from {{mono|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|date=September 2015}}

The VMPC function is a transformation of n-element [[permutation]]s defined as:

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".<ref name="Kulesza2006">{{cite web|last1=Kulesza|first1=Kamil|date= 2008-10-27|title=On Inverting the VMPC One-Way Function|url=http://www-old.newton.ac.uk/preprints/NI06009.pdf|access-date=9 February 2015}}</ref>

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

The VMPC one-way function is used in an [[encryption]] algorithm -– the VMPC Stream Cipher (see what a [[stream cipher]] is. The algorithm isallows veryfor efficient in software implementations; to (encrypt {{mono|L}} bytes of plaintext do):

Interestingly 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²⁶⁰.

<span style="color: green;">''All arithmetic is performed modulo 256.''</span>

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

i := 0

'''while''' GeneratingOutput:

P[n]j := PS[sj + S[i]]

1. n = 0

'''output''' S[S[S[j]] + 1]

swap S[i] and S[j] <span style="color: green;">(''b := S[j]; S[j] := S[i]; S[i] := b)'')</span>

P[s]i := Tempi + 1

'''endwhile'''

Where 256-element permutation {{mono|P}} and integer value {{mono|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.

In 2006 at Cambridge University Kamil Kulesza published a paper "On inverting the VMPC one-way function", which investigated the issue but it left the problem open - the one-wayness of the function was neither proved nor denied.

==References==

The VMPC one-way function is used in an [[encryption]] algorithm - the VMPC Stream Cipher (see what a [[stream cipher]] is. The algorithm is very efficient in software implementations (encrypt L bytes of plaintext do):

{{reflist}}

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==

* [http://www.vmpcfunction.com/ VMPC Homepage]

* [http://www.okna.wroc.pl/vmpc.pdf Original conference paper on VMPC from okna wrocław (PDF)]

* [http://talks.cam.ac.uk/talk/index/4950/ Kamil Kulesza: On inverting the VMPC one-way function]

* [http://cartman-cipher.narod.ru/mirror/vmpcksa3.zip Unofficial C implementation of VMPC Stream cipher]

* [http://cartman-cipher.narod.ru/mirror/vmpclib.dpr 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

{{Uncategorized stub|date=September 2010}}

* 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

[[Category:Stream ciphers]]

{{Crypto-stub}}

{{cryptography navbox | stream}}

[[pl:VMPC]]

[[ru:VMPC]]