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

VMPC KSA3 Algorithm

1. VMPC-KSA3 algorithm specification
2. Security analysis of the VMPC-KSA3 algorithm
3. Test output of the VMPC-KSA3 algorithm

See also:
VMPC Stream Cipher and KSA specification

Download VMPC Encryption Technology Implementation:
VMPC Encryption Technology Implementation in C
VMPC Encryption Technology Implementation in Pascal/Delphi
VMPC Encryption Technology Implementation in Assembler

Download paper
"Security of Symmetric Encryption Schemes
with One-Way IND-CNA Key Setup":
vmpc_proof.pdf (140 KB) (239 KB)
vmpc_proof.dvi (35 KB)

Paper also available at
IACR ePrint archive

1. VMPC-KSA3 algorithm specification

VMPC-KSA3 is a variant of the VMPC Key Scheduling Algorithm. See the VMPC Stream Cipher specification for reference.

This section discusses the security benefits from using the VMPC-KSA3 instead of the basic VMPC-KSA variant.

The VMPC-KSA was not designed to fix any security flaw of the basic VMPC-KSA algorithm (we are not aware of any weakness of the basic VMPC-KSA). Instead the VMPC-KSA3 offers an additional layer of security which begins to work in the scenario of a hypothetical successful internal-state-recovery attack.

The VMPC-KSA3 algorithm specification (click here for the definitions of variables):

0. s = 0;  P[i] = i  for i ∈ {0,1,...,255}

1. KSARound(K, k)
2. KSARound(V, v)
3. KSARound(K, k)

Function KSARound(M, m) definition:
  4. n = i = 0
  5. repeat steps 6-9  768  times:
      6. s = P[ s + P[n] + M[i] ]
      7. swap P[n] with P[s]

      8. i = (i + 1) mod m
      9. n = n + 1

2. Security analysis of the VMPC-KSA3 algorithm

A feasible attack recovering the cipher's internal state is considered to be a complete break of the cipher. In VMPC Stream Cipher the internal state is the 256-byte permutation P initialized by the VMPC KSA (Key Scheduling Algorith) The KSA algorithm transforms a secret cryptographic key and a message-unique Initialization Vector (IV) into the cipher's internal state (here the P permutation). This internal state is then used directly by the VMPC Stream Cipher to generate the keystream and encrypt data.

In general the VMPC KSA algorithm performs 2 phases. In the first phase it takes a constant permutation P0 (0,1,2,...,255), performs 768 swap operations driven by the secret value of the key, and this way permutation P1 is generated. In the second phase permutation P1 is swapped again in the next 768 steps however now driven by the value of the Initialization Vector (IV). This way permutation P2 is generated. P2 is the final result of the VMPC KSA algorithm and is used directly by the cipher to generate keystream and encrypt data.

Attacks recovering the cipher's internal state usually require the knowledge of both the plaintext and the ciphertext and a huge amount of computations. For VMPC Stream Cipher such attack would need to recover the P2 permutation and is believed to require an average effort of about 2900 operations (see Research section). If hypothetically this is overcome - the cipher is considered to be completely broken. This is because the standard VMPC KSA algorithm is INVERTIBLE, which is a standard feature. In more detail - if the attacker gets to know the cipher's internal state P2, she can easily backtrack the operations performed by the last 768 swaps of the VMPC KSA because the value of the Initialization Vector (IV), which drives these swaps, is known (which also is a standard feature). This way an attacker can easily determine the value of P1.

Now knowing the value of the IV_new of a new message and P1, the attacker simply inputs them directly to the KSA, performs the second phase 768 swap operations of the VMPC KSA and derives the P2_new permutation which was used to encrypt the the new message. At this moment she simply inputs P2_new to VMPC Stream Cipher and decrypts the new message instantly.

This is all standard - if the cipher is broken and its internal state is recovered - the cipher no more ensures secrecy of data.

However with a simple modification to the original VMPC KSA algorithm we can make the attacker's taks much harder, even if she breaks the cipher.

The VMPC KSA3 algorithm, on the contrary to the standard VMPC KSA, is NOT INVERTIBLE. How this works: VMPC KSA3 uses not 2 but 3 phases of swapping of the P permutation before P is input to the cipher. The two first phases are the same as in the standard KSA (P0 → mixing with secret key → P1 → mixing with IV → P2) but VMPC KSA3 has one additional phase: P2 → mixing again with secret key → P3. In the third phase the P permutation undergoes 768 swaps again driven by the secret value of the key.

This modification has crucial consequences. Now when the attacker gets to know the internal state of the cipher (the P3 permutation), she cannot derive P2 or P1 from it (of course she neither can derive the secret key from it). Any new message (encrypted under the same key) has a different IV. The attacker - to dedcrypt the new message - needs to know its P3_new internal state, which was easy to find for the standard VMPC KSA algorithm. However for the VMPC KSA3 algorithm the attacker cannot invert the third phase of the VMPC KSA3 algorithm because the third phase of KSA3 operates on the unknown and undistinguishable from random values of P2 and the secret key, and has a very complex algebraic structure.

One detail to fill the picture are the statistical properties of the algorithm. The 768 steps of the KSA algorithm provide an undistinguishable from random diffusion effect or - they are IND-CNA (Indistinguishable under Chosen Nonce Attack (Nonce = IV here)). This means that given permutation P1 and two Initialization Vectors (IV_1 and IV_2), which are ALMOST identical (e.g. IV_1 and IV_2 differ only in one bit), the permutations P2_1 (where P1 → mixing with IV_1) → P2_1) and P2_2 (where P1 → mixing with IV_2) → P2_2) are "randomly" different (relations between them are undistinguishable from relations between two truly random permutations).

This way about the only way for an attacker to recover P3_new, even if she somehow recovered P3, is still performing a brute-force search of the secret key or any other attack, which would allow her to decrypt the new message.

The fundamental point of the VMPC KSA3 algorithm is that if the attacker breaks the cipher and finds the internal state used to encrypt one message (we assume it cost her A LOT of effort), then VMPC KSA3 forces the attacker to perform the same attack AGAIN to decrypt the new message, even if it is necrypted with the same secret key. This way an attacker CANNOT use the result of his break (the P3 permutation) to make the task of breaking any new message any easier.

A note: the usual assumption for the attacker to find the internal state of the cipher is that she knows both the plaintext and the ciphertex. Then by analysing them she finds the value of the internal state (still at an effort of 2^900 operations as believed today).

Given the discussed observations we might informally agree that VMPC KSA3 algorithm gives us a cryptographic insurance policy. Even if the attacker somehow breaks one of our messages and recovers the cipher's internal state (as noted above - the attacker would need to intercept both the plaintext and the ciphertext to do so), all other messages, even encrypted with the same key, remain as secure, as the original message was.

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-2018 by Bartosz Zoltak