Strona główna
- Technologia
- Schemat uwierzytelnionego szyfrowania VMPC-MAC
English version
|
1. Introduction
2. Specification of a 4-level VMPC-MAC scheme
3. Performance of the VMPC-MAC scheme
4. Best known attack against the VMPC-MAC scheme
5. Test output of the VMPC-MAC scheme |
Download paper
"VMPC-MAC: A Stream Cipher Based
Authenticated Encryption Scheme":
vmpc_mac.pdf (151 KB)
vmpc_mac.ps (253 KB)
vmpc_mac.dvi (43 KB)
Paper also available at
IACR ePrint archive
|
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 (resistamce 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 initialized by the
VMPC KSA |
| |
s |
: |
8-bit
variable initialized by the
VMPC KSA |
| |
T |
: |
32-byte
table (general size of T is (8*d) bytes) |
| |
x1,x2,x3,x4 |
: |
1-byte
variables (general number of x variables is d) |
| |
M |
: |
20-byte
table the resulting MAC will be stored in |
| |
n,m,g,R |
: |
temporary integer
variables |
| |
+ |
: |
denotes
addition modulo 256 |
|
| Table 1. VMPC-MAC scheme |
1.1 Run the VMPC Key Scheduling Algorithm (VMPC KSA)
1.2 (n,m,g,x1,x2,x3,x4)=0; T[x]=0 for x = 0,1,...,31
2. Repeat steps 3-16 Length_of_plaintext 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. Temp = P[n]; P[n] = P[s]; P[s] = Temp
14. g = (g + 4) modulo 32
15. n = n + 1
16. Increment m
17. Execute the Post-Processing Phase
specified in steps 17.1-17.15 in
Table S.17
18. Input T to the IV-phase (step 8) of the VMPC KSA
(execute steps (18.1 - 18.3) specified in
Table S.18)
19. Store 20 new outputs of the VMPC Stream Cipher in table M
(execute steps (19.1 - 19.3) specified in
Table S.19)
20. Append the MAC, stored in table M, to the Ciphertext
|
|
|
| Table S.17. Step 17 of the algorithm specified in
Table 1 |
17.1. Set R to 1
17.2. Execute 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. Temp = P[n]; P[n] = P[s]; P[s] = Temp
17.13. g = (g + 4) modulo 32
17.14. n = n + 1
17.15. R = R + 1
|
|
|
| Table S.18. Step 18 of the algorithm specified in
Table 1 |
18. for m from 0 to 767 execute steps (18.1 - 18.3):
18.1. n = m modulo 256
18.2. s = P[ s + P[n] + T[m modulo 32] ]
18.3. Temp = P[n]; P[n] = P[s]; P[s] = Temp
|
|
|
| Table S.19. Step 19 of the algorithm specified in
Table 1 |
19. for n from 0 to 19 execute steps (19.1 - 19.3):
19.1. s = P[ s + P[n] ]
19.2. M[n] = P[P[P[s]]+1]
19.3. Temp = P[n]; P[n] = P[s]; P[s] = Temp
|
|
|
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[x]=x for x=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 Stream Cipher |
VMPC-MAC scheme |
VMPC KSA3 algorithm |
Inverting Challenge |
Research
|
|
