Subject: [TLS] DSA/SHA-1, and OIDs

From: Eric Rescorla <[email-masked]>
Date: Mon, 12 Nov 2007 11:11:14 -0800

Hi PKIX guys,

As you probably know, in some modes of TLS one or the other party
signs data. In some cases, this presumably means DSA. This is 
fine if you can guarantee that you are going to use SHA-1 with
DSA, but obviously there's going to be a desire to transition
to SHA-256, which raises the issue of digest substitution.

My understanding of the current thinking on how to prevent this
is to indicate in the certificate which digest algorithm is to
be used with the cert. So, the rule we plan to promulgate in TLS
is: 

	OID 1 2 840 10040 4 1 MUST only be used with SHA-1.  Future
	revisions of [PKIX] MAY define new object identifiers for DSA
	with other hash algorithms.

I wanted to check that this is compatible with the current PKIX
thinking.

Thanks,
-Ekr

_______________________________________________
TLS mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tls

---

From: Stefan Santesson <[email-masked]>
Date: Fri, 16 Nov 2007 15:27:20 +0000

Not really.

The OID 1 2 840 10040 4 1 identifies DSA only and is used in the subject public key info for declaring the DSA key. In FIPS 186-2 sha-1 was the only hash algorithm, but this is expanded in FIPS 186-3

The following OIDs are relevant

>From RFC 3279:

  -- OID for DSA public key
   id-dsa OBJECT IDENTIFIER ::= {
        iso(1) member-body(2) us(840) x9-57(10040) x9algorithm(4) 1 }

   -- OID for DSA signature generated with SHA-1 hash
   id-dsa-with-sha1 OBJECT IDENTIFIER ::=  {
        iso(1) member-body(2) us(840) x9-57 (10040) x9algorithm(4) 3 }

>From draft-ietf-pkix-sha2-dsa-ecdsa-01.txt

        id-dsa-with-sha224 OBJECT IDENTIFIER ::=  { joint-iso-
        ccitt(2) country(16) us(840) organization(1) gov(101)
        csor(3) algorithms(4) id-dsa-with-sha2(3) 1}

        id-dsa-with-sha256 OBJECT IDENTIFIER ::=  { joint-iso-
        ccitt(2) country(16) us(840) organization(1) gov(101)
        csor(3) algorithms(4) id-dsa-with-sha2(3) 1}

Stefan Santesson
Senior Program Manager
Windows Security, Standards

> -----Original Message-----
> From: Eric Rescorla [mailto:[email-masked]]
> Sent: den 12 november 2007 20:11
> To: [email-masked]; [email-masked]
> Subject: [TLS] DSA/SHA-1, and OIDs
>
> Hi PKIX guys,
>

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 17 Nov 2007 06:17:38 -0800

At Fri, 16 Nov 2007 15:27:20 +0000,

>         csor(3) algorithms(4) id-dsa-with-sha2(3) 1}

Stefan,

Maybe it's worth upleveling a bit.

My claim is that for security reasons it's necessary for DSA certs
to indicate the hash algorithm(s) that may be used with the cert.
This prevents hash algorithm substitution in the signature. 
Do you agree with this?

If so, then it becomes a question of encoding this information in
the cert. I'm not a PKIX expert and don't have an opinion about
how it should be encoded except that:

1. Current certificates must obviously be usable with at least
   SHA-1.
2. There must be a way for future certificates to rule out SHA-1.

How does PKIX propose to solve this?

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 19 Nov 2007 08:47:53 -0800

At Mon, 19 Nov 2007 11:35:47 -0500,
Stephen Kent wrote:
> Eric,
> Your question was:
> The wording here strikes me as a bit odd.  The hash algorithm used to 
> verify a cert IS specified in the cert, in the SignatureAlgorithm 
> field.
>
> The hash algorithm(s) that may be used with the public KEY in the 
> cert are not specified, in general, as the key may be used to verify 
> signatures for certs or for other signed objects (in the case of EE 
> certs).

I agree my wording was imprecise. Let me rephrase:

 	My claim is that for security reasons it's necessary for DSA
 	certs to indicate the hash algorithm(s) that may be used with
 	the public key contained in the cert. This prevents hash
 	algorithm substitution in signatures formed with that key
	(or rather the private key that corresponds to that key). Do
 	you agree with this?

-Ekr

---

From: Stefan Santesson <[email-masked]>
Date: Mon, 19 Nov 2007 18:39:00 +0000

First a small technicality.

I copied the OID from the ASN'1 section of the draft.

Someone pointed out to me that the two OIDs were identical. So here are the correct OIDs

     --
     -- DSA with SHA-224 and SHA-256 signature algorithms
     --

     dsa-with-sha224 OBJECT IDENTIFIER ::=  { joint-iso-
             ccitt(2) country(16) us(840) organization(1)
             gov(101) csor(3) algorithms(4) id-dsa-with-sha2(3)
             1}

     dsa-with-sha256 OBJECT IDENTIFIER ::=  { joint-iso-
             ccitt(2) country(16) us(840) organization(1)
             gov(101) csor(3) algorithms(4) id-dsa-with-sha2(3)
             2}

On the subject I have a clear opinion and that is an absolute no to do this through subject public key info.

The subject public key info is a core field of a certificate and it has a defined meaning to provide the key and its parameters. In addition to this the field also supplies an identifier of the key which identifies the key and parameter structure and syntax so it can be parsed. All X.509 software and systems using X.509 built to this date that I know of is designed to use the field exclusively in this manner.

In general, it is the responsibility of the protocol to limit the algorithms used, not the public key certificate. When limitations are specified in the certificate this is guidance for the applications using it. Except for a few core restrictions defined in path validation, it is nothing that will be enforced on the crypto API level. ANSI has made attempts to defined expanded restrictions in the subject public key field for ECC algorithm modes and this is exactly the type of complexity and change in field usage we don't need in X.509. Especially since nobody has defined where in the system architecture these restrictions should be enforced (protocol level, application level or crypto library level where keys are stored and used).

Conclusion is. Any new types of usage restrictions must be provided in a new field. i.e. in a certificate extension and it must be understood that this serves as information to the relying party on when it is appropriate to use this certificate.

Stefan Santesson
Senior Program Manager

> Sent: den 19 november 2007 17:48
> To: Stephen Kent
> Cc: Eric Rescorla; Stefan Santesson; [email-masked]; [email-masked]
> Subject: Re: [TLS] DSA/SHA-1, and OIDs
>
> certs

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 19 Nov 2007 11:07:03 -0800

At Mon, 19 Nov 2007 18:39:00 +0000,
Stefan Santesson wrote:
> The subject public key info is a core field of a certificate and it
> has a defined meaning to provide the key and its parameters. In
> addition to this the field also supplies an identifier of the key
> which identifies the key and parameter structure and syntax so it
> can be parsed. All X.509 software and systems using X.509 built to
> this date that I know of is designed to use the field exclusively in
> this manner.

OK.

> In general, it is the responsibility of the protocol to limit the
> algorithms used, not the public key certificate.

This seems problematic: the issue here is downgrade attack.
The relying party has support for a variety of digest
algorithms and if there's no indication in the certificate
of which digests will be used, then essentially an attacker
can attack the weakest one. 

> When limitations
> are specified in the certificate this is guidance for the
> applications using it. Except for a few core restrictions defined in
> path validation, it is nothing that will be enforced on the crypto
> API level. ANSI has made attempts to defined expanded restrictions
> in the subject public key field for ECC algorithm modes and this is
> exactly the type of complexity and change in field usage we don't
> need in X.509. Especially since nobody has defined where in the
> system architecture these restrictions should be enforced (protocol
> level, application level or crypto library level where keys are
> stored and used).
>
> Conclusion is. Any new types of usage restrictions must be provided
> in a new field. i.e. in a certificate extension and it must be
> understood that this serves as information to the relying party on
> when it is appropriate to use this certificate.

OK well, I don't have a problem with it being in a new field,
or that it's for the information of the relying party, but for
the reasons I argue above, I think it needs to be uniform for
all protocols and needs to be in the cert.

-Ekr

---

From: Stephen Kent <[email-masked]>
Date: Mon, 19 Nov 2007 15:01:07 -0500

>	(or rather the private key that corresponds to that key). Do

OK, that is clearer.

While I do see some benefits to being able to specify a has algorithm 
to use with a public key and algorithm specified in a cert, I agree 
with Stefan that the SubjectPublicKeyInfo field is NOT the place to 
do this, given the history of how this field is used and the 
peripheral nature of the info you want to specify.  I think it would 
be best to create a new extension that one could use for this 
purpose, like the extension created for S/MIME to express the 
symmetric  algorithm(s) supported by a recipient of encrypted 
messages.

Steve

---

From: Stephen Kent <[email-masked]>
Date: Mon, 19 Nov 2007 15:01:07 -0500

OK, that is clearer.

Steve

---

From: "Manger, James H" <[email-masked]>
Date: Tue, 20 Nov 2007 13:17:50 +1100

RXJpYywNCg0KUEtJWCBkaXNjdXNzZWQgdGhpcyBpc3N1ZSBpbiBkZXB0aCBhIHllYXIgYWdvLg0KRGlmZmVyZW50IGFwcHJvYWNoZXMgaGFkIGJlIHNwZWNpZmllZCBmb3IgRUNDIGFuZCBSU0ENCltkcmFmdC1pZXRmLXBraXgtZWNjLXBrYWxncy0wMy50eHRdW1JGQyA0MDU1XS4NCkEgRGVzaWduIFRlYW0gd2FzIGZvcm1lZCB0byBwcm9wb3NlIGEgc29sdXRpb24uDQpBcHBhcmVudGx5IHRoZXkgc3VnZ2VzdGVkIGEgM3JkIGFsdGVybmF0aXZlIC0tDQpkZWZpbmluZyBhIG5ldyBjZXJ0aWZpY2F0ZSBleHRlbnNpb24uDQpJIGNhbm5vdCByZW1lbWJlciBzZWVpbmcgYW55IGZ1cnRoZXIgcHJvZ3Jlc3Mgb24gdGhhdCB3b3JrLg0KSSBhbSBzdXJlIG5vIHN1Y2ggZXh0ZW5zaW9uIHdhcyBhY3R1YWxseSBzdGFuZGFyZGl6ZWQuDQoNCkEgZ29vZCBwbGFjZSB0byBzdGFydCBpbiB0aGUgZW1haWwgYXJjaGl2ZSB3b3VsZCBiZQ0KIlN0cmF3IHBvbGwgZm9yIEFsZ29yaXRobSBJZGVudGlmaWVycyBpbiBTdWJqZWN0IFB1YmxpYyBLZXkgSW5mbyIsDQpieSBTdGVmYW4gU2FudGVzc29uLg0KaHR0cDovL3d3dy5pbWMub3JnL2lldGYtcGtpeC9tYWlsLWFyY2hpdmUvbXNnMDIzMDUuaHRtbA0KDQoNCi0tLS0tIC0tLS0tDQpGcm9tOiBvd25lci1pZXRmLXBraXhAbWFpbC5pbWMub3JnIFttYWlsdG86b3duZXItaWV0Zi1wa2l4QG1haWwuaW1jLm9yZ10gT24gQmVoYWxmIE9mIEVyaWMgUmVzY29ybGENCg0KIAlNeSBjbGFp20 06:13:56 2007Return-path: <[email-masked]>Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com)	by megatron.ietf.org with esmtp (Exim 4.43)	id 1IuR2v-0006fo-I0; Tue, 20 Nov 2007 06:13:37 -0500Received: from tls by megatron.ietf.org with local (Exim 4.43)	id 1IuIgY-0004Lz-3Q	for [email-masked]; Mon, 19 Nov 2007 21:17:58 -0500Received: from [10.90.34.44] (helo=chiedprmail1.ietf.org)	by megatron.ietf.org with esmtp (Exim 4.43) id 1IuIgX-0004Lq-Ob	for [email-masked]; Mon, 19 Nov 2007 21:17:57 -0500Received: from mailipbo.ntcif.telstra.com.au ([202.12.233.29])	by chiedprmail1.ietf.org with esmtp (Exim 4.43) id 1IuIgX-0002vP-3P	for [email-masked]; Mon, 19 Nov 2007 21:17:57 -0500Received: from unknown (HELO mailai.ntcif.telstra.com.au) ([202.12.162.17])	by mailipbi.ntcif.telstra.com.au with ESMTP; 20 Nov 2007 13:17:54 +1100Received: from mail.cdn.telstra.com.au (localhost [127.0.0.1])	by mailai.ntcif.telstra.com.au (Postfix) with ESMTP	id 525CAFF85; Tue, 20 Nov 2007 13:17:54 +1100 (EST)Received: from wsmsg2952.srv.dir.telstra.com (wsmsg2952.srv.dir.telstra.com	[192.74.195.51]) by mail.cdn.telstra.com.au (8.8.2/8.6.9) with	ESMTP id NAA20036; Tue, 20 Nov 2007 13:17:53 +1100 (EST)Received: from WSMSG2103V.srv.dir.telstra.com ([172.49.40.20]) by	wsmsg2952.srv.dir.telstra.com with Microsoft SMTPSVC(6.0.3790.1830); 	Tue, 20 Nov 2007 13:17:53 +1100X-MimeOLE: Produced By Microsoft Exchange V6.5Content-class: urn:content-classes:messageMIME-Version: 1.0Subject: RE: [TLS] DSA/SHA-1, and OIDsDate: Tue, 20 Nov 2007 13:17:50 +1100Message-ID: <[email-masked]>In-Reply-To: <[email-masked]>Thread-Topic: [TLS] DSA/SHA-1, and OIDsThread-Index: Acgq2OmrK/CPwedORjuYCnyihrUTXgAQSaBAReferences: <[email-masked]>	<[email-masked]>From: "Manger, James H" <[email-masked]>To: <[email-masked]>, <[email-masked]>X-OriginalArrivalTime: 20 Nov 2007 02:17:53.0002 (UTC)	FILETIME=[8E352CA0:01C82B1B]X-Spam-Score: 0.0 (/)X-Scan-Signature: d6b246023072368de71562c0ab503126X-Mailman-Approved-At: Tue, 20 Nov 2007 06:13:35 -0500Cc: X-BeenThere: [email-masked]: 2.1.5Precedence: listList-Id: "This is the mailing list for the Transport Layer Security working	group of the IETF." <tls.lists.ietf.org>List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/tls>,	<mailto:[email-masked]?subject=unsubscribe>List-Archive: <http://www1.ietf.org/pipermail/tls>List-Post: <mailto:[email-masked]>List-Help: <mailto:[email-masked]?subject=help>List-Subscribe: <https://www1.ietf.org/mailman/listinfo/tls>,	<mailto:[email-masked]?subject=subscribe>Content-Type: multipart/mixed; boundary="===============1998109409=="Errors-To: [email-masked]

Eric,

PKIX discussed this issue in depth a year ago.
Different approaches had be specified for ECC and RSA
[draft-ietf-pkix-ecc-pkalgs-03.txt][RFC 4055].
A Design Team was formed to propose a solution.
Apparently they suggested a 3rd alternative --
defining a new certificate extension.
I cannot remember seeing any further progress on that work.
I am sure no such extension was actually standardized.

A good place to start in the email archive would be
"Straw poll for Algorithm Identifiers in Subject Public Key Info",
by Stefan Santesson.
http://www.imc.org/ietf-pkix/mail-archive/msg02305.html

----- -----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Eric Rescorla

-Ekr

---

From: Stephen Kent <[email-masked]>
Date: Mon, 19 Nov 2007 11:35:47 -0500

Eric,

Your question was:

Steve

---

From: Stefan Santesson <[email-masked]>
Date: Tue, 20 Nov 2007 16:19:40 +0000

James,

The design team has met again and will talk about it at the PKIX meeting.
However, this has never extended beyond the public key algorithm itself.
No one has seriously requested a full signature algorithm with hash algorithm to be specified in this field.

Stefan Santesson
Senior Program Manager

> From: [email-masked] [mailto:owner-ietf-
> [email-masked]] On Behalf Of Manger, James H
> Sent: den 20 november 2007 03:18
> Subject: RE: [TLS] DSA/SHA-1, and OIDs
>
>
> Eric,
>
> From: [email-masked] [mailto:owner-ietf-
> [email-masked]] On Behalf Of Eric Rescorla
>

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 20 Nov 2007 09:33:36 -0800

At Tue, 20 Nov 2007 16:19:40 +0000,
Stefan Santesson wrote:
> 
> [1  <text/plain; utf-8 (base64)>]
> James,
> 

Please take this message as a request from me that it be so, at
least for DSA/ECSDA.

-Ekr

---

From: Russ Housley <[email-masked]>
Date: Tue, 20 Nov 2007 10:42:09 -0500

Eric:

I disagree.  When an actual signature is generated, then signer must 
indicate which hash was used to generate the signature.  Only the 
holder of the private key can generate the signature, so the holder 
of the private key is totally in control of which hash function they 
choose to use.

X.509 and CMS include the algorithm identifier of the signature 
algorithm (which implicitly identifies the hash function) in two 
places.  One is outside the signature to aid in signature 
validation.  The second one is covered by the signature, and it must 
match the one on the outside.

Putting a list of hash functions in the certificate would be 
protected by the hash function that the CA employed in signing the 
certificate, which might be a better studied structure, but it just 
move the concern that you seem to be raising to the certificate 
instead of the signed data.

Russ

---

From: "Kemp, David P." <[email-masked]>
Date: Tue, 20 Nov 2007 17:26:02 -0500

Is there any reason to believe that DSA or ECDSA signatures
are more susceptible to hash downgrade attacks than
RSA-with-digest signatures?

And is there a reason such attacks are important?  It would
seem that a relying party should not accept algorithms that
it is not willing to accept. I.e., if the RP would accept a
DSA-with-SHA1 signature on message X, then why should the
RP not accept DSA-with-SHA1 signature on message Y?
(Assume X was signed with SHA1 and Y was signed with SHA2
but was attacked).  Putting restrictions on the cert used
to sign Y will have no effect on other messages.

In the logical end, if an RP is willing to accept signed
and unsigned messages, there is no way to prevent a
"downgrade" attack of stripping the signature entirely.

I don't see the value of using certificate contents to 
constrain and signal hash algorithms as opposed to the
established practice of using protocol and configuration
mechanisms.  The benefit of the latter is that algorithms
can be *upgraded* without reissuing the cert, i.e. users
who have been signing using SHA1 can also use SHA2.

-----Original Message-----
From: Eric Rescorla [mailto:[email-masked]] 
Sent: Tuesday, November 20, 2007 12:34 PM
To: Stefan Santesson
Cc: [email-masked]; Manger,James H; [email-masked]
Subject: Re: [TLS] DSA/SHA-1, and OIDs

-Ekr

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 20 Nov 2007 14:55:02 -0800

Russ,

But, assuming the trust anchor (self-signed certificate) contains the
hashing algorithm you trust (just like the public key) and the
certificates in the path have the hash extension, certification path
does provide that transitive trust.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of Russ Housley
Sent: Tuesday, November 20, 2007 10:42 AM
To: Eric Rescorla
Cc: [email-masked]; [email-masked]
Subject: Re: [TLS] DSA/SHA-1, and OIDs

Eric:

Russ

---

From: Stefan Santesson <[email-masked]>
Date: Wed, 21 Nov 2007 12:47:58 +0000

This is not the place to request it, but I really think we should bring this up in a common meeting like the saag, because it is a general problem that is relevant cross protocols.

Trying to solve downgrade problems by stuffing  hash limitations in the certificate worries me, feels like the easy way out for the protocol designers and principally wrong.
As pointed out, it makes management of hash selection a lot harder and a slow moving target as it requires certificate issuance to match the hash policy.

As a basic principle I think the major effort to transition to better hashes is to upgrade the capability of communicating hosts before the lowest grade of hash used becomes a realistic security issue. As a secondary solution protocols could be amended to protect against downgrading, as with S/MIME and as a last resort enhance the certificates.

Is there any studies out there showing that this is a real security issue (has any realistic chance of being exploited) or are we simply chasing a ghost far away from the scene of real internet crime?

Stefan Santesson
Senior Program Manager

> Sent: den 20 november 2007 18:34
> To: Stefan Santesson
> Cc: Manger, James H; [email-masked]; [email-masked]

---

From: max pritikin <[email-masked]>
Date: Wed, 21 Nov 2007 08:34:19 -0600

I too feel that placing protocol hints in the certificate is a bad  
way to go.

	- max

On Nov 21, 2007, at 6:47 AM, Stefan Santesson wrote:

>
> This is not the place to request it, but I really think we should  
> bring this up in a common meeting like the saag, because it is a  
> general problem that is relevant cross protocols.
>
> Trying to solve downgrade problems by stuffing  hash limitations in  
> the certificate worries me, feels like the easy way out for the  
> protocol designers and principally wrong.
> As pointed out, it makes management of hash selection a lot harder  
> and a slow moving target as it requires certificate issuance to  
> match the hash policy.
>
> As a basic principle I think the major effort to transition to  
> better hashes is to upgrade the capability of communicating hosts  
> before the lowest grade of hash used becomes a realistic security  
> issue. As a secondary solution protocols could be amended to  
> protect against downgrading, as with S/MIME and as a last resort  
> enhance the certificates.
>
> Is there any studies out there showing that this is a real security  
> issue (has any realistic chance of being exploited) or are we  
> simply chasing a ghost far away from the scene of real internet crime?
>
>
>
> Stefan Santesson
> Senior Program Manager

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 21 Nov 2007 06:57:49 -0800

At Wed, 21 Nov 2007 12:47:58 +0000,
> protocol designers and principally wrong.

I don't know what you mean by "the easy way out". TLS, for
instance, has extensive anti-downgrade provisions. But this
particular one cannot go in the protocol, because it's
fundamentally tied to the signing key. [The exception here
is to make an explicit tie to key length, i.e., keys of 
length X need SHA-1. I'll note that this is what FIPS 186-3
already does but it's notmandatory.]

> and a slow moving target as it requires certificate issuance to

I don't see this. What I would expect would simply be that
certificates would be issued with digest algorithms that
match the FIPS 186-3 recommendations. 

> issue.

This isn't about turning on new hashes, it's about allowing
old ones to be used once the new ones are turned on during
the transition period.

> As a secondary solution protocols could be amended to protect
> against downgrading, as with S/MIME and as a last resort enhance the
> certificates.

We're talking about two different kinds of downgrade here.
The S/MIME anti-downgrade issue is about signature stripping
when multiple signatures are applied. The downgrade issue
I'm concerned about is straight-line forgery: Alice always
signs with digest algorithm H1: she then generates a signature
over some message M where H1(M) = X. The attacker compromises H2
and forms M' st. H2(M2) = X. He can then craft a new message
apparently signed by Alice. There's no act that Alice can take
involving H1 and her signature algorithm that can prevent this:
it has to be in information available to a verifier who has only
the cert and a candidate signature.

> issue (has any realistic chance of being exploited) or are we simply
> chasing a ghost far away from the scene of real internet crime?

Is this the current PKIX standard for work items?

-Ekr

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 21 Nov 2007 08:50:33 -0800

>the cert and a candidate signature.

The proposed solution of an extension that says which hash functions 
can be used with the public key in a cert has a few flaws. First, it 
means that all CAs must understand the safety of all the hash 
algorithms out there to know to not list H2. In some sense, they must 
all predict the future as well, because they might list H2 today and 
then next year find out that some set of Mallorys have compromised 
it. Further, this puts CAs into the position of saying what can and 
cannot be done with a public key; "key usage" has proven this to be a 
disaster.

Instead, we have to assume that all relying parties need to know 
which of the hash algorithms that they know how to use are 
trustworthy, and which aren't. Hopefully, for any that are not, the 
relying party simply forgets how to use it, or marks it as poisoned.

--Paul Hoffman, Director
--VPN Consortium

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 21 Nov 2007 08:52:57 -0800

At Wed, 21 Nov 2007 08:50:33 -0800,
Paul Hoffman wrote:
> algorithms out there to know to not list H2.

Not really, no. As I said, I think this is pretty much an issue
of matching SHA variant to DSA key size. I agree that this is
imperfect, but the situation is imperfect.

> In some sense, they must 

This strikes me as a pretty different case.

> relying party simply forgets how to use it, or marks it as poisoned.

This seems highly undesirable from the perspective of the
verifying party, who has opinions about what digests he
will use, but who needs the relying party to enforce it.

-Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 21 Nov 2007 10:03:59 -0800

At Wed, 21 Nov 2007 11:26:53 -0600,
max pritikin wrote:
> Placing usage instructions in the certificate does not enforce the  
> verifying parties behavior any more than protocol handshakes would.   

It's not a matter of enforcement than information.
Again, there's no way to do this in the protocol handshake
because it needs to be authenticated by a separate mechanism.

> Paul's  
> example of key usage seems to be very topical.
> 
> Long lived device certificates would suffer from this approach. The  
> certificates on these devices (cable modems, wimax, IEEE 802.1AR, etc  
> etc etc) are profiled and baked well in advance. Attempting to expand  
> those profiles to limit the use of the credentials to particular hash  
> algorithms would be problematic.

No more than limiting them to particular signature algorithms,
which is baked into the certificate right now. In fact, I'd
observe that current DSA certificates are effectively
restricted to SHA-1 right now in that there is no DSS for 
DSA with other digests.

-Ekr

---

From: Stephen Kent <[email-masked]>
Date: Wed, 21 Nov 2007 14:53:49 -0500

At 6:57 AM -0800 11/21/07, Eric Rescorla wrote:

>...

Two observations:

PKIX does take into account the viability of attacks when deciding 
how to address newly discovered vulnerabilities.  So, for example, we 
noted that a CA could assign non-predictable cert serial numbers as a 
countermeasure to the first published hash attacks, which rely on the 
attacker being able to know/control the prefix of a signed object 
such as a cert submitted in a cert request.

Several of the recent messages refer to problem of using the right 
hash algorithm with a given signature algorithm and key size.  PKIX 
will certainly address this problem in the context of our data 
objects, e.g., certs. It is less clear whether PKIX should advocate 
carriage of additional data in certs to assist other protocols in 
this area. One could define suitable conventions for hash alg and 
signature alg/key size in the context of each protocol, for example.

That doesn't mean we ought not consider an extension for carrying 
this info, but as several there  folks have pointed out, this 
approach has problems too:

	- a CA may not want to assume liability for putting this info 
into a cert

	- a cert lifetime many not match the time frame for 
expressing new algorithm pairing info

	- an application/protocol or a CAPI may not have ready access 
to a private extension used  to convey this info

We have to proceed cautiously here. I am not (yet) ruling out an 
extension to carry such info, if these issue can be addressed.

Steve

---

From: max pritikin <[email-masked]>
Date: Wed, 21 Nov 2007 11:26:53 -0600

Placing usage instructions in the certificate does not enforce the  
verifying parties behavior any more than protocol handshakes would.   
Also it maybe more difficult if the certificate verification  
operations are distinct from the protocol hashing operations. Paul's  
example of key usage seems to be very topical.

- max

---

From: "Manger, James H" <[email-masked]>
Date: Thu, 22 Nov 2007 12:21:53 +1100

I agree with Ekr.
RFC 4055 “Additional RSA Algorithms and Identifiers”
§8 “Security Considerations” describes the reasons for binding
a public key to a signature algorithm. It talks about RSA keys,
but the logic also applies to DSA keys -- in fact to any crypto key.

“Generally, good cryptographic practice employs a given RSA key pair
in only one scheme.  This practice avoids the risk that vulnerability
in one scheme may compromise the security of the other, and may be
essential to maintain provable security.  While PKCS #1 Version 1.5
[P1v1.5] has been employed for both key transport and digital
signature without any known bad interactions, such a combined use of
an RSA key pair is not recommended in the future.  Therefore, an RSA
key pair used for RSASSA-PSS signature generation should not be used
for other purposes.  For similar reasons, one RSA key pair should
always be used with the same RSASSA-PSS parameters (except possibly
for the salt length).  Likewise, an RSA key pair used for RSAES-OAEP
key transport should not be used for other purposes.  For similar
reasons, one RSA key pair should always be used with the same RSAES-
OAEP parameters.”

There actually have been “known bad interactions” with PKCS #1 v1.5.
The “million-message attack” against PKCS #1 v1.5 block-type 2 encryption
in SSL can be used to create a PKCS #1 v1.5 block-type 1 signature.
A certificate binding the SSL server’s public encryption key to a
specific encryption algorithm would prevent the forged signature from
being accepted.
In this case, a (critical) key usage extension would also suffice.

In practise, the benefits of being able to use a single key (for
signing and decrypting email, for acting as a TLS server and client,
for signing XML and authenticating in TLS) often far outweigh the
risk of bad interactions. That is, the risk that an operation in one
context being misinterpreted as an operation in a different context.
“Often” “in practise” is not “always” “for all users” “in all circumstances”.

Key usage (1), key purpose (2) and signature/encryption/transport
algorithm (3) are really three points on a continuum
for giving the certificate holder control over where the
key->name binding (which is the core of their certificate) will be used.
There is no theoretical reason to support controls 1 & 2, but not 3.

So we come down to practical objections:
* control 3 (eg over signature hash) will be used less than
  controls 1 & 2 (key usage & purpose) -- perhaps infrequently
  enough that it doesn’t warrant inclusion in a standard
  for Internet use;
* key usage has been a disaster (according to Paul Hoffman),
  implying that deprecating the existing controls would be
  better than adding another (though such deprecation would
  cause too big a storm to contemplate);
* messy/painful/awkward to implement given the common divide
  between crypto libraries, cert processing libraries and
  application logic (this area is not my forte, but that is
  the impression I remember from Stefan Santesson --
  though it may only concern the placement of the control
  in subjectPublicKeyInfo vs in an extension);
* existing public CAs don’t (that I have seen) allow certificate
  holders to arbitrarily specify the key usage or purposes they want
  (other than choosing a server or code signing cert) so
  they are unlikely to allow algorithms to be specified,
  which means any extension has little hope of widespread deployment;
* interoperability issues where a certificate holder wants
  one algorithm, but a relying party wants another
  (this is a clash of deliberate crypto choices (policy),
  not syntax details -- but the resulting frustration is similar).

My gut feel is that a new extension holding “algorithm identifier
matching rules” should be defined.
List hash:SHA-1 in the extension, mark it critical,
and pray that the other end understands.

----------

-Ekr

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 22 Nov 2007 12:53:33 +0100

> verifying parties behavior any more than protocol handshakes would.   

It does provide authenticated usage information to the verifying
parties, though.  Without such information, verifying parties cannot
tell if the observed usage in any given handshake should be considered
suspicious (and thus rejected) or is benign.

> algorithms would be problematic.

One the one hand, you wouldn't *have* to use such hash algorithm
constraints in long-lived certificates for which you consider it
problematic.

On the other hand, this is where it is particularly important to
specify such constraints.  (You don't really need hash constraints to
prevent SHA-1 use of your (EC)DSA key that is only meant to be used
with SHA-256: Except with tiny probability, none of the signatures
that you ever generate using SHA-256 could be interpreted as a
SHA-1-based signature, unless the (EC)DSA subgroup you are using is
too small.)

Consider the following scenario.  The SHA-3 competition is now open.
So one interesting business idea is to take the signature from any
certificate signed by some high-profile ECDSA or DSA root certificate
that is far away from expiring, and then to engineer a new hash
algorithm that appears sound and secure, except that it happens to
have a particularly interesting pre-image for the hash value from said
non-root certificate's signature: namely, a preimage that would
provide you with a certificate of your own with generous
basicConstraints, simply by reusing the previous signature coming from
the CA.  So you submit this hash function to the SHA-3 competition,
provide a reference implementation and hope that it ends up in relying
parties' software.  If this plan works out, suddenly you have become a
high-profile CA yourself -- even though in this particular example
none of the cryptographic algorithms involved would have to be
insecure in itself.

If your are ambitious about security, then to avoid hash algorithm
substitution attacks of any kind, generally you'd want to limit the
use of any given key beforehand if at all possible.  I don't agree
that long-lived certificates are a severe obstacle to this.  If you
want algorithm flexibility for everyday use, then you can introduce an
intermediate CA whose certificate is updated sufficiently often,
always specifying the appropriate algorithm to use, while the root CA
would continue to use the initially chosen hash algorithms for the few
certificates that it signs.  If there is ever a time where you want
to completely exchange the set of allowed algorithms, why not take the
extra step and exchange the long-lived certificate as well?

Bodo

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 23 Nov 2007 07:20:46 -0800

At 12:53 PM +0100 11/22/07, Bodo Moeller wrote:
>parties, though.

Um, so? It is "authenticated" to be from a party that is not the 
signer. In most situations, my CA doesn't have the slightest idea 
what I am doing, or want to be doing, with my public key.

>Without such information, verifying parties cannot

And with such information from my CA, they still have no idea.

>none of the cryptographic algorithms involved would have to be

Even if there were any "high-profile ECDSA or DSA root certificates", 
they would contain the signature algorithm, which includes the hash 
used, ecdsa-with-SHA1 or id-dsa-with-sha1, and that is covered by the 
signature itself. This is no different than RSA.

--Paul Hoffman, Director
--VPN Consortium

---

From: Jack Lloyd <[email-masked]>
Date: Fri, 23 Nov 2007 12:58:43 -0500

> intermediate CA whose certificate is updated sufficiently often,

The idea to "introduce an intermediate CA" seems to assume that either
your CA will issue you new certificates as needed (and I'm sure they
would be happy to do so, at $X00 per cert), or they will issue you a
CA cert that allows you to generate new certificates when you want to
(unlikely), or you form your own root CA (with all the many problems
that entails). Am I missing something about this approach?

-Jack

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 23 Nov 2007 19:53:30 +0100

> what I am doing, or want to be doing, with my public key.

Only if you haven't told the CA what you want to do, by using
ExtensionReq and the like.

Of course, if you can't trust a CA to achieve a sufficiently close
approximation of what you want it do to, then that CA is pretty much
worthless.  If a CA starts to put other people's keys in certificates
naming you as the subject, say, that's pretty bad; if it does not
follow your requests regarding relevant certificate options, then
that's pretty bad too.

> signature itself. This is no different than RSA.

Actually, it is different from RSA signatures.  PKCS #1 v1.5
RSA signatures do contain the hash used in unhashed form
(i.e. as a literal part of what you get when computing x^e mod n,
where x is the signature in question and e, n are the components
of the public key).  DSA and ECDSA signatures in a certificate, in
contrast, involve the algorithm identifer determining the hash
function only *as part of the hashed input*.  The literal
algorithm identifier does not affect the signature verification
calculation beyond providing part of the input to the hash function.

Bodo

---

From: Stefan Santesson <[email-masked]>
Date: Mon, 26 Nov 2007 12:27:23 +0000

Eric,

Help me to understand the real security threat here.

So you are concerned that someone can select a totally different hash algorithm than intended (H2), instead of using the intended hash algorithm (H1) where H1(M) =X and H2(M2) = X.
For this to work, the relying party needs to both implement and approve the use of H2 within its environment, or it would never believe that M2 matches X (assuming that H1(M2) <> X).

This is very different from any hash threats I've looked into. How likely is it, within the set of hash algorithms the relying party has agreed to use (as they are considered good enough), that 2 different hash algorithms produces the same output hash (with the same length) for 2 different meaningful messages?

What am I missing here?

Stefan Santesson
Senior Program Manager

> Sent: den 21 november 2007 15:58

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 26 Nov 2007 07:01:53 -0800

At Mon, 26 Nov 2007 12:27:23 +0000,
Stefan Santesson wrote:
> So you are concerned that someone can select a totally different
> hash algorithm than intended (H2), instead of using the intended
> hash algorithm (H1) where H1(M) =X and H2(M2) = X.  For this to
> work, the relying party needs to both implement and approve the use
> of H2 within its environment, or it would never believe that M2
> matches X (assuming that H1(M2) <> X).
> 
> This is very different from any hash threats I've looked into.

Really? It's pretty commonly discussed in the signature literature.
See: http://www.rsa.com/rsalabs/node.asp?id=2020
Also, it's the explicit reason why the OID is included in the
PKCS1 RSA signature.

> likely is it, within the set of hash algorithms the relying party
> has agreed to use (as they are considered good enough), that 2
> different hash algorithms produces the same output hash (with the
> same length) for 2 different meaningful messages?

The likelihood is pretty much that an attacker has a working
preimage attack on one accepted algorithm. The difficulty is
this: say we have an expensive preimage attack on SHA-1--expensive
enough that people don't delete it immediately, which I would say
is pretty consistent with people's models so far of how aggressive
they are about aging out algorithms. I note that TLS 1.1. still has
DES-CBC.

I get my first DSA certificate which we'll say is signed by SHA-256.
I never sign with SHA-1. Without some indicator in the certificate,
people can go around impersonating me as long as they can break
SHA-1 and there's nothing I can do about it. That seems not so
OK.

-Ekr

---

From: "Kemp, David P." <[email-masked]>
Date: Mon, 26 Nov 2007 13:36:45 -0500

-----Original Message-----
> From: Manger, James H [mailto:[email-masked]]
>

It is not really a continuum.  Key usage constrains the use
of a key to support confidentiality or integrity, which are
qualitatively different services, not just different thresholds
along a single dimension.  Confidentiality requires some
sort of relationship between sender and recipient (the sender
must know the public key of each recipient, and the sender
and recipients must share a common algorithm).  Integrity is
a broadcast mechanism where the sender may know nothing about
the universe of potential recipients - a data object is signed,
and some recipients will accept the signature algorithm while
others will not.  All recipients have access to the same data
but they make individual, potentially different, decisions
on what to do with it.

>From: Eric Rescorla

I do not agree.  Assume that a recipient accepts weak hash algorithms
for signatures, and that an attacker wishes to attack a signed object.
If a cert contains the proposed constraint, then the attacker can
just create a new cert without the constraint signed with the weak
algorithm.  The only way a certificate constraint would be useful
is if the relying party believed that algorithm X is not broken
(is acceptable) with respect to data signatures but is broken
(is not acceptable) wrt certificate signatures.  Why would any
rational RP believe that?

(Before saying that covering a certificate algorithm ID with a
weak signature prevents that algid from being modified, perform a
thought experiment assuming the recipient accepts a hypothetical
DSA-with-CRC32 signature algorithm.  If it is possible to compute
preimages, why would it not be possible to compute a preimage
containing the DSA-with-CRC32 algid?  Extending to MD5 and SHA1
is just a matter of required and available resources.)

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 26 Nov 2007 10:35:58 -0800

At Mon, 26 Nov 2007 13:36:45 -0500,
> rational RP believe that?

You seem to be making the implicit assumption that the RP
trusts a CA who signs certificates with a weak digest.
Why need that be the case?

-Ekr

---

From: "Kemp, David P." <[email-masked]>
Date: Mon, 26 Nov 2007 15:20:24 -0500

-----Original Message-----
> Why need that be the case?

It doesn't need to be the case.  However, if an RP has
an opinion about what is "weak", my assumption is that
the RP would trust neither a CA who signs certificates
with weak signatures nor another party who signs data with
weak signatures.

> It's pretty commonly discussed in the signature literature.
> Also, it's the explicit reason why the OID is included in
> the PKCS1 RSA signature.

Thanks for the pointer - very interesting.

Fundamentally, I disagree with Kaliski's premise:
  "Signer accepts the risk from its own choices [of acceptable
   algorithms], but needs some way to mitigate the risk due
   to the verifier's choices."

The premise is that the signer *has* some risk (faces some
negative consequences) as a result of a verifier choosing to
accept a weak signature.  If a signer signs an electronic
bank check, a forger receives the check, weakens the signature,
and increases the amount, and a bank accepts the forged
signature, my assumption is that the signer is not liable
because the bank accepted an algorithm that is against generally
accepted business practices.

If Paypal accepted certificates for user authentication over
TLS instead of passwords, I'd expect them to advertise "safe
because we use SHA-256" the same way they say "safe because
we use 128 bit SSL" today.  If community standards regarded
MD5 signatures to be the risk equivalent of 40 bit encryption,
I (as a signer) wouldn't expect to be held responsible if
Paypal accepted a forged MD5 signature as coming from me.

(This whole discussion has something of an angels-on-pinheads
flavor, given that even "weak" SHA-1 signatures are much
stronger than the typical user-selected password.  But I'll
suspend disbelief and assume that signatures are being used
in the first place.  Note that most of my email is signed, but
I turn off signatures for mail to IETF security-area WG
lists.  How Lewis Carroll is that?)

What is a scenario in which "Signer needs to mitigate risk
due to verifier accepting a weak signature"?

---

From: Stefan Santesson <[email-masked]>
Date: Fri, 30 Nov 2007 04:11:07 +0000

Eric,

> See: http://www.rsa.com/rsalabs/node.asp?id=2020

Yeah, really :)

Maybe I should be more clear. AFAIK In order to substitute a message in this way you would need to successfully do a preimage attack on the week hash algorithm. A marginal attack with bit flipping is not enough, is has to be a complete break so you can create a meaningful message substantially different from the original message and make that match a given signed hash value by including some nonce in a syntactically legal manner.

Nothing in the article I could find in my quick read tells me how to do that on any generally accepted hash algorithm, and as far as I know we should be pretty safe.
We start to move away from hash algorithms as soon as they show cracks against collision resistance. We should definitely have abandoned them before they are completely broken.

Or what have I missed?

Stefan Santesson
Senior Program Manager

> Sent: den 26 november 2007 16:02
> To: Stefan Santesson
> Cc: Eric Rescorla; [email-masked]; [email-masked]

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 30 Nov 2007 12:07:33 +0100

Eric,

> SHA-1 and there's nothing I can do about it. That seems not so

To me, this seems to be just one example of a general problem. If
certain services accept / deploy weak identification and
authentification methods, anybody can impersonate you there. This is
the case with ebay accounts and could also happen with CAs deploying
poor identification methods. Services / RP accepting MD4 based
signatures are just another example.

Of course, the hash function downgrade attack abuses a real
signature and at first sight, it may seem logical to call for
measures in the PKI to prevent that. But I can also understand PKIX
being reluctant about including extensions / attributes in
certificates (and hence, adding complexity and potential problems)
to counter an attack which are leveraged by third parties applying
poor security, and which can still occur on a different level.

Johannes Merkle