1、AES and Attacks on Cryptographic HashesJohn MPortions 2004-2005, John Manferdelli. This material is provided without warranty of any kind including, without limitation, warranty of non-infringement or suitability for any purpose. This material is not guaranteed to be error free and is intended for i
2、nstructional use only.JLM 20060212 14:16 1AES History Call for DES successor 1/97 Square begets Rijndael (1998) Rijndael Designers: Vincent Rijmen and Joan Daemen Nine Submissions CAST-256, CRYPTON, DEAL, DFC (cipher), E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, and Twofish
3、. Finalists MARS, RC6, Rijndael, Serpent, and Twofish FIPS 197 published 11/2001JLM 20060212 14:16 2AESPlaintextCiphertextr Roundsk1k2krKey ScheduleKeyJLM 20060212 14:16 3AES Requirements 128, 192, 256 bit keys Algorithms will be judged on the following factors: Actual security of the algorithm comp
4、ared to other submitted algorithms (at the same key and block size). The extent to which the algorithm output is indistinguishable from a random permutation on the input block. Soundness of the mathematical basis for the algorithms security. Other security factors raised by the public during the eva
5、luation process, including any attacks which demonstrate that the actual security of the algorithm is less than the strength claimed by the submitter. Claimed attacks will be evaluated for practicality. Key agility (NSA): “Two blocks encrypted with two different keys should not take much more time t
6、han two blocks encrypted with the same key.JLM 20060212 14:16 4Mars (Multiplication, Addition, Rotation and Substitution)Basic Structure1. Whiten2. 8 rounds of key independent mixing3. 16 rounds of keyed Feistel transforms (2 S-boxes)4. 8 rounds of key independent mixing5. WhitenJLM 20060212 14:16 5
7、RC6 Design Philosophy Leverage our experience with RC5: use data-dependent rotations to achieve a high level of security. Adapt RC5 to meet AES requirements Take advantage of a new primitive for increased security and efficiency: 32x32 multiplication, which executes quickly on modern processors, to
8、compute rotation amounts.Slide by Ron Rivest (Second AES Conference)JLM 20060212 14:16 6Estimate of number of plaintext pairs required to mount a differential attack. (Only 2128 such pairs are available.)Rounds Pairs8 25612 211716 219020 RC6 223824 2299Security against differential attacksInfeasible
9、Slide by Ron Rivest (Second AES Conference)JLM 20060212 14:16 7Rijndael Overview Input p consisting of Nb words k with Nk words (Nk= 4,6,8) State 4 rows, Nb columns Key 4 rows, Nk columns Output c consisting of Nb wordsAll tables filled first col first s0,0, s1,0, s2,0, s3,0, s0,1, JLM 20060212 14:1
10、6 8Rijndael Overview Design Philosophy Wide Trails 32 bit word operations Non-linear substitution uses arithmetic over GF(2) Mixing uses polynomial arithmetic mod (x4+1)JLM 20060212 14:16 9Rijndael Round StructureNr= max(Nk, Nb)+6Nr Nb=4 Nb= 6 Nb=8Nk=4 10 12 14Nk=6 12 12 14Nk=8 14 14 14JLM 20060212
11、14:16 10Rijndael State LayoutState: si,j, i= Nb (mod 4), j= Nb/4, Nb=4j+iFor Nb= 4s0,0 s0,1 s0,2 s0,3s1,0 s1,1 s1,2 s1,3s2,0 s2,1 s2,2 s2,3s3,0 s3,1 s3,2 s3,3JLM 20060212 14:16 11Rijndael Key LayoutKeys: ki,j, i= Nk (mod 4), j= Nk/4For Nk= 4k0,0 k0,1 k0,2 k0,3k1,0 k1,1 k1,2 k1,3k2,0 k2,1 k2,2 k2,3k3
12、,0 k3,1 k3,2 k3,3JLM 20060212 14:16 12Rijndael AlgorithmRijndael (p, k, Nb, Nk) ComputeRoundKeys(K, W0Nr)state= pAddRoundKey(0, state)for (i=1, i0)InvMixCol(state)InvShiftRow(state)for each byte, b in stateInvByteSub(b)AddRoundKey(0, state)p= stateJLM 20060212 14:16 14Review: Arithmetic of GF(2n) Su
13、ppose m(x) is an irreducible polynomial of degree n over GF(2): m(x)= xn + mn-1 xn-1 + + m 0. Let a(x) and b(x) be polynomials of degree 6 RC1= 0x01RCi+1= RCi*”0x2” multiply by “x”JLM 20060212 14:16 24AES Finalist BakeoffScore: 1 (low) to 3 (high). From NIST report 2 Oct 2000.MARS RC6 Rijndael(AES)S
14、erpent TwofishGeneral Security 3 2 2 3 3Implementation 1 1 3 3 2SW Perf 2 2 3 1 1Smart Card Perf 1 1 3 3 2HW Perf 1 2 3 3 2Design features 2 1 2 1 3JLM 20060212 14:16 25Algebraic Attacks - Preview XSL, Courtois, Pieprzyk, Murphy, Robshaw1. Generate equations of higher degree than the original equati
15、ons by multiplying equation of an active S-box by passive S-box equations2. Solve the equations in the formal terms of the equations Estimate of linearly independent equations is necessary Claim that solving the equations for AES was possible because the estimated number of linearly independent equa
16、tions was adequate generated excitement. Coppersmith cast doubt on the number of linearly independent equations.JLM 20060212 14:16 26Stream Ciphers Synchronous stream ciphers The keystream is generated independently of the plaintext and the ciphertext Using Keyed PRNG Asynchronous stream ciphers The
17、 keystream is generated as a function of the key, K, and at most t previous ciphertext symbols.JLM 20060212 14:16 27Stream Cipher Encryption and PRNGsPlaintext:PRNG(seed):Ciphertext:Encryption Equation: cj=pj kjJLM 20060212 14:16 28Synchronous Stream using Linear Feedback Shift Register (LFSR)st+L2 st+L1st+1st a1a0 aL-2 aL-1. . . . . . .ai, sj FqRecurrence: sj+L= S j=0, 1 L-1 aj sj+L-1Polynomial: f(x)= S j=0, 1 L-1 aj xj -xLJLM 20060212 14:16 29LFSR-based keystream generator Nonlinear combination generators Nonlinear filter generatorsJLM 20060212 14:16 30
