Tokenizing card numbers and SSNs with format-preserving encryption

PCI DSS v4.0 requirement 3.5.1 says a stored card number (PAN) must be unreadable wherever it's stored, and lists the acceptable ways: one-way hashes of the whole PAN, truncation, index tokens, or strong cryptography with proper key management. Privacy rules put similar pressure on national ID numbers such as US Social Security numbers. The trouble is where these values live: a CHAR(16) column, a 9-digit field in a mainframe record layout, a CSV feed whose consumer validates 'digits only', a fraud model keyed on the BIN.

AES-GCM is the right answer for most data, and the wrong shape here. A 16-digit PAN becomes 16 bytes of ciphertext plus a 12-byte nonce and a 16-byte tag, as binary or as 60-odd characters of base64. Every column, interface, and validation rule between the database and the report would have to change. Tokenization replaces the sensitive value with a stand-in of the same shape, so the systems that only store or pass the value along never see the real one, and drop out of the most sensitive part of the audit scope.

Vault tokenization generates a random token and stores the token-to-PAN mapping in a database, the vault. The token has no mathematical relationship to the PAN, so stealing tokens reveals nothing, but the vault itself becomes the crown jewels: it needs replication, backup, and the same protection as the data it replaced, and every detokenization is a lookup in it. EMVCo network tokens, covered in the 3-D Secure and tokenization use case, are vault tokens run by the card networks, and unlike the tokens here they can be used to pay.

Vaultless tokenization computes the token with format-preserving encryption: token = FF1(key, tweak, PAN digits). There's no table to store or replicate, any node with access to the key can tokenize and detokenize, and the same PAN always produces the same token, so tokenized columns can still be joined. The security now rests entirely on the key, which is why FF1 normally runs inside an HSM or behind a KMS-backed service, and on the domain being large enough that the permutation can't be mapped out.

Most deployments don't encrypt all 16 digits. PCI DSS requirement 3.4.1 allows at most the BIN (first six) and last four digits to be displayed, and those are exactly the digits that routing, fraud rules, and 'card ending in 1111' receipts need. So the first six and last four stay in the clear and FF1 encrypts the six digits between them in radix 10. The kept digits go into the tweak: two cards with the same middle digits but different BINs then get unrelated tokens, and an attacker can't move an encrypted middle onto a different card's visible digits and have it decrypt to anything meaningful.

Six digits is 10⁶ = 1,000,000 values, exactly the minimum domain in SP 800-38G Rev. 1, which leaves no slack. A 15-digit American Express number under the same rule leaves only five digits, which is below the minimum, so it needs a different split (keeping fewer digits, or encrypting the whole number). The Luhn check digit is another design decision: FF1 knows nothing about it, so about 9 in 10 tokens fail the check. Some systems keep it that way on purpose, so a token can never be mistaken for a live card number; others adjust a digit so tokens pass validation in systems that insist on it.

A 9-digit SSN encrypted with FF1 in radix 10 is a domain of 10⁹ values: large enough for the standard, small enough to enumerate. Anyone who can call the tokenization service can tokenize all billion possible SSNs and build a reverse table, so for small domains the access control on the tokenize operation matters as much as the key. Determinism adds a second leak: two records with the same token have the same SSN, whoever can read the tokens.

Structure is the other issue. FF1 permutes all 10⁹ digit strings, so the token for a valid SSN can be one that no real SSN can be, such as one starting 000 or 666. That's often fine, and even useful, since it marks the value as a token. When downstream validation must accept the token, the standard technique is cycle-walking: encrypt, and if the result falls outside the valid set, encrypt the result again until it lands inside. Because FF1 is a permutation, this always terminates and is reversible by decrypting the same way.

SP 800-38G originally standardized two modes, FF1 and FF3. FF3 fell to a practical attack over small domains in 2017; its replacement FF3-1 was itself attacked in 2021; and the February 2025 second public draft of SP 800-38G Rev. 1 specifies FF1 only. Some products still offer FF3-1, and some older deployments used FF3. New tokenization schemes should use FF1, and an existing FF3 or FF3-1 deployment is worth putting on a migration list, especially where domains are small. The modes module's format-preserving encryption section has the details.