[Cryptography] Is it mathematically provably impossible to construct a mechanism to test for back doors in programs?

[Stephan Neuhaus]

On 2014-05-31, 17:22, ianG wrote:
> The bit half-way through second para.  It seems to be an interesting
> property;  can someone work through the logic of it for me?
> 
> I'm specifically wondering whether we are limiting this case to all
> backdoors, backdoors of the nature of a public-private key pair, or
> something in between.
> 
> E.g., if it is impossible to detect any backdoor, why do we favour open
> source, which might provide a neat mechanism to insert undetectable back
> doors?  Just to be controversial...

To tackle your questions in turn: the answer to the question of whether
it is "mathematically provably impossible to construct a mechanism to
test for back doors in programs?" is yes, and the proof is simple and
requires only elementary logic.  It is the same proof that was used by
Fred Cohen some thirty years ago to prove that no perfect virus detector
could exist. It is a classic proof by contradiction.

Assume therefore that such a method existed.  In other words, if P is
any program, we assume the existence of a function f such that

  * f(P) is "yes" if P contains a backdoor
  * f(P) is "no" if P contains no backdoor
  * the computation of f always terminates

Now I build an encryption program C that contains the following code:

  void encrypt (buffer b, key k) {
    if (f(C) == "no")
      send_key(k, NSA);
    ... /* encryption code here */
  }

In other words, C exhibits a back door if and only if f(C) says it has
no backdoor.  This is a contradiction to our assumption and we must
therefore conclude that no such function f can exist.

Now for the second question: given the impossibility of f, why do we
favour open source?  The first answer to this is that "we" might *not*
favour open source at all, for a variety of reasons, but that is a
fairly cheap and glib answer.  The real answer is that while no
algorithm with the properties given above can exist, there is
nevertheless the possibility of detecting a great number of backdoors in
a practical way.  Also, the contortions that program C above went
through are rather easy to detect themselves and would lead one to
reject program C.

The same mistake is occasionally made in cryptography.  Ralph Merkle
once invented a cryptosystem where an attacker had to solve a knapsack
problem, but where the legitimate recipient had secret information that
would allow him to turn the knapsack problem into a so-called
"superincreasing" knapsack problem, which is easy to solve by brute
force.  The reasoning was that since the knapsack problem is known to be
NP-complete, then unless P = NP, the attacker has a very difficult job.
The fault in the logic was that, yes, a *random* instance of the
knapsack problem is hard to solve on average, but the knapsack problems
that came out of his cryptosystem were *not* random instances.  In fact,
they were solved on standard desktop hardware just a few years later,
and the cryptosystem thus broken.

Fun,

Stephan