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.
|