crypto1

Overview ¶

Package crypto1 is the pure-Go implementation of the Crypto1 stream cipher used by MIFARE Classic and some HID iCLASS legacy systems.

Algorithm overview ¶

Crypto1 is a 48-bit LFSR-based stream cipher. State is a 48-bit register; a non-linear output filter f(x) produces one keystream bit per clock. The filter is built from boolean functions f_a, f_b, f_c at specific tap positions (see filterOutput below).

References (clean-room reimplementation from the public papers; do NOT copy mfoc/mfcuk/proxmark3 C source):

• Garcia, de Koning Gans, Muijrers, van Rossum, Verdult, Schreur, Jacobs. "Dismantling MIFARE Classic." ESORICS 2008.
• Courtois, Nohl, O'Neil. "Algebraic Attacks on the CRYPTO1 Stream Cipher in MiFare Classic and Oyster Cards." IACR 2008.

Thread safety ¶

A Cipher is not safe for concurrent use. Create one per goroutine, or serialise access externally.

API surface ¶

• Init(key uint64) — load the 48-bit sector key into LFSR positions 0..47.
• Crypt(input uint32) uint32 — clock LFSR 32 times, XOR keystream with input. NO external feedback. Symmetric.
• EncCrypt(input, nr uint32) — like Crypt, but mixes input bits into LFSR feedback (used during the reader-nonce phase of MIFARE auth).
• CryptFeedback(in uint32) — feeds external bits into LFSR feedback while running keystream (used during the tag-nonce nT phase of MIFARE auth).
• Prng(from uint32, n int) — advance the tag PRNG (16-bit LFSR pair, x^16 + x^14 + x^13 + x^11 + 1) n cycles.

Bit ordering ¶

All inputs and outputs are LSB-first. The 48-bit LFSR has bit 0 as the freshest shift-in position; new bits enter at bit 47 each clock. Inputs to Crypt/EncCrypt/CryptFeedback are processed bit-by-bit, LSB first, for `len(input)*8` clocks; with input as uint32 we run 32 clocks.

mfcuk.go — pure-Go offline darkside key recovery.

This implements the offline portion of the mfcuk (MIFARE Classic darkside attack) from Garcia et al. ESORICS 2008 and Courtois 2009. The live-NFC phase (driving malformed authentication frames at a real card) is handled by the Proxmark3 / libnfc integration layer; this package handles the cryptographic core.

Background ¶

The MIFARE Classic ISO14443A framing includes a parity bit for each byte. During authentication, the reader sends {NR}Ks (the reader nonce encrypted with the cipher keystream). The card checks the parity of each received encrypted byte; if a parity bit is wrong, the card sends a 4-bit NACK response instead of the normal {AT}Ks.

The NACK is sent encrypted: the card XORs the constant NACK value (0x5) with the next 4 keystream bits. An attacker who observes (NT, NR, enc_NACK) can compute the 4-bit keystream at that position:

ks_nack[0..3] = enc_NACK XOR 0x5

These 4 bits constrain the 48-bit key. Collecting many (NR_i, Parity_i) pairs — each with a different first-byte of NR — gives enough constraints to reconstruct the key via exhaustive search over the surviving candidates.

Key-stream position ¶

With the cipher initialised as:

Init(key) → CryptFeedback(uid ^ NT) [32 bits] → 8 EncCrypt clocks with NR[0..7]

the NACK 4-bit keystream occupies cipher-clock positions 8..11 of the EncCrypt phase (after the first byte of NR has been absorbed with feedback). The EncCrypt feedback mixes the PLAIN NR bits into the LFSR (LSB-first: bits 0..7 of the NR uint32 = the first 8 cipher clocks), so the cipher state at the NACK position depends on both the key and the low byte of NR.

Search strategy ¶

For each candidate key K:

1. Simulate Init(K) + CryptFeedback(uid ^ NT) → base state S.
2. For each observation (NR_i, P_i): a. Copy S, clock 8 EncCrypt bits using NR_i[0..7] as feedback. b. Collect 4 more keystream bits (NACK window). c. Require those 4 bits == P_i XOR 0x5.
3. A key that passes all observations is returned.

Worst-case complexity is O(2^48 * N) where N is the number of pairs. For keys fitting in 16 bits (the closed-loop test regime) and N=256 pairs the search is sub-millisecond. For full 48-bit keys, callers use RecoverDarksideWithRange with a restricted high-bit range.

The expected survivor count after N observations is 2^48 / 16^N. With N=256 pairs the key is fully over-constrained, but in practice the first failing pair eliminates ~94% of candidates, making the search fast even without algebraic pre-filtering.

Degeneracy note ¶

For certain (uid, nt) combinations a small number of distinct keys (typically 2) produce identical 4-bit NACK keystreams for all 256 NR low-byte values. This is an inherent property of the 4-bit NACK position constraint and is not a bug. Such degeneracies can be resolved by collecting observations at a different NACK byte position (i.e. using a NR that forces the parity error at byte 1 or 2 rather than byte 0). The current implementation uses only the byte-0 NACK position; operator-facing documentation should note this limitation for live capture workflows.

SPDX-License-Identifier: AGPL-3.0-or-later

mfoc.go — pure-Go offline nested-authentication key recovery.

v0.6 status:

• mfoc/mfcuk handlers: REAL — offline nested-authentication key recovery backed by internal/crypto1.RecoverNestedWithRange. Operator provides pre-captured nested-auth nonces (at least 2 NestedAttempts per NestedCapture). For live-NFC attacks requiring a real reader, federate mplogas/pm3-mcp.

This implements the offline portion of the classical mfoc (MIFARE Classic nested attack) from Garcia et al. ESORICS 2008. The live-NFC phase (driving a real reader) is handled by the Flipper / Proxmark3 integration layer; this package handles the cryptographic core that can run without any hardware.

Background ¶

MIFARE Classic's "nested authentication" feature lets a reader authenticate to a second sector without going through a full anticollision cycle. In a nested auth the card sends the new sector's nT encrypted under the cipher state left over from the previous (known-sector) authentication, rather than as a plain random value. This encrypted nT leaks information: an attacker who knows the cipher state at the end of the previous auth can decrypt the nT for the new sector, which yields a valid (uid, nt, nr, ar) tuple that can be fed directly to the mfkey32 rollback in mfkey32.go.

Data capture model ¶

Each NestedAttempt captures one complete nested authentication sequence. The attacker re-authenticates to the known sector before each nested attempt, so the cipher is reset to a fresh known-state for every attempt. Concretely, each attempt has:

• KnownNT, KnownNR: nonces of the known-sector re-authentication for this attempt (the tag issues a fresh nT each time, and the reader chooses a fresh nR — both are captured by the sniffer).
• NTEnc: the encrypted nT the card sent for the target sector in the nested authentication (on-wire value).
• NR, AR: the reader nonce sent to the target sector, and the card's encrypted aR response, both captured by the sniffer.

RecoverNested decrypts each NTEnc to obtain a plain (nt, nr, ar) tuple, then feeds the first two tuples into the mfkey32 rollback to recover the target sector key.

Package crypto1 — Garcia §4 filter-selectivity optimised key recovery.

Algorithm overview — Garcia et al. ESORICS 2008 §4 ¶

The Crypto1 filter f() reads ONLY the 20 odd-indexed LFSR bits at positions {9,11,13,...,47}. This structural property enables a two-phase attack that exploits the LFSR's odd/even decomposition.

The 48-bit state is decomposed into:

oddState  — 24 bits at positions 1,3,5,...,47  (oddState[k] = state[2k+1])
evenState — 24 bits at positions 0,2,4,...,46  (evenState[k] = state[2k])
fullState = interleave(oddState, evenState)

Key structural facts:

1. filterOutput at t=0 reads ONLY oddState bits 4..23. Therefore ks2[0] = filterOdd(oddState) exactly — no approximation.

2. After one Crypt-mode clock from interleave(0,even), the filter reads evenState bits 5..23 plus the even-part feedback bit. Therefore filterEven(even) approximates ks2[1] from the even sub-state.

Two-phase attack ¶

Phase 1 — oddState enumeration with pred16EvenFromOdd filter:

Enumerate 2^24 oddState candidates X. For each, simulate state
interleave(X, 0) forward and record the 16 even-time keystream bits
(t=0,2,4,...,30). Compare against the captured ks2's even-indexed bits.
Expected ~256 survivors from 2^24 when the approximation aligns.

Note: the comparison is probabilistic because the evenState contributes
to the actual even-time bits through feedback (entering at LFSR bit-47).
The first bit (t=0) is exact; subsequent bits are correlated at ~50%.
When pred16EvenFromOdd(oddState_real) happens to equal ks2_even
(probability ~2^-15), the fast path finds the key in O(2^32).

Phase 2 — evenState enumeration per survivor:

For each phase-1 survivor X, enumerate 2^24 evenState candidates Y.
Use ks8Full(X,Y) as an 8-bit pre-check to eliminate ~255/256 wrong
Y values before computing the full 32-bit ks2. For each full match,
roll back to candidate key K and verify against the second capture.

Correctness guarantee ¶

RecoverFast always falls back to RecoverWithRange(0, 1<<32) if the phase-1+phase-2 path does not find the key. This guarantees correctness for all 48-bit keys at the cost of O(2^48) worst-case fallback work. The fallback terminates quickly for small keys (O(2^N) for N-bit keys).

References ¶

• Garcia, de Koning Gans, Muijrers, van Rossum, Verdult, Schreur, Jacobs. "Dismantling MIFARE Classic." ESORICS 2008.
• equipter/mfkey32v2 — bit-packing convention reference (clean-room reimplementation; no code was copied from that project).