Protecting White-Box AES with Dual Ciphers - Information Security and Cryptology-ICISC 2010 - page 289

changed the dual cipher at the round level (to ease the description). It is possible
to use even more dual ciphers. Since each 4 bytes output of a round depends
only on 4 bytes of input to that round, a different dual AES cipher may be used
for each of the four mappings in a round, which means that up to 4

·

10 = 40
different dual ciphers can be used in a given white-box AES implementation. If
we let y i is the i -th output byte of type III tables of the round r then we have:

y 0 ,y 4 ,y 8 ,y 12 depend on x 0 ,x 1 ,x 2 ,x 3 ;
y 1 ,y 5 ,y 9 ,y 13 depend on x 4 ,x 5 ,x 6 ,x 7 ;
y 2 ,y 6 ,y 10 ,y 14 depend on x 8 ,x 9 ,x 10 ,x 11 ;
y 3 ,y 7 ,y 11 ,y 15 depend on x 12 ,x 13 ,x 14 ,x 15 .

Without loss of generality, let Δ ( r )

σ 0 ,...,Δ ( r ) σ 3 be the four different transformation

matrix associated to the dual ciphers used in round r . Let the bytes ( x 0 ,...,x 3 ) σ 0 =
Δ σ 0 · ( x 0 ,...,x 3 ) t .Using Δ ( r ) σ 1 ,Δ ( r ) and Δ ( r ) σ 3 we get ( x 4 ,...,x 7 ) σ 1 ,( x 8 ,...,x 11 ) σ 2

and ( x 12 ,...,x 15 ) σ 3 . The resulting bytes are taken as input of type II tables for
which the T -boxes were built as follows:

σ 2

K i,j ) T i,j ( x 4 ·i + j ):= IS σ i K σ i

[0 .. 3] 2 ( x 4 ·i + j ⊕ ⊕

i,j ,

( i, j ) ∈

i

T i,j ( x 4 ·i + j ):= IS σ i K σ i

[0 .. 3] 2 ,

( x 4 ·i + j ) ⊕

i,j ,r

∈ [2 .. 10] , ( i, j ) ∈

i

where K 0
i,j

= Δ (1)

( K i,j )and IS σ i for i ∈ [0 .. 3] are modified from original

σ i

i

accordingtothematrix representing Δ ( r )

InvSubBytes for the round r .Now,as

σ i

data are shifted (to implement InvShiftRows ) as input to type III tables, care

should be taken as to which product Δ

Δ − 1 is to be combined with which of
type II tables of the next round to have the correct input state. As illustrated in
Figure 4, we then encode the mixing bijections of type II tables of round r +1
as follows:

×

z (1)

4 ·i + j = Δ (1)

P i,j ( y 4 ·i + j ) , ( i, j ) [0 .. 3] 2

σ i ×

∈

z ( r +1)
4 ·i + j

P r +1
i,j

= Δ ( r +1)
σ i

( Δ ( r )
σ j

) − 1 [0 .. 3] 2 . × × ( y 4 ·i + j ) ,r ∈ [1 .. 9] , ( i, j ) ∈

It can be noted that product Δ ( r +1) ( Δ ( r )

) − 1 changes for each of the 16 tables
in a round r +1, for r in [1 .. 9]. Similarly, we modify the mixing bijections in
type I.b table as:

σ i ×

σ j

( Δ (10)
σ j

) − 1 ( y 4 ·i + j ) ,i z 4 ·i + j = G × ∈ [0 .. 3] ,j ∈ [0 .. 3] .

In the case of Billet et al. attack, an attacker would need to put each 4 bytes
output in the standard AES state. To do so, he has to check 61200 4

2 63
combinations. The complexity for recovering mixing bijections for a round would
be then 4

≈

2 25 2 63 =2 90 . For two rounds, the complexity is bounded by 2 91 · ·

computation steps.