AES Fast ImplementationIntroductionFast Implementation Project RationaleHardware vs. Software ImplementationNeed for H/W Implementation and Higher SpeedsRijndael functions (1)Rijndael functions (2)Basic Algorithm in Reconfigurable HardwareRijndael Flow DiagramRijndael AlgorithmRijndael AlgorithmModified Decryption AlgorithmCrypto Hardware ArchitectureAES Basic Implementation Mathematical ModelAES Fast ImplementationPROPOSED T-Box Implementation16 T-Box ImplementationEncryption/Decryption Unit RAM RequirementsKey SchedulingPossible Rijndael Fast Implementations on FPGABasic Architecture (Iterative Looping)Speed Comparison of Basic vs. Fast ImplementationProject SimulationSimulation ResultsXilinx FPGAProject Synthesis (1)Project Synthesis (2)Synthesis Black BoxPossible Follow-ups (ECE746)Lessons learnedConclusionsQuestionsAES Fast ImplementationAhmed DarwishMS Computer Engineering,George Mason UniversityProf. Kris GajECE646: Cryptology and Network SecurityIntroductionRijndael is the selected algorithm for AESTwo implementations for Rijndael: Basic implementation: more oriented to Hardware realizations Fast Implementation: Recommended for Software realizations to speedup processingFast Implementation Project RationaleVery fast throughput in Software for 32-bit processors Up to 100 times faster than the basic algorithmTested in Altera FPGA by Fischer and DrutarovskyTo test it in Xilinx FPGA Compare with Altera results Compare with Software throughput Conclude on usefulness of such implementation in HardwareHardware vs. Software ImplementationHardware Imp. Advantages Higher performance Fast implementation in S/W has significant improvement over Basic S/W Imp. H/W performance increase is not as significant Higher system securityHardware Imp. Disadvantages Large memory requirements 1 KB per T-Box vs. 256B per S-BoxNeed for H/W Implementation and Higher SpeedsS/W implementations enough for many users Can handle up to 10 and 100 Mbps LANH/W implementations are required for 10 Gigabit Ethernet LAN Using H/W accelerator cards in general purpose computers Many Network based IPSEC gateways requires such high speeds to achieve line rates on high speed interfaces (10 GE, OC-192) E.g ASIC HiFn chipsRijndael functions (1)Rijndael functions (2)Basic Algorithm in Reconfigurable HardwareBasic operations Shift Row (permutation): Cell interconnection reordering Byte Sub : Look-up Table or Block RAMs Add Round Key: XOR (1/2 CLB)Complex Operations Mix Column: Matrix multiplication in Galois field (28) square matrices in Mix Column and Inv Mix Column functions contain constant elements (polynomials in GF(28)), thus this multiplication can be replaced by several XOR (⊕) operations that are simple to implement in FPGA.Rijndael Flow DiagramRijndael Algorithm16K RAM16K RAMRijndael Algorithm16K RAM16K RAMModified Decryption AlgorithmThe order of inverse byte substitution and inverse byte rotation can be changed (both operation are byte oriented. Since Inv. Mix Col. is a linear transformation, the following equation is validInv. Mix Column(d ⊕K) = Inv. Mix Column(d) ⊕Inv. Mix Column(K)Round keys have to be inverted by Inv. Mix Column function with the exception of the first and last round keys.Crypto Hardware ArchitectureAES Basic Implementation Mathematical ModelAES Fast ImplementationPROPOSED T-Box Implementation16 T-Box Implementationx0, x1, x2, x3 represents the round state (each 32 bits), k0, k1, k2, k3 are the current round key, and Tij are the T-boxes, where i is a duplication index and j is the T-box indexEach round is then:t0 = T00[s0>>24] xor T01[s1>>16] xor T02[s2>>8] xor T03[s3] xor k0;t1 = T10[s1>>24] xor T11[s2>>16] xor T12[s3>>8] xor T13[s0] xor k1;t2 = T20[s2>>24] xor T21[s3>>16] xor T22[s0>>8] xor T23[s1] xor k2;t3 = T30[s3>>24] xor T31[s0>>16] xor T32[s1>>8] xor T33[s2] xor k3;s0 := t0; s1 := t1; s2 := t2; s3 := t3;Encryption/Decryption Unit RAM Requirements4 x (256-wordx32bit) T-Box/column = 4 KB RAM=> x (4 columns) => 16 TBOX = 16 KB RAM32k for both encryption and decryptionPlus 32k if implementing Final Rounds via TBOX for higher speeds => Total of 64KB RAM4 XOR per round per column => x 4 columns =16 XORFast implementation: 16 T-Box for encryption and 16 for decryption (32KB RAM)Ultra Fast Implementation: Final Rounds via T-Box (extra 32K RAM)Economic Implementation: 4 T-Box For encryption Decryption computed from S-boxesKey SchedulingKey Scheduling Could be done in the fly as combinational logic Can be also implemented via T-Box (requiring 32 T-BOX for encryption and 32 for decryption) 64KB RAM rk_d(4 + 4*i) := Td00(TO_INTEGER(UNSIGNED(Te04(TO_INTEGER(UNSIGNED( rk(4 + 4*i)(31 downto 24) ))) (7 downto 0) ))) XOR Td01(TO_INTEGER(UNSIGNED(Te04(TO_INTEGER(UNSIGNED(rk(4 + 4*i)(23downto 16))))(7 downto 0)))) XOR Td02(TO_INTEGER(UNSIGNED(Te04(TO_INTEGER(UNSIGNED(rk(4 + 4*i)(15downto 8))))(7 downto 0)))) XOR Td03(TO_INTEGER(UNSIGNED(Te04(TO_INTEGER(UNSIGNED(rk(4 + 4*i)(7 downto 0))))(7 downto 0)))); rk_d(5 + 4*i) := …. … Or use Memory of Internal keys 2 Arrays of 60x32 bit session keys for both encryption and decryptionPossible Rijndael Fast Implementations on FPGABasic Iterative Looping Architecture The only possible architecture for T-BOX Fully Unrolled and Outer Round Pipelining designs require huge amount of memory T-BOX Architecture composed of ROM’s and XOR(S) leaves no room for Inner Round Pipelining Advantages: Minimum Area Disadvantages Impact on Speed due to loop iterations (one per clock cycle)Basic Architecture (Iterative Looping) # clock cycles = # rounds Speed(ba) = 128/ #rounds × clock_periodSpeed Comparison of Basic vs. Fast ImplementationMuch higher speeds (12.2 Gbps) realized with Basic Implementation using Inner and Outer Round PipeliningProject SimulationVHDL With ModelSim simulation toolBehavioral Architecture with sequential logicBoth Asynchronous and clocked processes were implementedTest-bench with NIST FIPS 197 Test Vectors and Round Keys Simulation Results: All tests were OKSimulation ResultsXilinx FPGAProject Synthesis (1)Performed initial synthesis on xilinix ISE 5.1 Foundation SeriesProject synthesized into a Fully Unrolled architecture Required 1536 256x32 ROMs (1.536 MB) For both encryption and decryption, plus Final Round plus Inverse Mix Column Key Scheduling 768 256x32 bit ROMs (768 KB) without
View Full Document
Unlocking...