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

relent95

5/17/24, 9:41 AM

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.

1 + 0

ctr

format-preserving

Score:3

Crypto

fgrieu

5/17/24, 11:56 AM

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.

+ 4

relent95

5/18/24, 2:52 AM

Thanks for a quick answer. I think there's no merit to use a FPE when encrypting a long message having multiple blocks. So, assuming only a single block is encrypted and an IV is kept secret(as a part of a key), the only known weakness except for side channel attacks is the malleability. Am I right?

fgrieu

5/18/24, 8:44 AM

@relent95: Yes, there is no merit to use FPE when encrypting a long message having multiple blocks, and AES-CTR (with proper IV, which needs not be secret) is fine for this. Beware that no, keeping the IV secret does not help at all when encrypting blocks independently. The main problem remains: as soon as we reuse IV, AES-CTR degenerates to XOR with a fixed constant.

relent95

5/18/24, 10:20 AM

Got it. Now I understand that a leak of one pair of matching plain text and cipher text can compromise the key, when using AES-CTR without varying IV. Is there any name for this kind of weakness like the malleability?

fgrieu

5/18/24, 12:24 PM

@relent95: Both the key leak for known plaintext/ciphertext pair, and the malleability (that is possibility to change a ciphertext in a way that changes a known characteristic of the plaintext) are consequences of the so-called _linearity_ of AES-CTR. Actually the proper terminology is that for fixed key, the ciphertext is an _affine_ function of the plaintext.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.