# Encrypt array of int for individual retrieval

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.

-
Your basic idea looks sound(btw 3DES is a 64 bit block cipher), but 64 bits sounds quite low. I'd tend to double it. –  CodesInChaos Jul 31 '12 at 10:23
Thanks for the 3DES info, and for reviewing my design. If I don't get other answers I'll proceed with it. I suppose I could increase the block size without further-increasing the wire-size if I return pairs of IDs in addition to the already-described design. –  shannon Jul 31 '12 at 10:33
I agree with CodeInChaos: as proposed, picking a random 64-bit value has one chance in $2^{16}$ to succeed, this is uncomfortably possible. Using AES (128-bit block) would allow to allocate say 56 bits to the constant and 40 bits to the random, and live safe. –  fgrieu Jul 31 '12 at 10:56
Another thing: as described, the whole protocol seems unnecessarily complex. The client could receive the number of items in the list rather than the list, choose and return an index rather than an item, and leave the rest to the server; that requires no cryptography at all. Probably some context is missing (like: multiple server instances bound to communicate between each other by proxy of the client's encrypted token). –  fgrieu Jul 31 '12 at 11:03
@fgrieu: also, I've implemented the whole application without state so far. I'm trying to keep it that way. Currently, all interactions will survive an application restart. Also, across multiple users and potentially multiple active search results, caching result list indexes (especially if they have to be persisted to the DB) will get to be a bit of a load. –  shannon Jul 31 '12 at 11:12

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 232 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 264, where N ≤ 232 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 264, and the probability of a successful forgery is at most one in 2128.

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 232) with a 64-bit output per item.

-
This is a very complete answer, thank you. Your reference to cryptographic terms, especially ciphertext indistinguistability, is extremely helpful. –  shannon Aug 2 '12 at 4:26