Re: gnupg rsa question // why use e of 41 ?

daniel bleichenbacher wrote:
>There are many attacks that work
>well with very small exponents such as e=3, but don't work or are much
>harder with e=65537 or larger.

Sure, but not if you use proper padding. If you use appropriate padding,
I'm not aware of any attack that works against e=3 but fails against
e=65537. And you'd have to be crazy not to use proper padding.

>Of course these attacks can be avoided
>if implemented correctly. But implementations do have mistakes.

Well, maybe. Personally I'd be more inclined to spend the time to
examine the implementation to make sure it is done correctly, rather than
increasing e and hoping that the large e will cover up implementation
mistakes. I suspect that, for every possible implementation mistake
that renders e=3 insecure but poses no risk to e=65537, there are a
half dozen possible implementation mistakes that render both choices
insecure, so there is no getting around the need for careful scrutiny
of the implementation.

It's even remotely possible that using e=65537 may make things worse,
because using e=65537 probably requires the encryption routine to
call a general-purpose modular exponentiation subroutine, whereas e=3
only requires the encryption routine to call modular multiplication
and a modular squaring subroutines, which are simpler. When it comes
to risk of implementation mistakes, it is remotely possible that the
added opportunities to make mistakes in the encryption routine might
counterbalance any other benefits of e=65537. I think this is a little
far-fetched, but not entirely impossible.

Have you seen any implementation mistakes in the wild that render the
library insecure with e=3 but secure with e=65537? Can you share a
concrete example or two? Maybe I'm just having a hard time imagining
how an implementation error could compromise e=3 but not compromise
e=65537, if the developer knows what they're doing. Seeing an example
might be enlightening.

P.S. In any event, I'm still suspicious that the comment in the GPG
source code indicates a developer who didn't understand these issues
and wasn't doing an analysis of anywhere near this depth.
Received on Mon May 1 02:06:24 2006