Subject: Re: [Cfrg] [saag] Further MD5 breaks: Creating a rogue CAcertificate

From: [email-masked] (Peter Gutmann)
Date: Fri, 02 Jan 2009 00:17:49 +1300

Mike <[email-masked]> writes:

>> We are simply not vigilant enough.  This issue has been on our plate
>> since 2004.
>>
>> SHA-1 is next and neither the client side vendors nor the big
>> Enterprises have pushed to move to SHA-256.
>
>There is a simple fix -- a CA can just reorder the extensions prior to
>issuing a certificate.

That's actually a nice fix, but unfortunately not universally applicable: for
some types of signed data (e.g. S/MIME attributes) the DER rules require
sorting the encoded extensions, so there's only one valid order for them (and
some applications actually check for this, so you have to do it or sig checks
will start failing).

Peter.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Santosh Chokhani" <[email-masked]>
Date: Thu, 1 Jan 2009 06:39:50 -0500

Also, for the actual attack, the ordering of extensions will not work as
long as the certificate size does not change.  If you look at the actual
attack, collision block in the real certificate is up to the SPKI.  The
extension values from the real certificate are simply copied in the
tumor of the rogue certificate.

Given the property that if H(M) = H (M') then H(M | X) = H (M' | X), the
attacker simply copies the extensions from actual certificate in the
tumor.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Peter Gutmann
Sent: Thursday, January 01, 2009 6:18 AM
To: [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [saag] [Cfrg] Further MD5 breaks: Creating a rogue
CAcertificate

>There is a simple fix -- a CA can just reorder the extensions prior to

That's actually a nice fix, but unfortunately not universally
applicable: for
some types of signed data (e.g. S/MIME attributes) the DER rules require
sorting the encoded extensions, so there's only one valid order for them
(and
some applications actually check for this, so you have to do it or sig
checks
will start failing).

Peter.
_______________________________________________
saag mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/saag
_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Ben Laurie <[email-masked]>
Date: Thu, 1 Jan 2009 15:06:17 +0000

> some applications actually check for this, so you have to do it or sig checks

Surely the whole point of DER is that there's only one correct way to
encode any particular certificate?

So, either extensions must be sorted, or changing their order changes
their meaning. Either way, nothing can be reordered.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Santosh Chokhani" <[email-masked]>
Date: Thu, 1 Jan 2009 10:14:49 -0500

Changing the order of extensions does not change their meaning.

Actually, a CA could put the extensions in random order for various
certificates.  The attack will still work if the certificate size does
not change.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Ben Laurie
Sent: Thursday, January 01, 2009 10:06 AM
To: Peter Gutmann
Cc: [email-masked]; [email-masked]; [email-masked];
[email-masked]; [email-masked]
Subject: Re: [Cfrg] [saag] Further MD5 breaks: Creating a rogue
CAcertificate

applicable: for
checks

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 01 Jan 2009 09:07:05 -0800

At Thu, 01 Jan 2009 07:51:38 -0800,
Mike wrote:
> 
> 
> Is there anything that could be added to RP software to reliably
> detect and thwart the use of a rogue CA certificate?  Or would
> any attempt to do that just cause too many problems?
> 
> Mike (who is writing "I am not a security expert" 100 times on
>        the chalkboard)

You could certainly add a check for this particular certificate
and any others you discovered. To the extent to which CAs no 
longer use MD5, this would likely quickly clean up the damage.
It's less clear that you could safely detect this kind of
cert in a generic way.

-Ekr

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 1 Jan 2009 09:20:00 -0800

>encode any particular certificate?

Not so "surely". The SEQUENCE for extensions does not say what order they should be in.

>their meaning. Either way, nothing can be reordered.

Wrong on both counts. Each extension has stand-alone semantics, and they can be in any order.

However, this is irrelevant for the MD5 break discussion, as is clearly shown in the paper.

--Paul Hoffman, Director
--VPN Consortium

---

From: Ben Laurie <[email-masked]>
Date: Thu, 01 Jan 2009 17:44:32 +0000

> Not so "surely". The SEQUENCE for extensions does not say what order they should be in.

That doesn't change the _point_ of DER. If extensions should have been
specified as a SET but are defined as a SEQUENCE, then they are broken
(technically).

> Wrong on both counts. Each extension has stand-alone semantics, and they can be in any order.

My point was about the correct use of DER. It seems extensions use it
incorrectly.

> However, this is irrelevant for the MD5 break discussion, as is clearly shown in the paper.

I am discussing the correct use of DER :-)

-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Ben Laurie <[email-masked]>
Date: Thu, 01 Jan 2009 19:39:54 +0000

Santosh Chokhani wrote:
> We must fix X.509 since it is not broken.

I am not suggesting that we should fix X.509, I am pointing out, in my
own roundabout way, that X.509 certs are supposed to have a canonical
form. But it seems they do not.

Makes me wonder why we go to all the effort of using a supposedly
canonical encoding that isn't? If we can only rely on the original bits
in the cert when checking the signature, why bother?

---

From: "Santosh Chokhani" <[email-masked]>
Date: Thu, 1 Jan 2009 14:48:40 -0500

I do not think canonical means only one way to represent.

Extensions have always been a SEQUENCE with their OID denoting what
extension is next and their syntax.

Actually, we find SET in the case of RDN problematic.

-----Original Message-----
From: Ben Laurie [mailto:[email-masked]] 
Sent: Thursday, January 01, 2009 2:40 PM
To: Santosh Chokhani
Cc: Paul Hoffman; [email-masked]; [email-masked]; [email-masked];
[email-masked]; [email-masked]
Subject: Re: [saag] [Cfrg] Further MD5 breaks: Creating a rogue
CAcertificate

---

From: "Santosh Chokhani" <[email-masked]>
Date: Thu, 1 Jan 2009 14:29:46 -0500

We must preserve MD5 since it is weak.

We must provide economic and political support to client side vendors
who refuse to implement SHA-256.  We must treat them with kid gloves and
work around them.

The world economy is in the tank.

People want to shoot each other.

I see a patent here that is not very random.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Ben Laurie
Sent: Thursday, January 01, 2009 12:45 PM
To: Paul Hoffman
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked];
[email-masked]
Subject: Re: [saag] [Cfrg] Further MD5 breaks: Creating a rogue
CAcertificate

---

From: Robert Moskowitz <[email-masked]>
Date: Fri, 2 Jan 2009 10:35:34 -0500

Peter Hesse wrote:
> Since MD5 is known bad and potentially dangerous at this point, I would
> suggest that the best client side action would be to fail to verify any
> signatures created using MD5.  This will break some things, especially if
> existing business processes are relying on a certificate signed with MD5.
> However, it is a fail-safe and would prevent a rogue CA certificate created
> in this fashion from being considered trustworthy.
>
> And to Santosh's point (and others), my earlier email about
> removing/replacing trust anchors was not because the self-signed
> certificates are signed using MD5; I agree the trust anchor public keys are
> protected using other mechanisms.  I am recommending that if CAs do nothing
> to prevent this kind of attack (non-random serial numbers, issue
> certificates signed with MD5, issue certificates in an automated,
> predictable fashion) that those CAs should be removed from trust lists
> because they are no longer acting in the interest of the relying party--they
> are an accomplice to the creation of these rogue certificates.
Peter,

This sounds great at an IETF mike, but out in the field how do you get 
all those millions of browsers to pull down a new trust list that will 
no longer include CA foobar?

Can't happen now, and the way things are going, ain't going to happen 
before 2026 either.

So what tool do we have to get compliance to best practices? The good 
old 5th estate, get out their and give bad press to foobar until they 
fix their behaviour or their business model collapses and they go out of 
business and can no longer issue potentially rogue certs.

We can talk and posture all we want in the IETF. We are rather good at 
that, IMNSHO. But this is perfect proof of our impact as such on the 
business model of companies that use our technology; they will do what 
is expedient, not what is Best Practices.

---

From: Paul Hoffman <[email-masked]>
Date: Sun, 4 Jan 2009 11:11:09 -0800

At 9:02 AM +0200 1/4/09, Yoav Nir wrote:
>Best we can do is to get the CAs to
>
>(1) not issue MD5 certs anymore and
>(2) randomize the serial number and/or
>(3) and a random fluff extension that people are talking about

Just to repeat it one more time: #3 does not prevent the published attack.

>But still, I don't see Microsoft removing a root CA because one of their sub-CAs is issuing non-compliant certificates.

It is hard to see Microsoft removing or adding CAs. If anyone knows of a public interface (mailing list, web site, whatever) for when this happens, by all means please the world know.

>And if Microsoft don't, nobody else will. The Firefox/Opera/Safari/Chrome people don't want any sites that "only work with Explorer".

At least with respect to Firefox, I think that statement is false.

--Paul Hoffman, Director
--VPN Consortium

---

From: Paul Hoffman <[email-masked]>
Date: Sun, 4 Jan 2009 12:40:10 -0800

At 10:23 PM +0200 1/4/09, Yoav Nir wrote:
>On Jan 4, 2009, at 9:11 PM, Paul Hoffman wrote:
>
>It does if the random fluff is inserted by the CA. The attack depends on their ability to predict the entire TBS part.

I may have misunderstood the paper, but I think that changes after the subjectPublicKeyInfo do not affect the attack.

>I managed to find a page with their policy on adding new root CAs. Nothing there about removing old root CAs.

I'm not talking about the policy: I'm talking about the actual trust anchors themselves.

>They've done quite a bit to render broken sites that were made for IE.

That is irrelevant for this thread. There are active discussions in the Firefox community about adding and removing trust anchors that are and are not already in the IE trust anchor pile.

>Also, I've updated today and all the "bad" CAs with MD5 signatures are still in the TAS.

As was pointed out to me earlier: it does not matter if the CA has its cert signed with MD5, only whether that CA *signs* with MD5. RapidSSL, for example, is still signed with MD5 but is now signing with SHA-1.

--Paul Hoffman, Director
--VPN Consortium

---

From: "Weger, B.M.M. de" <[email-masked]>
Date: Sun, 4 Jan 2009 23:02:36 +0100

Hi Paul,

> >It does if the random fluff is inserted by the CA. The 
> attack depends on their ability to predict the entire TBS part.
> 
> I may have misunderstood the paper, but I think that changes 
> after the subjectPublicKeyInfo do not affect the attack.

Almost correct. A random looking "collision block" has to be inserted
somewhere. We chose to insert it in the public key, as that seems
the most convenient. Somebody else may find another place where
it can be hidden (maybe in a "subject key identifier" field or something,
I don't know what would be feasible). Everything after the "collision
block" must be copied bitwise into the twin certificate, and must be
'harmless' there. If 'random fluff' is inserted by the CA after the
"collision block", this 'random fluff' can be copied into the twin 
certificate as well, retaining the collision property, and this
would indeed be irrelevant to our attack.

> As was pointed out to me earlier: it does not matter if the 
> CA has its cert signed with MD5, only whether that CA *signs* 
> with MD5. RapidSSL, for example, is still signed with MD5 but 
> is now signing with SHA-1.

Correct.

Grtz,
Benne de Weger

---

From: "Santosh Chokhani" <[email-masked]>
Date: Sun, 4 Jan 2009 17:34:21 -0500

I agree with Paul.

Unless the Length of TBD certificate as part of DER is made
unpredictable, any values on extensions just go in the tumor.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Paul Hoffman
Sent: Sunday, January 04, 2009 3:40 PM
To: Yoav Nir
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cfrg] [saag] Further MD5 breaks: Creating a rogue
CAcertificate

At 10:23 PM +0200 1/4/09, Yoav Nir wrote:
>It does if the random fluff is inserted by the CA. The attack depends
on their ability to predict the entire TBS part.

I may have misunderstood the paper, but I think that changes after the
subjectPublicKeyInfo do not affect the attack.

>>>But still, I don't see Microsoft removing a root CA because one of
their sub-CAs is issuing non-compliant certificates.
>>
>>It is hard to see Microsoft removing or adding CAs. If anyone knows of
a public interface (mailing list, web site, whatever) for when this
happens, by all means please the world know.
>
>I managed to find a page with their policy on adding new root CAs.
Nothing there about removing old root CAs.

I'm not talking about the policy: I'm talking about the actual trust
anchors themselves.

>>>And if Microsoft don't, nobody else will. The
Firefox/Opera/Safari/Chrome people don't want any sites that "only work
with Explorer".
>They've done quite a bit to render broken sites that were made for IE.

That is irrelevant for this thread. There are active discussions in the
Firefox community about adding and removing trust anchors that are and
are not already in the IE trust anchor pile.

>Also, I've updated today and all the "bad" CAs with MD5 signatures are
still in the TAS.

As was pointed out to me earlier: it does not matter if the CA has its
cert signed with MD5, only whether that CA *signs* with MD5. RapidSSL,
for example, is still signed with MD5 but is now signing with SHA-1.

--Paul Hoffman, Director
--VPN Consortium

---

From: Stephen Kent <[email-masked]>
Date: Mon, 5 Jan 2009 21:53:15 -0500

At 8:10 AM -0600 1/5/09, Timothy J. Miller wrote:
>Ben Laurie wrote:
>That was last month's major discussion on PKIX.  The upshot: there's 
>no canonical form other than what's in memory.
>
>-- Tim

Tim,

Your response is an oversimplification, in several respects.

Ben's comment was a bit ill-formed. It's not that certs in general do 
or do not have a canonical form, but whether a given cert has a 
canonical representation. If the cert has no extensions, then it 
does. If it has extensions, then since the top level extension syntax 
is a SEQUENCE, there the order of extensions in that sequence (when 
the cert was signed) is definitive. (if that syntax had called for a 
SET, then  DER encoding would impose an order at this level, so use 
of the SEQUENCE construct here make life a bit easier.)

The context in which there is some disagreement is whether an 
extension needs to be DER encoded below the next level, where it is 
defined as an OCTET string. If one stops at the OCTET string level, 
the  life is easy and an RP can always encode to DER upon receipt 
(since the base cert format IS known by all RPs and they are 
technically capable of encoding it in DER).

If one interprets X.509 to require DER for the lower levels of the 
structure of a cert extension, then a problem can arise. It was noted 
that a non-critical extension (which therefore ought not be rejected 
out of hand by an RP) might have a syntax unknown to an RP. Thus the 
RP needs to assume that what it received is DER encoded when 
computing the signature, as it has no way to recompute the DER.

Steve