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




David Wagner wrote:
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.

Coppersmiths short padding attack is just one example.

And you'd have to be crazy not to use proper padding.

Let's call people that make mistakes implementing a padding scheme
careless not crazy.

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.

Certainly, everone should check their implementations carefully.
And just to be clear, I think most implementators are not testing their
implemenation careful enough.
But, can you be sure to find all implementations errors?
So what is wrong with trying to make your implementation a little bit
more robust?

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.

Mere speculation? It's certainly not my experience.

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?

I have seen such libraries. And I have a quite educational flaw I'd
like
to publish sometimes. But the company I worked for has so far not
released
the paper.

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.

Well, my first impression was that you tried to ridicule the GPG
developer
for his comment. I personally don't find anything wrong with trying to
make
an implementation a little bit more robust against unknown attacks.
All he needed to know is that smaller exponents might be more risky
than
bigger ones. I prefer developers that try to be on the safe side to the
ones
that spend most of their time optimizing the running time of their
implementation.

Daniel Bleichenbacher

.



Relevant Pages

  • Re: Proof Attempt For Fermats Last Theorem
    ... takes time to learn from your mistakes and finally suceed. ... primefactors and the possible exponents. ... numbers, squarefreeness of Mersenne numbers, Sophie Germain-primes, ... then the problem of the difficult properties of Wieferich primes, ...
    (sci.math)
  • Re: [CFT] Some updates to libc/rpc (second try)
    ... On Thu, Aug 30, 2012 at 2:21 AM, Andrey Simonenko ... This is rather critical stuff (libc) so I have no hurry and would ... Detailed description of mistakes in these files and correct implementation: ... A developer at $work developed a slightly simpler patch than ...
    (freebsd-current)
  • Re: gnupg rsa question // why use e of 41 ?
    ... well with very small exponents such as e=3, but don't work or are much ... But implementations do have mistakes. ... analysing many cryptographic libraries I know that these libraries have ... idea to make RSA implementations more robust by avoiding the smallest ...
    (sci.crypt)
  • Re: gnupg rsa question // why use e of 41 ?
    ... well with very small exponents such as e=3, but don't work or are much ... Of course these attacks can be avoided ... But implementations do have mistakes. ... analysing many cryptographic libraries I know that these libraries have ...
    (sci.crypt)