# Determining if a ciphertext can be decrypted

I want to know what the state of the art in the following cryptographic problem is.

Assume a public channel on which encrypted messages are exchanged, using symmetric key encryption. I hold a couple of secret keys. For each ciphertext message on the shared channel, I need to determine if I can decrypt the ciphertext. If not, I ignore the message, otherwise I produce the plaintext as usual. (In my use-case, authentication and message integrity are not relevant.)

What is the industry standard way of doing this, what are the pitfalls? I'd be interested in both, Dolev-Yao formal crypto modes, as well as concrete algorithms. I have no concrete adversary model in mind, what are good adversary models for this question?

• What is the adversary model? What kinds of attacks are you interested in protecting against? – otus Sep 14 '15 at 16:27
• So you own the key (one of your many), used to encrypt the data sent over the wire? Try them all and see which ones yields a correct tag. This is essentially what Bitmessage is doing. – SEJPM Sep 14 '15 at 16:29
• @otus I have no concrete adversary model in mind. I would be interested in good models. I have edited the question accordingly. – Martin Berger Sep 14 '15 at 16:35
• @SEJPM Tagging and then trail decryption is the obvious thing to do. But not being a cryptographer, I'm mortally afraid of overlooking attacks on this scheme. Has this scheme ever been described formally? In particular, there is a certain probability that this mechanism yields a false positive. I will need to have a good handle on such failure probabilities for my use case. – Martin Berger Sep 14 '15 at 16:38
• I'm not sure on this, but I think the probability that a random key lets a given tag appear valid is negligible. – SEJPM Sep 14 '15 at 16:45

In the first part of this answer, I consider the problem of decryption using leaked keys of a protocol not intended for that, which was my original reading of the question. I'll ignore that dominant industry practice is to use random symmetric session keys, leaving little opportunity to "hold a couple of secret keys" without knowing to what session they belong to.

The mode used with symmetric secret keys sometime provides message integrity (e.g. AES-GCM). This gives you a robust mean to determine if a secret key is correct or not, by checking if the integrity test passes. Odds of the wrong key accidentally letting the integrity check pass are demonstrably at least as low as the odds of forgery, thus won't occur for secure modes.

When only encryption is used, any known redundancy of the plaintext can be used to test if the correct secret key was used (deciphering with the wrong key will lead to incorrect plaintext which will be indistinguishable from random). An example of redundancy is the magic number found at the beginning of many practical payloads. Also, for encryption modes with message padding, often the padding is enough for reliable recognition of correct decryption.

For something more general, performing a chi-squared test of the distribution of bytes, or byte pairs for long enough messages, will often work. Exceptions include already compressed plaintext, and plaintext which really is cyphertext.

It is impossible to detect if the right key was used in attempting to decipher a payload consisting exclusively of cyphertext for some other cipher (including OTP, or AES-CTR), as this ability would match the modern definition of an attack of the other cipher.

The actual question turns out to be about building a demonstrably secure protocol intended for selective decryption. Such situation occurs in e.g. satellite internet or TV, and many network applications.

If hiding who the packets are for is not a security objective, it can not harm to include a label in clear in each packet, identifying the key that enciphered the packet, since that's public data. That's the practice in many TCP/IP protocols, where the label is that of the TCP/IP session, thus of the session key. That allows the receivers to decipher the packet with at most one key: the right one, if and only if they hold it. That saves effort/energy. Addition per comment: the tag must somewhat be decided. A sequential number would be fine, if practical (and again if that can be made public). Using a (first-preimage-resistant) hash of the key value would also do, if the hash and cipher are unrelated. The hash can be truncated to save bandwidth, but must be next to $(r-1+2\log_2m)$-bit wide if $m$ keys are around in order to limit the residual risk that two keys get the same tag to $2^{-r}$. An issue (more practical than theoretical) is that hashing a random value and checking if a (truncated) hash is among the keys might well become the best brute-force attack for an adversary, therefore the keys must be at least $(n+\log_2m)$-bit for $n$-bit security.

A situation that can be encountered (e.g. in satellite TV) is that many different receivers need the same large data set. In order to save bandwidth, an option is to encipher all the packets of such large data set with a random key dedicated to this set, and send (previously) that dedicated key enciphered with the key of each intended recipient. The label of the dedicated key can be in clear in the packets for the data set, and in the previous packets for the dedicated key value.

In the rest of this answer, I consider that hiding who the packets are for is an objective. I'll disregard side channel leaks from receivers (which in practice could very well reveal if a receiver uses or disregards a packet, contrary to the objective).

One option (already discussed) is to encipher the packets in a mode with integrity, such as AES-GCM. We do not need to modify this mode, thus can reuse its security analysis. Main issues with this approach: every holder of a key will need to check the integrity of every packets with its key(s), that's effort/energy; and modes with integrity require more effort/energy and bandwidth than pure confidentiality modes.

Another simple and unobjectionable thing is to start all plaintext packets with constant data (e.g. 12 bytes at zero), have all receivers decipher all ciphertext packets with their key(s) and stop wasting effort/energy on this packet/key pair when it is determined that the plaintext does not match the condition. If the cipher is secure by modern standards (CPA), adding this known plaintext demonstrably does not harm. Addition per comment: padding (or better prefixing) the plaintext with a cryptographic hash of the secret key before encryption would also work, but I see no clear advantage compared to the simplest solution. Don't put the bare secret key in the plaintext, that could conceivably have bad interaction with the cipher (e.g. AES-128's first step is a XOR of plaintext and key, so enciphering the key is a slightly special case).

If we go into something bidirectional (e.g. with acknowledge or retries), then things get more complex, and quite hard, in particular because the mere existence of packets sent by receivers will tend to be revealing of something we try to hide. And again, we should fear side channels.

• Thanks. Unfortunately, in my use-case I really do not know what session a message belongs to. I get just opaque ciphertext on the shared channel. I also have to deal with compressed plaintext and plaintext which really is cyphertext, so looking at byte distribution is not an option. Indeed I expect that almost all the messages I see are made from random plaintext. – Martin Berger Sep 14 '15 at 16:50
• I could definitely add message integrity, but it's not needed in my use-case, so would appear to be overkill. In some sense I am looking at the minimal technology needed to solve the problem. – Martin Berger Sep 14 '15 at 16:51
• @Martin Berger: your latest comment suggest that you are in a position to decide the ciphertext format; in that case, why not simply label each packet with an identifier (in clear) of the appropriate key? – fgrieu Sep 14 '15 at 16:57
• Yes, I can use any protocol I like, including plain or encrypted identifiers. But I'm not a cryptographer, I am worried that I overlook something. I wonder if such a scheme has been described in the literature, e.g. as a Dolev-Yao style description in Applied-pi? I will need to produce a formal security proof, so would like to read the existing work. – Martin Berger Sep 14 '15 at 17:18
• Thanks for the additional material, it's very useful. Would it also be safe to use a cryptographic hash of the secret key as tag, or, alternatively, pad the plaintext with the secret key, or a cryptographic hash of the secret key before encryption? – Martin Berger Sep 15 '15 at 6:14

Encrypt-then-MAC schemes offer the ability to authenticate the encrypted data before attempting to decrypt it, which may offer a degree of assurance that the ciphertext is legitimate and decryptable prior to the attempt.

These mechanisms have gained popularity, and several EtM schemes are now defined for SSH and TLS.