[Cryptography] How programming language design can help us write secure crypto code

Jerry Leichter leichter at lrw.com
Mon Nov 2 06:40:51 EST 2015


> Before the standard for floating point arithmetic (IEEE 754),
> the same formula (program) would produce different results on
> different calculators (computers).
Actually, that's still the case.  IEEE 754 pins down a great deal, but not everything.  In particular, intermediate results may be carried to a higher precision, which can have a significant effect on the final results.  Early Java ran into this by being even more explicit than IEEE 754, requiring "bit by bit" equality of results.  This destroyed performance on x86 hardware, which carried values in registers to extra precision, and only rounded when storing into memory.  IEEE 754 permits this.

IBM's Power series of chips have run into a simpler version of the same issue by providing a fused multiply and add instruction, which gives you more precision than doing the operations separately can attain.  (It's also faster.)

In each case, there was strong sentiment that if you're writing FP code, you don't expect bit-by-bit equality, and you'll take the extra performance.  Compilers for Power will generate multiply-and-add when they can (you can disable this if you want), and Java was changed to eliminate the bit-for-bit-equality requirement (except in strict_fp code).

In these two cases, you got *more* precision - but if you go back to the old CDC machines - the champions of big numeric computations for many years - their FP arithmetic wasn't as precise as it could have been - but that was considered a worthwhile tradeoff for increased performance.

> Those computers that, given a good program, would produce bad
> results, Kahan called "egregious machines."
I've read some of Kahan's stuff and heard him speak once.  He's made important contributions, but realize that not all numerical analysts agree 100% with his approach.

Numerical analysis deal with several classes of problems, and Kahan has been accused of mainly worrying about algorithms for doing linear algebra.  While these are very important, they aren't the whole story.  This isn't my field, but I gather that as one example, the guys doing interval analysis (where you try to compute a tight bound around the true result of your computation - so in general your inputs and outputs are not individual values but intervals guaranteed to contain the actual value) have never been particularly happy with IEEE 754, even though the rounding modes were supposed to help them.  (I suspect one complaint is exactly that they are *modes*, not separate instructions, so if, as in interval arithmetic, you want results with different kinds of rounding, you end up switching modes all the time - which kills performance.)

The whole non-standard arithmetic business - Infinity and NaN - helps with some kinds of code, adds complexity to other kinds of code.  (I mentioned earlier that a bug I've seen repeatedly is combining some vector of measures M with a weight vector W and assuming that when you set some Wi to 0, you've "knocked out" the corresponding Mi.  This is true *only as long as Mi is finite*.  Once NaN and Infinity enter the domain of values, you have to add a special check each time you do the inner product - which in many algorithms is right at the center of all your loops.)

It's easy to say that "getting the wrong answer faster" is pointless, but in numerical work, you pretty much *always* get "the wrong answer" because the "right" answer requires infinite precision.  Even as simple an equation as 3x=1 has a root that cannot be represented exactly in any binary FP system.

So the issue isn't rightness or wrongness, it's being able to understand and control what the bounds of the wrongness are and get them small enough for the result to be useful.  Once you've done that, performance is everything.

                                                        -- Jerry



More information about the cryptography mailing list