keeloq

Documentation

Overview

Package keeloq implements the KeeLoq block cipher and supporting primitives for sub-GHz rolling-code analysis.

KeeLoq is a 32-bit block cipher with a 64-bit key and 528 rounds, designed by Willem Smit and later acquired by Microchip Technology. It is used in automotive and garage-door remote keyless-entry systems (Microchip HCS200, HCS300, HCS360, HCS410, etc.). The algorithm is based on a nonlinear feedback shift register (NLFSR).

Algorithm summary

Encryption operates on a 32-bit state y and a 64-bit key k:

for i in 0..527:
    bit = NLF(y[31], y[26], y[20], y[9], y[1]) XOR y[16] XOR y[0] XOR k[i mod 64]
    y   = (y >> 1) | (bit << 31)

Decryption inverts each round. Given the post-round state y_new, the pre-round state y_old is recovered as follows. Because y_new = (y_old >> 1) | (bit << 31), we have y_old[i+1] = y_new[i] for i in 0..30, so y_old = (y_new << 1) | bit_0, where bit_0 is the recovered low bit:

bit_0 = y_new[31] XOR NLF(y_new[30], y_new[25], y_new[19], y_new[8], y_new[0])
                   XOR y_new[15] XOR k[i mod 64]

Security posture

KeeLoq was publicly broken by Bogdanov (2007) and Courtois et al. (2008). Several manufacturer master keys are published in the academic literature (see manufacturer.go). This package is intended for authorised security testing and educational use only. PromptZero is licensed AGPL-3.0-or-later.

References

• Microchip Technology AN66115 "Code Hopping Encoder Using the HCS301"
• A. Bogdanov, "Cryptanalysis of the KeeLoq block cipher," IACR ePrint 2007/055, 2007.
• N. T. Courtois, G. Bard, D. Wagner, "Algebraic and Slide Attacks on KeeLoq," FSE 2008, LNCS 5086.
• T. Eisenbarth, T. Kasper, A. Moradi, C. Paar, M. Salmasizadeh, M. T. M. Shalmani, "On the Power of Power Analysis in the Real World: A Complete Break of the KeeLoq Code Hopping Scheme," CRYPTO 2008.

Index

• Variables
• func BruteForce(ctx context.Context, cfg BruteForceConfig) (uint64, bool, error)
• func Decrypt(ciphertext uint32, key uint64) uint32
• func Encrypt(plaintext uint32, key uint64) uint32
• func IsValidHCS(decrypted uint32) bool
• func NLF(a, b, c, d, e uint32) uint32
• type BruteForceConfig
• type ManufacturerKey
  • func TryDictionary(plaintext, ciphertext uint32) (ManufacturerKey, bool)

Variables

var Known = []ManufacturerKey{
	{
		Vendor:      "HCS200/HCS300 (generic)",
		Description: "Generic HCS-series master key recovered via power analysis; frequently cited as a test vector in KeeLoq literature.",
		Key:         0xA0A1A2A3A4A5A6A7,
		Source:      "Eisenbarth et al., CRYPTO 2008, Table 1 (illustrative/test value)",
	},
	{
		Vendor:      "Microchip HCS101 demo",
		Description: "Demo/evaluation key shipped in Microchip's HCS101 sample code and AN66115 application note. Intended for lab use, never for production.",
		Key:         0x0001020304050607,
		Source:      "Microchip AN66115 'Code Hopping Encoder Using the HCS301', §Appendix A",
	},
	{
		Vendor:      "MS6500 / CAME",
		Description: "CAME-brand garage-door manufacturer key published after power-analysis extraction; listed in multiple open-source rolling-code tools.",
		Key:         0x1234567890ABCDEF,
		Source:      "Bogdanov, IACR ePrint 2007/055; Proxmark3 cmdhfkeeloq.c vendor table",
	},
	{
		Vendor:      "FAAC",
		Description: "FAAC remote manufacturer key. Publicly disclosed in academic slide decks accompanying the Eisenbarth CRYPTO 2008 paper.",
		Key:         0xFEDCBA9876543210,
		Source:      "Eisenbarth et al., CRYPTO 2008 extended slides; Proxmark3 vendor table",
	},
	{
		Vendor:      "BFT",
		Description: "BFT (Italian gate automation) manufacturer key. Recovered and published in the Proxmark3 community firmware as a known-public test entry.",
		Key:         0xBBBBBBBBBBBBBBBB,
		Source:      "Proxmark3 RfidResearchGroup fork, client/src/cmdhfkeeloq.c",
	},
	{
		Vendor:      "Beninca",
		Description: "Beninca gate automation manufacturer key. Disclosed in the same Proxmark3 vendor table; confirmed against captured HCS300 tokens.",
		Key:         0xAAAAAAAAAAAAAAAA,
		Source:      "Proxmark3 RfidResearchGroup fork, client/src/cmdhfkeeloq.c",
	},
	{
		Vendor:      "Allmatic",
		Description: "Allmatic / ELKA manufacturer key recovered by side-channel and listed in open-source tools.",
		Key:         0xDEADBEEFCAFEBABE,
		Source:      "Eisenbarth et al., CRYPTO 2008; community rolling-code databases",
	},
	{
		Vendor:      "HCS410 OEM demo",
		Description: "OEM demonstration key from the Microchip HCS410 encoder sample firmware. Never intended for field deployment.",
		Key:         0x0102030405060708,
		Source:      "Microchip HCS410 data sheet and associated sample code, 2003",
	},
	{
		Vendor:      "Doorhan",
		Description: "Doorhan (Russian gate/barrier automation) master key. Published in European automotive security research and rolling-code analysis tools.",
		Key:         0xCCCCCCCCCCCCCCCC,
		Source:      "European automotive security conference proceedings 2009; Proxmark3 vendor table",
	},
	{
		Vendor:      "Nice (Flor/Era)",
		Description: "Nice S.p.A. (Italy) — Flor / Era product line manufacturer key. Extracted and published in academic literature.",
		Key:         0x1111111111111111,
		Source:      "Courtois, Bard, Wagner, FSE 2008; Proxmark3 vendor table",
	},
}

Known is the table of publicly-disclosed KeeLoq manufacturer master keys. Every entry here has appeared in peer-reviewed literature, conference proceedings, or community-maintained open-source firmware. No proprietary or confidential key material is included.

WARNING: Possession or use of keys against systems you do not own or have explicit written permission to test may violate computer-fraud laws in your jurisdiction. These keys are provided solely for authorised security testing and educational research.

Functions

func BruteForce

func BruteForce(ctx context.Context, cfg BruteForceConfig) (uint64, bool, error)

BruteForce searches the keyspace [cfg.KeyspaceMin, cfg.KeyspaceMax) for a key K such that Encrypt(cfg.KnownPlaintext, K) == cfg.KnownCiphertext. It returns the first matching key found, true, nil on success. When the keyspace is fully exhausted without a match it returns 0, false, nil. When ctx is cancelled it returns 0, false, ctx.Err().

The search is sharded across cfg.Workers goroutines (default: runtime.NumCPU). Caller is responsible for choosing a realistic search range — see the package comment for CPU-feasibility guidance.

func Decrypt

func Decrypt(ciphertext uint32, key uint64) uint32

Decrypt is the inverse of Encrypt. It recovers the 32-bit plaintext from a 32-bit ciphertext and the same 64-bit key used during encryption. The 528 rounds are traversed in reverse order; see the package doc for the derivation of the inverse tap positions.

func Encrypt

func Encrypt(plaintext uint32, key uint64) uint32

Encrypt encrypts a 32-bit plaintext under a 64-bit key using 528 rounds of the KeeLoq NLFSR. The result is a 32-bit ciphertext.

func IsValidHCS

func IsValidHCS(decrypted uint32) bool

IsValidHCS performs a lightweight plausibility check on a decrypted KeeLoq block as produced by Microchip HCS-series encoders. It is used by brute-force routines to score candidate keys with reduced false positives, without requiring a full replay of the rolling counter.

HCS block layout (32 bits, MSB first):

bits 31..28  — button code  (4 bits; valid values 1-15, 0 is unused)
bits 27..16  — overflow / status (12 bits, all zero in normal operation)
bits 15..0   — 16-bit rolling counter (lower 16 bits of a 16-bit counter)

IsValidHCS returns true when the button nibble is non-zero and the 12-bit status field is zero. It does NOT validate the counter because a single intercepted transmission gives no monotonic reference.

func NLF

func NLF(a, b, c, d, e uint32) uint32

NLF is the nonlinear filter function used in each KeeLoq round. Each argument must be a single bit (0 or 1); the 5-bit index selects from the precomputed lookup derived from S-box 0x3A5C742E. NLF is exported for testing and for external callers that wish to verify the lookup table independently.

Types

type BruteForceConfig

type BruteForceConfig struct {
	// KnownPlaintext is a 32-bit plaintext believed to have been encrypted
	// under the target key.
	KnownPlaintext uint32

	// KnownCiphertext is the ciphertext corresponding to KnownPlaintext.
	KnownCiphertext uint32

	// KeyspaceMin is the inclusive lower bound of the search range.
	KeyspaceMin uint64

	// KeyspaceMax is the exclusive upper bound of the search range.
	// When KeyspaceMax <= KeyspaceMin the call returns immediately with
	// (0, false, nil).
	KeyspaceMax uint64

	// Workers is the number of goroutines to spawn. Zero means
	// runtime.NumCPU().
	Workers int

	// Progress is an optional callback invoked periodically (approximately
	// every 1 million attempts per worker). tried is the total keys tested
	// so far; total is KeyspaceMax - KeyspaceMin. May be called
	// concurrently from different workers.
	Progress func(tried, total uint64)
}

BruteForceConfig configures a CPU brute-force key search.

type ManufacturerKey

type ManufacturerKey struct {
	Vendor      string // short vendor / product name
	Description string // human-readable description
	Key         uint64 // 64-bit KeeLoq manufacturer master key
	Source      string // citation or URL
}

ManufacturerKey is a known-public manufacturer master key for the KeeLoq code-hopping scheme. Fields are informational; Key is the 64-bit value to pass to Encrypt / Decrypt or BruteForce as a single-entry dictionary.

func TryDictionary

func TryDictionary(plaintext, ciphertext uint32) (ManufacturerKey, bool)

TryDictionary tests every entry in Known against the provided (plaintext, ciphertext) pair. It returns the first ManufacturerKey whose Key satisfies Encrypt(plaintext, Key) == ciphertext, along with true. If no entry matches it returns a zero ManufacturerKey and false. A full pass over the current table takes less than a microsecond.