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

[Henry Baker]

At 09:31 PM 8/26/2016, D. Hugh Redelmeier wrote:
>| 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.

There are clever ways to do "tail recursion" in C:

http://home.pipeline.com/~hbaker1/CheneyMTA.html

http://home.pipeline.com/~hbaker1/CheneyMTA.pdf

Although my paper doesn't provide the particular optimization in the
Gnu C compiler, there is (or used to be!) a switch that tells the Gnu
C compiler that certain calls aren't coming back, so don't bother
emitting any more code.

(Note also that the Intel x86 -- and most likely the x64, as well --
includes a hardware lookaside cache that attempts to avoid memory
references for stack pushes & pops for return addresses.  This cache
will get totally discombobulated if you use x86 stack instructions
for non-nested behavior.  Furthermore, there are some new architectural
"features" that attempt to outlaw non-nested behavior completely, in
order to try to stop "return-oriented programming" (ROP) which is
more-and-more utilized for exploits.)