[Cryptography] "How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts"

[Jerry Leichter]

The world of academic cryptography has gotten highly theoretical and rather abstruse and often far removed from practice.  But ... not entirely by any means.  The pre-print https://eprint.iacr.org/2018/212 considers the following problem:  The Clipper chip (well, an improved version) won.  Only one acceptable encryption algorithm exists and the attacker knows all the keys.  It's illegal to send any message whose plaintext is not immediately meaningful - i.e., sending pre-encrypted text into the chip will land you in jail.  Can you communicate securely and safely?

The answer turns out to be yes, by a clever bit of judo that turns a security assumption - that the single cryptosystem supported provides semantic security, because the government wants a strong NOBUS guarantee - against the government.  The basic idea is as follows:  It's long known that semantic security requires that (a) the output be indistinguishable from random if you don't know the key; (b) the cryptosystem must choose randomly among many possible cryptotexts for a given plaintext.  So the output of a hash function independent of the key on a pair of successive encrypted messages is itself indistinguishable from random.  By repeatedly apply the encryption function to the same "cover" inputs, I can force the bottom bit (say) to encode a bit of a real message.

Yes, the government can apply the same (public) hash function.  If the real message is *not* random, he can recognize it.  But if the real message *is* random, every possible pair of messages carries a possible message, and there's no way to tell.

Now consider a DH key exchange.  The messages exchanged are, indeed, random.  Further, they have the property that they can be public:  Even an attacker who can observes them doesn't learn the agreed-to key.  So Alice and Bob can, in this system, establish a secret key between themselves while sending messages that cannot be distinguished from legitimate messages encrypted using the "legal" system:  *Every* exchange of encrypted messages potentially hides a DH key exchange.

Once they have their shared key, Alice and Bob can turn their real messages into strings of bits indistinguishable from random and those, in turn, can be transmitted subliminally using the same technique.

I've grossly over-simplified even parts of the system I *do* understand.  Why does h() look at two successive messages?  Why not just use the bottom bit directly?  This gets into the theory of randomness extractors and a theorem that says no randomness extractor from a single biased source is possible, but one from two biased but independent sources can be safe.  And extractors further allow you to send log(k) bits (k a security parameter) at a time, rather than just one, which makes the system much more practical.

Cool stuff.
                                                        -- Jerry