[Cryptography] how reliably do audits spot backdoors?

[James A. Donald]

"James A. Donald" <jamesd at echeque.com> wrote:
>> I find C quite intuitive, possibly as a result of having done a bit
>> of code review.
>>
>> What you would call counterintuitive, I read as idiomatic, and what
>> is undefined, I read as unidiomatic.

On 2013-12-25 08:12, Benjamin Kreuter wrote:
> So the fact that it is possible for the sum of two positive integers to
> be a negative number is idiomatic?

To me that is totally intuitive and natural, and I have written code 
that takes advantage of this effect (sliding window code)  It just 
seemed natural to do it that way.

>> So, the underhanded C examples would have failed code review, not
>> because their terribly sneaky measures would have been detected in
>> code review, but for being unidiomatic, obfuscated, uglified, or
>> complexified.

> Nonsense.  The UCC entries win points for not be obfuscated or
> uglified or complicated.

Yet they would have instantly failed any code review in which I have 
participated.  I would not have found the bug, because I would have 
tossed back the code on sight.

In the example cited, 
http://graphics.stanford.edu/~danielrh/vote/mzalewski.c  the macro was 
egregious and obnoxious obfuscation and complexification, and would have 
led to a swift and automatic demand for rewrite without the macro - 
which rewrite in turn would have rendered the bug highly visible to code 
review - indeed it did render the bug highly visible to code review. 
That is how I spotted the bug, by de-obfuscating the code, whereupon it 
becomes obvious that the variable t is overused for incompatible purposes.

>> The code review would have come to an end, and the developer ordered
>> to do a rewrite, before the trick had been detected.

> So what do we do when we are asked to check an already completed
> program for back doors?

Do what I did in the example, and de-obfuscate the obfuscated code, by 
manually substituting the macro.  It did not take me very long.

> Now, if it is on the table, then I do not see any reason why it would
> be desirable to choose C over a more well-defined language.  If a
> complete rewrite is something we can undertake, then even if *none* of
> the languages available now fit the bill, why not just create a new
> one?  Why not just identify that subset of C that is "good" and write a
> compiler for that language, without any undefined behavior?  Why not
> create a new language that we can audit more easily if something like
> OCaml is "too slow" (or whatever reason people are giving for avoiding
> high-level languages these days)?

Whenever you attempt to do a project in "high level code", the project 
becomes ninety percent complete in much less time than when you do it in 
C++, and then remains ninety percent complete forever.

You get the higher level language problem that the libraries are 
slightly different on each machine, which results in nightmare 
installations.  Doubtless you can audit your code faster, but can you 
audit all those installations and libraries?

If you have one high level program using a library, and another high 
level program using that same library, there is, with remarkable 
frequency, a way for the one high level program to screw over the other 
high level program.