Subject: RE: Protecting Against Weak Hash Algorithms

From: Paul Hoffman <[email-masked]>
Date: Fri, 22 Sep 2006 13:27:09 -0700

At 12:56 PM -0700 9/22/06, Santosh Chokhani wrote:
>Do you see interoperability problems with defining new ECDSA OIDs?

Of course, if people are still expecting the old ones in certs they receive.

--Paul Hoffman, Director
--VPN Consortium

---

From: "Santosh Chokhani" <[email-masked]>
Date: Fri, 22 Sep 2006 12:56:23 -0700

Paul,

-----Original Message-----
From: Paul Hoffman [mailto:[email-masked]] 
Sent: Friday, September 22, 2006 3:54 PM
To: Santosh Chokhani; [email-masked]
Subject: RE: Protecting Against Weak Hash Algorithms

At 12:29 PM -0700 9/22/06, Santosh Chokhani wrote:
>When you register a new OID for subject public key information and that
>OID has in its parameters list the possible hash OIDs, that is not a
>change to the certificate syntax since it is dependent on the OID for
>the subject public key information.

Thank you for the clarification. If you want people to use new OIDs 
(such as "RSA over SHA-1" instead of today's "RSA"), then people 
using the new OID would have their signatures rejected by receiving 
software that didn't know the new OID, even though the receiving 
software has all the bits needed to validate the signature. I suggest 
that this is not a good idea, and that it will be terribly confusing 
to both software vendors ("which of the OIDs should I use here") and 
users ("he says he signed it with RSA and SHA-1, and I can read other 
certs with those algorithms, why can't I read his?").

>As to weak and strong hash, I would assume MD4 followed by MD5 and some
>day SHA-1 could be candidates.

Sorry to be so repetitive, but please define "weak". From this 
sentence, you seem to be saying "weak" means has less that expected 
collision resistance because there have been no practical preimage 
attacks on the functions you list. So, either you mean that your 
proposed attack works with a collision attack, or you believe that 
there are practical preimage attacks on those functions. Please 
specify which you believe to be true.

--Paul Hoffman, Director
--VPN Consortium

---

From: Daniel Brown <[email-masked]>
Date: Fri, 22 Sep 2006 17:31:24 -0400

Paul, Santosh,

Regarding your discussion of interoperability and ECDSA:

The new ECDSA OIDs from X9.62 that I've proposed for PKIX use the old 
ecdsa-with-Sha1 OID to indicate that a signature is signed with SHA-1. 
Therefore old and new implementations should be able to interopate.

If a signature is not signed with Sha-1, then are several options.  The 
preferred option are the fixed OIDs, such as ecdsa-with-Sha256 is SHA-256 
is used.  Another option is ecdsa-with-Specified, where a hash OID is put 
in the parameters field.  Note that only approved hash functions are 
allowed to go in the parameters field.  (This makes it slightly easier new 
hash functions, e.g. AHS). A third option is ecdsa-with-Recommended, which 
was intended to bind the hash function to the public key size, but that 
seems impractical now because of the uncertainty about hash functions.  If 
new implementations cannot agree on which of the three options, then 
there's interop problems.  If they all agree to support the fixed OID 
option, which is the preferred choice, then they should be fine.

As for security: 

I'm not aware of any practical preimage attack on the currently specified 
hash functions for ECDSA.   Suppose, however that a verifier was persuaded 
to use ecdsa-with-Specified with some illegal pre-image-weak hash OID in 
the parameter.  (Note again, this defies the currently specified ASN.1 
syntax.)   It is tempting to think that an attacker would then want to 
re-use an existing signature as singnature for some other message computed 
as the preimage of the hahs of the truly signed message.  However, it is 
well-known that if a hash is preimage-weak, then an attacker can directly 
forge ECDSA signatures.  (The same applies to DSA).  For example, see 
Section 6 of http://eprint.iacr.org/2002/026 .  Therefore, standards for 
ECDSA need to be very strict about what hash can be used.  Signatures for 
RSA may be a little different in this regard: a hash inverter may be 
insufficient for existential forgery.  However, a hash inverter + an 
existing signature may lead to a forgery.  This, there is a weak rationale 
for putting a hash id "firewall" in a RSA signature to prevent the 
substitution by a weak hash.  ECDSA and DSA simply have to directly 
disallow hash substituion.

I hope that helps,

Thanks,

Dan Brown
(905) 501-3857
http://www.certicom.com

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 22 Sep 2006 14:46:13 -0700

At 5:31 PM -0400 9/22/06, Daniel Brown wrote:
>The new ECDSA OIDs from X9.62 that I've proposed for PKIX use the 
>old ecdsa-with-Sha1 OID to indicate that a signature is signed with 
>SHA-1.  Therefore old and new implementations should be able to 
>interopate.

So, it sounds like Santosh's suggestion isn't needed for ECDSA.

>I'm not aware of any practical preimage attack on the currently 
>specified hash functions for ECDSA.

Right. It seems like the attack is not practical.

--Paul Hoffman, Director
--VPN Consortium