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

Speck - Setups

Speck - Rundenfunktion

• Wird für die Generierung des Rundenschlüssels aufgerufen
• Wird bei der Verschlüsselung des Klartextes aufgerufen
• Arbeitet auf zwei geteiltem Input

Speck - Pseudocode

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

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:

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 → 1; 1 → 0), wird Strom benötigt
• Verhalten kann durch die Hamming-Distanz simuliert werden
• Hamming Distanz: Anzahl der veränderten Bits:

HD(0100101,0010101) = 2

Der Unterschied zweier per XOR verknüpfter Daten, wird als Hamming-Gewicht bezeichnet:

HammingDistance(0100101,0010101) = HammingWeight(0100101⊕0010101)

Speck - Modell

• Einfaches Modell der Speck Verschlüsselung
• Kann für die ersten 2 Byte des Rundenschlüssels genutzt werden:

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

1. Simulation anhand des Modells mit n traces
2. Generieren von n zufälligen Klartexten mit fixem Keybyte (+ noise)
3. Simulation aller möglichen Keybytes per Hamming Weight
4. Berechnen des PCC aller Keys über alle traces

→ Das korrekte Keybyte ist: 0x68

Angriff - Hardware

1. Implementierung von Speck auf CW
2. Aufzeichnen von n Power Traces
3. Leakage Test
4. Berechnung des Software Modells
5. Berechnen der Korrelationen zwischen Modell/Powertraces
   • Keybyte für Keybyte
   • Rückrechnen des Rundenschlüssels

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:

• Vergleicht zwei unabhängige Stichproben miteinander
• Je unterschiedlicher die Mittelwerte → desto mehr Leakage

T-Test

• T-Test der aufgezeichneten Power-Traces:

• Erkennbar, dass Leakage vorhanden sein muss

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)

Problem: Blocksize

• Bei Speck3264: Operationen nicht auf Byte, sondern auf 16-Bit Ebene
• Erste Idee: Modell und Korrelation auf 2¹⁶ Keys
• → Keyspace ist abdeckbar (65536 Keys)
• → Zu langsam
• → Nicht möglich für andere Modis von Speck (32 Bit Subkeys)
• Lösung: Modell funktioniert auch auf allen Teilbytes per Shift:

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:

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 (⊕-Operation)

Problem: n^th Keybytes

• Anpassung des Modells:

 # -------------- 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

Gegenmaßnahmen

Hiding

• Verstecken des eigentlichen “Leakages” in Rauschen
• → 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:

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:

• 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

• Es war nicht möglich den Angriff erneut durchzuführen
• Neue Korrelationen nach einigen Tests lediglich bei ~0.18 mit falschem Keybyte
• → 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

→ Bypass konnte nicht realisiert werden

Referenzen

• Improved Differential Cryptanalysis of Round-Reduced Speck
• Breaking Speck cryptosystem using correlation power analysis attack
• Speck-R: An ultra light-weight cryptographic scheme for Internet of Things