Could one construct a cipher that is secure for friendly parties to use but insecure for hostile parties?

Question

Consider the situation of a nation state (Blue) at war with another nation state (Red). Blue wants to deploy a secure cipher that blue currently can not break, but they are considered that Red could reverse engineer the cipher and use it to secure Red's communication (Red is unable to develop it's own secure cipher).

Questions:

1. How have governments in the past approached this problem?
2. How could one design such a cipher?

I have been working on an incomplete (maybe impossible) formulation of such a system. I know that asking is "my cipher secure" questions is frowned upon, but I hope my outline below is free of enough implementation details that it will not be seen in such a light. It is more of a "is my cipher possible" question.

Here is my formulation of a backdoor cipher.

Assume a function $g$, takes as input a integer $s_i$ and outputs a cipher $c_s$. That is, $g$ generates ciphers based on a seed $s$.

$$\text{Let } g(s) = c_s$$

The cipher $c_s$ has the property that if one knows $s$ one can decrypt all messages encrypted with $c_s$. Thus, the cipher is safe for Blue to use since Red doesn't know $s$ and can't learn $s$ from $c_s$, but if Red attempts to use $c_s$ Blue can decrypt all their communications.

One could build $c_s$ by appending an encrypted (using a public key derived from $s$) form of the key used by $c_s$ to the ciphertext. That is,

$$\text{Let } c_s.\text{encrypt}(key, plaintext) = ciphertext|publicKey_s(key)$$

While in principal this would work it would not satisfy our scenario above because the backdoor is so blatant and easy to remove. Red could just alter the cipher to not append the encrypted form, $publicKey_s(key)$, of the key.

Instead a more subtle approach would be to create a function $g'$, which still takes $s$ but produces both a cipher $c'_s$ and a function $v_s$.

$$\text{Let } g'(s) = (c'_s, v_s)$$

The cipher $c'_s$ has the property that some of its keys are insecure and some of its keys are secure. The function $v_s$ produces only secure keys.

Blue can generate and distribute many secure keys using $v_s$.

Best case, Red doesn't realize that some keys are weak and some are strong and thus assumes that Blue would never use a cipher that Blue could break. Red trusting in this uses $c_s$ for secret communications.

Even if the vulnerability comes to light, Blue communication are still secure and Red still can't generate strong keys. Nor can Red use captured keys that were generated by Blue because Blue remembers generating them.

Question: Is this scheme is remotely possible, if so what math could be used to construct it?

EDIT:

I wrote this up as "Imagining a Secure Backdoor Cipher".

Answer 1

Mathematically, it can probably be done. There has been research into trapdoor block ciphers. See, e.g., A family of trapdoor ciphers by Rijmen and Preneel, and follow-up papers.

In practice, though, the problem statement is not realistic. The assumptions are just not realistic. Today, there's no reason why Red would be limited to using Blue's ciphers. Instead, Red could just use any well-vetted cipher, like AES. There's no reason why Blue should assume that Red will use Blue's ciphers; that's just not how adversaries are likely to behave given the current state of the public literature. So while your problem statement might have been relevant and interesting to ponder 40 years ago, when there was no public literature on cryptography ... today, it is irrelevant.

Answer 2

The design of DES might give some insight into the problem. The NSA altered the S-box of DES. Many people thought they planted a backdoor. It wasn't until later that differential cryptanalysis was independently discovered by Biham and Shamir that people realized that the NSA actually made DES stronger.

So the lesson to learn from this is: clearly the NSA knew about differential cryptanalysis and were some of the only people who did (IBM says they knew about it too). NSA really could have designed the S-box to be weak against a differential attack, but strong against all publicly known attacks. Only until differential cryptanalysis was discovered would anyone have known DES was weak.

Since differential cryptanalysis is publicly known, you couldn't use it then right? Actually, you probably could design a cipher which is weak to differential cryptanalysis without getting caught for some time. How would you do it? It all comes down to the difference function. From wikipedia:

The basic method uses pairs of plaintext related by a constant difference; difference can be defined in several ways, but the eXclusive OR (XOR) operation is usual.

So, construct your S-box so that the differences are not XOR. Choose some other difference function and hope no one figures out what function you used. You could probably do a similar thing with linear cryptanalysis.

In all reality though, you'd probably be better off using a standard cipher in an insecure protocol. For example, the padding oracle attack is fairly practical and could be hard to spot, especially if you took the idea and put it somewhere else in the protocol (not in the padding).

Answer 3

Wow 501, you are asking some BIG questions here! :) In answer to your first question, you might want to thumb through the journal Cryptologia, probably the best public source of past military cryptological practice available. In answer to your second question, well, we ALL would like to have the answer to this one, right? :) Let me drop in my two cents worth and try to give you a general answer . If you are talking about wartime cryptography where real lives are at stake, I think you would want to go with the one time pad crypto system because it is the only "proven secure" system publically known(we don't know if the government has anything "stronger" than the one time pad so for the sake of this answer we can leave them out of the discussion). For a modern warfare cryptosystem you are no doubt going to want to stream real-time video information to your troops in the field so you will have to have a high speed (Ghz) one time pad stream cipher running on a cryptographically secure psuedorandom bitstream generator with a very large period. Each warrior in the field would have to have his/her own key so if one crypto unit is compromised the whole system doesn't go down. The key here(no pun intended) is creating the secure high speed keystream generator and doing the key distribution logistics. Good luck!