Variably Modified Permutation Composition: Difference between revisions

Revision as of 11:15, 13 March 2016

Latest revision as of 10:22, 8 October 2024

(26 intermediate revisions by 19 users not shown)

Line 1:

{{Short description|Stream cipher}}

{{context|date=October 2009}}

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

'''VMPC'''well known ('''Variablyand Modifiedpopular Permutationcipher Composition''')[[RC4]] isdesigned aby [[streamRon cipherRivest]]. It technologywas designed by Bartosz ZoltakŻółtak, presented in 2004 at the [[Fast Software Encryption]] conference. VMPC is a modification of the [[RC4]] cipher.<ref name=maximov>{{cite paperjournal |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 confernececonference)</ref>

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

'''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.<ref name=maximov>{{cite paper |title=Two Linear Distinguishing Attacks on VMPC and RC4A and Weakness of RC4 Family of Stream Ciphers (Corrected) |author=Alexander Maximov |date=2007-02-22 |url=https://eprint.iacr.org/2007/070 }} (originally presented at FSE 2006 confernece)</ref>

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

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

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

The function was designed such that inverting it, i.e. obtaining {{mono|f}} from {{mono|g}}, would 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}}

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

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 paperweb|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|accessdateaccess-date=9 February 2015}}</ref>

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|date=September 2015}}

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

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 paper|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|accessdate=9 February 2015}}</ref>

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

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. ni := 0

'''while''' GeneratingOutput:

j := S[j + S[i]]

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

i := i + 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).

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).

==References==

Line 34 ⟶ 37:

* [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

[[Category:Cryptography]]

* 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:CryptographyStream ciphers]]

{{Crypto-stub}}