Why the exponent 3 error happened:

Whyte, William WWhyte at ntru.com
Fri Sep 15 17:54:17 EDT 2006


>  > If so, I fear we are learning the wrong lesson, which
>  > while valid in other contexts is not pertinent here.
>  > TLS must be flexible enough to accommodate new
>  > algorithms, this means that the data structures being
>  > exchanged are malleable, and that implementations must
>  > validate strict adherence to a specifically defined
>  > form for the agreed algorithm, but the ability to
>  > express other forms cannot be designed out.
> 
> There is no need, ever, for the RSA signature to encrypt
> anything other than a hash, nor will their ever be such
> a need.  In this case the use of ASN.1 serves absolutely
> no purpose whatsoever, other than to create complexity,
> bugs, and opportunities for attack.  It is sheer
> pointless stupidity, complexity for the sake of
> complexity, an indication that the standards process is
> broken.

I think this is a bit unfair.

PKCS#1 signatures were originally designed to include a hash 
identifier to address a specific concern, arising from the
fact that RSA signers can freely choose the hash algorithm
to use.

Say that Alice uses SHA-1 to generate her signature on m,
and SHA-1(m) = h.

Then the concern is that Bob can find a broken hash function
BASH such that BASH(m') = h. If he can do that and format a
message that claims to be signed with RSA and BASH, then he
can present Alice's signature as a valid signature on m'.

There are a number of different protections against this.
For example, Alice's cert could identify her key as only 
to be used with SHA-1 (this is effectively what happens with
DSA public keys). However, the convention has been to mark an
RSA key in an X.509 cert as rsaEncryption and not specify
in the AlgorithmIdentifier that it's only to be used with a
certain hash function (or signature scheme).

So PKCS#1 incorporated the hash identifier, which prevents
a signature generated with one hash algorithm from being
used with a different hash algorithm. (Since then, Burt
Kaliski's done some research on the use of hash "firewalls"
of this type: see
http://www.rsasecurity.com/rsalabs/node.asp?id=2020.
His conclusion is that by and large they aren't necessary,
but that isn't relevant to the discussion here).

At the time, ASN.1 was in widespread use, so it was an 
obvious decision (rather than pointless stupidity) to use 
it to encode the hash function identifier. In practice, 
the ASN.1 doesn't introduce complexity because most implementations 
(certainly ones I've worked on) simply treated it as a memcmp 
rather than wheeling out the heavy ASN.1 machinery.

The real problem isn't ASN.1; the problem is that an
encoding method was used for the rest of the signature
that didn't specify the length of the signature block
and it didn't occur to anyone to check it.

Cheers,

William


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



More information about the cryptography mailing list