Subject: RE: Protecting Against Weak Hash Algorithms

From: "Santosh Chokhani" <[email-masked]>
Date: Thu, 21 Sep 2006 03:52:14 -0700

Russ,

I will be happy to.  I would like to prepare and run the presentation by
you.

________________________________

From: Russ Housley [mailto:[email-masked]] 
Sent: Wednesday, September 20, 2006 9:24 PM
To: Santosh Chokhani; [email-masked]
Subject: Re: Protecting Against Weak Hash Algorithms

Can you make a presentation in San Diego?

At 03:09 PM 9/20/2006, Santosh Chokhani wrote:

As you know the hashing algorithms are in state of flux (We know MD5 is
bad, SHA-1 is beginning to smell and so on).
 
Also, we know that many relying parties implement many of these
algorithms.
 
Also, Russ has been talking about making PKIX RFCs algorithm independent
so that algorithms can be easily swapped in and out.
 
I think we should have a debate on security issues surrounding weak
hashes, specifically relying parties snookered into verifying a
signature using a weak hash that can easily create collision with
payload that was actually signed using a strong hash.
 
While it will be a great deal of pain to the client software, but
subject public key information through OID or parameters could specify
one or more hash algorithms to be used with a signature key.  This will
protect against the spoofing of relying party into using a weak hash
during signature verification.  I thought while we are debating the
syntax for ECC based algorithms, this may be a good time to suffer that
pain.

Santosh Chokhani 
Orion Security Solutions, Inc. 
(703) 401-7088 
[email-masked]

---

From: "Santosh Chokhani" <[email-masked]>
Date: Thu, 21 Sep 2006 14:48:21 -0700

I am not a crypto mathematician.

I was doing protocol level analysis and reviewing the following Kaliski
paper 

http://www.rsasecurity.com/rsalabs/staff/bios/bkaliski/publications/hash
-firewalls/kaliski-hash-firewalls-ct-rsa-2002.pdf

Note that the paper was written 2002 (before all the hoopla about hash
functions).

The paper illustrates a theoretical attack against PKCS #1, Version 1.5.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of Wan-Teh Chang
Sent: Thursday, September 21, 2006 10:11 AM
To: [email-masked]
Subject: Re: Protecting Against Weak Hash Algorithms

Santosh Chokhani wrote:
> Paul,
> 
> Let us say that you as a signer is using SHA-1 and RSA.  I thought I
can
> keep your signature, but create a payload using a weak hash scheme
(say
> MD-4 or chokhani Hash) that is still lying in the relying party
system.
> Since the identification of the hash algorithm to be used in
> verification lies with the payload, pointing to the weak hash OID will
> be part of creation of the material.

If I understand you correctly, your proposal is useful
for DSA and ECDSA signatures because the (r, s) components
don't tell you what hash algorithm should be used.  On
the other hand, your proposal isn't necessary for PKCS #1
v1.5 RSA signatures because the hash algorithm is also
encrypted along with the hash.

Seems like the attack you want to protect against also
requires that the weaker hash algorithm's output is the
same length as the hash algorithm used in the original
signature.  Right now MD2, MD4, and MD5 are probably
the only such hash algorithms(all 128 bits long).  But
none of these can be used with DSA and ECDSA.

Wan-Teh

---

From: "Denis Pinkas" <[email-masked]>
Date: Fri, 22 Sep 2006 14:23:55 +0200

Santosh,

Why re-inventing the wheel ? There is another approach (Archive validation data )
 that avoids to over-complexify the problem.

Take a look at RFC 3126, page 20 :

   Before the algorithms used in any of electronic signatures become or
   are likely, to be compromised or rendered vulnerable in the future,
   it is necessary to time-stamp the entire electronic signature,
   including all the values of the validation and user data as an ES
   with Archive validation data (ES-A). 

and page 76 :

                                        The Archive validation data is
   necessary if the hash function and the crypto algorithms that were used
      to create the signature are no longer secure.

Denis

As you know the hashing algorithms are in state of flux (We know MD5 is bad, SHA-1 is beginning to smell and so on).
Also, we know that many relying parties implement many of these algorithms.
Also, Russ has been talking about making PKIX RFCs algorithm independent so that algorithms can be easily swapped in and out.
I think we should have a debate on security issues surrounding weak hashes, specifically relying parties snookered into verifying a signature using a weak hash that can easily create collision with payload that was actually signed using a strong hash.
While it will be a great deal of pain to the client software, but subject public key information through OID or parameters could specify one or more hash algorithms to be used with a signature key.  This will protect against the spoofing of relying party into using a weak hash during signature verification.  I thought while we are debating the syntax for ECC based algorithms, this may be a good time to suffer that pain.
Santosh Chokhani 
Orion Security Solutions, Inc. 
(703) 401-7088 
[email-masked]

---

From: "Santosh Chokhani" <[email-masked]>
Date: Fri, 22 Sep 2006 07:13:54 -0700

Denis,

I suspect we are discussing different threats.  My suggestion is to deal
with the threat of an attacker exploiting existence of weak hash
algorithms in the relying party system.

From: [email-masked] [mailto:[email-masked]]
On Behalf Of Denis Pinkas
Sent: Friday, September 22, 2006 8:24 AM
To: [email-masked]
Subject: Re: Protecting Against Weak Hash Algorithms

Santosh,

Why re-inventing the wheel ? There is another approach (Archive
validation data )

and page 76 :

   necessary if the hash function and the crypto algorithms that were
used

Denis

Santosh Chokhani

---

From: "Santosh Chokhani" <[email-masked]>
Date: Fri, 22 Sep 2006 14:57:43 -0700

That is my point.

I think in the longer run it is better to tie hash algorithm to the
SPKI.

From: Daniel Brown [mailto:[email-masked]] 
Sent: Friday, September 22, 2006 5:53 PM
To: Santosh Chokhani
Cc: [email-masked]; Paul Hoffman
Subject: RE: Protecting Against Weak Hash Algorithms

Santosh, Paul, 

Inclusion of hash OIDs in the subject public key info field is an option
in the current proposed syntax. Similarly, it is an option in the RFC
4055 for RSA-PSS and RSA-OAEP. 

I said in an earlier email there that I knew of neither hash
substitution attacks nor practical hash inversion attacks.  That said,
there are some impractical, and thus theoretical considerations one
might consider.  Suppose that Alice has a 384-bit EC public key, because
she wants 192 bits of security (i.e. very high security).  It is then
theoretically reasonable for Alice to insist that Bob not to accept her
signatures if they are signed with SHA-1, because SHA-1 has a maximum of
160 bits of security against preimage attacks.  Admittedly, this is
theoretical concern, because we don't foresee 160-bit attack being
practical for the next 20 years or more.  Anyway, Alice could indicate
this by putting ecdsa-with-Sha384 in the subject public key info of her
cert, if she wanted to this paranoid. 

Thanks, 

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

Santosh wrote on 09/22/2006 05:06:31 PM:

> 
> May be the vendors should respond as to what the installed base of
ECDSA
> is and if they see it worthwhile to include hash OID(s) in the subject
> public key algorithm and the attendant change to the software and
> installed based of ECDSA certificates.
> 
> From: Paul Hoffman [mailto:[email-masked]] 
> Sent: Friday, September 22, 2006 4:27 PM
> Subject: RE: Protecting Against Weak Hash Algorithms
> 
> 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
>