Homepage
- Technology
- VMPC-KSA3 algorithm
Wersja polska
|
1. Introduction
2. VMPC KSA3 algorithm
3. Test output of the VMPC-KSA3 algorithm
|
Download paper
"Security of Symmetric Encryption Schemes
with One-Way IND-CNA Key Setup":
vmpc_proof.pdf (140 KB)
vmpc_proof.ps (239 KB)
vmpc_proof.dvi (35 KB)
Paper also available at
IACR ePrint archive
|
1. Introduction
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-element 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.
|
2. VMPC KSA3 algorithm
The VMPC KSA3 Key Scheduling Algorithm transforms a cryptographic
key and and Initialization Vector into a 256-element permutation P.
This permutation P (and variable s) are later used to generate keystream and encrypt data with the
VMPC Stream Cipher
Notation:
| |
P |
: |
256-byte
table storing the permutation |
| |
s |
: |
8-bit
variable initialized by the VMPC KSA3 algorithm
|
| |
c |
: |
fixed length
of the cryptographic key in bytes, c  {16...64} |
| |
K |
: |
c-element
table storing the cryptographic key |
| |
z |
: |
fixed length
of the Initialization Vector in bytes, z {16...64} |
| |
V |
: |
z-element
table storing the Initialization Vector |
| |
n |
: |
8-bit
variable |
| |
m |
: |
16-bit
variable |
|
| Table 2.1. VMPC KSA3 algorithm |
1. Set s to 0
2. Set i-th element of P to i for i  {0,1,...,255} |
3. Set m to 0
4. Add modulo 256 (m modulo 256)-th element of P to s
5. Add modulo 256 (m modulo c)-th element of K to
s
6. Set s to s-th element of P
7. Swap (m modulo 256)-th element of P with s-th
element of P
8. Increment m
9. Go to step 4 if m is lower than 768
|
10. Set m to 0
11. Add modulo 256 (m modulo 256)-th element of P to s
12. Add modulo 256 (m modulo z)-th element of V to s
13. Set s to s-th element of P
14. Swap (m modulo 256)-th element of P with s-th element of P
15. Increment m
16. Go to step 11 if m is lower than 768
|
17. Set m to 0
18. Add modulo 256 (m modulo 256)-th element of P to s
19. Add modulo 256 (m modulo c)-th element of K to s
20. Set s to s-th element of P
21. Swap (m modulo 256)-th element of P with s-th element of P
22. Increment m
23. Go to step 18 if m is lower than 768 |
|
|
| Table 2.2. VMPC KSA3 algorithm - pseudo code |
1. s = 0
2. for i from 0 to 255: P[i]=i
3. for m from 0 to 767: execute steps 4-6:
4. n = m and 255
5. s = P[ (s + P[n] + K[m mod c]) and 255 ]
6. Temp = P[n]
P[n] = P[s]
P[s] = Temp
7. for m from 0 to 767: execute steps 8-10:
8. n = m and 255
9. s = P[ (s + P[n] + V[m mod z]) and 255 ]
10. Temp = P[n]
P[n] = P[s]
P[s] = Temp
11. for m from 0 to 767: execute steps 12-14:
12. n = m and 255
13. s = P[ (s + P[n] + K[m mod c]) and 255 ]
14. Temp = P[n]
P[n] = P[s]
P[s] = Temp
|
|
|
3. Test output of the VMPC KSA3 algorithm
16 bytes of a 102.400-byte data-stream generated by the VMPC Stream Cipher
for a given key and a given Initialization Vector are shown in Table 3.
The internal state of the cipher (P) is initialized with the VMPC KSA3 algorithm.
Table 3. Example data-stream generated by the VMPC Stream Cipher using VMPC KSA3 algorithm
Key
(hex) |
96, 61, 41, 0A, B7, 97, D8, A9, EB, 76, 7C, 21, 17, 2D, F6, C7 |
Initialization Vector
(hex) |
4B, 5C, 2F, 00, 3E, 67, F3, 95, 57, A8, D2, 6F, 3D, A2, B1, 55 |
Output-byte number
(dec) |
0 |
1 |
2 |
3 |
252 |
253 |
254 |
255 |
Output-byte value
(hex) |
B6 |
EB |
AE |
FE |
48 |
17 |
24 |
73 |
Output-byte number
(dec) |
1020 |
1021 |
1022 |
1023 |
102396 |
102397 |
102398 |
102399 |
Output-byte value
(hex) |
1D |
AE |
C3 |
5A |
1D |
A7 |
E1 |
DC |
|
For a scheme of authenticated encryption based on
the VMPC Stream Cipher, see the VMPC-MAC specification
For further analysis of the algorithms, see the Research section
|
Home |
VMPC Function |
VMPC Stream Cipher |
VMPC-MAC scheme |
VMPC KSA3 algorithm |
Inverting Challenge |
Research
|
|
