Optimisation Considered Harmful

[bear]

On Thu, 23 Jun 2005, Jerrold Leichter wrote:

> Consider what it means to create an optimizing compiler (or some
> kind of opti- mization in hardware - the issues are the same, but
> I'll talk in terms of a compiler for definiteness.)  The input is
> source code; the output is a bunch of instructions.  A compiler's
> transformation is correct if it's semantics- preserving:

Yep.  As a sometime compiler weenie, I'll give literal answers
to your next few questions.

> The big issue in compiler optimization - and even more so in some
> hardware optimization - is defining exactly what semantics has to be
> preserved.  For example, must computations be done even if the
> compiler can determine that they cannot affect the output?

No.  There's no language higher than assembly that requires that.  A
lot of compilers will do the redundant computations anyway because
the authors of those compilers considered that it would be too much
work to prove what can be eliminated, and in imperative languages
like C there's often little benefit in doing so.  But there are
transformations and techniques you can do (autoconverting to laziest
semantics allowed by the language spec) to absolutely determine what
can be eliminated, and emit code that *only* evaluates that which
does affect the output.  And increasingly, compilers are doing them.

> Can the
> rules of algebra be used to rearrange expressions (possibly breaking
> carefully crafted error management strategies, since floating point
> arithmetic doesn't actually obey the rules of algebra)?

If it changes the output, it's considered an error for C compilers to
do this.  That said, it's considered a minor error, and since a lot of
people are in a great hurry to get wrong answers, GCC will knowingly
and willingly commit this error for you (as an "extension" to the
language) if you give it a -O option that's too high.  And several
other compilers (including Borland's and Microsoft's) have committed
this error in the past without giving anyone the ability to turn it
off, or "by default" with a --fpstrict option to turn it off.

That said, in languages other than C you have to look to the language
spec to see whether this is allowed or not.  If the spec is silent on
the topic then rearranging in a way that changes output is still
usually considered a bug, but it becomes open to debate whether it is
an actual bug or not.

Some language specs (including Common Lisp, IIRC) and several
single-implementation languages (including Mathematica, IIRC) allow
arbitrary rearrangement of floating-point operations, provided that
the compiler can prove that *at least* as much precision is preserved
as would be gained by doing it in the order it appears in the source.
This is explicitly allowed to change output, provided the compiler can
prove that the changed output is a closer approximation to the
algebraic solution.  Even in languages where this is allowed, many
implementors consider it tasteless and try to avoid doing it,
conforming thier compilers' behavior to a tenet of the "principle of
least surprise."

>  Do writes
> to two variables written in order in the source code have to occur
> in that order in the object code?

In C, the answer depends on whether the variables are declared
volatile.  If they are not declared volatile, then the writes need not
appear in any particular order, and if the compiler can prove the
values are not used, need not appear at all.  In languages without
volatile variables, the answer is usually no.

> If two writes are issued in order
> to the hardware, do they have to hit memory in that order?

Uh, I think the short answer is no, but you'll never be able to
tell the difference in normal circumstances.  It's common for a
superscalar chip to buffer memory writes in its L1 Cache, and
write a cache line to memory at a go (which may reorder the writes
to memory that's off the chip).  But no software running on the
same chip will be able to tell it by "reading" those addresses,
because it will snag the "written" values (even though they
haven't hit phyiscal memory yet) out of the L1 cache.

Where this can break down with the possibility that you'd be able to
tell it's breaking down, is volatile variables in multiprocessor
machines.  But these are normally protected by mutexes, the
implementation of which must trigger explicit L1 cache flushes on
multiprocessor machines.

> An understanding of what semantics has to be preserved, and what
> semantics is "side-effect" and can be tossed to gain performance,
> has gradually emerged in the hardware and software communities.
> There have been, and continue to be, missteps along the way.  Some
> of the weaker memory consistency models might have helped the
> hardware guys, but were just too hard for the software guys to deal
> with.  Newbies to multi-threaded programming are caught by the
> not-so obvious memory access semantics present even at the language
> level in all common programming languages.  (Java tried to pin this
> down exactly and got it completely wrong for several tries.)

Um.  Yup.

> Enter cryptographic algorithms.  On their face, these are simple
> mathematical transformations. ... The problem is that these side-
> channel attacks broaden "the meaning of the program" to something
> that has never been considered in previous work that I know of.

Certainly I haven't seen any discussion of these problems anywhere
along my four-foot bookshelf of compiler books.

> What can be done?  Well, the first thing that's clearly needed is a
> more complete specification of the semantics of cryptographic
> algorithms.  Just the input/output transformation - which is all we
> write down in most analyses - is insufficient.  We sometimes state
> things informally, almost in passing - as in the comments on AES
> that "table accesses take constant time".  We certainly assume
> things like "the time to add two numbers is independent of the
> number of carries" - which is probably true on machines today, but
> may actually have been false at one time.

Interestingly, although the timing attack is obsolete, there is a
potential power attack here.  Since power is consumed when gates
switch from 0 to 1 or vice versa, if you know the machine is
performing an add instruction and you know how much power it's eating
at that precise instant, you can probably tell how many carries it
took, because the gates that hold the carry bits are normally 0 when
the add instruction starts and switch back to 0 before it's over.
I dunno if you can separate this from the other stuff going on at
the same time, and when you got it it would be combined with the
power for changing the destination operand to the answer - but you
might be able to eliminate a lot of possible keys that way.

> Without a way to write
> down what matters, we have no way to judge whether a particular
> compilation/hardware approach is safe.  There's some work on
> abstract program interpretation that might help here (though it's
> mainly aimed in other directions).

Right now there is no computer language (and no mathematical notation)
for writing this kind of stuff down.  Our compiler theory is mainly
based on math, our idea of program semantics almost wholly so based,
and these issues are not now modeled or tracked in any formal
semantics we use.

Further, the chip architecture used by most desktop machines is
not equipped to treat such semantic requirements correctly, and
even if we developed notation and semantic models that took these
issues into account, it would be difficult to get them to run
correctly on desktop machines.

>	- Use specialized hardware, designed not to leak side-channel
>		information.

I think the easiest way to achieve such hardware would be to
make it *constantly* leak side-channel information based on
several chaotic processes - in the hopes that attackers couldn't
isolate which parts of the information were related to your
algorithm.

					Bear

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com