# Leak-proof protocol: is such a thing possible?

Is it possible to design a protocol that by itself guarantees that a malicious implementation cannot leak secret data without breaking the protocol?

Setting:

• Alice and Bob have a pre-shared secret key K. Using this key, Alice encrypts a bunch of plaintexts and sends them to Bob as a collection of files. The plaintexts are short-ish texts in a natural language.
• Each plaintext is encrypted independently of others, and must be decryptable independently. Some sort of authenticated encryption is used.
• Eve receives a copy of the collection. This is the only data she gets (i.e. no timing or other side channels). She does not communicate with Alice (but can have a previous arrangement with her, e.g. pre-share some secret keys). Alice cannot communicate with Eve directly, or otherwise send out any data except as defined by this protocol.
• We want to ensure that Alice cannot manipulate the encryption, without consequences detectable by Bob, in such a way that Eve can obtain information about the secret key. We assume that transmission is 100% reliable, so if Bob can't decrypt some of the files, he will conclude that Alice is a bad actor.
• Also, obviously, we don't want Eve to obtain the plaintexts. It's tolerable if Eve can detect multiple copies of the same plaintext.

It seems that any kind of randomness in the protocol has to be excluded.

For example, if we use an encryption scheme with random IV which is prepended to the ciphertext, Alice can just encrypt the secret key K using another secret key known to Eve, Ke, and apply it instead of IV (IV := E(Ke, K)). Instant leak!

If our protocol adds randomness to the plaintext itself (before encryption), Alice still can manipulate the encryption result by choosing the random value. In the worst case she will have to use brute force, changing the random bits until specific bits of the ciphertext assume the values she wants. On average, she will need about 2n iterations to leak n bits of data. If, say, 1000 encryptions is a small enough number to be unnoticeable on any modern equipment (even "weak" such as a smartphone), then Alice would be able to leak ~10 bits of data per encrypted file.

The next thought I tried is to use deterministic encryption with Synthetic IV based on plaintext (similar to SIV-CTR construct). Besides obvious drawbacks caused by the low entropy of the natural-language plaintexts, this scheme still does not preclude Alice from leaking if she can manipulate plaintexts in a way not obvious to Bob. For example, she can try adding spaces at the ends of text lines, or insert some non-spacing Unicode chars, until she gets desired bit pattern in the ciphertext. (I don't know how to estimate the effort she'll need to leak n bits per ciphertext. Is it still O(2n), as in previous case?)

The last option seems better than others, because the manipulations are detectable by Bob, at least potentially. But this detection happens outside the domain of the protocol, and is not reliable. Are there other possibilities?

-
Another covert channel: timing –  CodesInChaos Apr 10 '14 at 13:04
If Alice and Bob can share some more state, and since transmission is 100% reliable anyway, you could keep a counter as IV - you would still achieve semantic security (with a suitable mode of operation) yet Alice would not be able to mess with the IV and inject key material in it. It seems a simpler solution than SIV-CTR, of course it doesn't solve the plaintext malleability issue - I doubt there is a robust solution in that case, since you're basically asking for a way to not allow arbitrary data to be sent over the wire, which Bob cannot distinguish since Alice and Eve share a key. –  Thomas Apr 10 '14 at 13:17
If you assume one of the sides is malicious, what's to stop them from subverting your communication outside of the protocol? For instance, simply handing the session key over to the NSA. –  Stephen Touset Apr 10 '14 at 18:23
Why can't a malicious implementation leak whatever it wants directly to the NSA? It could do something obvious like opening a network connection and sending them secret keys directly, or something more surreptitious like remembering the keys and waiting for an incoming connection with a specific fingerprint before leaking that data to the client over the normal encrypted protocol? –  Stephen Touset Apr 10 '14 at 20:14
@StephenTouset The assumption is that no communication outside of the protocol is possible. An example application would be an encrypted-text-file-editor on an air-gapped machine for Alice; then the collection of files is transferred to Bob via an untrusted channel. Another possibility is a reverse firewall on Alice's network that wouldn't allow non-conforming data out, so Alice can only communicate within the bounds of the protocol. (Thank you for pointing this out; I'll try to clarify this point in the question). –  atzz Apr 15 '14 at 15:37

It doesn't work without further restrictions.

For simplification, let's assume Alice encrypts a bunch of files but doesn't have to send all of them to Bob. She can still decide to re-order the files or leave out some.

Then she can encode the secret shared key between Alice and Bob in the least significant bits of the ciphertexts without changing the files. She is only rearranging them so that Eve can extract the key. But if Bob checks the integrity of each message, it holds.

If more files are transmitted than the keylength, this works. Otherwise, more than one bit has to be encoded in less messages. And in order to get enough decryptable ciphertexts more files might have to be encrypted.

-

Sort-of, like the way you describe. $\:$ (It's still O(2n), as in previous case.)

For encryption, one could have scrypt be involved, to reduce the leakage rate.
For signatures, one could use a scheme in which each message has at most one valid signature,
so that anyone who knows the public key and sees the output can potentially detect manipulation.

-
How would using scrypt in any way reduce the leakage rate? I can see it reducing the encryption rate, but this would not really help. –  Paŭlo Ebermann Jul 14 '14 at 19:17
Using scrypt would reduce the leakage rate by making it more difficult to find a $\hspace{1.33 in}$ plaintext that will produce a suitable ciphertext. $\:$ –  Ricky Demer Jul 16 '14 at 7:09

What you want is a protocol where Alice sends a message to Bob without being able to control any ciphertext bits. This would be possible if either

1. The message and encryption are completely deterministic and give Alice no freedom to choose between two ciphertexts, or
2. Alice is unable to predict the ciphertext without sending a message.

The first could be possible if the message space is small enough (e.g. Alice only sends True or False and cannot choose which) and the encryption deterministic (e.g. block cipher in CTR mode with messages using consecutive IVs).

The second would probably require a trusted third party who does the actual encryption and sending. Further, you would have to assume communications between Alice and the TTP are not leaked.

For a real-time protocol, with an assumption on Alice's computing power you could be able to lock Alice into only being able to calculate one encryption in time. It would be like a reverse time capsule. All the caveats from Time Capsule cryptography would apply, a well as a few others like that parallelism would be trivial.

An example of such a time-locked protocol could be:

1. Choose a key-derivation function $H_n(K, S)$ that takes $n$ seconds for Alice to compute using all her resources. Have Alice and Bob share two secret keys $K_1$ and $K_2$.
2. Bob sends a random number $R$ to Alice and starts a timer.
3. Alice computes $H_n(K_1, R||M)$ and uses that as the IV for AES encrypting the message $M$ with $K_2$ and sends $IV||E(K_2, IV, M)$ to Bob.
4. Bob verifies that he has received the reply within $t < 2n$ and that the IV matches $H_n(K_1, R||M)$.

Since Alice can calculate neither the IV nor the ciphertext before receiving the random number $R$, she only has time to calculate them once before the time limit, meaning she cannot hide any information in them even by choosing a different message.

This assumes Alice always co-operates and follows the protocol. She can of course hide information if she sends an invalid message or fails to reply to some messages.

-