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

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.

$$\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".

-
Does the Dual_EC_DRBG qualify? – user11342 Sep 12 '11 at 14:49
@user11342 +1 but please add more (maybe sum up the various claims made about it). Dual_EC_DRBG does seem rather close to the above scheme in that it has "weak values" and "strong values". I find this really interesting. – Ethan Heilman Sep 12 '11 at 16:57
Look you can't ask me to expand on a subject and at the same time move my answer to a place where I can't exactly do that because I don't have enough reputation. This and the generally low level of the answers have lost my interest in this cite. Good bye. – user11342 Nov 18 '11 at 16:51
How about Cryptomeria cipher (C2)? Their (4C Entity's) licensees are given different S-Boxes depending on their use of the algorithm. Theoretically, if a customer was given bad choice of S-Boxes, their variant of the algorithm could be insecure, because it is known that the choice of S-boxes may significantly affect security of a algorithm. – user4982 Sep 30 '13 at 16:20

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.

-
I agree that in all likelihood you are correct, AES is fairly secure and harddrives are so cheap everyone can use OTPs. For the sake of argument lets assume that the NSA, GCHQ or whatever found a devastating attack on all known ciphers (AES, SERPENT, etc). Rather than publish the attack, they slowly move all military systems to the new secure cipher (the USA does employ unpublished/secret ciphers like BATON). The NSA wishes to maintain their ability to listen to communications if the "other side" begins to suspect something and switches to the new secure cipher. – Ethan Heilman Sep 12 '11 at 1:26
@e501: "lets assume that the NSA, GCHQ or whatever found a devastating attack on all known ciphers" - But in reality, NSA is actively encouraging use of AES, and permits its use for classified traffic (at the SECRET level, given that certain conditions are met). This suggests that the NSA probably does not have a devastating attack on all ciphers. Movie-theater plots are fun to think about, but the reality is most likely more mundane. In practice, the way that NSA snoops on bad guys is probably not by whizbang cryptanalysis, but by traffic analysis, operator error, insecure endpoints, etc. – D.W. Sep 12 '11 at 2:19
I agree completely, if history is the judge general mathematical attacks are not the way most military ciphers are broken. Never the less there is a non-zero chance that GCHQ could break AES tomorrow. Do they tell the world? Many friendly governments are not going to be able to switch to new ciphers in time. If they announce a new contest out of the blue they are tipping their hand. Furthermore, there is a valid strategic argument to be made that the benefit of secretly listening on enemy communications out weighs the risk that enemy has discovered the attack as well. What do you do? – Ethan Heilman Sep 12 '11 at 2:38
Well then you have another answer to your question -- use any cipher that has a cryptographic flaw that only you know. – David Schwartz Sep 14 '11 at 13:48

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).

-
The NSA did weaken DES so they could break it and others could not. They did by reducing the key size such that only someone with as much compute resources (likely custom built hardware as well) as the NSA could hope to break DES in a reasonable amount of time. – Ethan Heilman Sep 12 '11 at 0:58
I disagree. Today, I don't believe you could design a cipher that's weak against differential cryptanalysis and get away with it. I think it'd be noticed pretty quickly. Using some other difference function wouldn't be enough to hide it; cryptanalysts routinely look for d.c. attacks under other notions of differences. And, even if the flaw wasn't noticed quickly, people pretty much demand that any new block cipher proposal had better come with a proof of security (or at least strong evidence of security) against differential cryptanalysis and other standard attacks, so you wouldn't get far. – D.W. Sep 12 '11 at 1:06
@D.W. I agree in general with your comment (known attacks are probably a bad place to start) but I've spend some time researching differential backdoors. Consider the case in which the difference that the attack relies on is defined by some logical function constructed such that finding the "difference function" to perform the attack is equivalent to 3SAT. How many of the SHA3 finalists have proofs of differential security? The ones that do are conditional on independence assumptions (one can differentially backdoor a function and still prove resistance). – Ethan Heilman Sep 12 '11 at 1:36

In the asymmetric encryption context I think something can be done in this direction with a double trapdoor function. I studied few examples of them in the past and briefly you can build up an encryption scheme with a "local" trapdoor and a "global" one.

If you keep the secret for the global trapdoor for you you'll have a sort of escrow key allowing you to decipher all ciphers made under this encryption scheme. The local trapdoor is used by users to communicate among them.

Give a look to this paper for more details: http://www.iacr.org/archive/asiacrypt2003/01_Session01/03_106/28940037.pdf

As noted on an other answer, this is interesting only for an accademic point of view. There is no reason that someone would use such cryptosystem knowing that someone out there has an escrow key.

-

It may looks like off-topic.

But there exist hardware solution today.

In the early years, both Soviet and USA used reverse engineering to get the scheme of crypto-system. Military standards today are too closed. What we use called a civil standard, and it is open. So reverse engineering seems unnecessary.

There is such technology: Physical_Unclonable_Function

it is the hardware analog of a one-way function.

Crypto-system may be manufactured that way to maximum complicate reverse engineering task.

When Red get Blue's crypto-system, they may try to use it like a black-box for encryption, but they can't get the full crypto-scheme and can't clone this black-box.

In this sight, Red make mistake with one "s-block" and their encrypted message will be easily broken by Blue.

Such malicious circuit with "PUF shield" may stay like tiny trust-trigger for Blue against Red.

-
Why would Red use something when they don't know how it works? They'd most likely use it to crack captured comms – rath Jul 25 '13 at 11:09
2rath, from question: "(Red is unable to develop it's own secure cipher)" – reticulatus Jul 26 '13 at 10:07

If we suppose the world where this is interesting again, where say AES and kind has fallen to a currently unknown attack, then even so Red has to be stupid to fall for it. We shall consider two cases of defense:

In case A, almost all ciphers can be strengthened by weaving in another cipher with its own key. The cipher doesn't have to be all that strong of itself to radically smash-up the break against the original cipher. (Consider for a moment Enigma, which was quite breakable. Now consider gzip-base26-Engima. The cipher power is now absurd as compared to the original and the original attacks don't work at all.) Stacking is weak in the modern case, but weaving is much more terrible. If we broke out within the rounds of one block cipher into another one and back into the block cipher with the block state encrypted, strange things happen.

In case B, Red has only to reroll the dice on all large constants in Blue's cipher, constructing a variant likely to have a different backdoor key that is unknown to anybody.

-