Crypto-1 — The Mifare Classic RFID Cipher Broken by Peeling Chips

1 2 3 4 5 6 7

difficulty levels — click green to claim

> CRYPTO-1 — THE BROKEN RFID CIPHER

crypto1 difficulty: 6–8 invented: 1994, NXP Semiconductors broken: 2008, Nohl & Plötz

The idea in plain English: Crypto-1 is a stream cipher — it generates a pseudo-random keystream that's XORed with data sent between an RFID card and a reader. The cipher uses a 48-bit Linear Feedback Shift Register (LFSR). Think of an LFSR as a row of 48 light switches, where flipping one switch causes a chain reaction through the row according to fixed wiring. Every clock tick shifts the bits and computes a new bit at the end. A clever non-linear filter function (a look-up table of scrambled bits) pulls 20 bits out of the 48-bit state and mixes them together to produce each keystream byte. The result: a stream of seemingly random bytes that XOR-encrypts the communication. The problem? The cipher turned out to be catastrophically weak — its 48-bit key can be recovered from just a few known plaintext bytes.

Why this really exists: In 1994, NXP (then Philips) designed the Mifare Classic chip as a contactless smart card for public transit. It had to be cheap — under $0.50 per chip — and fast enough that a turnstile could read it in under 150 milliseconds. The Crypto-1 cipher was kept proprietary and secret (security-by-obscurity). By 2008, over one billion Mifare Classic chips were in circulation worldwide: London's Oyster card, Hong Kong's Octopus card, Boston's CharlieCard, Dutch OV-chipkaart, and countless building access badges. The cipher was never published, never peer-reviewed — and when it was finally reverse-engineered, it collapsed in hours.

▸ The Story — How Crypto-1 Was Broken

In 2007, security researchers Karsten Nohl and Henryk Plötz decided to find out what was inside the Mifare Classic chip. NXP refused to publish the cipher specification. So the researchers physically reverse-engineered it:

1. They dissolved the plastic casing of a Mifare Classic chip in hot nitric acid

2. They placed the exposed silicon die under a microscope

3. Using a Focused Ion Beam (FIB) workstation, they carefully peeled away layers of the chip, photographing each metal and polysilicon layer

4. By stitching thousands of micrograph images together, they reconstructed the full gate-level netlist — every transistor, every logic gate

5. From the netlist, they extracted the LFSR taps, the non-linear filter function (a 20-bit S-box), and the authentication protocol

It took months of painstaking work. But once the cipher was known, the actual cryptanalysis took only hours. Nohl and colleagues (including David Oswald, Timo Kasper, and Christof Paar) realized that the nested authentication protocol leaked enough information to recover the 48-bit key from as few as 8 known plaintext bytes. Within a year, practical attacks could clone a Mifare Classic card in under a second using a $300 Proxmark3 device.

💡 This was a landmark moment in security history: it proved that secret, proprietary ciphers are almost always weaker than published, peer-reviewed ones. The security-by-obscurity approach of Mifare Classic directly led to the vulnerability.

▸ How the Crypto-1 Cipher Works

The Crypto-1 core is a 48-bit LFSR combined with a non-linear filter function:

LFSR structure:
- 48 flip-flops, each holding one bit (state[0..47])
- Feedback taps at positions: 47, 46, 43, 42, 41, 40, 37, 36, 35, 34, 33, 32,
29, 28, 27, 26, 25, 24, 21, 20, 19, 18, 17, 16, 13, 12, 11, 10, 9, 8,
5, 4, 3, 2, 1, 0
- Feedback polynomial: x⁴⁸ + x⁴³ + x³⁹ + x³⁸ + x³⁶ + x³⁴ + ... (proprietary, extracted from chip)

Non-linear filter:
- 20 bits are tapped from the LFSR at each clock cycle
- They're fed through four 5×1 S-box look-up tables (20-bit → 4-bit output)
- The 4 output bits become one nibble of keystream

Keystream generation:
- Each clock tick shifts the LFSR 1 position and outputs 4 keystream bits
- Keystream is XORed with plaintext to produce ciphertext
- Same operation decrypts (symmetric XOR stream cipher)

▸ How the Attack Works

The critical weakness wasn't the LFSR itself — it was the nested authentication protocol:

1. Reader sends a random challenge (32-bit nonce) to the card

2. Card encrypts it with Crypto-1 and returns Enc(nonce) plus its own random nonce

3. Reader must encrypt the card's nonce to prove it knows the key

4. Critical bug: If the first authentication fails, the card resets but keeps the same LFSR state — allowing the attacker to gather multiple ciphertexts with the same keystream

5. With known plaintext (the nonces are sent in the clear), the attacker recovers keystream = ciphertext XOR plaintext

6. Using the recovered keystream and knowledge of the LFSR structure, the attacker inverts the cipher to recover the 48-bit key via algebraic attack or brute-force over the reduced key space

💡 Modern attacks (like the mfcuk and mfoc tools) can clone a Mifare Classic card in under 2 seconds using a Proxmark3 or even a smartphone with NFC. The attack was so effective that many transit agencies had to upgrade to Mifare DESFire (which uses AES).

▸ Simplified LFSR in Python

Here's a simplified 16-bit LFSR to demonstrate the concept. The real Crypto-1 uses 48 bits with a proprietary polynomial and non-linear filter, but the structure is the same:

class SimpleLFSR:
    """A simplified 16-bit LFSR to illustrate Crypto-1's core mechanism."""
    def __init__(self, seed):
        self.state = seed & 0xFFFF
        # Feedback taps (x^16 + x^14 + x^13 + x^11 + 1)
        self.taps = [16, 14, 13, 11]

    def clock(self):
        """Advance LFSR by one step, return output bit."""
        feedback = 0
        for t in self.taps:
            # Tap position t: bit at position (t-1) from LSB
            feedback ^= (self.state >> (t - 1)) & 1
        out_bit = self.state & 1 # output LSB
        self.state = (self.state >> 1) | (feedback << 15)
        return out_bit

    def generate_keystream(self, n_bits):
        """Generate n_bits of keystream."""
        return sum(self.clock() << i for i in range(n_bits))

# ===== CRYPTO-1 STYLE ENCRYPTION =====
def crypto1_encrypt(plaintext_bytes, key_48bit):
    """Conceptual Crypto-1 encryption (simplified).
    Real Crypto-1 uses a 48-bit LFSR, non-linear filter (4× S-box),
    and proprietary feedback polynomial. This shows the structure."""
    lfsr = SimpleLFSR(key_48bit & 0xFFFF) # simplified: only 16 bits
    keystream = lfsr.generate_keystream(len(plaintext_bytes) * 8)
    ciphertext = bytearray()
    for i, b in enumerate(plaintext_bytes):
        ks_byte = (keystream >> (i * 8)) & 0xFF
        ciphertext.append(b ^ ks_byte)
    return bytes(ciphertext)

# Test:
key = 0xACE1 # 16-bit example (real Crypto-1 = 48 bits)
msg = b"HELLO"
enc = crypto1_encrypt(msg, key)
print(f"Plain: {msg}")
print(f"Encrypted: {enc.hex()}")
# Decrypt is the same operation (XOR stream cipher)
dec = crypto1_encrypt(enc, key)
print(f"Decrypted: {dec}") # b'HELLO'

💡 The crucial difference between this demo and real Crypto-1: a 48-bit (not 16-bit) LFSR, a non-linear filter function (four 5×1 S-box lookups instead of direct output), and a proprietary feedback polynomial extracted from the physical chip.

▸ Real-World Consequences

London Oyster card: Attackers could clone an Oyster card balance — TfL had to deploy gate-side checks and eventually migrate to DESFire
Hong Kong Octopus: The most widely used contactless payment system in the world (90+ million cards) was theoretically clonable with a $50 device
Boston CharlieCard: Used for subway access — critical infrastructure vulnerable to cloning
Building access: Millions of office badges and hotel key cards worldwide could be cloned in seconds
Lesson learned: The Crypto-1 break accelerated adoption of AES-based RFID (Mifare DESFire EV1/EV2, ISO 14443-4)

▸ Why It Matters for Puzzle Solvers

Crypto-1 puzzles in Node 734 may involve:

Reversing an LFSR: given keystream output, find the initial state (seed)
XORing ciphertext with known plaintext to extract keystream
Brute-forcing a reduced keyspace when partial key bits are known
Implementing the Berlekamp-Massey algorithm to recover the LFSR polynomial

The same techniques used to break Crypto-1 apply to any LFSR-based cipher. Understanding the LFSR structure is the foundation.

← Back to all ciphers