3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ There are a number of options, but PKCS#7 is probably the most widely used: en.wikipedia.org/wiki/Padding_(cryptography)#Byte_padding $\endgroup$
    – Daniel S
    Jan 18 at 9:10
  • $\begingroup$ Is it safe to assume that 1) you don't require the ciphertext to keep the input lenght and format? Which is quite likely if you are considering ECB 2) The input has fixed length of 64 bits? $\endgroup$ Jan 18 at 10:23
  • $\begingroup$ Input is always a 64-bit integer. Output can be up to 128 bits. Using FPE or a 64-bit block cipher would work, but I would prefer using more output bits to increase the security. $\endgroup$
    – Sjoerd
    Jan 18 at 10:48

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I think the randomized padding solution has quite a bit of advantage compared to the other schemes. In particular, if format preservation is not necessary, then the randomized padding + verification of padding upon decryption would also insure authenticated encryption kind of security. The FPE scheme will probably require a tweak, even though the plaintext space isn't tiny. $\endgroup$ Jan 18 at 10:15
  • $\begingroup$ When using randomized padding, is it even possible to have padding verification? $\endgroup$
    – Sjoerd
    Jan 18 at 10:43
  • $\begingroup$ I don't understand this myself. Fully random padding certainly not. But randomized basically allows any scheme that results bytes that seem random to an adversary. Ciphertext, authentication tags and hashes (with specific constraints on the input messages) would all be considered randomized. $\endgroup$
    – Maarten Bodewes
    Jan 18 at 10:47
  • 1
    $\begingroup$ @Sjoerd, The idea is that the ciphertext is augmented by the padding (using concatenation for example). Upon decryption, the inner padding is verified against outer one. Now, this adds 64 bits of overhead which might be acceptable depending on what is meant by "not too long in the question". $\endgroup$ Jan 18 at 10:54
  • $\begingroup$ Zero or constant padding in general would work but it has weaker privacy guarantees. In either case the recovered padding must be verified against the expected padding. Also, you should probably not perform too many encryptions under the same key for random padding. $\endgroup$ Jan 18 at 11:01
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.