--- title: CPA Angriff auf Speck author: Robin Dietrich & Marius Schwarz data: 17.02.22 --- # Agenda * Speck Chiffre * CPA Angriffe * CPA auf Speck * Gegenmaßnahmen * Hiding --- # Speck * Symmentrische ARX Chiffre * Add/Rotate/XOR * Effizient und einfach umzusetzen * Entworfen von der NSA (Zusammen mit der Chiffre Simon) * Performant in Hard-/Software * Speck bietet mehrere mögliche Modis - Anzahl Runden, Schlüssellänge, Blocklänge * Paper: [Simon and Speck: Block Ciphers for the Internet of Things](https://csrc.nist.gov/csrc/media/events/lightweight-cryptography-workshop-2015/documents/papers/session1-shors-paper.pdf) --- # Speck - Setups | Speck | Blocklänge | Schlüssellänge | Runden | | ------------------------------------------------ | --------------------------------------------- | --------------------------------------------- | ----------------------------------------- | | **Speck3264** | **32 Bit** | **64 Bit** | **22** | | Speck4872 | 48 Bit | 72 Bit | 22 | | Speck4896 | 48 Bit | 96 Bit | 23 | | Speck6496 | 64 Bit | 96 Bit | 26 | | Speck64128 | 64 Bit | 128 Bit | 27 | | Speck9696 | 96 Bit | 96 Bit | 28 | | Speck96144 | 96 Bit | 144 Bit | 29 | | Speck128128 | 128 Bit | 128 Bit | 32 | | Speck128192 | 128 Bit | 192 Bit | 33 | | Speck1281256 | 128 Bit | 256 Bit | 34 | --- # Speck - Rundenfunktion ![](img/rundenfunktion.png){width=400px} * Wird für die Generierung des Rundenschlüssels aufgerufen * Wird bei der Verschlüsselung des Klartextes aufgerufen * Arbeitet auf zwei geteiltem Input --- # Speck - Pseudocode ```C pt = Plaintext Bytes Pt = Plaintext as 16 Bit Words ct = Ciphertext Bytes Ct = Ciphertext as 16 Bit Words k = Key as Bytes K = Key as 16 Bit Words // Key Schedule D=K[3], C=K[2], B=K[1], A=K[0] for i in 0..<22 rk[i]=A ER16(B, A, i++) rk[i]=A ER16(C, A, i++) rk[i]=A ER16(D, A, i++) // Encryption Ct[0]=Pt[0]; Ct[1]=Pt[1]; for i in 0..<22 ER16(Ct[1], Ct[0], rk[i++]) ``` --- # Speck - Möglicher Angriff * Angriff der Rundenfunktion * ADD/XOR/ROT Operationen ```C void FuncER16(u16 *x, u16 *y, u16 k) { u16 tmp_x = *x; u16 tmp_y = *y; *x = (((tmp_x)>>(7)) | ((tmp_x)<<(16-(7)))); // ROR(7) *x += *y; *x = *x ^ k; *y = (((tmp_y)<<(2)) | (tmp_y>>(16-(2)))); // ROL(2) *y = *y ^ *x; } ``` --- # Speck - Möglicher Angriff * Der Rundenschlüssel steckt in der XOR Operation: ![](img/er16_enc_rk.png) ![](img/er16_annot.png) --- # Correlation Power Analysis * Variante von Differential Power Analysis (DPA) * Nutzt Pearson Correlation Coefficient (PCC) * **Bei Speck:** Korrelation zwischen Power-Trace und Rundenschlüssel * Vorgehen: - Modell erstellen - Finden der Korrelationen im Modell - Anwenden auf Hardware Implementierung --- # Hamming Weight * Passendes Modell zum 'bewerten' des Stromverbrauchs * Chip hat ein gewissen Basisverbrauch (IDLE) * Werden Bytes im Chip verändert ($0 \rightarrow 1 ; 1 \rightarrow 0$), wird Strom benötigt * Verhalten kann durch die Hamming-Distanz simuliert werden * **Hamming Distanz:** Anzahl der Veränderter Bits: $$HammingDistance(0100101, 0010101) = 2$$ Der Unterschied zweier per XOR verknüpfter Daten, wird als Hamming-Gewicht bezeichnet: $$HammingDistance(0100101, 0010101) = HammingWeight(0100101 \oplus 0010101)$$ --- # Speck - Modell * Einfaches Modell der Speck Verschlüsselung * Kann für die ersten 2 Byte des Rundenschlüssels genutzt werden: ```Python def simple_speck(plaintext, key): Ct_0 = (int(plaintext[1]) << 8) + int(plaintext[0]) # RIGHT Key Ct_1 = (int(plaintext[3]) << 8) + int(plaintext[2]) # LEFT Key Ct_1, Ct_0 = ER16(Ct_1, Ct_0, key) # Calculate Roundfunction return popcount((Ct_1 << 8) + Ct_0) # Return Hamming Weight (aka Popcount) ``` --- # Speck - Simulation 0) Simulation anhand des Modells mit $n$ traces 1) Generieren von $n$ zufälligen Klartexten mit **fixem** Keybyte (+ noise) 2) Simulation aller möglichen Keybytes per Hamming Weight 3) Berechnen des PCC aller Keys über alle traces ![](img/simulation_corr.png) $\rightarrow$ Das korrekte Keybyte ist: 0x68 --- # T-Test * Kann verwendet werden, um _Leakage_ zu erkennen - Gibt das Berechnen einer Chiffre mehr Information zurück als geplant: Leakage - Ausnutzbar z.B. durch die Power Traces * Berechnet durch: ![](img/ttest_calc.png) * Vergleicht zwei unabhängige Stichproben miteinander * Je unterschiedlicher die Mittelwerte $\rightarrow$ desto weniger Leakage --- # T-Test * T-Test der aufgezeichneten Power-Traces: ![](img/t_test_original.png) * Erkennbar, dass Leakage vorhanden sein muss --- # Angriff - Hardware 1) Implementierung von Speck auf CW 2) Aufzeichnen von $n$ Power Traces 3) Berechnung des Software Modells 4) Berechnen der Korrelationen zwischen Modell/Powertraces - Keybyte für Keybyte - Rückrechnen des Rundenschlüssels --- # Korrelationen des ersten Keybytes * Korrelationen des ersten Keybytes * Korrelation fällt höher aus als im Modell * Deutliches Maximum der Korrelation bei 0x22 (Korrektes Keybyte) ![](img/correlation_first_keybyte.png){width=550px} --- # Problem: Blocksize * Bei **Speck3264:** Operationen nicht auf Byte, sondern auf 16-Bit Ebene * Erste Idee: Modell und Korrelation auf $2^16$ Keys * $\rightarrow$ Keyspace ist abdeckbar (65536 Keys) * $\rightarrow$ Zu langsam * $\rightarrow$ Nicht möglich für andere Modis von Speck (32 Bit Subkeys) * **Lösung:** Modell funktioniert auch auf allen Teilbytes per Shift: ```Python rightkey = 0x00 for guess_key in range(256): leftkey = model( (guess_key << 8) + righkey ) for guess_key in range(256): rightkey = model( (leftkey << 8) + guess_key ) ``` * Auch umsetzbar auf Speck mit Blocksize > 16 Bit --- # Problem: $n^{th}$ Keybytes * Modell kann nur für die ersten zwei Keybytes genutzt werden, da: ```C for i in 0..<22 ER16(Ct[1], Ct[0], rk[i++]) ``` * Die bereits bekannten Rundenschlüssel müssen mit eingeschlossen werden * Muss an der richtigen Stelle passieren ($\oplus$-Operation) --- # Problem: $n^{th}$ Keybytes * Anpassung des Modells: ```Python # -------------- for one key -----------------# x = ((x << (16 - ALPHA)) + (x >> ALPHA)) & mod_mask # x = ROR(x, 7) x = (x + y) & mod_mask # x = ADD(x, y) x = x ^ knownkey[0] # -------------- for second key -----------------# y = ((y >> (16 - BETA)) + (y << BETA)) & mod_mask # y = ROL(y, 2) y = y ^ x # y = XOR(y, x) x = ((x << (16 - ALPHA)) + (x >> ALPHA)) & mod_mask # x = ROR(x, 7) x = (x + y) & mod_mask # x = ADD(x, y) x = x ^ knownkey[1] # x = XOR(x, k) # -------------- for third key -----------------# # [...] ``` --- # Korrelationen des ersten Keybytes * Graph zeigt die Korrelationen des ersten Keybytes bis 5000 traces * Ab ~800 Traces hebt sich die Korrelation deutlich hervor ![](img/traces.png){width=550px} --- # Gegenmaßnahmen --- # Hiding * Verstecken des eigentlichen "Leakages" in Rauschen * $\rightarrow$ Erhöhung des vorhandenen Rauschens während der Berechnung * Mehrere Möglichkeiten * Mischen der Instruction-Order * **Hinzufügen von "Dummy Instructionen"** * Clock Jitter --- # Hiding - Code * **Ansatz:** Korrelation kommt von `ER16()` * Add/XOR/Rotate * Hinzufügen weitere AXR Operationen um noise zu erhöhen * Ersetzen von jeder XOR Operation mit folgender Implementierung: ```C uint16_t XOR(uint16_t a, uint16_t b, int random) { uint8_t tmp = random ^ 0x5F; tmp ^= (random ^ a); tmp ^= (tmp ^ b); tmp &= (tmp & a); tmp &= (tmp & b); return a ^ b; } ``` * `Random` wird bei jeder Verschlüsslung erneut generiert --- # Hiding - T-Test * Ergebnisse des T-Tests mit implementierter Hiding Maßnahmen: ![](img/t_test_hiding_random.png) * Bedarf weiterer Analysen, denn Unterschiede der beiden T-Tests sind nur minimal * Laut T-Test **keine** Indikation dass Hiding funktioniert --- # Korrelationen des ersten Keybytes * Besseres Ergebnis der Korrelationen bis 5000 Traces * Korrelationen flachen ab ~800 drastisch ab * Keine Korrelation sticht heraus ![](img/corr_traces_hiding_5k.png){width=550px} - Es war nicht möglich den Angriff erneut durchzuführen - Neue Korrelationen nach einigen Test lediglich bei ~0.18 mit falschem Keybyte - $\rightarrow$ Maßnahme ist erfolgreich --- # Hiding (potentieller) Bypass * Korrelation sollte weiterhin möglich sein, wenn die Operationen in Betracht gezogen werden * Schwierigkeit hängt am Zufallszahlengenerator * **Problem:** Sichere Zufallszahlen auf Embedded Chips sind nicht trivial $\rightarrow$ Bypass konnte **nicht** realisiert werden --- # Referenzen * [Improved Differential Cryptanalysis of Round-Reduced Speck](Improved Differential Cryptanalysis of Round-Reduced Speck) * [Breaking Speck cryptosystem using correlation power analysis attack](Breaking Speck cryptosystem using correlation power analysis attack) * [Speck-R: An ultra light-weight cryptographic scheme for Internet of Things]({Speck-R: An ultra light-weight cryptographic scheme for Internet of Things)