Experiment 6 AES Look up Tables Memory Testing Sorting AES Rijndael Advanced Encryption Standard Contest June 1998 15 Candidates from USA Canada Belgium France Germany Norway UK Isreal Korea Japan Australia Costa Rica August 1999 5 final candidates Mars RC6 Rijndael Serpent Twofish October 2000 1 winner Rijndael Belgium Round 1 Security Software efficiency Round 2 Security Hardware efficiency External format of the AES algorithm plaintext block 128 bits AES key 128 192 256 bits 128 bits ciphertext block Iterative cipher Round Key 0 Initial transformation i 1 Round Key i Cipher Round i rounds Round Key rounds 1 Final transformation i i 1 rounds times RoundKey 0 AddRoundKey i 1 SubBytes AES encryption ShiftRows MixColumns RoundKey i AddRoundKey i Nr 1 SubBytes ShiftRows RoundKey Nr AddRoundKey i i 1 Nr 1 times Order of bytes within input internal state and output arrays SubBytes S box a0 0 a0 1 a0 2 a0 3 b0 0 b0 1 b0 2 b0 3 a1 0 a1 1 aa 1 2 a1 3 b1 0 b1 1 b a1 2 b1 3 a2 0 a2 1 a2 2 a2 3 b2 0 b2 1 b2 2 b2 3 a3 0 a3 1 a3 2 a3 3 b3 0 b3 1 b3 2 b3 3 i j i j SubBytes Look up Table ShiftRows a e b f c g d h i j k l m n o p no shift cyclic shift left by C1 1 cyclic shift left by C2 2 cyclic shift left by C3 3 a b f g h e k l i j p m n o c d MixColumns a0 0 a0 1 aa 0 20 ja0 3 a1 0 a1 1 aa 1 2 a1 3 1 j 2311 1231 1123 3112 b0 0 b0 1ba0 j 0 2 b0 3 b1 0 b1 1 a1 2 b1 3 b1 j a2 0 a2 1 a2 2 a2 3 b2 0 b2 1 a2 2 b2 3 a3 0 a3 1 b3 0 b3 1 a2 j a a a3 j 3 2 3 3 ba2 j b3 j 3 2 b3 3 High diffusion A difference in 1 input byte propagates to all 4 output bytes A difference in 2 input bytes propagates to at least 3 output bytes AddRoundKey a0 0 a0 1 a0 2 a0 3 k0 0 k0 1 k0 2 k0 3 b0 0 b0 1 b0 2 b0 3 a1 0 a1 1 a1 2 a1 3 k1 0 k1 1 k1 2 k1 3 b1 0 b1 1 b1 2 b1 3 a2 0 a2 1 a2 2 a2 3 a3 0 a3 1 a3 2 a3 3 k2 0 k2 1 k2 2 k2 3 k3 0 k3 1 k3 2 k3 3 b2 0 b2 1 b2 2 b2 3 b3 0 b3 1 b3 2 b3 3 simple bitwise addition xor of round keys Rijndael Animation by Enrique Zabala from Uruguay http teal gmu edu courses ECE746 viewgraphs S08 Rijndael ingles 2004 exe S box Based Basic Iterative Architecture Data input round key Encryption circuit Decryption circuit R1 ShiftRows MixColumns round key SubBytes InvSubBytes InvShiftRows round key round key InvMixColumns Data output Memory Testing Memory cell array faults 1 One cell faults Name Stuck at Definition i x x is not possible Cases stuck at 0 x 0 stuck at 1 x 1 Transition i x and Wix transition 0 1 x 0 transition 1 0 x 1 i x Simple detection sequence Wi1 Ri Wi0 Ri Wi0 Wi1 Ri Wi1 Wi0 Ri Memory cell array faults 2 Two cell coupling faults Name Idempotent coupling Inversion coupling toggling Definition j y i x and Wjy i x x symmetric fault if x y asymmetric fault if x y j y and Wjy i x x i is inverted Cases j i j i j i j i y 0 x 0 y 1 x 1 y 0 x 1 y 1 x 0 j i y 0 j i y 1 Simple detection sequence Wi0 Wj0 Wj1 Ri Wj1 Wi1 Wj0 Ri Wj0 Wi1 Wj1 Ri Wj1 Wi0 Wj0 Ri Wi Wj0 Wj1 Ri Wj1 Wi Wj0 Ri Detection Sequence Notation w1 r1 w0 r0 w1 r1 MAX w1 r1 w0 r0 w1 r1 w1 j r1 w0 r0 w1 r1 i w1 r1 w0 r0 w1r1 w1 r1 w0 r0 w1 r1 w1 r1 w0 r0 w1 r1 0 i j Functional RAM Chip Tests Tests for stuck at transition and coupling faults Marching tests 1 Test US MATS MATS w0 r0 w1 r1 w0 r0 w1 r1 w0 2 Test UT Marching 1 0 w0 r0 w1 r1 r1 w0 r0 w1 r1 w0 r0 r0 w1 r1 MATS w0 r0 w1 r1 w0 r0 3 Test UCin March X w0 r0 w1 r1 w0 r0 4 Test Ucid March C w0 r0 w1 r1 w0 r0 w1 r1 w0 r0 Functional RAM Chip Tests Traditional tests 1 Zero one solid pattern memory scan w0 r0 w1 r1 Complexity O n 2 Checkerboard Complexity O n 3 GALPAT GALloping PATtern and Walking 1 0 Complexity O n2 4 GALCOL GALROW Complexity O n n Walking 1 0 Test for d 0 to 1 do begin for i 0 to n 1 do M i d for base cell 0 to n 1 do begin M base cell not d Call READ ACTION M base cell d end end function READ ACTION begin for cell 0 to n 1 base cell excluded do begin if M cell d then output cell end if M base cell not d then output base cell end Memory Testing 7 segment displays I O Interface Joystick Global Controller Test Generator 1 RAM 1 Test Generator 2 RAM 2 Test Generator 3 RAM 3 Test Generator 29 RAM 29 Test Generator 30 RAM 30 Memory Testing with Fault Emulation 7 segment displays I O Interface Joystick Global Controller Test Generator 1 Fault Emulator 1 RAM 1 Test Generator 2 Fault Emulator 2 RAM 2 Test Generator 3 Fault Emulator 3 RAM 3 Test Generator 29 Fault Emulator 29 RAM 29 Test Generator 30 Fault Emulator 30 RAM 30
View Full Document
Unlocking...