Analysis and design of symmetric cryptographic algorithms Jean-Philippe Aumasson PhD public defense 1 / 49 Agenda Introduction I Cryptography and its applications I Symmetric cryptographic algorithms I What is a cryptographic attack? This thesis I Context I Attacks on ciphers I Attacks on hash functions I New design of hash function Conclusion 2 / 49 Introduction 3 / 49 Cryptography “Science of secret” Historical application: encryption Need to know the secret key to encrypt/decrypt 4 / 49 Crypto in practice The Enigma machine (1920’s) Used by German army during WWII. . . . . . broken by British intelligence Modern crypto: different machines, more applications. . . 5 / 49 Secure communication Goals I Message privacy I Sender & recipient authentication I Non-repudiation Tools I Symmetric crypto I Public-key crypto I Key-agreement protocols I Digital signatures I Certificates 6 / 49 Digital money Goals I Anonymity I Fairness I Untraceability I Transferability I etc. Tools I Number theory mathematics I Zero-knowledge protocols I Secure hardware tokens 7 / 49 Conditional access TV Goals I Broadcast operation (satellite, etc.) I Message privacy I Selective reception Tools I Symmetric crypto I Public-key crypto I Secure hardware 8 / 49 Conditional access TV Goals I Broadcast operation (satellite, etc.) I Message privacy I Selective reception Tools I Symmetric crypto I I I I Ciphers Hash functions Public-key crypto Secure hardware 9 / 49 Ciphers Transform a plaintext to a ciphertext Key K necessary to encrypt and to decrypt EncryptK MESSAGE −−−−−−−→ LSJFSDH DecryptK LSJFSDH −−−−−−−→ MESSAGE 10 / 49 Ciphers Transform a plaintext to a ciphertext Key K necessary to encrypt and to decrypt EncryptK MESSAGE −−−−−−−→ LSJFSDH DecryptK LSJFSDH −−−−−−−→ MESSAGE EncryptK “meaningful text” −−−−−−−→ “unreadable text” 10 / 49 Cipher by substitution Replace A by D, B by E, C by F, etc. Ex: EPFL −→ HSIO 11 / 49 Cipher by substitution Replace A by D, B by E, C by F, etc. Ex: EPFL −→ HSIO Used by Julius Caesar in -50. . . 11 / 49 Cipher by substitution Replace A by D, B by E, C by F, etc. Ex: EPFL −→ HSIO Used by Julius Caesar in -50. . . . . . and Sicilian Mafia bosses in 2000’s 11 / 49 Cipher by substitution Replace A by D, B by E, C by F, etc. Ex: EPFL −→ HSIO Used by Julius Caesar in -50. . . . . . and Sicilian Mafia bosses in 2000’s (with less success) 11 / 49 Modern cryptography I Uses computers, not pencil-and-paper I Operates on bits, not on letters I Is hard to break (in general) 12 / 49 Perfect cipher 0111011· · · 0101011 ⊕ Key: 1101011· · · 1001101 = Ciphertext: 1010000· · · 1100110 Plaintext: “XOR” operation on bits 1⊕1=0 0⊕0=0 1⊕0=1 0⊕1=1 13 / 49 Perfect cipher 0111011· · · 0101011 ⊕ Key: 1101011· · · 1001101 = Ciphertext: 1010000· · · 1100110 Plaintext: “XOR” operation on bits 1⊕1=0 0⊕0=0 1⊕0=1 0⊕1=1 Used during the cold war to encrypt the Moscow-Washington telescripter liaison Problem: the key must be as long as the plaintext 13 / 49 Solution: stream ciphers Generate a long string of bits from a short key Plaintext: Key: 101011 −→ Keystream: Ciphertext: 0111011· · · 0101011 ⊕ 1101011· · · 1001101 = 1010000· · · 1100110 Expands a short bit string to a long one If the key of 128 bits, there are 2128 possible keystreams ⇒ ideally, an attack makes 2128 trials 14 / 49 Hash functions Compresses a long bit string to a short one −→ Message: 0100· · · 1101 −→ Hash: 110101 x −→ H(x) Main application: digital signatures (signing short documents is cheaper than long ones) 15 / 49 Hash functions security: preimage resistance Given a hash y, it should be difficult to find x such that H(x) = y 16 / 49 Hash functions security: collision resistance It should be difficult to find x1 and x2 such that H(x1 ) = H(x2 ), x1 6= x2 17 / 49 Hash functions security: randomness The hashes should look like random values 18 / 49 What is an attack? Any mathematical method that finds either. . . I the secret key (stream ciphers) I preimages or collisions (hash functions) I non-randomness in less time than ideally expected Bruteforce: works against any cipher or hash function 19 / 49 What is an attack? 128-bit keys are typical: finding the secret key should require 2128 operations 2128 ≈ 1038 = 100 000 000 000 000 000 000 000 000 000 000 000 000 Using 7 000 000 000 computers at 4 GHz in parallel: It would take 1011.6 years to find the key ≈ 28 times the age of the universe 20 / 49 What is an attack? 128-bit keys are typical: finding the secret key should require 2128 operations 2128 ≈ 1038 = 100 000 000 000 000 000 000 000 000 000 000 000 000 Using 7 000 000 000 computers at 4 GHz in parallel: It would take 1011.6 years to find the key ≈ 28 times the age of the universe Suppose we find an attack in 2120 only It would only take 1 billion years! 20 / 49 What is an attack? 128-bit keys are typical: finding the secret key should require 2128 operations 2128 ≈ 1038 = 100 000 000 000 000 000 000 000 000 000 000 000 000 Using 7 000 000 000 computers at 4 GHz in parallel: It would take 1011.6 years to find the key ≈ 28 times the age of the universe Suppose we find an attack in 2120 only It would only take 1 billion years! The cipher is considered broken 20 / 49 This thesis 21 / 49 Context: crypto public competitions 1. Cryptographers submit algorithms 2. They try to destroy competitors 3. The organizer picks a design that survived 22 / 49 Context: crypto public competitions eSTREAM (2005-08) I I European Network of Excellence (EPFL, CNRS, etc.) New stream ciphers: Salsa20, Grain, etc. SHA-3 Competition (2008-12) I I US Institute of Standards (NIST) Future hash function standard SHA-3 23 / 49 The stream cipher Salsa20 Operations on 32-bit words: I XOR: words viewed as strings of bits 0101 · · · 0101 ⊕ 1010 · · · 1010 = 1111 · · · 1111 I Rotation: words viewed as strings of bits 1000 · · · 0000 ≪ 1 = 0000 · · · 0001 I Integer addition: words viewed as integer numbers 1000 + 1 ≡ 1001 mod 232 (232 − 1) + 1 ≡ 0 mod 232 24 / 49 The stream cipher Salsa20 1. Initialize a table of 32-bit words with 256 key bits 0 x0 B x4 B @ x8 x12 x1 x5 x9 x13 x2 x6 x10 x14 1 x3 x7 C C x11 A x15 2. Repeat 10 times (rounds) x4 ⊕ = (x0 + x12 ) ≪ 7 ; x8 ⊕ = (x4 + x0 ) ≪ 9 ; x9 ⊕ = (x5 + x1 ) ≪ 7 ; x13 ⊕ = (x9 + x5 ) ≪ 9 ; x14 ⊕ = (x10 + x6 ) ≪ 7 ; x2 ⊕ = (x14 + x10 ) ≪ 9 ; x3 ⊕ = (x15 + x11 ) ≪ 7 x7 ⊕ = (x3 + x15 ) ≪ 9 x12 ⊕ = (x8 + x4 ) ≪ 13; x1 ⊕ = (x13 + x9 ) ≪ 13; x6 ⊕ = (x2 + x14 ) ≪ 13; x11 ⊕ = (x7 + x3 ) ≪ 13 x0 ⊕ = (x12 + x8 ) ≪ 18; x5 ⊕ = (x1 + x13 ) ≪ 18; x10 ⊕ = (x6 + x2 ) ≪ 18; x15 ⊕ = (x11 + x7 ) ≪ 18 x1 ⊕ = (x0 + x3 ) ≪ 7 ; x6 ⊕ = (x5 + x4 ) ≪ 7 ; x11 ⊕ = (x10 + x9 ) ≪ 7 ; x2 ⊕ = (x1 + x0 ) ≪ 9 ; x7 ⊕ = (x6 + x5 ) ≪ 9 ; x8 ⊕ = (x11 + x10 ) ≪ 9 ; x12 ⊕ = (x15 + x14 ) ≪ 7 x13 ⊕ = (x12 + x15 ) ≪ 9 x3 ⊕ = (x2 + x1 ) ≪ 13; x0 ⊕ = (x3 + x2 ) ≪ 18; x4 ⊕ = (x7 + x6 ) ≪ 13; x5 ⊕ = (x4 + x7 ) ≪ 18; x9 ⊕ = (x8 + x11 ) ≪ 13; x10 ⊕ = (x9 + x8 ) ≪ 18; x14 ⊕ = (x13 + x12 ) ≪ 13 x15 ⊕ = (x14 + x13 ) ≪ 18 3. Add the initial table to the final table 25 / 49 Attack strategy for 4 rounds Structure permut(K ) ⊕ K , with K a 256-bit key 2 rounds 2 rounds biased differential inverted to detect discovered the bias −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ ←−−−−−−−−−−−−−−− ⊕K ⊕K ⊕K 0 Invert 2 rounds to observe the bias, based on partial knowledge of the key Can be used to verify the correctness of 220 key bits ⇒ can find the key 64 times faster than ideally 26 / 49 Summary and impact We developed the best known attacks on the stream cipher Salsa20 Contributes to increase the confidence in the cipher Salsa20 chosen as I Cowinner of the eSTREAM competition I Alternative to AES by programmers I Basis for a new hash function. . . 27 / 49 New differential attacks Differential equations play an important role in. . . I Quantum mechanics (evolution of a quantum state) i~∂t |ψi = H|ψi I Image processing (PDE-based techniques) ∂I = div (c(x, y , t)∇I) = ∇c · ∇I + c(x, y , t)∆I ∂t I Economics (evolution of stock prices) dSt = µSt dt + σSt dWt I Cryptography (differential attacks) ˆ in ) = ∆ ˆ out Êk (m) ⊕ Êk (m ⊕ ∆ 28 / 49 New attacks: cube testers View the cipher as a black-box Differentiate its implicit Boolean equations n −1 2M fk (vi ) i=0 Try to detect a structure in the differential equations Ex: vs. 29 / 49 Application of cube testers Goal: attacking the stream cipher Grain-128 30 / 49 Application of cube testers Implementation in programmable hardware 31 / 49 Application of cube testers Optimize parameters with evolutionary methods for(i=0;i