Cryptanalysis of KeeLoq with

COPACOBANA

Martin Novotný1,2, Timo Kasper1

Horst Görtz Institute for IT-Security

1

Ruhr University Bochum

Faculty of Information Technology

2

Czech Technical University in Prague

 Case Study Access Control

Simple access controls: fixed code (“password”)

code

eavesdropper duplicates key (cloning)

but the industry learned…

 Case Study Access Control

advanced theft control: rolling code

code = ek(ni)

rolling code (or hopping code)

code = ek(n) ek() is often a
block cipher
code = ek(n+1)
code = ek(n+2)
….
KeeLoq Hopping Code Generation
INCREMENTS CONSTANT

Synchronization Counter Discrimination Value Func

32

64
Device KEELOQ
Key encryption
Derived from
Manufacturer Key 32

Hopping Code
 So what can we do now?

If we have access to a remote

Recover device key and clone the device

People usually do not lend

their keys to unknown people

In a shop
If we have access to a receiver
Recover manufacturer key and generate new remotes
Identical for all GarageOpeners2000 and corresponding remotes
Device Key Derivation

Serial Number / SEED

32 32
Manufacturer
KEELOQ Key KEELOQ
decryption/ decryption/
64 64
/XOR XOR

32 32

Device Key MS 32 bits Device Key LS 32 bits

 So what can we do now?

After extracting of manufacturing key:

Remotely eavesdrop on 1-2 communications & clone key!

Serial Number,
KeeLoq(n+1)
Device Key Derivation

0h SN
Serial
– 12 b Serial
number – 28Number
Serial
SEED – 60/ SEED
bits number
SEED bits
–SEED
48 bits
– 32 bits scheme #4
#1
#2
#3

Sniffed from
communicatio 32 32
n Manufacturer
KEELOQ Key KEELOQ
decryption/ decryption/
64 64
/XOR XOR
Retrieve
d via
32 DPA 32

Device Key MS 32 bits Device Key LS 32 bits

2Precomputed
1 candidate value
16
28 in SW
values 2
Precomputed
32
candidate values
in SW
KeeLoq Cracker
KeeLoq Cracker
2 (consecutive) hopping codes
sniffe
d
Hopping Code #1 Hopping Code #2

KEELOQ Device Key KEELOQ

decryption Generator decryption

Counter1 Discrim1 F1 Counter2 Discrim1 F2

(Counter2 – Counter1) < 7 ? Discrim1F1 == Discrim2F2 ?

KEY CANDIDATE
Device Key Derivation

0h SN
Serial
– 12 b Serial
number – 28Number
Serial
SEED – 60/ SEED
bits number
SEED bits
–SEED
48 bits
– 32 bits scheme #4
#1
#2
#3

32 32
Manufacturer
KEELOQ Key KEELOQ
decryption/ decryption/
64 64
/XOR /XOR

32 32

Device Key MS 32 bits Device Key LS 32 bits

Precomputed in SW
Precomputed
(228
16 in SW
candidate values)
Precomputed
Generated ininHW
SW
KeeLoq Cracker

Hopping Code #1 Hopping Code #2

KEELOQ Device Key KEELOQ

decryption Generator decryption

Counter1 Discrim1 F1 Counter2 Discrim1 F2

(Counter2 – Counter1) < 7 ? Discrim1F1 == Discrim2F2 ?

KEY CANDIDATE
Device Key Generator

Host computer

32

32 bit register 32 bit counter

64
KeeLoq Cracker

Hopping Code #1 Hopping Code #2

KEELOQ Device Key KEELOQ

decryption Generator decryption

Counter1 Discrim1 F1 Counter2 Discrim1 F2

(Counter2 – Counter1) < 7 ? Discrim1F1 == Discrim2F2 ?

KEY CANDIDATE
 KeeLoq – The Algorithm
State Register, y
7
32 2
4 0
1 1
0 10

NLF

XOR

Key Register, k
7 6 5 4 3 2 1 0 0

64 bit key, 32 bit block length

NLFSR comprising a 5x1 non-linear function
Simple key management: key is constantly rotated
528 rounds, each round one key bit is read
 Lightweight cipher – cheap and efficient in hardware
KeeLoq Encryption
• 32 bit block length, 64 bit key
• NLFSR comprising a 5x1 non-linear
function
• Simple key management: key is
constantly rotated
• 528 rounds, each round one key bit is
read
 Lightweight cipher – cheap and
efficient in hardware

source: Wikipedia
KeeLoq Decryption

like encryption, but

in reverse order 

source: Wikipedia
KeeLoq Decryption

32 bit state

NLF

64 bit key
KeeLoq Decryption

32 bit state 64 bit key

NLF
KeeLoq Decryption

32 bit state 64 bit key

NLF
KeeLoq Decryption

32 bit state 64 bit key

NLF
KeeLoq Decryption

32 bit state 64 bit key

NLF
Unrolled KeeLoq Decryption

32 bit state 64 bit key

NLF
Unrolled KeeLoq Decryption

32 bit state 64 bit key

NLF
… … … …
Unrolled KeeLoq Decryption

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF
Unrolled KeeLoq Decryption

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF
… … … …
Unrolled KeeLoq Decryption

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF
Unrolled KeeLoq Decryption

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF
… … … …
Unrolled KeeLoq Decryption

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF 528 x
… … … …

32 bit state 64 bit key

NLF
… … … …
Unrolled KeeLoq Decryption

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF 528 x
… … … …

32 bit state
each 464
th
round
bit key
registered
NLF
… … … …
Unrolled KeeLoq Decryption

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF
… … … …
Unrolled KeeLoq Decryption

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF
… … … …

32 bit state 64 bit key

NLF
… … … …
 unrolled decrypter
KeeLoq Cracker with 132 pipeline
stages

Hopping Code #1 Hopping Code #2

KEELOQ Device Key KEELOQ

decryption Generator decryption

Counter1 Discrim1 F1 Counter2 Discrim1 F2

(Counter2 – Counter1) < 7 ? Discrim1F1 == Discrim2F2 ?

KEY CANDIDATE
Results

fmax = 110 MHz

110 million keys/s verified in 1 FPGA Spartan 3-1000

32 bit seed: 39 seconds / 1 FPGA

48 bit seed: 5.9 hours / 1 COPACOBANA
60 bit seed: 1011 days / 1 COPACOBANA