Back to Homepage
VMPC One-Way Function P vs NP Project VMPC Encryption Technology VMPC-R CSPRNG VMPCrypt Application Permutu Game Publications About Author Contact


Inverting the VMPC One-Way Function

1. Introduction
2. Algorithm of inverting the VMPC function
    2.1. The deducing process
    2.2. The selecting process
3. Example complexities of inverting the VMPC function

Download FSE'04 paper
"VMPC One-Way Function
and Stream Cipher":
vmpc.pdf (171 KB)
vmpc.ps (289 KB)
vmpc.dvi (55 KB)

Earlier paper "VMPC One-Way Function"
available also at IACR ePrint archive





1. Introduction

n-element permutation P has to be recovered given information from n-element permutation Q,
where Q=VMPCk(P) (e.g. n=256, k=1: Q[x]=P[P[P[x]]+1]).

By definition each element of Q is formed by k+2 (e.g. 3), usually different, elements of P. One element of Q (e.g. Q[33]=25) can be formed by many possible configurations of P elements (e.g. P[33]=10, P[10]=20, P[21]=25 or P[33]=1, P[1]=4, P[5]=25, etc.).

It cannot be said which of the configurations is more probable. One of the configurations has to be picked (usually k+1 (e.g. 2) elements of P have to be guessed) and the choice must be verified using all those other Q elements, which use at least one of the P elements from the picked configuration.

Each element of P is usually used to form k+2 (e.g. 3) different elements of Q. As a result, usually (k+2)*(k+1) (e.g. 6) new elements of Q need to be inverted (all k+2 elements of P used to form each of those Q elements need to be revealed) to verify the P elements from the picked configuration.

This would not be difficult for a simple (e.g. triple) permutation composition, where the cycle structure of P is retained by Q (some cycles are only shortened).

In Variably Modified Permutation Composition however the cycle structure of P is corrupted by the addition operation(s) and cannot be easily recovered from Q.

Due to that it is usually impossible to find two different elements of Q, which use at least k+1 (e.g. 2) exactly the same elements of P. (This can be done easily for a simple permutation composition)

In fact only such element of Q can usually be found, name it Q[r], which uses only one of the k+2 (e.g. 3) elements of P, used to form another Q element. This forces the k remaining (e.g. 1) elements of P, used to form Q[r], to be guessed to make the verification of the initial pick possible.

However at each new guessed element of P, there usually occur k+1 (e.g. 2) new elements of Q which use this element of P and which need to be inverted to verify the guess.

The algorithm falls into a loop, where at every step usually k (e.g. 1) new elements of P need to be guessed to verify the previously guessed elements. It quickly occurs that the k+2 (e.g. 3) elements of P picked at the beginning of the process indirectly depend on all n (e.g. 256) elements of Q.


The described scenario is the case usually and it is sometimes possible to benefit from coincidences (where for example it is possible to find two elements of Q, which use more than one (e.g. 2) exactly the same P elements (e.g. Q[2]=3: P[2]=4, P[4]=8, P[9]=3 and Q[5]=8: P[5]=9, P[9]=3, P[4]=8)).

The actual algorithm of inverting VMPC was optimized to benefit from the possible coincidences. The average number of P elements which need to be guessed - for n=256 - has been reduced to only about 34 for 1-level VMPC function, to about 57 for 2-level VMPC, to about 77 for 3-level VMPC and to about 92 for 4-level VMPC function.

Searching through half of the possible states of these P elements takes on average about 2260 steps for 1-level VMPC function (not 2268,7), about 2420  for 2-level VMPC, about 2550  for 3-level VMPC and about 2660 steps for 4-level VMPC function.






2. Algorithm of inverting the VMPC function

The fastest method of inverting the VMPC function found derives n-element permutation P which produces
a given Q=VMPCk(P) permutation, according to the following algorithm:

Notation:

           Pt : n-element table, the searched permutation will be stored in
          Argument, Value; Base, Parameter of an element of Pt :
                    For an element Pt[x]=y : x is termed the argument and y the value.
                    The base is either the argument or the value; the parameter is the corresponding -
                    the value or the argument.
                              Example: for an element Pt [3]=5: If value 5 is the base, argument 3 is the parameter.



1.1) Reveal one element of Pt by assuming Pt [x]=y; where x and y are any values within range
       x {0,1,...,n-1}, y {0,1,...,n-1}
1.2) Choose at random whether x is the base and y the parameter or y the base and x the parameter
       of the element Pt [x]=y. Denote Pt [x]=y as the current element of Pt.

2) Reveal all possible elements of Pt by running the deducing process (see section 2.1)

3) If n elements of Pt have been revealed with no contradiction in step 2: Terminate the algorithm and output Pt

4) If fewer than n elements of Pt have been revealed with no contradiction in step 2:
    4.1) Reveal a new element of Pt by running the selecting process (see section 2.2).
            Denote the revealed element as the current element of Pt.
    4.2) Save the parameter of the revealed element of Pt
    4.3) Go to step 2

5) If a contradiction occurred in step 2:
    5.1) Remove all elements of Pt revealed in step 2 when the current element of Pt had been revealed
    5.2) Increment modulo n the parameter of the current element of Pt
    5.3) If the parameter of the current element of Pt has returned to the value saved in step 4.2:
           5.3.1) Remove the current element of Pt
           5.3.2) Denote the element, which had been the current element of Pt directly before the element
                     removed in step 5.3.1 became the current one, as the current element of Pt
           5.3.3) Go to step 5.1

6) Go to step 2



2.1. The deducing process

The deducing process reveals all possible elements of Pt, given Q and given the already
revealed elements of Pt, according to the following algorithm:

Notation: as in section 2, with:

          C,A : temporary variables
          Word x of Statement y:
                    Statement y: A set of all elements of Pt used to calculate Q[y]
                    Word x: x-th consecutive element of Pt used to calculate Q[y]:
                             Example for VMPC2 : Q[ x ] = P[P[P[P[x]]+1]+2] :
                             Assume Pt[2]=3, Pt[3]=5, Pt[6]=2, Pt[4]=7, which produces Q[2]=7.
                             The elements Pt[2]=3, Pt[3]=5, Pt[6]=2, Pt[4]=7 form statement 2.
                             The element Pt[2]=3 is word 1 of statement 2; Pt[3]=5 is word 2 of statement 2, etc.




1.1) Set C to 0
1.2) Set A to 0

2) If the element Pt [A] is revealed:
    2.1) If the element Pt [A] and k other revealed elements of Pt fit a general pattern of k+1 words
           of any statement : Deduce the remaining word of that statement (see example 2.1.1)
    2.2) If the deduced word is not a revealed element of Pt :
           2.2.1) Reveal the deduced word as an element of Pt
           2.2.2) Set C to 1
    2.3) If the deduced word contradicts any of the already revealed elements of Pt (see example 2.1.2) :
            Output a contradiction and terminate the deducing algorithm

3.1) Increment A
3.2) If A is lower than n: Go to step 2
3.3) If C is equal 1: Go to step 1.1



Example 2.1.1)

          For VMPC2 : Q[ x ] = P[P[P[P[x]]+1]+2]:
          Assume that Q[0]=9 and that the following elements of Pt are revealed:
          Pt [0]=1, Pt [1]=3, Pt [8]=9
          Word 3 of statement 0 can be deduced as Pt'[4]=6 (Pt'[3+1]=8-2)


Example 2.1.2)

          For VMPC2 : Q[ x ] = P[P[P[P[x]]+1]+2]:
          Assume that Q[7]=2 and that the following elements of Pt are revealed:
          Pt [1]=8, Pt [9]=3, Pt [5]=2 and Pt [6]=1
          Word 1 of statement 7, deduced as Pt'[7]=1, contradicts the already revealed element Pt [6]=1.






2.2. The selecting process

The selecting process selects such new element of Pt to be revealed which maximizes the number
of elements of Pt possible to deduce in further steps of the inverting algorithm.

The selecting process outputs a selected base and a randomly chosen parameter of a new element of Pt.

Notation: as in section 2.1, with:

          G,R,X,Y : temporary variables
          Ta,Tv : temporary tables
          Weight : table of numbers:
          Weight[1; 2; 3; 4] = (2; 5; 9; 14); Example: Weight[3]=9




1.1) Set Ta and Tv to 0
1.2) Set G to 0
1.3) Set R to 1

2) Count the number of revealed elements of Pt which fit the general pattern of words of a statement
     in which an unrevealed element of Pt with argument G would be word R.
     Increment Ta[G] by Weight of this number (see example 2.2.1)

3) Count the number of revealed elements of Pt which fit the general pattern of words of a statement
     in which an unrevealed element of Pt with value G would be word R.
     Increment Tv[G] by Weight of this number

4.1) Increment R
4.2) If R is lower than k+3: Go to step 2
4.3) Increment G
4.4) If G is lower than n: Go to step 1.3

5.1) Pick any index of Ta or Tv for which the number stored in any of the tables Ta or Tv is maximal
       (see example 2.2.2)

5.2) If the index picked in step 5.1 is an index of Ta:
       5.2.1) Store this index in variable X
       5.2.2) Generate a random number Y within range Y {0,1,...,n-1} ,
                  such that an element of Pt with value Y is not revealed
       5.2.3) Output Pt'[X]=Y, where X is the base and Y is the parameter

5.3) If the index picked in step 5.1 is an index of Tv:
       5.3.1) Store this index in variable Y
       5.3.2) Generate a random number X within range X {0,1,...,n-1} ,
                  such that an element of Pt with argument X is not revealed
       5.3.3) Outputs Pt'[X]=Y, where Y is the base and X is the parameter




Example 2.2.1)

          For VMPC2 : Q[ x ] = P[P[P[P[x]]+1]+2]:
          Assume that G=8; R=2; Q[6]=1 and that the following elements of Pt are revealed:
          Pt [6]=8, Pt [5]=1


          There are two revealed elements of Pt which fit the general pattern of words of a statement in which
          Pt [8] would be word 2 : Pt [6]=8, Pt [5]=1:


          word 1     word 2     word 3    word 4
          Pt [6]=8,  Pt [8]=?,   Pt [?]=?,  Pt [5]=1


          Ta[8] = Ta[8] + Weight[2] = Ta[8] + 5

Example 2.2.2)

          Assume Ta = (0, 5, 2, 7, 5, 7) and Tv = (2, 7, 0, 0, 5, 2)
          The maximal number stored in any of the tables is 7: Ta[3]=Ta[5]=Tv[1]=7
          Pick any of: index 3 of Ta, index 5 of Ta or index 1 of Tv





3. Example complexities of inverting the VMPC function

Complexity of inverting the VMPC function has been approximated as an average number of times
the deducing process in step 2 of the inverting algorithm described in section 2 has to be run until
permutation Pt satisfies Q=VMPCk(Pt)
Average numbers of elements of Pt which need to be assumed are given in brackets in Table 1.

Complexities of inverting the VMPC function of the following levels have been approximated:

          VMPC1 : Q[ x ] = P[P[ P[x]]+1]
          VMPC2 : Q[ x ] = P[P[P[P[x]]+1]+2]
          VMPC3 : Q[ x ] = P[P[P[P[P[x]]+1]+2]+3]
          VMPC4 : Q[ x ] = P[P[P[P[P[P[x]]+1]+2]+3]+4]

Table 1. Example complexities of inverting the VMPC function
        Function
n
VMPC1 VMPC2 VMPC3 VMPC4
6 24.1  (2.3) 25.5  (3.1) 26.1  (3.3) 26.9  (3.8)
8 25.5  (2.7) 27.5  (3.4) 28.8  (4.0) 29.8  (4.4)
10 27.1  (3.0) 29.7  (4.0) 211.5  (4.7) 213.0  (5.2)
16 211.5  (3.8) 216.6  (5.4) 220.4  (6.6) 223.3  (7.5)
32 224  (6.0) 237  (9.1) 247  (11.5) 254  (13.4)
64 253  (10.2) 284  (16.2) 2108  (21.0) 2127  (24.9)
128 2117  (18.5) 2190  (30.0) 2245  (40.0) 2292  (47.0)
256 2260  (34.0) 2420  (57.0) 2550  (77.0) 2660  (92.0)

Example: For 1-level VMPC function applied on 256-element permutations about 34 elements of Pt need to be assumed to recover all elements of Pt. Searching through half of the possible states of the 34 assumed elements takes about 2260 steps.


Home  |   VMPC Function  |   VMPC-R CSPRNG  |   VMPC Stream Cipher  |   VMPC-MAC scheme  |   VMPC KSA3 algorithm  |   Research  |   Inverting Challenge
P vs NP Project  |   VMPCrypt Application  |   Permutu Game  |   Publications  |   About Author  |   Contact

Copyright © 1999-2016 Bartosz Zoltak
Supported by OHTON EXPO Okna Wroc³aw