[Cryptography] tail recursion in C [was Re: "NSA-linked Cisco exploit poses bigger threat than previously thought"]

[D. Hugh Redelmeier]

| From: Ron Garret <ron at flownet.com>

|  You can’t GOTO a label outside of the current function.  That 
| makes it impossible to implement tail recursion in pure C unless you 
| compile your entire program into a single C function.

If the last act of a function is to call another function, that call
can be compiled as a goto (plus some conversion of the current
function's activation record into the parameters for the new
function).  Tail recursion optimization is a special case of this.

This is purely an implementation feature.  I cannot think of anything
in C that precludes this optimization.  Just culture?

This optimization confuses programmers trying to debug the result,
but then so do many optimizations.

Slide to crypto relevance:

Optimization can destroy some properties that one might have
intentionally coded into a program.

If you carefully coded all paths through a loop to take the same time (to 
avoid timing sidechannel attacks) an optimizer might re-introduce them.  

If you clear variables to avoid having sensitive values laying around, an 
optimizer might detect that the clearing is redundant and eliminate it.

GCC optimization has been known to eliminate assert calls that would
have fired.  Technically, these optimizations were correct but the
result was unsafe for human programmers.  Roughly, if your code
dereferences a pointer, that tells the compiler that it may assume
that the pointer is non-Null; a subsequent test of that pointer for
NULL may then be assumed to yield false.