Re: VMPC

fortune.bruce@xxxxxxxxx wrote:
On Mar 26, 1:18 pm, "Wei Dai" <use...@xxxxxxxxxx> wrote:
"Bartosz Wójcik" <antis...@xxxxxxxxxxx> wrote in message

news:7knk5cdpbqld$.6zptv4ujnor.dlg@xxxxxxxxxxxxx

What do you think about VMPC encryption?

It is not a substitute for AES. But it is a wicked fast streaming
algorithm that may have use.

It is interestingly simple and elegant, like RC4.

VMPC isn't very secure. Seehttp://www.it.lth.se/movax/Publications/2005/vmpc.pdf.

It may not be very secure, but it may be secure enough.

This article talks about a distinguisher of VMPC from random after
observing 2^54 output bytes of data.

Alexander Maximov's paper attacks only what Bartosz Zoltak in the original VMPC paper called level one. BZ hoped that if level one were broken, levels two and higher might still be secure. To get level two, replace P[(P[P[s]]+1)%modulus] in the algorithm with P[(P[(P[P[s]]+1)%modulus]+2)%modulus], which admittedly slows it down somewhat.
To derive Maximov's epsilon_min for VMPC level two, it looks to me like you'd replace 9 with 10 in Maximov's proof of Theorem 1, since one more value, P[P[P**2[j]+1]+2], to use Maximov's notation, gets defined in his Algorithm 1. I believe that leaves delta_min still at 128 (since (256-1)*...(256-10)+delta_min==0 mod 256 for delta_min=128). That makes the level two epsilon_min equal to 1/247 times the level one epsilon_min. (2**-56.8)/247=2**-64.7.

Of course, Maximov's paper does not take into account VMPC's initialization procedure of the array from the key, which conceivably (I'm not saying believe it, just that at this point it's conceivable.) could reduce the bias, since the probability of any particular initial array contents would be a multiple of 2**-k (assuming a k-bit binary key), not 1/(256!), which obviates part 1 of the proof of Theorem 1.

Note: I haven't looked at Maximov's Theorem 2 for VMPC level two.

--Mike Amling
.

Relevant Pages

  • Re: VMPC isnt free
    ... > Tom St Denis wrote: ... >>Companies willing to use the VMPC function, ... > the algorithm and revealed it publicly. ...
    (sci.crypt)
  • Re: About VMPC
    ... surprises for not well analized features of the cypher. ... > will list you at the VMPC website as a self-made implementation user. ... both in the stream and in the KSA. ... I would like to do some more tests about streams and KSAs of algorithm ...
    (sci.crypt)
  • Re: Paper - impossible to prove P=?NP
    ... Even if one could prove that any algorithm solving VMPC based on systematic ... step back when an impossibility arise) is necessarily exponential in n ... it appears a reasonable proposition that the best-scoring value for each ...
    (sci.crypt)
  • Re: VMPC isnt free
    ... > Companies willing to use the VMPC function, ... And I hoe the cipher will receive a fair evaluation, ... the algorithm and revealed it publicly. ... There are some statistical tests on the cipher currently in progress and ...
    (sci.crypt)
  • About VMPC
    ... Some days ago i looked at the documentation about VMPC, ... interesting since add further levels of non linearity compared to RC4 ... is a 257-byte array indexed by numbers from 0 to 256, ... about 256**212 so keys up to 212 bytes would teorically have sense, ...
    (sci.crypt)