Cushioned Encryption and Deniability

by Phunda Mental

As I'm sure most of us know by now, the world is getting to be a scary place.  We are getting placed in bondage against our wills when there is little or no evidence that any crime was committed, or that anyone (other than the Feds' sense of order) was somehow harmed.

With the latest examples of injustice, such as those endured by Bernie S. and Kevin Mitnick, it is no stretch of the imagination to envision a case in which a person is held in prison for failing to reveal her encryption key.  Certainly a warrant can be legally obtained for such a key, and this makes sense when we understand cryptography merely as a way to lock away secrets.  The problem with this model is that the very same bits that serve us as locks also serve us as identification.  If a law enforcement officer obtains the keys to our files, he can also "prove" to our associates that "he is us."  He can sign digital contracts in our names, and even sign digital confessions for us.  A scary proposition.

It is for these reasons that I began looking for a way to pull one over on Joe Officer.  Simply hoping against hope that the government will keep itself away from our keys is probably naive.

What we would like to have is a system where if Joe Officer demands the key to our ciphertext file, we can choose to supply one of many keys.  One key might reveal a love letter to his wife, the other might reveal the completed works of Shakespeare.  A third key might give us our secret documents.  This is usually called deniable encryption.  This term usually carries the added stipulation that user be able to invent keys on the fly, when pressure is applied by enforcement to reveal a meaningful text.  I don't find this idea to be that great though because this assumes that the decryption is done in a black box; in other words that law enforcement isn't watching us and looking at our programs.  They would see us invent a key for a given plaintext.

Instead of this, I find it preferable to decide beforehand what plaintexts will be available.  In this way, law enforcement sees us apply a key with a given algorithm, the plaintext simply appears out of that.  No specialized calculations specifically for deniability need to take place.  The enemy would know that we probably have a means to extract other data sets, but any additional data in there can legitimately be said to exist to frustrate cryptanalysis, in the terms we will use, this data is just junk chaff.  I call this type of system a "cushioned" encryption system, that is, we set up an alibi to fall back on beforehand.  But before we consider this method, let's look at the simplest method of deniability.

The most obvious way to achieve this is with a One-Time Pad (OTP).  An OTP has the property that a key can be constructed to reveal any possible message of length N from ciphertext (also of length N).  To achieve this feat, however, our key also needs to be N bytes in length.  This might be O.K. for a few bytes here and there that we can remember the pad (key) for, but in this case why not just memorize the plaintext and be done with it?

We can store all of the pads on disk, but not only is this troublesome to work with, Joe Officer can simply confiscate all of the pads.  Even if the pads are encrypted with PGP, he just demands the key to the pads instead of to our secret document.

One-time pads just aren't going to cut it.

Enter Ron Rivest.  Rivest, most widely known for his work on the RSA public-key algorithm, recently introduced a small paper on a method of data confidentiality that he calls "winnowing and chaffing."

The basic "winnowing and chaffing" method is discussed in [RIV98] and is a really interesting idea.  Rivest proposed it as a method of achieving confidentiality without encryption: the plaintext is transmitted in the clear.  See Rivest's paper for how this is done - if the material in this article is not clear, read Rivest's paper to get a clear understanding of the basis of "winnowing and chaffing," and this stuff should fall right into line with you.

For our purposes, what we want to look at is merely the idea of using Message Authentication Codes (MACs) to separate one strand of data from another.

What we are going to do to achieve our goal of deniable encryption is to use two tools: a strong hash function H() and a symmetric cipher C().  Of course, we can turn any hash function into a block cipher and vice versa, so we could really do it with one tool, but that is academic.

We need a passphrase from the user, which gets hashed with H() like so (the notation gets a little slippery, but stick with me):

H(user_passphrase) --> k H(user_passphrase + k) --> k1 # Where + denotes concatenation

It should be noted here that H() may be something like SHA-1 or MD5, but it would be preferable to use a complete MAC system like HMAC.

For our uses here, I believe that ordinary hash functions will suffice, however since HMAC is available in good crypto libs right next to RC4 (for our byte-by-byte encryption, RC4 is the easiest to implement and block ciphers offer no obvious advantages to a stream cipher with just heavy MAC'ing), so all the tools are right there for you: use HMAC.

But let's get back to the algorithm:

k is the key that we will use for our cipher, and k¹ is the key that we will use for MAC'ing.

For every byte of plaintext that we get, we will also increment a sequence number (sqn).

1.) We grab a byte of plaintext (P) 2.) Encrypt: C(P,k) --> M # Encrypt P with k yielding M 3.) MAC: H(M + k1 + sqn) --> M1 # Hash M, k1 and the sequence number together 4.) Output: M + M1 5.) If we have more bytes, GOTO 1.

To decrypt this stuff, we do the following after we get the user's key and set up k and k¹ as before.  D() denotes the inverse of C().

1.) Grab a block of data, and separate out M and M1 2.) H(M + k1 + sqn) --> R1 # Recalculate what we think M1 should be and call it R1 3.) If R1 and M1 match, decrypt M, D(M,k) --> P 4.) Output P 5.) If we have more bytes, GOTO 1.

To see how this lets us form deniable encryption, imagine what would happen if R¹ and M¹ did not match in the decryption process.  We simply discard that packet and move on.  Rivest calls this "winnowing."

Why wouldn't M¹ and R¹ match?  Because M¹ was created with a key different from what the user supplied in the decryption process.  That packet may very well be meaningful data, it was just encrypted with a different key.  This allows us to encrypt two or more files using the ciphertext of each file as chaff for the others.  An example is in order.

Let's define two messages that we want to send; the bytes "A" and "B".

The keys for A are k=S, k¹=T and the keys for B are k=Y and k¹=Z.  We start our sequence number at 1.

Let's suppose that our functions H() and C() do the following:

C("A",S) = G = M # "A", encrypted with key k (= "S") yields "G" H("GT1") = 2 = M1 # Hash the ciphertext byte above with k1 and the sequence number, yielding 2. This is M1

So our first message packet is G2 - on to the first byte of the second message:

C("B",Y) = O # "B", encrypted with key k (= "Y") yields "O" H("BZ1") = 8 = M1 # First byte of the second message, use 1 for sqn

Ciphertext output (both messages merged and interpolated): G2O8

When we attempt to decrypt the first block of our message we have some keys that the user supplied.  If the user supplied k=S and k¹=T then we will accept G as a valid byte (M¹ and our calculated R¹ will match) and we reject O: we have just stripped out the second message's byte leaving only the first.

Now we can just pass this byte through D() which will yield the plaintext, in our case "A".  If we supplied the other set of keys (k=Y and k¹=Z) then we would have stripped out A and decrypted O and therefore obtained B.

It is easy to see how this can be used against Joe Officer: if he wants A we hand him the keys to B, if he wants B we hand him the keys to A.

To round out the method and make it all hold up, we insert chaf packets (just some random bytes that won't be accepted by the MAC'ing) at random intervals.  If scrutinized, an attacker will have no idea whether or not the packet in question is a bogus chaf packet or a meaningful packet.  There is no obvious analytical way for an attacker to show whether more meaningful data exists in the file or if the remains are just random bytes.  The most "straightforward" way of attacking this system is to dictionary attack the user passphrase, as always.  Failing this, one must attack the hash function and the cipher.  This gets difficult very quickly.

Another modification to this basic system is to obtain more data from the user's passphrase through multiple hashes and using this additional data to seed a cryptographically strong PRNG and grabbing 128-bits or so from the PRNG and hashing this into each MAC.  This ensures that there is always a good amount of new bits getting turned over to the hash function.

If the hash function is biased, this bias may be able to be used to predict how the digest bits change in the next hash, the sequence number is incremented, so the changes in those bits are also minimal.  The remaining bits are just those 8-bits for the plaintext byte.  Known plaintext statistics can be used here.  All of this may help an analyst in breaking a MAC.  Putting 128 new bits from a secure PRNG limits helps to alleviate this possibility.

But you still have to watch your passphrase.  And if you are going to put a PRNG into the implementation, it is better to get k and k¹ in a different manner.  If R() is the PRNG and H() is a hash function then we construct k and k¹ by seeding R() with H(user_passphrase) and grab to 128-bit (or 256, or whatever you like) blocks from R() for use as k and k¹.  The prior method of getting k and k¹ seems secure, but for the few kilobytes of RAM needed for a nice PRNG, it seems silly not to use it.

Implementing programs to do this sort of deniable encryption is a rather trivial matter.  Source code to strong hash algorithms and good streams ciphers is widely available, and simple to use.

It is tempting to just implement the basic winnowing tools and let the crypto be done with an external program.  I advise against this as it requires more keys to be remembered, and when under actual pressure from law enforcement to reveal a key you may not be able to get your wits together and give the right key.  Accidents happen - you don't want to give the wrong key.  It is also preferable to add documents of a "sensitive" nature for the ex-press purpose of giving up to law enforcement.  Maybe encrypt a few articles from Phrack and a few porn pictures.  Such material seems more likely to get encrypted than Hamlet, and will give you a better alibi regarding why you have that ciphertext, not that you should even need one, but such is the state that we live in.  Be prepared.

Shouts go to Sryth and Wipe0ut for good hacks, lots of beer, and really sick looking code while under the influence.

References and Related Material

[RIV98]  Chaffing and Winnowing: Confidentiality without Encryption; Ronald L. Rivest, theory.lcs.mit.edu/~rivest/chaffing.txt

[CAN97]  Deniable Encryption, Ran Canetti, Cynthia Dwork, Moni Noir, Rafail Ostrovsky, theory.lcs.mit.edu/pub/tcrypto1/96-02r.ps