[Cryptography] 1023 nails in the coffin of 1024 RSA...

[Peter Gutmann]

James Cloos <cloos at jhcloos.com> writes:

>In order for that mis-rounding to occur, the compiler must mis-optimize the
>code.

Having had to deal with waaay too many optimisation bugs in gcc (including one
just found in in 4.8.2 that produces totally incorrect code when optimisation
is enabled) this may not be too far-fetched.  It seems like every new release
of gcc has a new set of code-generation bugs, but unless you run extensive
test suites (which a crypto library typically will, or at least should) you
won't notice them.  The advantage of a crypto test suite is that slight errors
are much easier to detect when everything is cryptographically secured, while
they'd slip by unnoticed in other cases.

That's the scary thing about this, the the buggy code that gcc can generate
will appear to function just fine in 99.9% of cases [0], it's only if you
include lots of internal consistency checks that you'll catch these can-never-
occur cases (in my case I have both a huge test suite and large amounts of
internal self-checks that caught this problem, even if I haven't been able to
track down the exact location and after a day of poking through disassembled
code I'm tempted to just say "get a less buggy compiler").

So a quick question for the people behind this:

- What version of gcc was this present for, and what level of optimisation was
  used?
- Does it still occur with a different gcc version?
- Does it still occur if you disable optimisation?
- Does it still occur if you use a less buggy compiler like clang/LLVM or MSVC,
  or in fact anything but gcc?

If, and that's a big if, this is real, I'd say the probability that it's yet 
another gcc compiler bug is far, far higher than the probability that it's 
some fundamental flaw in RSA or the RSA implementation.

Peter.

[0] Figure freely pulled out of thin air.