
Analysis of cycle lengths for scaleddown 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 nelement 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 scaleddown
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 scaleddowntoN 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*Nelement
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



Copyright © 19992018 by Bartosz Zoltak

