Transcript Theorem 1 - IEEE-SA

Alternative Wide Block
Encryption
For Discussion Only
Comparison to Draft Proposal
• Draft proposal uses 65 AES blocks
• Alternative uses 32 AES blocks and 32 modulo P
multipliers.
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
K0
PP3
2K0
PPP1
PPP2
*
PP31
229K0
PPP4
PP32
230K0
XOR
XOR
PPP3
K32 P32
H16
PP4
4K0
XOR
K31 P31
XOR
XOR
PPP31
PPP32
Mixing Function Description
• Mixing function uses the following operations
– Addition module 2^128
•
• “SUM” as in “SUM(H1,…,H16)”
– Multiplication modulo P where P = (2^128-159)
• Indicated by
*
– XOR (addition in GF[2^128])
– Multiplication in GF[2^128] in the case K0 multiplied by powers
of two.
• Secret Keys, K0 ,K1 … K32, unknown to attacker.
– Kn = AES( n, Km ), where Km is main Key
Pseudo-code of Mixing Function
uint128_t HashPrimitive( uint128_t x, uint128_t y, uint128_t kx, uint128_t ky )
{ return
( (x+kx) * (y+ky) ) % P; }
Mix( in uint128_t
P[32],
in uint128_t
T,
in uint128_t
K[32],
out uint128_t PPP[32] )
{
HashSum = HashPrimitive( T, P[2], K[1], K[2] )
for ( i=2; i<=16; ++i )
{
HashSum = HashSum + HashPrimitive( P[2*i-1], P[2*i], K[2*i-1], K[2*i] );
}
PP[1] = P[1] + HashSum;
PPP[1] = PP[1]
for ( i=2; i<=16; ++i )
{
PP[i] = P[i] + K[i] + PP[1];
PPP[i] = PP[i] ^ 2(i-2)K[0]; // exp and mult done in GF[2^128]
}
}
Notes on Pseudo-Code
• “uint128_t” denotes 128 bit unsigned integer type.
• “+” denotes addition modulo 2128 of 128 bit wide quantities.
• “*” denotes multiplication of two 128 bit unsigned integers producing
256 bit unsigned integer result.
• “%” denotes modulo operation. 256 bit unsigned integer on left is
divided by 128 bit unsigned integer on right producing 128 bit
unsigned integer remainder.
• “[x]” denotes subscripting. Subscripts range from 1 to N, except for K
which ranges from 0 to 32.
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 proposed method (EME-32AES) 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
M denotes 2128. All quantities are represented by 128 bits and range in value from 0 to M-1.
“g” denotes the number of blocks in the wide-block. It is assumed to be 32 in this case.
P is the largest 128 bit prime and is equal to M-159.
“+”, “-”, “*”, and “/” represent addition, subtraction, multiplication, and division (multiplicative inverse) modulo P. The
inputs to these operators range from 0 to M-1, but the output is always in least terms and ranges from 0 to P-1.
“%” represents modular reduction. (X%P) equals X if X<P, otherwise it equals X - P.
“#” and “~” are non-standard symbols and represent addition and subtraction modulo M.
Note the following relationships that exist between modulo M and modulo P addition.
(X # Y)%P is equal to either (X+Y) or (X+Y-159)
The equation “X ~ Y= Z” implies one of the following equations must also hold.
X - Y = Z%P
X - Y + 159 = Z%P
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.
Definition:
A “special case” is defined as a case where the inputs to any of the modulo P multipliers, (P i # Ki) or
(T # K1), is greater than or equal to P.
Theorem 2:
If (Pn, T) is any input to the mixing function which is independent of { K0 … Kg }, then the
probability of a special case occurring is no greater than 159*g/M. If N sets of inputs are
selected, the probability of a special case occurring in any of them is no greater than
159*N*g/M.
Proof:
For each input there are exactly 159 out of M possible values of Ki that result in the value of ( A # Ki ) being greater than
or equal to P.
Theorem 3:
If D, E, F, G and H are chosen not including the case of D=F and E=G, and neither {D,E} and {F,G}
constitute a “special case” as defined in theorem 2, 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 16/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.
In order for the above equation to be true, the following equations must be true.
( X + D - A1)*( Y # E ) - ( X + F - A2 )*(Y # G ) + A3 = H%P
A1, A2, and A3 are each either 0 or 159.
This equation can be solved for X as follows.
X*( ( Y # E ) - (Y # G ) ) + ( D - A1)*( Y # E ) - ( F - A2 )*(Y # G ) + A3 = H%P
X%P = ( H%P - ( D - A1 )*( Y # E ) + ( F - A2 )*(Y # G ) - A3 ) / ( (Y # E ) - (Y # G ) )
Since we excluded the special case and E is not equal to G, we can be sure that ( (Y # E ) - (Y # G ) ) is not zero. Since A1,
A2, and A3 each have two possible values, for each value of Y there are at most 8 possible values of X%P that will
work. For each value of X%P there are at most two possible values of X, therefore probability of the original
equation holding is no more than 16/M.
[I suspect the actual probability is much lower than 16/M, but 16/M is easy to prove.]
Theorem 4:
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. Also assume that the
special case defined in theorem 2 does not hold for either set of inputs.
The probability of any collision between PPPm and PPP’m is no greater than 16/M.
The probability of a collision between PPPm and PPP’n or PPPm and PPPn where m is unequal to n
is 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 3 that the probability
that PPPm = PPP’m is no greater than 16/M.
Theorem 5:
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.
159*N*g/M + N2*g2/(2*M) + 16*N2*g/(2*M)
For g>16 and N moderately large, the following provides a simple upper bound.
N2*g2/M
Proof:
The first term represents the probability of the special case defined in theorem 2.
The second term represents the general case of PPPmn and PPPm’n’, with m!=n for which there are N2*g2/2 pairs and
probability of 1/M per pair.
The third term represents a collision of PPPmn and PPPmn’ for which there are N2*g/2 pairs and probability of collision of
16/M per pair.
This equation overstates the actual probability of a collision but provides a valid upper bound.
Theorem 6:
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.