Is a naive 27bit FPE algorithm using AES-CTR insecure?

Question

I don't have a deep mathematical background in cryptography. I am reading "The FFX Mode of Operation for Format-Preserving Encryption". Section D says the following.

Why feistel? The authors believe that, for FPE, there is, at present, no serious alternative to some form of Feistel. The approach benefits from being a classically known and extensively studied. For all their prescience in identifying FPE, the actual mechanistic ideas described by Brightwell and Smith do not possess any such history and are rather incoherent [5]. Methods to achieve uniform shuffles on large domains, starting with a random function, remain completely impractical [7]. Developing a new confusion/diffusion primitive seems out of that question in terms of delivering assurance and leveraging existing AES experience and implementations, while resurrecting an old confusion/diffusion primitive, say Hasty Pudding [26], is unrealistic for the same reasons. Only Feistel combines decades of history and a corpus of significant academic work.

Because a block cipher in the counter mode such as AES-CTR can encrypt a n bits plain text into a same sized n bits cipher text, it may be thought of a naive FPE cipher. But I guess it is not secure enough because they have invented many complex ciphers and finally standardized a few of them.

Can you explain the security aspects of this naive FPE cipher for n = 27 for example? I understand the concept of permutation, one-to-one mapping, key space, and message space.

Answer 1

FFX supports information in arbitrary radix (aka base) beyond 2 of binary, and multiple allowed lengths. I'll restrict to Radix = 2 and Lengths = {27} , that is plaintext(s) of n = 27 bits.

Because a block cipher in the counter mode such as AES-CTR can encrypt a n-bit plain text into a same sized n-bit cipher text, it may be thought of a naive FPE cipher.

Only with the caveat that AES-CTR requires an Initialization Vector assumed large enough that it's unlikely to lead to keystream reuse; typically an IV of 64 to 128 bits. This IV must be known to decrypting entities, thus typically is made part of the ciphertext, and adds to it's size. This goes straight against the goal of FPE that the ciphertext can fit where the plaintext does.

Is a naive 27bit FPE algorithm using AES-CTR insecure?

Yes, essentially because as soon as we reuse IV, AES-CTR degenerates to XOR with a fixed constant.

We must distinguish different breeds of AES-CTR:

• Normal AES-CTR with proper IV part of the ciphertext

  1. For i-bit IV there's a size increase from n to n+i bits. For n = 27 and i = 96 that's over 255% overhead (so this is not FPE, as explained above).
  2. The cipher is totally malleable, contrary to FPE. In particular, knowing one plaintext/ciphertext pair it's trivial to make ciphertext for any desired plaintext (it's possible to fix this with authenticated encryption, but that's no longer AES-CTR and adds extra size overhead).
  3. A confidentiality compromise following attacks based on information leaks in the receiver is more likely than with properly implemented FPE. E.g. when attackers craft bogus ciphertexts and observe what error code or response time that yields when the receiver proceeds using the decrypted plaintext.
  4. IV reuse would compromise confidentiality (see below AES-CTR with fixed IV).
  5. A small confidentiality improvement over FPE is that it's impossible to detect if two plaintexts are identical by comparing their ciphertexts.

• AES-CTR with implicit IV: as above, but the IV is agreed-upon in a way that solves issue 1. As a typical example, in database encryption, a record index can be used as IV, but issues 2/3/4 typically remain.

• AES-CTR with fixed IV: this truly fits the definition of FPE, but degenerates to XOR with a constant and is extremely insecure. On top of 2/3, the effective key is revealed by leak of any plaintext; there is no diffusion across plaintext bits; the effective keyspace is tiny ( n-bit versus the key size of AES, always 128-bit or more).

Note: in the context, keeping the IV secret does not help at all: every issue there is with fixed IV remains, including reduction of effective key size to n-bit. Secret IV only helps CTR when the plaintext is more than the minimum of (block size, key size + few bits); and then only marginally helps.