Exponent 3 damage spreads...

[David Wagner]

"James A. Donald" <jamesd at echeque.com> writes:
>Parameters should not be expressed in the relevant part
>of the signature.  The only data that should be
>encrypted with the RSA private key and decrypted with
>the public key is the hash result itself, and the
>padding.  If the standard specifies that additional
>material should be encrypted, the standard is in error
>and no one should follow it.

I agree with this comment, and with many of the other sensible
comments you have made in this thread.

I would modify what you said slightly: it may be reasonable to include a
field identifying the hash algorithm alongside the hash digest.  But apart
from that, throwing in additional optional parameters strikes me as just
asking for trouble.

It seems to me that e=3 is a distraction.  I think that these security
holes have revealed some more fundamental issues here that are independent
of the value of e you use.

It seems to me that the problems can be attributed to two problems:
(a) implementation bugs (failures to implement the spec faithfully); and
(b) ad hoc signatures schemes that have never been adequately validated.
In more detail:

  (a) Any implementation that doesn't check whether there is extra
  junk left over after the hash digest isn't implementing the PKCS#1.5
  standard correctly.  That's a bug in the implementation.  Of course,
  as we know, if you use buggy implementations that fail to implement
  the specification faithfully, all bets are off

  (b) The discussion of "parameter fields" in PKCS#1.5 signatures
  illustrates a second, orthogonal problem.  If your implementation
  supports appending additional parameter fields of some general
  structure, then you have not implemented conventional PKCS#1.5
  signatures as they are usually understood; instead, you have implemented
  some extension.  That raises a natural question: Why should we think
  that the extended scheme is still secure?  I see no reason to think
  that throwing in additional parameters after the hash digest is a safe
  thing to do.  I suggest that part of the problem here is that people
  are using signature padding schemes that have not been validated and
  have not been proven secure.  These PKCS#1.5 variants that allow you to
  include various optional ASN.1 crud alongside the hash digest have never
  been proven secure.  These days, using an ad hoc padding scheme that
  has not been proven secure is asking for trouble.  Why are people still
  deploying cryptographic schemes that haven't been properly validated?

I would suggest that there are two lessons we can learn from this
experience: (a) maybe more attention needs to be paid to verifying
that our implementations correctly implement the specification; and,
(b) maybe more attention needs to be paid to validating that the spec
defines a cryptographic mode of operation that is sensible and secure --
and provable security might be a good starting point for this.

Consequently, I think the focus on e=3 is misguided.  I think we should
be more concerned by the fact that our crypto implementations have
implementation bugs, and that our specs were never adequately validated.
This time, the impact of those failures may have been worse for signatures
using e=3, but it seems to me that this is more an accident than anything
particularly fundamental.  The latest problems with e=3 are just the symptom,
not the root cause.  I think it's worth putting some effort into treating
the root cause, not just the symptom.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com