How to handle padding when encrypting a value smaller than the block size

Question

I want to encrypt numeric identifiers into ciphertexts that are deterministic and not too long. I am considering AES-128 in ECB mode to encrypt 64-bit integers. How should I pad the 64-bit integers, and specifically, how should I verify the padding?

When encrypting, I could encrypt a block where the first 64 bits are set to zero, and the last 64 bits are the integer I want to encrypt:

00000000 00000123

When decrypting, what do I do with the first 64 bits?

• If I ignore them and don't check that they are all zeroes, all 128-bit ciphertexts result in a valid 64-bit number. For a brute-force attack to find a specific number, the security is reduced from 128 bits to 64 bits.
• If I raise an error when they are not all zero, this provides a kind of padding oracle. The attacker can determine whether a ciphertext is correct or not, and potentially brute-force they key. Is this an actual problem for the security of the system?
• I could also return an invalid identifier such as 0 or a negative number when the padding is incorrect, and continue with the business logic. However, this does require more coordination between the encryption logic and the business logic. The encryption algorithm wouldn't be a generic algorithm to encrypt numbers anymore.

What is the correct way to pad a 64-bit value when encrypting with a 128-bit block cipher?

Answer 1

I want to encrypt numeric identifiers into ciphertexts that are deterministic and not too long. I am considering AES-128 in ECB mode to encrypt 64-bit integers.

You are not considering ECB mode as you are only encrypting one block. You are considering using the block cipher directly. This is important as a block cipher represents a permutation, and (multi-block) ECB doesn't. Of course, using single-block ECB mode without padding is identical to just using the block cipher, which may help you if you're planning to use a high level API.

Generally we try to use Format Preserving Encryption or FPE for this. It might be prudent to look at algorithms for that such as FF1 or FF3. There are security drawbacks for using FPE, and it might be a good idea to look into those. Obviously you are not just limiting the input space but also the output space, as a block cipher is a permutation and therefore the result is 1:1.

Apparently this is deliberate in your case. If you don't need deterministic encryption you could think of padding with random bits instead.

If I ignore them and don't check that they are all zeroes, all 128-bit ciphertexts result in a valid 64-bit number. For a brute-force attack to find a specific number, the security is reduced from 128 bits to 64 bits.

It depends on which attacks you want to be feasible. I presume you mean an attack where the attacker injects numbers into an encryption oracle? Or do you mean one where a decryption oracle is involved?

If I raise an error when they are not all zero, this provides a kind of padding oracle. The attacker can determine whether a ciphertext is correct or not, and potentially brute-force the key. Is this an actual problem for the security of the system?

The key will always be protected by the block cipher. But yes, an attacker can this way check if a ciphertext represents a valid plaintext.

I could also return an invalid identifier such as 0 or a negative number when the padding is incorrect, and continue with the business logic. However, this does require more coordination between the encryption logic and the business logic. The encryption algorithm wouldn't be a generic algorithm to encrypt numbers anymore.

The business logic will simply create an error which will be reflected in the runtime, re-creating the padding oracle attack. Or worse, it will keep running on with erroneous data. This is not a solution.

---

All in all, given the premises, I don't think there is a perfect generic solution. You'll need to weigh the advantages and disadvantages given your specific use case.

---

As indicated in a comment it is possible to use standard padding for this. In that case the rightmost bytes will simply be set to 8 values of `0x08'.

With regards to security there is no difference between explicitly setting leftmost bytes to 0x00 or the rightmost bytes to 0x80. Usually libraries will validate all 8 bytes to have the same value when unpadding, but sometimes they just look at the final byte. It might be a good idea to use this scheme but do the unpadding manually (see below).

---

A relatively cost effective measure is to at least implement time-constant method of validating the padding. That way the attacker won't be able to ascertain which byte of the padding is invalid. This will probably not affect much of security, but it won't hurt it either.

Answer 2

Here is one possibility (using only a single blockcipher call) that would work and provide both confidentiality and integrity under the following conditions:

• The inputs are of fixed-size: 64 bits
• An overhead of 64 bits is acceptable i.e., ciphertext are 192 bits long
• The applications should not encrypt too many values under the same key. More on this later.

The idea is rather simple. For a given key $k$ and 64-bit input $m$, sample a random 64-bit value $r$. Then, encrypt the concatenation of $r$ and $c$. That is $c = \text{Enc}(k, r||m)$. The ciphertext is $(c, r)$. Upon decryption of a ciphertext $(r,c)$, do $r', m' = \text{Dec}(k,c)$. If $r \neq r'$ reject the ciphertext. Otherwise, output $m$ as the decrypted message.

In the above $(\text{Enc, Dec})$ are the "enciphering" and "deciphering" functions of a blockcipher like AES. Assuming the blockcipher behaves as a strong pseudorandom permutation, this scheme provides confidentiality and authenticity even under chosen message attacks. However, this holds only until no collision happens in the chosen randomizer. This brings us back to the third condition above. You will want to use a tool like this to decide on the tradeoff security/encryption limits. But it seems advisable not to go below $1/2^{20}$ for collision probability.