Deceptive Cryptography

Alexander Liss

03/25/98

 

Many of us possess the art of speaking with euphemisms - the third party, which eavesdrops on conversation hears just the opposite to what is said. Some grew up in such culture, other developed it to stay alive in autocratic countries. Real world of hiding secrets widely employs deception hence Cryptography should be able to do it also.

We start with "one time pad", its modifications with secure channel and subliminal channels.

We assume that our software cannot be modified (protected some way), hence we do not have problems with subliminal channels and can use them to our advantage.

We assume also, that we have a secure channel. Secure channel can be sending encrypted messages across public communication lines.

As a basis for our construction we use one time pad. There is a long array of randomly generated bits x(j) - the key, which sender and receiver share. Senderís message is an array of bits y(j). Instead of sending bit y(j) he sends z(j) = y(j) XOR x(j) . The receiver transforms it: y(j) = z(j) XOR x(j). Bits of the key are never reused. (There is no known theoretical attack on this method.)

The simplest construction is: send the key through secure channel and encrypted message z(j) through open one. It does not give much, except the fact, that we are sending random bits through secure channel, hence it should be more secure.

Now we will use subliminal channels. Subliminal channel - the possibility to send additional information along with encrypted information, usually is not welcomed, because this additional information can be the secret key, which is leaked out. However in our setting we use subliminal channels to our advantage. We encrypt in the ordinary way the deceptive message. The key is passed through secure channel. We know that capable adversary can break our secure channel, extract the key and read the message. The adversary will read what we want him to read. The real message we encrypt differently and use as a key, which we pass through secure channel. Now the real message has three layers of protection: secure channel, its encryption and deception.

Encrypted message usually looks as gibberish and immediately catches the attention as a bag with secrets. We can make it more innocent looking. We have a message x and we want the eavesdropper to see the innocent message y (not gibberish) of the same length. We create a long key k, that y = x XOR k, and pass it with secure channel (usually encrypted some way and appended or mixed into message y). For example, it can be presented as actually encrypted message, which looks as a clear text, with encrypted appendix, which actually is an encrypted key k . The attacker, who tries to break the secure channel, might not realize that encrypted appendix does not have patterns, because it is not a message.

We can elaborate on this plot. We encrypt in two steps. First we encrypt the actual message in usual way. After we create the deceptive message as above using encrypted message, instead of actual one. In this case, even if the deception is uncovered, only encrypted actual message is revealed. We have here deception as an additional layer of protection.

We can elaborate even further. Usually the message has only a small part of information, which really needs protection. The rest is normal for the language redundant information, or normal for any message "basic" information - point of reference, on top of which we convey really new information. Now, first we prepare the message: we extract all blocks of text, which carry any information, which needs protection. We replace these blocks with deceptive ones. Now the information, which has to be encrypted, includes placement of these extracted blocks and actual information in them. This information we encrypt using one of the known methods, for example described here. We even can compress this information before encryption. As a result we have Deceptive Encryption, which is not so straight forward as above, which makes it more difficult to recognize.

Speaking with euphemisms can be the tool of regular encryption. The main parts of it are the substitution tables of modules of message - letters, numbers, words and expressions, and inclusion-extraction algorithms.

When we encrypt the message we:

When we decrypt the message we:

This scheme requires shared inclusion-extraction algorithm, and two shared substitution tables. The fact that we use an internal encryption scheme, which makes semantically correct encrypted messages, makes creation of substitution tables similar to usual euphemisms.

Next we elaborate on the idea of mixing a few non-encrypted streams as the way of encryption (it was described by R.Rivest in http://theory.lcs.mit.edu/~rivest/chaffing.txt).

We interpret it as follows. There are a few message senders and receivers. Each sender breaks the message in small parts; each part does not allow the extraction of useful information. He appends each part with the marker, which allows the receiver to extract it from the information stream and place it properly in the message. We combine all these message parts from all senders in one common stream. Receivers pick from the stream their parts and construct their messages. If only designated receiver can pick properly his messages from the common stream and no one else, then this procedure works as encryption. It can be called Encryption by Misdirection and Decryption by Filtering.

Interesting that this idea is absolutely useless for the traditional application of cryptography by spies and military. Their information is narrowly focused and the amount of this information is relatively small. Hence any exposure of any part of this information can be potentially dangerous - the adversary can figure out what goes on based on limited and seemingly irrelevant information, and this is what actually happens. Hence, the parts, on which we need to break the message, have to be very small. Most likely we have to break the message into bits, and the entire procedure becomes too expansive. However, in the world of enormous amounts of e-mail messages, which do not require high level of protection, the parts of the message can be big. The really sensitive piece of the message can be broken on smaller parts, for example bytes. This can be practical.

We can supplement this with Obscure Routing, which allows hiding of the patterns of communication.

We have a system of interconnected network servers. Some of them have assigned senders and receivers; all of them pass messages-"packets" to each other.

We supply each "packet", which we send across the network, with routing header-array. The "packet" travels from server to server. Each server reads its element of header-array, and based on this information decides where to send the "packet" next.

Routing information is a server's "name" with the time-stamp, encrypted with the key specific to the server.

Some messages have routing information, which designate the server as the final place - in this case the server stores the message and initiates filtering procedure, which allows sorting messages according to the recipients assigned to this server (Decryption by Filtering).

When message is sent, it reaches designated server, receiver's address is replaced with routing header-array, and the message is sent to travel across the network together with other messages, which are originated with this server, or pass through it.

Servers, which have to send messages, have to know secret keys of all servers in the system. The sharing and updating of these keys can be done with the public key system.

Some messages can travel around a few times before they settle in their designated server. There is no open information in the message about sender or receiver. This makes analysis of the traffic difficult.