Format-preserving encryption

Deep dive

How it works

In: key K, tweak T (bytes), numeral string X of n digits in radix r · Out: string Y of n digits in radix r · State: none (key and tweak only) · Cost: 10 rounds; per round one CBC-MAC PRF call, O(n) digits of big-number add

1. Split X into halves A (u = ⌊n/2⌋ digits) and B (v = n − u digits).
2. For round i = 0..9 compute the round value from the other half: S = PRF(K, fixed header P ‖ T ‖ padding ‖ i ‖ NUM(B)). In FF1 the PRF is AES-CBC-MAC over that string, extended to d bytes with further AES calls when the half is wide.
3. Convert S to an integer y and add it to NUM(A) modulo r^m, where m = u on even rounds and v on odd ones. The result is m digits, leading zeros kept.
4. Swap the roles: the old B becomes the new A, the sum becomes the new B.
5. After round 9 output A ‖ B. Decryption runs the rounds backwards and subtracts. The fixed header P holds radix, n, len(A) and the tweak length, so another length or radix gives an unrelated permutation.
6. For a domain that is not a full power of the radix, cycle-walk: re-encrypt the output until it lands in the allowed set. This is a permutation of that set (Black and Rogaway, CT-RSA 2002), expected N/bound tries for a domain of N and an allowed set of size bound.

Revisions, as read on csrc.nist.gov (2026-10-21). Original SP 800-38G (March 2016): FF1 and FF3, domain at least 100 required, at least 1,000,000 recommended. Rev. 1 initial public draft (Feb 2019): FF1 and FF3-1, FF3-1 tweak cut from 64 to 56 bits after Durak–Vaudenay, minimum domain 1,000,000 required. Rev. 1 second public draft (Feb 2025, comments to 2025-04-04): FF3 no longer specified because Beyne's tweak-schedule weakness hits FF3 and FF3-1 but not FF1; FF1 requires radix^minlen ≥ 1,000,000; the inverse AES function may not be CIPH; floating point is banned. I found no final Rev. 1: its /r1/final page returns "not found". FF3 and FF3-1 use 8 rounds (from the original spec, not re-checked here).

Code

Generic radix-10 Feistel in FF1's shape (10 rounds, alternating half lengths, modular addition in radix^m) with a pluggable round function. Halves of up to 19 digits fit u64. The demo PRF is a toy. Compiled and run (release and debug); all asserts pass.

// FF1-shaped radix-10 Feistel over digit strings. Round function is pluggable.
// The demo PRF is a TOY (keyed SplitMix64 mix): not FF1, never use in production. FF1 needs AES.
const ROUNDS: u8 = 10;
fn num(d: &[u8]) -> u64 { d.iter().fold(0, |a, &x| a * 10 + x as u64) }
fn digits(mut v: u64, m: usize) -> Vec<u8> { // m digits, leading zeros kept
    let mut o = vec![0u8; m];
    for i in (0..m).rev() { o[i] = (v % 10) as u8; v /= 10; }
    o
}
/// round function: (tweak, round index, half) -> pseudo-random u64
type Prf<'a> = &'a dyn Fn(&[u8], u8, &[u8]) -> u64;
fn encrypt(prf: Prf, tweak: &[u8], x: &[u8]) -> Vec<u8> {
    let u = x.len() / 2;
    let (mut a, mut b) = (x[..u].to_vec(), x[u..].to_vec());
    for i in 0..ROUNDS {
        let m = a.len(); // FF1: m = u on even rounds, v on odd (halves swap each round)
        let p10 = 10u64.pow(m as u32);
        let c = (num(&a) % p10 + prf(tweak, i, &b) % p10) % p10; // modular add in radix^m
        a = std::mem::replace(&mut b, digits(c, m));
    }
    [a, b].concat()
}
fn decrypt(prf: Prf, tweak: &[u8], y: &[u8]) -> Vec<u8> {
    let u = y.len() / 2;
    let (mut a, mut b) = (y[..u].to_vec(), y[u..].to_vec());
    for i in (0..ROUNDS).rev() {
        let m = b.len();
        let p10 = 10u64.pow(m as u32);
        let f = prf(tweak, i, &a) % p10; // undo: A = C - F(B); B is the current first half
        b = std::mem::replace(&mut a, digits((num(&b) % p10 + p10 - f) % p10, m));
    }
    [a, b].concat()
}
/// Cycle-walking: re-encrypt until the value lands below `bound` (keeps a non-power-of-10 domain).
fn encrypt_below(prf: Prf, tweak: &[u8], x: u64, width: usize, bound: u64) -> u64 {
    let mut c = x;
    loop {
        c = num(&encrypt(prf, tweak, &digits(c, width)));
        if c < bound { return c; }
    }
}
fn toy_prf(key: u64) -> impl Fn(&[u8], u8, &[u8]) -> u64 { // TOY PRF, not FF1
    move |t, r, h| {
        let mut s = key ^ (r as u64 + 1);
        for &b in t.iter().chain(&[0xFF]).chain(h) {
            s = s.wrapping_add(b as u64 + 0x9E37_79B9_7F4A_7C15);
            s = (s ^ (s >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
            s = (s ^ (s >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
            s ^= s >> 31;
        }
        s
    }
}
fn main() {
    let prf = toy_prf(0x1234_5678_9ABC_DEF0);
    let pan = digits(4111_1111_1111_1111, 16);
    let ct = encrypt(&prf, b"merchant-42", &pan);
    assert_eq!(ct.len(), 16);
    assert!(ct.iter().all(|&d| d < 10)); // same format
    assert_eq!(decrypt(&prf, b"merchant-42", &ct), pan); // round trip
    assert_ne!(ct, encrypt(&prf, b"merchant-43", &pan)); // tweak changes output
    let mut seen = vec![false; 10_000]; // bijection over all 4-digit strings
    for x in 0..10_000u64 {
        let c = encrypt(&prf, b"t", &digits(x, 4));
        assert!(!seen[num(&c) as usize]); seen[num(&c) as usize] = true;
        assert_eq!(num(&decrypt(&prf, b"t", &c)), x);
    }
    let mut seen = vec![false; 5000]; // cycle-walking: permutation of [0, 5000)
    for x in 0..5000u64 {
        let c = encrypt_below(&prf, b"t", x, 4, 5000) as usize;
        assert!(c < 5000 && !seen[c]); seen[c] = true;
    }
    let t = std::time::Instant::now();
    let acc = (0..200_000u64).fold(0u8, |a, i| a ^ encrypt(&prf, b"t", &digits(i, 16))[15]);
    println!("ok {} ns/16-digit encrypt (toy PRF) acc={acc}", t.elapsed().as_nanos() / 200_000);
}

Complexity and constants

• Time: O(rounds × n) digit work plus rounds × PRF. By my reading of Algorithms 3–5, a 16-digit radix-10 value with a tweak of at most 11 bytes gives a one-block header P and a one-block Q: a 2-block CBC-MAC per round, 20 AES block calls in total (derived, not measured).
• Memory: none per value beyond the key schedule; output length equals input length.
• The toy above took order of 550 ns per 16-digit encryption on an Apple M4 Pro (release build, 200,000 runs, a Vec per half). That is Feistel plus digit conversion, not FF1.
• Guessing (NIST Appendix A.1): g guesses hit with probability g/radix^n; for a 9-digit ID, 1,000 guesses give 10^-6.

Efficiency

• Cost: compute-bound and small: digit/integer conversion plus AES calls, no I/O, no state. Measured only for the toy (order of 550 ns, M4 Pro); FF1 adds 20 AES blocks for 16 digits (derived above).
• Levers:
  • Integers inside the round loop, not strings — the toy's Vecs dominate its time (measured here) — hot paths.
  • Cache the key schedule and header P per tweak — saves rebuilding one block per round (reading of Algorithm 5) — many values, few tweaks.
  • Encrypt only the free digits, not the check digit or a clear prefix — shorter halves (design choice) — card-like formats.
  • Cycle-walk only if needed — expected N/bound tries, near 1 when the bound is close to the domain — non-power domains.
• Naive → standard → state of the art:
  • Lookup table of random tokens · one database round trip and a write per new value.
  • FF1 on AES, key schedule cached · 20 local AES blocks per 16 digits, stateless.
  • FF1 with hardware AES and integer halves · memory-bound loop, no allocation.

Implementation notes

• Fix the radix and alphabet mapping at design time; a different mapping is a different permutation. Reject inputs shorter than minlen (radix^minlen ≥ 1,000,000) instead of encrypting them.
• Tweak: non-secret context that differs per column, tenant or merchant; NIST (2PD) says implementations should enforce different tweaks for different instances where feasible.
• Check digits: encrypt the digits without the check digit and recompute Luhn on the output so validators accept it. Leaving a 6-digit BIN clear for routing shrinks the domain: 16 − 6 − 1 leaves 9 digits, 10^9 values.
• Keys: a data key per column or tenant, wrapped by a KMS key (envelope encryption, AES key wrap), never in logs (secrets management). Rotation changes every ciphertext, so it is a re-encryption pass (key rotation); store a key id beside the data.
• Table-based AES leaks through cache timing; use hardware AES or constant-time code.

Pitfalls

• Small domains. Guessing succeeds with probability g/radix^n, and the draft's million-value minimum answers attacks on small domains. A 4-digit PIN is no use case.
• Determinism. Equal inputs give equal outputs under one tweak: frequency analysis works and matching rows are visible. This is also why joins keep working.
• Malleability. Any digit string decrypts; a flipped digit yields another plausible value. Add a MAC outside the string if tampering matters.
• Floating point. NIST cites a Bouncy Castle bug from floating-point arithmetic; use integers.
• FF3. Dropped in the 2025 draft; use FF1.
• The tweak is public. It separates contexts; it adds no confidentiality.

Variants and alternatives

In production

• Finance and payments: card and account numbers in legacy databases and files.
• Public sector and health: ID numbers in test and analytics copies.
• Telecom: phone and subscriber numbers in logs and billing exports.
• HashiCorp Vault Enterprise Transform engine offers FPE via FF1; its docs say FF3-1 is deprecated from Vault 2.2.0 and new FPE transformations use FF1.

Implementations

Sources

• Dworkin, NIST SP 800-38G: Methods for Format-Preserving Encryption, 2016. doi
• NIST, SP 800-38G Rev. 1, initial public draft, 2019. doi
• NIST, SP 800-38G Rev. 1, second public draft, 2025. doi · page
• Durak, Vaudenay, Breaking the FF3 Format-Preserving Encryption Standard over Small Domains, CRYPTO 2017. doi
• Black, Rogaway, Ciphers with Arbitrary Finite Domains, CT-RSA 2002. doi
• Bellare, Rogaway, Spies, The FFX Mode of Operation for Format-Preserving Encryption, 2010 (NIST submission, no link verified).
• HashiCorp, Transform secrets engine. docs