Re: VMPC

On Wed, 28 Mar 2007 21:50:02 -0500, Mike Amling <nospam@xxxxxxxxxx>
wrote:

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

This is some of the stuff I was hoping to gleen.

Thanks, Mike.
.