Transcript Theorem 1

Wide Block Encryption
5/14/04
For Discussion Only
Physical Implementation
• Uses 32 AES blocks and 32 GF[2^128] multipliers.
• Approximate size in gates of fully combinatorial implementation:
– AES (128 bit key)
– GF[2^128] multiplier
80K gates
40K gates
• Fully combinatorial implementation probably not the desired
implementation, but its size is a good first order metric of
implementation cost.
• Multiplication by constant (2^n) is trivial.
• 256 bit key AES would be 40% larger.
Structure of Alternative
Algorithm
• Algorithm consists of three steps
– A non-linear keyed mixing step
– ECB encryption using AES
– An inverse mixing step.
Wide Block Encryption
Mixing Function
ECB Encryption
Inverse Mixing Function
Mixing Function Diagram
P1
K1 T
K2 P2
K3 P3
K4 P4
…
SUM(H1,…,H16)
*
*
H1
H2
PP2
PP1
PP3
K0
K31 P31
PP4
PP31
4K0
PPP2
*
H16
PP32
230K0
229K0
2K0
PPP1
K32 P32
PPP3
PPP4
PPP31
PPP32
Mixing Function Description
• Mixing function uses the following operations
– Addition in GF[2^128] (bitwise XOR)
•
• “SUM” as in “SUM(H1,…,H16)”
– Multiplication in GF[2^128]
•
*
• Secret Keys, K0 ,K1 … K32, unknown to attacker.
– Kn = AES( n, Km ), where Km is main Key
ECB Encryption Diagram
PPP1
KA
AES
CCC1
PPP2
KA
AES
CCC2
PPP3
KA
AES
CCC3
PPP32
…
KA
AES
CCC32
Proof of Security
•
•
•
•
Mixing function has the property that for any chosen set of inputs, the probability of a
collision on any of the resulting 128 bit output blocks (assuming keys are chosen
randomly) is approximately the same as the probability of a collision occurring in same
size set of random data.
Claim is that it is impossible for attacker to cause ANY collisions on inputs to AES
blocks.
Because output of AES is indistinguishable from random (assuming inputs are collision
free), adaptive attack gains no advantage over non-adaptive attack.
Proof of security is therefore significantly simpler than EME-32-AES since there is no
need to handle the cases of AES collision cause by reuse of previously observed subsets
of data. Any change to any subset of previously observed data causes all AES blocks to
have different and new inputs and outputs.
Notation Used in Proof
“g” denotes the number of blocks in the wide-block. It is assumed to be 32 in this case.
M denotes 2^128.
“+”, “-”, “*”, and “/” represent addition, subtraction, multiplication, and division
(multiplication by multiplicative inverse) in GF[2^128].
Proof
Theorem 1:
If X is a random variable uniformly distributed over M possible values, C is
independent of X, and the following equation holds true
A=B+C+X
where “+” is addition operation for any group, then the probability that A=B is no
greater than 1/M.
Proof:
By definition if C is independent of X, the conditional probability that X= - C0
given that C = C0 is the same as the unconditional probability that X = - C0.
So A=B if and only if X= - C, and this has probability at most 1/M.
Theorem 2:
If D, E, F, G and H are chosen not including the case of D=F and E=G, and D, E, F, G, and H are
independent of X and Y, and X and Y are independent random variables uniformly distributed
between 0 and ( M – 1 ), The equation
( X + D )*( Y + E ) - ( X + F )*( Y + G ) = H
has a probability no more than 1/M of holding true.
Proof:
Assume that E is not equal to G. By symmetry the same argument applies when E=G but D does not equal F.
This equation can be solved for X as follows.
X*( E - G ) + D*( Y + E ) - F*(Y + G ) = H
Since E != G
X = ( H - D*( Y + E ) + F*(Y + G ) ) / ( E - G )
Therefore, for each value of Y, there is exactly one value of X for which the original equation holds true. Therefore, the
probability is 1/M.
Theorem 3:
Let (Pn, T) and (P’n, T’) be two inputs to mixing function defined above and differ somewhere. “n”
ranges from 1 to 32. Assume that K0 … K32 are independent random variables uniformly
distributed from 0 to M-1, and inputs are chosen independently of Kn.
The probability of any collision between PPPm and PPP’m is at most 1/M.
The probability of a collision between PPPm and PPP’n or PPPm and PPPn where m is unequal to n
is at most 1/M.
Proof:
Case (1): PPPm and PPPn or PPPm and PPP’n where m != n
PPPm = PPPn + K0 * (A - B ) + ( PPm - PPn )
PPPm = PPP’n + K0 * ( A - B ) + ( PPm - PP’n )
where “+” and “*” are addition and multiplication in GF[2128]. A and B are constants depending on m
and n, but are never equal. PPm, PPn and PP’n are all independent of K0, so by theorem 1, the
probability that PPPm = PPPn is 1/M.
Case (2): PPm and PP’m where T = T’, Pj = P’j for j > 1, and differ only for j = 1.
D = P’1 - P1, and D is unequal to zero.
PP’m - PPm = D for all m.
Therefore PPPm != PPP’m
Therefore there is never a collision.
Case (3): PPPm and PPP’m where { P, T } differs from { P’, T’ } for some value other than P1. Therefore
one of the values { H1, … , H32 } has differing components from its counterpart {H’1, … , H’32 }. Let
z be the index of an H that has different components. Define the following:
e = 2*z-1
f = 2*z
A = T if z=1, else A = Pe
A’ = T’ if z=1, else A’ = P’e
B = Pf
B’ = P’f
X = Ke
Y = Kf
So given these definitions we can compute the H in question.
H’z - Hz = ( A’ + X ) * ( B’ + Y ) - ( A + X ) * ( B + Y )
It is also the case that either A != A’ or B != B’.
For all m, the following equation holds
PPPm = PPP’m + Hz - H’z + EEE
The exact expression for “EEE” depends on what the values of m and z are, but in all cases “EEE” is an
expression that is independent of X and Y. It therefore follows from theorem 2 that the probability
that PPPm = PPP’m is 1/M.
Theorem 4:
Let (Pmn, Tn) be N sets of inputs to the mixing function. The subscript m ranges from 1
to g, where g is 32 in this case. The subscript n ranges from 1 to N. The inputs are
chosen independently of the keys, Kx, and Kx are independent random variables
uniformly distributed from 0 to M-1. The probability of any collision on any of the
inputs to the ECB encryption layer, PPPmn, is no greater than the following.
N2*g2/(2*M)
Proof:
1/M is the upper bound on the probability of a collision on any of the inputs to any of the AES blocks.
N*g is the total number of such inputs.
Theorem 5:
Assuming AES is secure, the overall encryption scheme is secure in the sense that an
attacker not knowing the key cannot distinguish the resulting encryptions or
decryptions from random data.
Proof:
Consider two black boxes, A and B, that will encrypt or decrypt blocks of data provided by a hypothetical attacker.
Box A implements that algorithm as defined, and B implements the algorithm with all the AES blocks
(including the key generation blocks) replaced by random number generators. If the attacker succeeds in
creating a collision on any AES block, or through other means produces non-random output, then he wins.
If the attackers succeeds in breaking A but not B, then he has successfully distinguished AES from a random number
generator with is contrary to the premise. It is therefore sufficient to show that the attacker cannot break B.
The following discussion applies to B.
It is important to note that the inverse mixing layer is a one to one mapping of its input to its output. Since the input
is pure random, the output is therefore pure random and uniformly distributed across all possibilities, and
most importantly independent of K0 … K32. Therefore any inputs provided by the attacker, even if based on
previous outputs, are still independent of K0 … K32.
Therefore the probability of the attacker creating any collision on the AES inputs are bound by the probability limits
of theorem 5. In the absence of a collision, all the outputs generated are uniformly distributed random values.