VMPC One-Way Function and VMPC Encryption Technology by Bartosz Zoltak

Short cycles

Analysis of cycle lengths for scaled-down variants of the VMPC Stream Cipher suggests that probability of entering a short cycle by the Cipher is approximately in line with a random permutation model, e.g. that probability of entering a cycle no longer than 2^1000 is about 1 / 2^700.

Probability of entering a cycle no longer than X for an n-element random permutation is equal X/n (following Donald Knuth's "The Art of Computer Programming", vol. 1, section 1.3.3. exercise 17).

To compare cycle lengths in the output of the VMPC Stream Cipher to a random permutation, the Cipher was scaled-down to use N element internal permutations, for N from 4 to 10.

The total number of possible states of the cipher is determined by all possible configurations of the internal permutation P and variables s and n and is equal N! * N * N.

Cycles of the following lengths occur for the scaled-down-to-N variants of the Cipher:

N=4: 200; 88; 40; 36; 12; 8;
N!*N*N=384. Sum of cycle lengths=384

N=5: 1,860; 640; 295; 110; 45; 25; 20; 5;
N!*N*N=3,000. Sum of cycle lengths=3,000

N=6: 15,510; 5,580; 2,508; 936; 516; 510; 252; 90; 12; 6;
N!*N*N=25,920. Sum of cycle lengths=25,920

N=7: 215,089; 23,821; 3,990; 2,485; 1,015; 392; 70; 56; 28; 14;
N!*N*N=246,960. Sum of cycle lengths=246,960

N=8: 2,401,728; 79,504; 53,512; 42,120; 2,136; 1,032; 288; 96; 24; 16 (2 different cycles of length 16 possible); 8;
N!*N*N=2,580,480. Sum of cycle lengths=2,580,480

N=9: 20,355,471; 2,908,098; 2,728,890; 1,359,855; 949,725; 609,174; 299,592; 125,091; 27,306; 13,068; 6,219; 5,067; 2,853; 2,538; 180; 90; 18 (3 different cycles of length 18 possible); 9;
N!*N*N=29,393,280. Sum of cycle lengths=29,393,280

N=10: 113,748,840; 99,425,590; 75,813,290; 37,178,940; 20,169,740; 9,955,030; 3,239,140; 2,349,150; 572,500; 363,830; 45,520; 8,730; 7,520; 700; 390; 370; 40 (17 different cycles of length 40 possible); 20; 10 (2 different cycles of length 10 possible);
N!*N*N=362,880,000. Sum of cycle lengths=362,880,000

The observed cycle lengths don't show an appreciable difference from a random N!*N*N-element permutation model.

We conjecture from this that probability of entering a cycle no longer than X by the VMPC Stream Cipher is approximately equal X / (256!*256*256).

An example estimate is that probability that the VMPC Stream Cipher will enter a cycle no longer than 2^1000 is about 1 / 2^700.

by Bartosz Zoltak