Encryption
February 15, 2008
AES Encryption
University of Central Florida
Encryption
Goal: Optimization walkthrough using encryption as the example AES - Advanced Encryption Standard
February 15, 2008
AES Encryption
University of Central Florida
AES
Works on 128 bits at a time in a 4x4 state array or 16 byte blocks
February 15, 2008
AES Encryption
University of Central Florida
AES - Cipher Algorithm
February 15, 2008
AES Encryption
University of Central Florida
Core Loop
Steps: 1) SubBytes 2) ShiftRows 3) MixColumns 4) AddRoundKey
February 15, 2008
AES Encryption
University of Central Florida
SubBytes
SubBytes is a simple transformation applied to each byte
February 15, 2008
AES Encryption
University of Central Florida
ShiftRows
February 15, 2008
AES Encryption
University of Central Florida
MixColumns
Finite field multiplies (binary polynomials)
February 15, 2008
AES Encryption
University of Central Florida
AddRoundKey
Add (XOR) the key to the state array
February 15, 2008
AES Encryption
University of Central Florida
How do we implement this on the GPU?
How do we represent the state array?
10
February 15, 2008
AES Encryption
University of Central Florida
How do we implement this on the GPU?
How do we represent the state array?
Four registers - four components each [Link] [Link] [Link] [Link]
10
February 15, 2008
AES Encryption
University of Central Florida
How to implement MixColumns?
11
February 15, 2008
AES Encryption
University of Central Florida
How to implement MixColumns?
What about now?
11
February 15, 2008
AES Encryption
University of Central Florida
How to implement MixColumns?
What about now?
11
February 15, 2008
AES Encryption
University of Central Florida
Use lookup tables
How big a table do we need?
12
February 15, 2008
AES Encryption
University of Central Florida
Use lookup tables
How big a table do we need? Bytes: 256 entries How many tables do we need?
12
February 15, 2008
AES Encryption
University of Central Florida
Use lookup tables
How big a table do we need? Bytes: 256 entries How many tables do we need? Swizzilng: arbitrary ordering (one table) Total: One table 256x4bytes
12
February 15, 2008
AES Encryption
University of Central Florida
How to implement ShiftRows?
13
February 15, 2008
AES Encryption
University of Central Florida
How to implement ShiftRows?
Swizzling is free: [Link] [Link] [Link] [Link]
13
= = = =
[Link] [Link] [Link] [Link]
AES Encryption University of Central Florida
February 15, 2008
How to implement SubBytes?
Lookup table again How big and how many tables?
14
February 15, 2008
AES Encryption
University of Central Florida
SubBytes table?
15
February 15, 2008
AES Encryption
University of Central Florida
SubBytes table?
MixColumns table can be pre-computed with SubBytes transform. No SubBytes table is needed.
15
February 15, 2008
AES Encryption
University of Central Florida
Putting it all together
Shiftrows: component swizziling
float4 c0, r0;
SubBytes + MixColumns
c0 =
txMcol[r0.w].wzyx ^ txMcol[r3.z].xwzy ^ txMcol[r2.y].yxwz ^ txMcol[r1.x].zyxw;
r0 = c0 ^ tKeyadd[round_offset]
Add RoundKey: pre-computed round key lookup
What about the XORs? R6XX or DX10 hardware supports native integer operations What about previous generations?
16
February 15, 2008
AES Encryption
University of Central Florida
XOR on floating point hardware
How do you do a XOR using only floating point hardware?
17
February 15, 2008
AES Encryption
University of Central Florida
XOR on floating point hardware
How do you do a XOR using only floating point hardware?
float4 XOR_CALC(float4 a, float4 b) { float4 ret; a*=256; b*=256; float4 pa = frac(a/2.f)*2.f; float4 pb = frac(b/2.f)*2.f; ret = (pa==pb) ? 0 : 1; a -= pa; b -= pb; pa = frac(a/4.f)*4.f; pb = frac(b/4.f)*4.f; ret += (pa==pb) ? 0 : 2; a -= pa; b -= pb; pa = frac(a/8.f)*8.f; pb = frac(b/8.f)*8.f; ret += (pa==pb) ? 0 : 4; a -= pa; b -= pb;
a -= pa; b -= pb; pa = frac(a/32.f)*32.f; pb = frac(b/32.f)*32.f; ret += (pa==pb) ? 0 : 16; a -= pa; b -= pb; pa = frac(a/64.f)*64.f; pb = frac(b/64.f)*64.f; ret += (pa==pb) ? 0 : 32; a -= pa; b -= pb; pa = frac(a/128.f)*128.f; pb = frac(b/128.f)*128.f; ret += (pa==pb) ? 0 : 64; a -= pa; b -= pb; pa = a; pb = b; ret += (pa==pb) ? 0 : 128; return ret/255; }
17
February 15, 2008
AES Encryption
University of Central Florida
Using XOR tables
float4 c0, r0; c0 = txMcol[r0.w].wzyx ^ txMcol[r3.z].xwzy ^ txMcol[r2.y].yxwz ^ txMcol[r1.x].zyxw;
float4 XOR(a,b) { float4 out; out.x = Txor[a.x][b.x]; out.y = Txor[a.y][b.y]; out.z = Txor[a.z][b.z]; out.w = Txor[a.w][b.w]; return out; }
float4 a0,a1,b0,b1,c0,t0,t1; a0 = txMcol[r0.w].wzyx; a1 = txMcol[r3.z].xwzy; t0 = XOR(a0, a1); b0 = txMcol[r2.y].yxwz; b1 = txMcol[r1.x].zyxw; t1 = XOR(a, b); c0 = XOR(t0, t1);
18
February 15, 2008
AES Encryption
University of Central Florida
Using XOR tables
float4 c0, r0; c0 = txMcol[r0.w].wzyx ^ txMcol[r3.z].xwzy ^ txMcol[r2.y].yxwz ^ txMcol[r1.x].zyxw;
float4 XOR(a,b) { float4 out; out.x = Txor[a.x][b.x]; out.y = Txor[a.y][b.y]; out.z = Txor[a.z][b.z]; out.w = Txor[a.w][b.w]; return out; }
float4 a0,a1,b0,b1,c0,t0,t1; a0 = txMcol[r0.w].wzyx; a1 = txMcol[r3.z].xwzy; t0 = XOR(a0, a1); b0 = txMcol[r2.y].yxwz; b1 = txMcol[r1.x].zyxw; t1 = XOR(a, b); c0 = XOR(t0, t1); float4 a, b, c0, r0; a = txMcol[r0.w][r3.z]; b = txMcol[r2.y][r1.x]; c0 = XOR(a, b);
18
February 15, 2008
AES Encryption
University of Central Florida
Analyzing the performance
Whether using ALU or textures what are the performance implications?
19
February 15, 2008
AES Encryption
University of Central Florida
Analyzing the performance
Whether using ALU or textures what are the performance implications? ALU:TEX ratio # fetch instructions Memory access patterns Texture sizes XOR tables achieves rates of ~300 Mbps Can we go faster?
19
February 15, 2008
AES Encryption
University of Central Florida
Latency hiding
20
February 15, 2008
AES Encryption
University of Central Florida
Latency hiding
Use ALU instructions to hide memory fetch latency Solution: Use both ALU and fetches for XOR calculations Mixed instructions reach ~990 Mbps
20
February 15, 2008
AES Encryption
University of Central Florida
What about with native XOR hardware?
int4 c0, c1, c2, c3; for(int i=0; i<9*4; i+=4) { c0 = [Link](int2(r0.x,0)).xyzw ^ [Link](int2(r1.y,0)).wxyz ^ [Link](int2(r2.z,0)).zwxy ^ [Link](int2(r3.w,0)).yzwx; c1 = [Link](int2(r1.x,0)).xyzw ^ [Link](int2(r2.y,0)).wxyz ^ [Link](int2(r3.z,0)).zwxy ^ [Link](int2(r0.w,0)).yzwx; c2 = [Link](int2(r2.x,0)).xyzw ^ [Link](int2(r3.y,0)).wxyz ^ [Link](int2(r0.z,0)).zwxy ^ [Link](int2(r1.w,0)).yzwx; c3 = [Link](int2(r3.x,0)).xyzw ^ [Link](int2(r0.y,0)).wxyz ^ [Link](int2(r1.z,0)).zwxy ^ [Link](int2(r2.w,0)).yzwx; r0 = c0 ^ keys[4 + i]; r1 = c1 ^ keys[5 + i]; r2 = c2 ^ keys[6 + i]; r3 = c3 ^ keys[7 + i]; }
Native XOR reaches performance of ~3.5 Gbps What are the performance issues?
21
February 15, 2008
AES Encryption
University of Central Florida
Can we do better?
22
February 15, 2008
AES Encryption
University of Central Florida
Can we do better?
Bitslicing - treat the processor as a vector processor with each bit representing an ALU unit (i.e. a 32-bit processor is a virtualized 32 vector processor) Everything in AES is be computed using AND, OR, NOT, and XOR gates Using bitslicing, GPU achieves 18.5 Gbps
22
February 15, 2008
AES Encryption
University of Central Florida