6-noninv-phy-attacks-1 (1).pdf

Security in Embedded Hardware Chapter 6: Non-Invasive Physical Attacks Dr.-Ing. Stefan Wildermann Lehrstuhl für Informatik 12 Integrated Circuit Packaging semiconductor die (contains passivation layer (protects die from the functi...

Security in Embedded Hardware Chapter 6: Non-Invasive Physical Attacks Dr.-Ing. Stefan Wildermann Lehrstuhl für Informatik 12 Integrated Circuit Packaging semiconductor die (contains passivation layer (protects die from the functional circuit) surrounding environment) target of invasive attacks bonding wires lead frame (connections for input and output signals of die) resin mold (chip case) Security in Embedded Hardware 2 Physical Attacks Physical Attacks require the physical accessibility and to some extend even intrusion into the target system. Non-Invasive Attacks: Semi-Invasive Attacks: Invasive Attacks: Do not physically harm Require access to the Require access to the internal the device under attack internal components of the components of the device device  De-packaging the chip Exploit side channels  De-packaging the chip Tamper or (partially) destroy But, the passivation layer the passivation layer of the stays intact chip Security in Embedded Hardware 3 Non-Invasive Physical Attacks Non-invasive physical attacks also called side-channel attacks  Usually, the goal is to gather information about cryptographic operations in embedded systems  The attacker has full control over power and clock lines Passive Side-Channel Attacks: The attacker only observes certain physical properties  Timing analysis, power analysis, electromagnetic field analysis, passive acoustic signal analysis active Active Side-Channel Attacks: The attacker tries to induce faults  Fault analysis, glitch analysis Security in Embedded Hardware 4 Passive Side-Channel Attacks (Crytpographic) Input Output Operation Secret Electromagnetic Side-channel Heat Emission Information Timing Power Side-channel Analysis (SCA) Secret Security in Embedded Hardware 5 Timing Side Channel in SEH Exercise 2 Code snipped checks whether input complies with secret passphrase Do you recall from Exercise 2 what’s wrong with this code snippet? For each correctly matched character in the sequence, the evaluation of strcmp() will take longer  Timing side channel Security in Embedded Hardware 6 Timing Attack on AES Security in Embedded Hardware 7  Advanced Encryption Standard (AES) AddRoundKey 128 Bit plaintext consists of 16 Bytes: p[i], i=0,…,15 plaintext p Each Byte p[i] of the plaintext is encoded with one Byte k[i] of the key, i=1, …, 16 Add Round Key key k 9 rounds x x x x x Sub Bytes (S-Box) p p p p p bitwise XOR x x x x p p p p Shift Rows b x x xx p p pp Mix Columns xxxx round keys p ppp Add Round Key k k k k Intermediate (1 to 9) k Plaintext Value (State) Sub Bytes k k k k k k kk Shift Rows round kkXk Add Round Key Round Key key (10) Security in Embedded Hardware 8  Advanced Encryption Standard (AES) SubBytes Each byte of the data block is replaced by another plaintext p according to a known rule (Rijndael substitution box) Add Round Key key k S-Box 9 rounds y y y y y Sub Bytes (S-Box) x x x x x (look up) y y y y x x x x Shift Rows b y y yy x x xx Mix Columns yyyy round keys xxxx Add Round Key Intermediate (1 to 9) Intermediate Value Sub Bytes Value Shift Rows round Add Round Key key (10) Security in Embedded Hardware 9  Advanced Encryption Standard (AES) Shift Rows Bytes are shifted row by row plaintext p Add Round Key key k 9 rounds Sub Bytes (S-Box) y y y y y y y y y y y y y yb y y Shift Rows y y yy yy y y Mix Columns round keys y yyy yyyy Add Round Key (1 to 9) Intermediate Intermediate Sub Bytes Value Value Shift Rows round Add Round Key key (10) Security in Embedded Hardware 10  Advanced Encryption Standard (AES) Mix Columns Data is mixed within each column plaintext p Mix Column as Matrix Multiplication in Galois Field GF(8) Add Round Key key k 9 rounds z z z z z Sub Bytes (S-Box) y y y y y z z z z z Shift Rows y y y y y b 2 3 1 1 z z zz y y yy 1 2 3 1 z Mix Columns y 1 1 2 3 zzzz round keys yyyy 3 1 1 2 z Add Round Key y (1 to 9) Sub Bytes ⊗c(x) Shift Rows round Add Round Key key (10) Security in Embedded Hardware 11 Closer Look at Mixed Column Mixed column involves multiplying bytes 𝑦𝑗,𝑖 with 1, 2, or 3 2 3 1 1 𝑦0,𝑖 𝑧0,𝑖 1 2 3 1 𝑦1,𝑖 𝑧1,𝑖 However, multiplication is not performed on natural numbers 1 1 2 3 𝑦2,𝑖 = 𝑧2,𝑖 but on Galois field 𝐺𝐹(28 ) 3 1 1 2 𝑦3,𝑖 𝑧3,𝑖 Each byte represents an element in 𝐺𝐹(28 )  Byte with 8 Bits 𝒂𝟕 , 𝒂𝟔 , 𝒂𝟓 , 𝒂𝟒 , 𝒂𝟑 , 𝒂𝟐 , 𝒂𝟏 , 𝒂𝟎  Binary polynomial 𝒂𝟕 𝑥 7 + 𝒂𝟔 𝑥 6 + 𝒂𝟓 𝑥 5 + 𝒂𝟒 𝑥 4 + 𝒂𝟑 𝑥 3 + 𝒂𝟐 𝑥 2 + 𝒂𝟏 𝑥 1 + 𝒂𝟎 𝑥 0 Multiplication in 𝐺𝐹(28) is multiplication of two binary polynomials modulo the irreducible polynomial 𝟏𝑥 8 + 𝟎𝑥 7 + 𝟎𝑥 6 + 𝟎𝑥 5 + 𝟏𝑥 4 + 𝟏𝑥 3 + 𝟎𝑥 2 + 𝟏𝑥 1 + 𝟏𝑥 0 Implementation:  Multiplication of 𝒚𝒋,𝒊 with 𝟑: multiplication by (2 + 1)  Multiplication of 𝒚𝒋,𝒊 with 𝟐: 1. Shift byte 𝒚𝒋,𝒊 one position to the left 2. If most significant bit (MSBit) of byte 𝒚𝒋,𝒊 is 1, XOR the result with binary representation of irreducible polynomial: 1 0001 1011 Security in Embedded Hardware 12 Examples: Multiplication 𝟐 ∙ 𝑦𝑗,𝑖 in GF(28) Example 1: Let 𝑦𝑗,𝑖 = 1101 01002  Shift left: 1 1010 100𝟎2 (shift left)  As MSBit was set before the shift, XOR the result with 1 0001 10112 (irreducible polynomial)  Result: 0 1011 00112 (result) Example 2: Let𝑦𝑗,𝑖 = 0101 01002  Shift left:0 1010 10002  As MSBit was not set before the shift, this is the result Multiplication takes one cycle longer when most significant bit (MSBit) is 1  Timing attack is possible Security in Embedded Hardware 13 Closer Look at the Beginning of the AES Encryption at Byte Level At the beginning of the AES encryption, the following steps are performed for each byte 𝑝[𝑖] of the plaintext:  Each byte 𝑝[𝑖] is XORed with a key byte 𝑘[𝑖] 𝟐 3 1 1  The result is input of the AES S-box 1 2 3 1  The output of the S-box is permuted (MixRows) and then multiplied inside the 1 1 2 3 MixColumn block 3 1 1 2 S-Box ⊗c(x) p p p p p x x x x x (lookup) y y y y y y y y y y bitwise p p p p x x x x y y y y y y y y XOR y p p p p x x x x y y y y y y y y y p p p p x x x x y y y y y y y y k k k k k y k k k k k k k k k k X k Security in Embedded Hardware 14 Attack Setting timing 𝒕𝒊,𝟎 Encrypt random data blocks pi ∈ 𝑃 using AES Assumption: The attacker knows the plaintext bytes (e.g, pi [j] ) entering AES and is able to observe the timing 𝒕𝒊,𝒋 of a single byte operation (GF multiplication) inside MixColumn 𝟐 3 1 1 Timing Analysis: Depending on whether the MSBit of the S-box output is 1 or 0, the AES 1 2 3 1 encryption takes a cycle longer or not 1 1 2 3 3 1 1 2 What can we learn from this? S-Box ⊗c(x) pip p p p x x x x x (lookup) y y y y y y y y y y bitwise p p p p x x x x y y y y y y y y XOR y p p p p x x x x y y y y y y y y y p p p p x x x x y y y y y y y y k k k k k y k k k k k k k k k k X k Security in Embedded Hardware 15 Basic Principle of Attack Plaintext byte is known How S-Box works is know Most-significant Bit of byte y[j] bitwise is known S-Box p[j] XOR x[j] (lookup) y[j] (obtained via timing analysis) k[j] key byte is not known Make hypothesis about key:  Make a guess k’[j] for key byte  Compute y’[j] = S-Box(p[j]⨁k’[j])  If the most-significant bit of y’[j] does not match with the known MSBit of y[j], key guess is wrong  If the most-significant bit of y’[j] matches with the known MSBit of y[j], key guess could be wrong or correct How many hypothesis exist for key byte (one Byte = 8 Bit)? 28 = 256 Security in Embedded Hardware 16  Learning About the Key based on the MSBit of the S-Box Output Encrypt multiple For all 256 possible key Compare the MSBit of each y’[j] Most- plaintexts pi ∈𝑃 candidates for this byte with the MSBit extracted via timing significant so that bytes (00 to FF in Hex), compute: analysis. Key candidate leading to Bit of byte pi[j] are known same bits is the correct key byte. yi[j] is yi’[j] = S-Box(p𝐢[j]⨁k’[j]) extracted via timing key hypothesis k’[j] key hypothesis k’[j] analysis pi[j] MSbit pi[j] pi[j] 00 01 02 03 04 … 00 01 02 03 04 … Test with multiple bytes BE 0 BE AE 08 65 7A F4 … BE 1 0 0 0 1 … CA 1 CA 74 1F E8 DD 8B … CA 0 0 1 1 1 … 4B 0 4B B3 D6 3B 52 84 … 4B 1 1 0 0 1 … B5 0 B5 D5 8D A9 4E C8 … B5 1 1 1 0 1 … 81 0 81 0C CD EC 13 97 … 81 0 1 1 0 1 … Bytes are encoded as Hexadecimals (Hex) Only this key byte leads to the observed timing *Example provided by Stefan Mangard, Infineon Technologies AG. behavior. Thus, this is the key byte of the device. Security in Embedded Hardware 17 Alternative Attack, if only Total Encryption Time is known Observations: 1. All parts of the implementation requiring constant timing do not change the attack (this just adds an offset to the overall timing). 2. All data-dependent timings except for the attacked one can be viewed as noise; the elapsed time for the overall AES encryption is on average still smaller if the MSBit of the considered S-Box output is 0 and longer, if it is 1. This leads to the following attack strategy. Security in Embedded Hardware 18 Attack Description Observe the timing of pi ∈ 𝑃 encryptions with random inputs. Select one S-Box output in the first round as the attack target. For all 256 possible key candidates and each input of this S-Box, calculate the MSBit of the S-Box output. For each of the 256 key candidates, calculate the average timing for the encryptions where the MSBit is 1 and the average timing for the encryptions where the MSBit is 0. For each key candidate, compare the difference between these average timings. Select the key as the best guess for the key that leads to the largest difference. If no significant peak occurs, perform more encryptions to further reduce the noise. Repeat this procedure for all S-Box outputs in the first round. Source: F. Koeune and J.-J. Quisquater, “A timing attack against Rijndael”, Technical report,1999. Security in Embedded Hardware 19 Attack on AES Software Implementation Result of an attack on an AES software implementation based on 10,000 timing measurements Security in Embedded Hardware 20