|
1. Introduction
VMPC-MAC scheme is an algorithm for computing Message Authentication
Codes (MACs) for the VMPC Stream Cipher. A MAC allows to verify whether the
message output from the decryption process is exactly the same message that
was encrypted (i.e. that there was no transmission error, that nobody
intercepted and changed (forged) our message and that we used the correct
key to decrypt the message).
According to current state of the art the VMPC-MAC scheme provides a 2^144 level
of security (resistance to best found message-forgery attack) (for value 4 of the d parameter).
The security level can be extended by increasing the
d parameter (e.g. 5-level VMPC-MAC scheme requires an effort of 2^200 to be forged)
The VMPC-MAC employs some of the internal-state-data of the VMPC Stream Cipher (the P permutation)
to compute the MAC. This allowed to simplify the design and minimize the amount of
additional-to-encryption
computations and achieve high performance in software implementations of the complete
encrypt-and-authenticate process. Performance of the VMPC-MAC scheme reaches a rate of
about 27 clock cycles / byte (about 100MBytes / second on an Intel Pentium 2,66GHz processor).
|
2. Specification of 4-level VMPC-MAC scheme (d=4)
Notation :
|
P |
: 256-byte table storing a permutation of integers {0,1,...,255} |
|
n, s |
: 8-bit integer variables |
|
T |
: 32-byte table (the general size of T is (8*d) bytes) |
|
x1, x2, x3, x4 |
: 8-bit integer variables (the general number of x variables is d) |
|
M |
: 20-byte table the resulting MAC will be stored in |
|
m, g, R, i |
: temporary integer variables |
|
L |
: length of plaintext in bytes |
|
+ |
denotes addition modulo 256 |
|
Table 1. VMPC-MAC scheme |
1.1 Run the
VMPC Key Scheduling Algorithm
(VMPC-KSA or VMPC-KSA3).
1.2 m = g = x1 = x2 = x3 = x4 = 0; T[i]=0 for i ∈ {0,1,...,31}
2. repeat steps 3-16 L times:
3. s = P[ s + P[n] ]
4. Ciphertext[m] = Plaintext[m] xor P[P[P[s]]+1]
5. x4 = P[ x4 + x3 ]
6. x3 = P[ x3 + x2 ]
7. x2 = P[ x2 + x1 ]
8. x1 = P[ x1 + s + Ciphertext[m] ]
9. T[g] = T[g] xor x1
10. T[g+1] = T[g+1] xor x2
11. T[g+2] = T[g+2] xor x3
12. T[g+3] = T[g+3] xor x4
13. swap P[n] with P[s]
14. g = (g + 4) mod 32
15. n = n + 1
16. Increment m
17. Execute the Post Processing Phase
specified in Table S.17.
18. Input T to the VMPC-KSA round function: KSARound(T, 32).
This is equivalent to executing the algorithm in Table S.18.
19. Store 20 new outputs of the
VMPC Stream Cipher in table M.
This is equivalent to executing the algorithm in Table S.19.
20. Append the 20-byte MAC (stored in table M) to the Ciphertext.
|
|
|
Table S.17. The Post Processing Phase (step 17 of the algorithm specified in Table 1) |
17.1. R = 1
17.2. repeat steps (17.3 - 17.15) 24 times:
17.3. s = P[ s + P[n] ]
17.4. x4 = P[ x4 + x3 + R ]
17.5. x3 = P[ x3 + x2 + R ]
17.6. x2 = P[ x2 + x1 + R ]
17.7. x1 = P[ x1 + s + R ]
17.8. T[g] = T[g] xor x1
17.9. T[g+1] = T[g+1] xor x2
17.10. T[g+2] = T[g+2] xor x3
17.11. T[g+3] = T[g+3] xor x4
17.12. swap P[n] with P[s]
17.13. g = (g + 4) mod 32
17.14. n = n + 1
17.15. R = R + 1
|
|
|
Table S.18. Step 18 (KSARound(T, 32)) of the algorithm specified in Table 1 |
18.1. n = i = 0
18.2. repeat steps 18.3 - 18.6 768 times:
18.3. s = P[ s + P[n] + T[i] ]
18.4. swap P[n] with P[s]
18.5. i = (i + 1) mod 32
18.6. n = n + 1
|
|
|
Table S.19. Step 19 (20 VMPC Stream Cipher outputs) of the algorithm specified in Table 1 |
19.0. Make sure that n = 0 (as should be after step 18)
19.1. repeat steps 19.2 - 19.5 20 times:
19.2. s = P[ s + P[n] ]
19.3. M[n] = P[P[P[s]]+1]
19.4. swap P[n] with P[s]
19.5. n = n + 1
|
|
|
3. Performance of the VMPC-MAC scheme
Performance of a moderately optimized 32-bit assembler implementation of the
VMPC-MAC scheme measured on an Intel Pentium 4, 2.66 GHz processor, is given in Table 2.
Table 2. Software performance of the VMPC-MAC scheme
MBytes / s |
MBits / s |
cycles / byte |
100 |
800 |
27 |
|
|
4. Best known attack against the VMPC-MAC scheme
The most efficient (chosen ciphertext) attack found against the VMPC-MAC scheme is described
in this section.
The attack assumes that the attacker has full passive and active access to the ciphertext and can use an unlimited number
of verification attempts for the new message. The purpose of the attacker is to introduce
a new ciphertext which conforms the MAC of the original one.
The attack model begins with a random (or intended by the attacker)
change of one bit (or byte) of the ciphertext - Ct[m]. The purpose of the attacker is to hide this change by manipulating
the remaining part of the ciphertext in such way as to leave the resulting MAC unchanged.
Let Ct[m] denote m-th byte of Ciphertext
Let xk(m) denote the value of the xk variable (for k=1,2,3 or 4) in iteration m
Let n = (m * d) modulo 32
Let (+) denote addition modulo 32
A change of Ct[m] unconditionally causes a change of x1(m), since P is a permutation.
Because x1(m) and only x1(m) directly updates x2(m+1) and indirectly updates x3(m+2)
and x4(m+3), the variables x2(m+1), x3(m+2) and x4(m+3) will be unconditionally changed too.
The following elements of table T will be updated and unconditionally changed by those
variables: T[n] changed by x1(m), T[n(+)5] changed by x2(m+1),
T[n(+)10] changed by x3(m+2) and T[n(+)15] changed by x4(m+3).
The most efficient method of reverting these changes found forces the
attacker to perform the following changes of the ciphertext:
1. Change Ct[m+1] in such way as to make x4(m+4) return to its original value.
The unavoidable cost of this is a change of x1(m+1), x2(m+2) and x3(m+3).
[x3(m+3) must be changed in such way as to make x4(m+4) = (x4(m+3) + x3(m+3))
modulo 256 return to its original value]
As a result T[n(+)4] is changed by x1(m+1), T[n(+)9] is changed by x2(m+2) and
T[n(+)14] is changed by x3(m+3).
T[n(+)19] remains unchanged because the change of x4(m+4) was reverted.
2. Change Ct[m+2] in such way as to make x3(m+4) return to its original value.
The unavoidable cost of this is a change of x1(m+2) and x2(m+3).
As a result T[n(+)8] is changed by x1(m+2) and T[n(+)13] is changed by x2(m+3).
T[n(+)18] remains unchanged because the change of x3(m+4) was reverted.
3. Change Ct[m+3] in such way as to make x2(m+4) return to its original value.
The unavoidable cost of this is a change of x1(m+3).
As a result T[n(+)12] is changed by x1(m+3). T[n(+)17] remains unchanged because
the change of x2(m+4) was reverted.
4. Change Ct[m+4] in such way as to make x1(m+4) return to its original value.
As a result T[n(+)16] remains unchanged.
At this moment the attacker succeeded in stopping the avalanche of changes of elements
of T, resulting from a change of Ct[m], by reverting the changes of x1,x2,x3,x4
in the earliest possible iteration (m+4). The cost of this is an unavoidable
change of 10 elements of the T table
(T[n, n(+)4, n(+)5, n(+)8, n(+)9, n(+)10, n(+)12, n(+)13, n(+)14, n(+)15]).
To complete a successful forgery, the attacker needs to revert the changes of these
elements of T, too. Operations similar to steps 1-4 need to be performed to
refrain x1,x2,x3,x4 from causing more damage to T and the additional requirement -
to revert the already caused changes to T - needs to be satisfied. The most efficient
approach found achieves that in the following steps 5-9:
5. Change Ct[m+8] in such way as to change x1(m+8) in such way as to revert the
change of T[n], make x2(m+9) change in such way as to revert the change of
T[n(+)5], make x3(m+10) change in such way as to revert the change of T[n(+)10],
and make x4(m+11) change in such way as to revert the change of T[n(+)15].
6. Change Ct[m+9] in such way as to make x4(m+12) return to its original value,
make x1(m+9) change in such way as to revert the change of T[n(+)4], make
x2(m+10) change in such way as to revert the change of T[n(+)9], make x3(m+11)
change in such way as to revert the change of T[n(+)14]. T[n(+)19] remains unchanged
because the change of x4(m+12) was reverted.
7. Change Ct[m+10] in such way as to make x3(m+12) return to its original value,
make x1(m+10) change in such way as to revert the change of T[n(+)8], make x2(m+11)
change in such way as to revert the change of T[n(+)13]. T[n(+)18] remains unchanged
because the change of x3(m+12) was reverted.
8. Change Ct[m+11] in such way as to make x2(m+12) return to its original value,
make x1(m+11) change in such way as to revert the change of T[n(+)12]. T[n(+)17]
remains unchanged because the change of x2(m+12) was reverted.
9. Change Ct[m+12] in such way as to make x1(m+12) return to its original value.
As a result T[n(+)16] remains unchanged.
A total complexity of the described attack is determined by the total number of changes to
variables x1,x2,...,xd and T[0,1,..., 8*d-1], which need to be reverted.
Steps 1-9 determine this complexity, for the assumed d=4, to 256^18 = 2^144.
Extending the the d parameter to 5 would, in an analogous attack,
yield a complexity of 256^25 = 2^200 (which would also imply an increase
of the size of the MAC to 25 or more bytes).
|
5. Test output of the VMPC-MAC scheme
An example 20-byte MAC generated by the algorithm described in
Section 2 is given in Table 3.
The MAC is generated for an example key and Initialization Vector specified in Table 3 and
for a 256-byte plaintext message consisting of consecutive numbers from 0 to 255
(Plaintext[i]=i for i=0,1,...,255; e.g. Plaintext[150]=150)
Table 3. Example MAC produced by the VMPC-MAC scheme
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 |
256-byte Message (dec) |
0, 1, 2, 3, ..., 252, 253, 254, 255 |
Resulting 20-byte MAC (hex) |
9B, DA, 16, E2, AD, 0E, 28, 47, 74, A3, AC, BC, 88, 35, A8, 32, 6C, 11, FA, AD |
|
|
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
|
|