What is a good way to handle longer strings using FPE?

Question

While experimenting with this FPE based on FE1

http://botan.randombit.net/manual/fpe.html

(well actually a port of it in C#) I found when the string length gets too long (number of characters N) basically it's designed to throw an exception

So the byte array for the modulus is limited to this value

    // Normally FPE is for SSNs, CC#s, etc, nothing too big
    private const int MAX_N_BYTES = 128 / 8;

And this is where we check the length of the byte array

    /// <summary>
    /// A simple round function based on HMAC(SHA-256)
    /// </summary>
    private class FPE_Encryptor
    {
        private System.Security.Cryptography.HMACSHA256 mac;

        private byte[] mac_n_t;

        internal FPE_Encryptor(byte[] key,
                         BigInteger n,
                         byte[] tweak)
        {
            mac = new System.Security.Cryptography.HMACSHA256(key);

            mac.Initialize();

            byte[] n_bin = n.encode();

            if (n_bin.Length > MAX_N_BYTES)
                throw new Exception("N is too large for FPE encryption");

            var ms = new MemoryStream();

            ms.update_be(n_bin.Length);
            ms.update(n_bin);

            ms.update_be(tweak.Length);
            ms.update(tweak);

            mac_n_t = mac.ComputeHash(ms.ToArray());
        }

        internal BigInteger F(int round_no, BigInteger R)
        {
            byte[] r_bin = R.encode();
            var ms = new MemoryStream();
            ms.update(mac_n_t);
            ms.update_be(round_no);

            ms.update_be(r_bin.Length);
            ms.update(r_bin);

            byte[] X = mac.ComputeHash(ms.ToArray()).Reverse().ToArray();
            var X_ = new byte[X.Length + 1];
            X.CopyTo(X_, 0);
            X_[X.Length] = 0; // guarantee a positive interpretation
            BigInteger ret = new BigInteger(X_);
            return ret;
        }
    }

However say I want to encode a long string like this "Asddasdasdasdasdasdasdasd"

I'm in Base 52 so my modulus is very large 7944811378381908491977011631194721432371200

Which after converting to byte array using

    internal static byte[] encode(this BigInteger n)
    {
        if (n.IsZero) return new byte[0];
        else return n.ToByteArray().Reverse().SkipWhile(h => h == 0).ToArray();
    }

gives a length of 18, bigger that the maximum 16.

Does anyone have suggestion how to deal with the larger number of characters in the plaintext you want to encrypt? I was thinking to chop it up into fragments and encrypt the pieces if the string gets longer than a maximum value. Would this be acceptable?

Answer 1

FE1 has no inherent maximum length; that limit is imposed by the implementation. The first obvious suggestion would be to use an alternate implementation without that limitation.

Now, lets assume that's not a viable option; that you have to use this particular FE1 implementation.

Now, the problem with chopping up the plaintext into fragments and encrypting those separately is that if someone modifies just one of those encrypted fragments, they'll modify part of the decrypted plaintext, but not all.

I'll suggest a way around that, using the "tweak" that FE1 also provides. This "tweak" value is another input into the FE1 algorithm that modifies how it encrypts data; it is not assumed to be secret, but not be presented to both the encryption and the decryption. What it is intended to do is bind the ciphertext to a particular context (so that the ciphertext cannot be used in any other context).

The idea is to split up the plaintext, and encrypt each one separately; however we use the rest of the message as a tweak. For example, if we split up the plaintext into three sections $P_1, P_2, P_3$, we generate the ciphertext as:

$$C_1 = FE1_k( P_1, 0 || P_2 || P_3 )$$ $$C_2 = FE1_k( P_2, 1 || C_1 || P_3 )$$ $$C_3 = FE1_k( P_3, 2 || C_1 || C_2 )$$

(where $FE1_k(A, B)$ means "the $FE1$ encryption of $A$, using key $k$, with tweak $B$).

In general, ciphertext $C_i$ is defined as $C_i = FE1_k( P_i, i || C_1 || C_2 || ... || C_{i-1} || P_{i+1} || P_{i+2} || ... || P_n )$

To decrypt, you just do things in the opposite order:

$$P_3 = FE1^{-1}_k( C_3, 2 || C_1 || C_2 )$$ $$P_2 = FE1^{-1}_k( C_2, 1 || C_1 || P_3 )$$ $$P_1 = FE1^{-1}_k( C_1, 0 || P_2 || P_3 )$$

By binding each ciphertext block to both the previous and subsequent blocks, you prevent anyone from modifying part of the message without affecting everything. This does assume that your FE1 implementation allows long tweaks.