[Cryptography] Montgomery multiplication bug in OpenSSL?

[dj at deadhat.com]

>
>
> Also I have reason to believe this is not that unusual. We already had
> a bug in BN_sqr earlier this year. I think testing bignum libraries is
> something that needs to be done more thoroughly.
>

We are implementing algorithms of this sort in hardware. The consequences
of bugs of this sort would be much worse than in software. Things can't be
patched. Having concluded that randomized testing wasn't going to get at
the corner cases and that our brains were not big enough to get it right,
we took the track of formal equivalence testing of the logic gates to high
level algorithm descriptions. The intent is to have validation for all
input values.

We have the advantage of knowing what a gate is, much more than we can
know what a compiler does (as per the recent discussions on gcc) so FEV is
good and powerful stuff.

It's maybe not relevant to the problem at hand, but high-level -> Gates
FEV has worked extraordinarily well for us. I can't help thinking it
should be able to work well against assembler for this class of algorithm.