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

[Nemo]

Stephan Neuhaus <stephan.neuhaus at tik.ee.ethz.ch> writes:

> 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 */
>   }

This assumes your program can feed _itself_ to a function it is
calling. Which is true, of course, but usually requires a bit of clever
quine-foo.

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

This is a generally under-appreciated point worth repeating (and
rephrasing).

Although it is impossible to build a function that correctly answers
"yes" or "no" to "is this program safe?", it is very possible to build
functions that answer "yes" or "I don't know".

The same principle applies during code review. Your code needs to be not
only correct, but simple enough to be "obviously correct". Otherwise it
will fail my review and I will ask you to rewrite it.

To build secure systems, we do not need to be able to detect all back
doors; we just need to be able to write code that provably does not have
back doors. The former is impossible; the latter is not.

 - Nemo
   https://self-evident.org/