Encrypt array of int for individual retrieval

Question

I have limited exposure to cryptographic terminology, so please bear with me.

My end goal is to encrypt integer IDs, before transmitting them to a web client in a list of search results, in a way that prevents enumerating IDs.

Only the transmitting authority should be able to decrypt them. The client will select a single ID from the provided encrypted list, and return it to the authority (in order to request details). This requested ID from the client should be verifiable as authentic. Also, multiple encrypted representations for each ID should be present (the decryption function should be "surjective" relative to a single ID, so that it is not possible to determine from looking at two encrypted IDs whether or not they represent the same decrypted value, thus preventing correlating multiple searches to discover valid IDs).

Here's an ugly example I've devised: Given an array of int32, prepend each with both a 16-bit constant (verified upon decryption, used as a MAC) and a 16-bit random value (discarded upon decryption, provides the surjective quality). Then perform 64-bit blocksize ECB encryption on the resulting array of int64.

My first problem with this example is that I'm not aware of any 64-bit ECB ciphers that are common enough to find in my library (.NET). My second is that I made it up - there's probably a much more direct and less naive route already supported by existing schemes/encryption libraries. My third (less important) issue is that I'm doubling the wire size of my result set (which could be reduced by, for example, requiring the surrounding IDs to be included in the request).

Note that I'd be willing to require client-application cooperation. For example transmit a separate signature, use CBC, and require both the desired ID and the previous one in the following client request. (Note a weakness here is that by varying only one of the IDs, all valid IDs are enumerated.)

Any help, even just correcting my terminology so I can try some new Google-fu, is appreciated.

Answer 1

As CodesInChaos comments, your basic idea seems sound, although a 64-bit block size leaves you with a rather low security margin.

Personally, I'd be more comfortable using a cipher with a 128-bit block size (like AES), zero-padding the IDs to 64 bits, appending 64 random bits and encrypting the resulting 128-bit block. This means that:

• even with the birthday paradox, an adversary must retrieve about 2³² encryptions of a given ID in order to have even odds of finding one duplicate, and
• the probability of a random encrypted block decrypting to a valid ID is N out of 2⁶⁴, where N ≤ 2³² is the number of valid IDs in your database.

Now, you also ask whether there is a standard cryptographic scheme for achieving your goals. In fact, there is: it's called authenticated encryption, and can be implemented either by combining a traditional encryption mode such as CBC, CTR or OFB with a message authentication code in the Encrypt-then-MAC construction, or by using a specialized authenticated encryption mode such as EAX, OCB or GCM.

Authenticated encryption provides IND-CCA2 security, which is short for indistinguishability under an adaptive chosen-ciphertext attack. This is a rather strong security property, and, in particular, subsumes your goals that an adversary should not be able either to guess a valid ciphertext or to determine that two ciphertexts correspond to the same plaintext.

The main disadvantage of standard authenticated encryption modes, for your purposes, is that they normally impose an overhead of at least two whole cipher blocks: one for the IV and one for the MAC. That said, their security margin is also correspondingly larger; for a standard AE mode using a 128-bit block cipher, the number of encryptions needed for a collision is around 2⁶⁴, and the probability of a successful forgery is at most one in 2¹²⁸.

For some modes, it may be possible to reduce this overhead by making the IV implicit. For example, with GCM (or, say, CTR mode with HMAC), you could just transmit a random initial counter value for the first item in your list, and then use successive counter values for the rest of the list. Also, some modes support truncating the MAC to reduce the output length at the expense of the security margin. Thus, combining an implicit IV with, say, a 32-bit truncated MAC, you could achieve security comparable to the 128-bit single block method described above (i.e. forgery probability less than one in 2³²) with a 64-bit output per item.