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

VMPC-R Cryptographically Secure Pseudo-Random Number Generator
1. VMPC-R CSPRNG general description 2. VMPC-R Algorithm 3. VMPC-R Key Scheduling Algorithm 4. Test output of VMPC-R 5. Authenticated encryption with VMPC-R (VMPC-R-MAC) Download VMPC-R CSPRNG Implementation: VMPC-R Implementation in C VMPC-R Implementation in Pascal/Delphi VMPC-R Implementation in Assembler	Download VMPC-R paper VMPC-R.pdf (260 KB) The paper is also available at the IACR ePrint archive Download VMPC-R-MAC paper VMPC-R-MAC.pdf (260 KB) The paper is also available at the IACR ePrint archive

1. VMPC-R Cryptographically Secure Pseudo-Random Number Generator

The VMPC-R CSPRNG was designed to produce a stream of values as close to the random model as possible and to have a large period. The algorithm's internal state for the common-in-practical-applications 8-bit word size is 256!²*256⁷=2³⁴²⁴.

The main statistical test we used to analyse the algorithm:

Distinguished the output of the popular RC4 stream cipher from randomness after 2^16.6 3-bit outputs.

Did not distinguish the output of VMPC-R from randomness after 2^46.8 3-bit outputs.

For smaller than 3-bit word sizes VMPC-R produced undistinguishable from random output after exhausting:

98% of the state-space (twelve 42-output-long cycles) operating on integers {0,1} (single-bit mode)

62% of the state-space (longest cycle) operating on integers {0,1,2}.

82% of the state-space (longest cycle) operating on integers {0,1,2,3} (2-bit mode).

33% of the state-space (longest cycle) operating on integers {0,1,...,5}.

78% of the state-space (longest cycle) operating on integers {0,1,...,6}.

10% of the state-space (test limited by computational power, no cycle found) operating on integers {0,1,...,7}.

No statistical anomalies were found in the shorter cycles for the quoted above 2,3,4,5,6 word sizes, either.

We tested the output of the VMPC-R algorithm in many other statistical tests for many different word sizes and found no way of distinguishing it from a truly random source. For the detailed description of the tests please refer to the VMPC-R paper

The VMPC-R algorithm generates a stream of pseudorandom integers from two N-element permutations (usually N=256 and the generated integers are 8-bit). The initial state of the permutations is determined by the VMPC-R Key Scheduling Algorithm described in section 3.

The VMPC-R algorithm can be used either as a pseudo-random number generator and as a stream cipher where its outputs are xored with the consecutive plaintext bytes.

2. VMPC-R algorithm:

	N	: word size; in most practical applications N=256
	P, S	: N-element tables storing permutations of integers {0,1,...,N-1}
	a, b, c, d, e, f, n	: integer variables
	L	: number of pseudorandom integers to generate
	+	denotes addition modulo N

Table 1. VMPC-R CSPRNG pseudo code

repeat steps 1-10 L times:

   1. a = P[a + c + S[n]]
   2. b = P[b + a]
   3. c = P[c + b]

   4. d = S[d + f + P[n]]
   5. e = S[e + d]
   6. f = S[f + e]

   7. output S[S[S[c + d]] + 1]

   8. swap P[n] with P[f]
   9. swap S[n] with S[a]

  10. n = n + 1

3. VMPC-R Key Scheduling Algorithm

The VMPC-R Key Scheduling Algorithm transforms the seed (which could be a cryptographic key and an Initialization Vector) into the algorithm's internal state.

Notation: as in section 2, with:

	a, b, c, d, e, f, n
	k	: length of the seed or cryptographic key; k ∈ {1,2,...,N}
	K	: k-element table storing the seed or cryptographic key
	v	: length of the Initialization Vector; v ∈ {1,2,...,N}
	V	: v-element table storing the Initialization Vector
	i	: temporary integer variable
	R	= N * Ceiling(k²/(6N))
	+	denotes addition modulo N

Table 2. VMPC-R Key Scheduling Algorithm pseudo code

0. a = b = c = d = e = f = n = 0
P[i] = S[i] = i for i ∈ {0,1,...,N-1}

1. KSARound(K, k)
2. KSARound(V, v)
3. KSARound(K, k)
4. n = S[S[S[c + d]] + 1]
5. generate N outputs with VMPC-R CSPRNG (for L=N)

Function KSARound(M, m) definition:
  6. i = 0
  7. repeat steps 8-18 R times:
       8. a = P[a + f + M[i]] + i;   i = (i + 1) mod m
       9. b = S[b + a + M[i]] + i;   i = (i + 1) mod m
      10. c = P[c + b + M[i]] + i;   i = (i + 1) mod m
      11. d = S[d + c + M[i]] + i;   i = (i + 1) mod m
      12. e = P[e + d + M[i]] + i;   i = (i + 1) mod m
      13. f = S[f + e + M[i]] + i;   i = (i + 1) mod m

      14. swap P[n] with P[b]
      15. swap S[n] with S[e]
      16. swap P[d] with P[f]
      17. swap S[a] with S[c]

      18. n = n + 1

The KSARound function performs R = N * Ceiling(k²/(6N)) iterations. This value ensures that each word of a k-word key updates the internal state at least k times. For N = 256 and key sizes k ∈ {2,3,...,39} (keys up to 312 bits) R = N. For N = 256 and key sizes k ∈ {40,41,...,55} (keys from 320 to 440 bits) R = 2N. And so on.

4. Test output of VMPC-R

Example output of the VMPC-R CSPRNG for a given key (K) and a given initialization vector (V) are shown in Tables 3,4 and 5.

Table 3. Example output of VMPC-R

K; k=9	`{11, 22, 33, 144, 155, 166, 233, 244, 255}`
V; v=8	`{255, 250, 200, 150, 100, 50, 5, 1}`
output of KSA:
P index	`0`	`1`	`2`	`3`	`252`	`253`	`254`	`255`
P value	`97`	`218`	`106`	`125`	`139`	`86`	`36`	`126`
S index	`0`	`1`	`2`	`3`	`252`	`253`	`254`	`255`
S value	`152`	`143`	`19`	`154`	`92`	`25`	`24`	`157`
output of CSPRNG:
Output index	`0`	`1`	`2`	`3`	`254`	`255`	`256`	`257`
Output value	`49`	`161`	`79`	`69`	`85`	`237`	`96`	`243`
Output index	`1000`	`1001`	`10000`	`10001`	`100000`	`100001`	`1000000`	`1000001`
Output value	`181`	`184`	`136`	`99`	`67`	`27`	`253`	`231`

Table 4. Example output of VMPC-R

K; k=32	`{104, 9, 46, 231, 132, 149, 234, 147, 224, 97, 230, 127, 124, 109, 34, 171, 88, 185, 158, 23, 116, 69, 90, 195, 208, 17, 86, 175, 108, 29, 146, 219} (X=123; repeat 32 times:{X=X*134775813+1; output=X mod 256})`
V; v=32	`{149, 234, 147, 224, 97, 230, 127, 124, 109, 34, 171, 88, 185, 158, 23, 116, 69, 90, 195, 208, 17, 86, 175, 108, 29, 146, 219, 72, 105, 14, 71, 100} (X=132; repeat 32 times:{X=X*134775813+1; output=X mod 256})`
output of KSA:
P index	`0`	`1`	`2`	`3`	`252`	`253`	`254`	`255`
P value	`76`	`44`	`167`	`7`	`250`	`147`	`240`	`51`
S index	`0`	`1`	`2`	`3`	`252`	`253`	`254`	`255`
S value	`239`	`59`	`110`	`207`	`98`	`23`	`178`	`227`
output of CSPRNG:
Output index	`0`	`1`	`2`	`3`	`254`	`255`	`256`	`257`
Output value	`219`	`178`	`157`	`119`	`2`	`155`	`62`	`20`
Output index	`1000`	`1001`	`10000`	`10001`	`100000`	`100001`	`1000000`	`1000001`
Output value	`3`	`239`	`236`	`81`	`195`	`11`	`186`	`127`

Table 5. Example output of VMPC-R

K; k=256	{147, 224, 97, 230, 127, 124, 109, 34, 171, 88, 185, 158, 23, 116, 69, 90, 195, 208, 17, 86, 175, 108, 29, 146, 219, 72, 105, 14, 71, 100, 245, 202, 243, 192, 193, 198, 223, 92, 205, 2, 11, 56, 25, 126, 119, 84, 165, 58, 35, 176, 113, 54, 15, 76, 125, 114, 59, 40, 201, 238, 167, 68, 85, 170, 83, 160, 33, 166, 63, 60, 45, 226, 107, 24, 121, 94, 215, 52, 5, 26, 131, 144, 209, 22, 111, 44, 221, 82, 155, 8, 41, 206, 7, 36, 181, 138, 179, 128, 129, 134, 159, 28, 141, 194, 203, 248, 217, 62, 55, 20, 101, 250, 227, 112, 49, 246, 207, 12, 61, 50, 251, 232, 137, 174, 103, 4, 21, 106, 19, 96, 225, 102, 255, 252, 237, 162, 43, 216, 57, 30, 151, 244, 197, 218, 67, 80, 145, 214, 47, 236, 157, 18, 91, 200, 233, 142, 199, 228, 117, 74, 115, 64, 65, 70, 95, 220, 77, 130, 139, 184, 153, 254, 247, 212, 37, 186, 163, 48, 241, 182, 143, 204, 253, 242, 187, 168, 73, 110, 39, 196, 213, 42, 211, 32, 161, 38, 191, 188, 173, 98, 235, 152, 249, 222, 87, 180, 133, 154, 3, 16, 81, 150, 239, 172, 93, 210, 27, 136, 169, 78, 135, 164, 53, 10, 51, 0, 1, 6, 31, 156, 13, 66, 75, 120, 89, 190, 183, 148, 229, 122, 99, 240, 177, 118, 79, 140, 189, 178, 123, 104, 9, 46, 231, 132, 149, 234} (X=234; repeat 256 times:{X=X*134775813+1; output=X mod 256})
V; v=8	`{255, 250, 200, 150, 100, 50, 5, 1}`
output of KSA:
P index	`0`	`1`	`2`	`3`	`252`	`253`	`254`	`255`
P value	`10`	`34`	`13`	`239`	`209`	`9`	`154`	`220`
S index	`0`	`1`	`2`	`3`	`252`	`253`	`254`	`255`
S value	`253`	`106`	`200`	`178`	`75`	`251`	`129`	`209`
output of CSPRNG:
Output index	`0`	`1`	`2`	`3`	`254`	`255`	`256`	`257`
Output value	`201`	`85`	`155`	`17`	`187`	`48`	`55`	`198`
Output index	`1000`	`1001`	`10000`	`10001`	`100000`	`100001`	`1000000`	`1000001`
Output value	`110`	`179`	`189`	`210`	`4`	`15`	`253`	`83`

5. Authenticated encryption with VMPC-R (VMPC-R-MAC) (PDF)