Subject: Re: [saag] Further MD5 breaks: Creating a rogue CA certificate

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 30 Dec 2008 13:33:46 -0500

--On Tuesday, December 30, 2008 11:05:28 AM -0500 Russ Housley 
<[email-masked]> wrote:

> http://www.win.tue.nl/hashclash/rogue-ca/
>
> MD5 considered harmful today
> Creating a rogue CA certificate
>
> December 30, 2008
>
> Alexander Sotirov, Marc Stevens,
> Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de
> Weger
>
> We have identified a vulnerability in the Internet Public Key
> Infrastructure (PKI) used to issue digital certificates for secure
> websites. As a proof of concept we executed a practical attack scenario
> and successfully created a rogue Certification Authority (CA) certificate
> trusted by all common web browsers. This certificate allows us to
> impersonate any website on the Internet, including banking and e-commerce
> sites secured using the HTTPS protocol.
>
> Our attack takes advantage of a weakness in the MD5 cryptographic hash
> function that allows the construction of different messages with the same
> MD5 hash. This is known as an MD5 "collision". Previous work on MD5
> collisions between 2004 and 2007 showed that the use of this hash
> function in digital signatures can lead to theoretical attack scenarios.
> Our current work proves that at least one attack scenario can be
> exploited in practice, thus exposing the security infrastructure of the
> web to realistic threats.

This is a practical application of an approach that I remember being 
brought up during discussions about MD5 at a saag meeting some time ago.  I 
also recall someone mentioning at the time that many/most CA's were already 
issuing certificates with random rather than sequential serial numbers, 
which would have thwarted this particular attack.

-- Jeff

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 30 Dec 2008 12:23:11 -0800

At Tue, 30 Dec 2008 13:33:46 -0500,
> which would have thwarted this particular attack.

Yep. Would that they all were.

FWIW, here is my writeup of this issue, targeted towards a broader
community:

http://www.educatedguesswork.org/2008/12/understanding_the_sotirov_et_a.html

-Ekr

---

From: Russ Housley <[email-masked]>
Date: Tue, 30 Dec 2008 15:10:45 -0500

Jeff:

>brought up during discussions about MD5 at a saag meeting some time 
>ago.  I also recall someone mentioning at the time that many/most 
>CA's were already issuing certificates with random rather than 
>sequential serial numbers, which would have thwarted this particular attack.

RFC 5280 does not include this advice.  It is sound advice that was 
discussed in PKIX and other venues.  Perhaps a BCP is in order.

Russ

---

From: Paul Hoffman <[email-masked]>
Date: Tue, 30 Dec 2008 12:53:06 -0800

At 1:33 PM -0500 12/30/08, Jeffrey Hutzelman wrote:
>This is a practical application of an approach that I remember being brought up during discussions about MD5 at a saag meeting some time ago.  I also recall someone mentioning at the time that many/most CA's were already issuing certificates with random rather than sequential serial numbers, which would have thwarted this particular attack.

Your recollection may be off. I believe I was the person who brought up the serial number hack at the mic, and I'm pretty sure I said "some", not "many" (and certainly not "most"!). When I looked at a handful of popular CAs earlier this week, I only found a few who are using randomization in their serial numbers.

Regardless of that, the authors of the MD5 paper are correct: trust anchors signed with MD5 are highly questionable as of today (well, actually, since they published their last paper). Hopefully, the maintainers of the popular trust anchor repositories (Microsoft, Mozilla, etc.) will yank out the trust anchors signed with MD5 (and MD2!) as soon as possible.

At 3:10 PM -0500 12/30/08, Russ Housley wrote:
>RFC 5280 does not include this advice.  It is sound advice that was discussed in PKIX and other venues.  Perhaps a BCP is in order.

Man, that is really stretching the definition of "best".

For one, it is only needed in signatures that use known-attackable hash functions. A "best practice" in that case is to use a better hash function in the signature. Also, it relies on the ability of the software using the random number to be sure that the result is a positive integer in ASN.1, which seems overly optimistic.

If the IETF feels that adding randomization to signatures is important, we should define randomized signature functions. We could start with NIST Draft SP 800-106 (<http://csrc.nist.gov/publications/drafts/800-106/2nd-Draft_SP800-106_July2008.pdf>). However, I think that doing so is sending the wrong message: we should instead be encouraging the use of non-broken hash functions.

--Paul Hoffman, Director
--VPN Consortium

---

From: "RL 'Bob' Morgan" <[email-masked]>
Date: Tue, 30 Dec 2008 13:17:50 -0800 (PST)

> Regardless of that, the authors of the MD5 paper are correct: trust 
> anchors signed with MD5 are highly questionable as of today (well, 
> actually, since they published their last paper). Hopefully, the 
> maintainers of the popular trust anchor repositories (Microsoft, 
> Mozilla, etc.) will yank out the trust anchors signed with MD5 (and 
> MD2!) as soon as possible.

This is a different claim than "CAs should stop issuing certs with MD5 
signatures", which is what I as an amateur take away from a quick scan of 
the material.  Obviously MD5 is suspect in various ways, but does this new 
work lead to the conclusion that MD5-signed roots are untrustworthy today?
Replacing a root is a much bigger deal then changing signing practices.

  - RL "Bob"

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 30 Dec 2008 13:39:34 -0800

At Tue, 30 Dec 2008 12:53:06 -0800,
Paul Hoffman wrote:
> Your recollection may be off. I believe I was the person who brought
> up the serial number hack at the mic, and I'm pretty sure I said
> "some", not "many" (and certainly not "most"!). When I looked at a
> handful of popular CAs earlier this week, I only found a few who are
> using randomization in their serial numbers.

So it's in my deck from SAAG at IETF 62.

http://www.ietf.org/proceedings/05mar/slides/saag-3.pdf

I don't know whether many or most do it. IMO everyone should.

> For one, it is only needed in signatures that use known-attackable
> hash functions. A "best practice" in that case is to use a better
> hash function in the signature. Also, it relies on the ability of
> the software using the random number to be sure that the result is a
> positive integer in ASN.1, which seems overly optimistic.
> 
> If the IETF feels that adding randomization to signatures is
> important, we should define randomized signature functions. We could
> start with NIST Draft SP 800-106
> (<http://csrc.nist.gov/publications/drafts/800-106/2nd-Draft_SP800-106_July2008.pdf>). However,
> I think that doing so is sending the wrong message: we should
> instead be encouraging the use of non-broken hash functions.

I certainly agree we should be encouraging the use of non-broken hash
functions. However, randomizing the SN seems like very cheap backward
compatible insurance against the fact that that's going to take a long time. 

-Ekr

---

From: "Peter Hesse" <[email-masked]>
Date: Tue, 30 Dec 2008 16:39:34 -0500

Ceasing the issuance of certificates with MD5 used in the signature doesn't
solve the problem of the certificates that have already been issued and are
still out there, any number of which may be rogue.

Replacing, or marking as untrusted all root certificates which have any
current valid (i.e. non-expired, non-revoked) certificates with MD5 used in
the signature could have tremendous undesirable impact and be an untenable
solution.

The right tool for the job is a client-side solution to fail validation of
any signature which uses MD5, especially certificate signatures.  I will not
hold my breath for such a solution.

--Peter 

----------------------------------------------------------------
 Peter Hesse                       [email-masked]
 http://securitymusings.com         http://geminisecurity.com

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of RL 'Bob' Morgan
Sent: Tuesday, December 30, 2008 4:18 PM
To: Paul Hoffman
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: [saag] Further MD5 breaks: Creating a rogue CA certificate

  - RL "Bob"

---

From: Russ Housley <[email-masked]>
Date: Tue, 30 Dec 2008 16:33:19 -0500

Paul:

>(<http://csrc.nist.gov/publications/drafts/800-106/2nd-Draft_SP800-106_July2008.pdf>). 
>However, I think that doing so is sending the wrong message: we 
>should instead be encouraging the use of non-broken hash functions.

This is a very different thing than a BCP that the recommends that 
the certificate serial number include some random bits.

Russ

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 30 Dec 2008 17:01:12 -0500

--On Tuesday, December 30, 2008 01:39:34 PM -0800 Eric Rescorla 
<[email-masked]> wrote:

>> > ago.  I also recall someone mentioning at the time that many/most CA's
>> > were already issuing certificates with random rather than sequential
>> > serial numbers, which would have thwarted this particular attack.
>>

I just checked my records, and shortly after that IETF, our internal CA 
started issuing certificates with SHA-1 signatures and randomized serial 
numbers, as a direct result of that discussion.

>> positive integer in ASN.1, which seems overly optimistic.

On the contrary, IMHO best practice is to take every reasonable measure to 
reduce the likelyhood of an attack.  In my book, that means both using a 
better hash function _and_ using randomized serial numbers, since the 
latter clearly helps when the hash is broken, and hash functions may become 
broken over time, and before you realize it.

>> important, we should define randomized signature functions.

I think that's a very good idea.  However...

> compatible insurance against the fact that that's going to take a long

"what he said".

Incidentally, the recently reported problems with CBC mode ciphers in SSH 
have gotten me to thinking that in some situations, a single REQUIRED 
algorithm isn't enough, because if something goes wrong and you have to 
abandon that algorithm in a hurry, operators may be in a position of having 
to choose between seriously compromising either security or 
interoperability.

In the case of usages like certificates where no live negotiation is 
possible and implementations may have to interoperate over a long period of 
time, I believe additional care is necessary.  For example, I think it 
would be a good idea to define a composite signature function which uses 
more than one hash computed independently.  This would likely make some 
attacks harder, but more importantly, it means that as long as at least one 
of the underlying hashes is strong enough, the signature is still usable.

-- Jeff

---

From: "Timothy J. Miller" <[email-masked]>
Date: Tue, 30 Dec 2008 16:05:56 -0600

> I don't know whether many or most do it. IMO everyone should.

Randomizing serial numbers has implications for OCSP operations, 
particularly those that use presigned responses in order to optimize 
performance.

Why presign?  Because for a large network with varying levels of 
support, it may be easier to move around sets of pre-produced responses 
to distributed keyless OCSP responders than to guarantee connectivity to 
a keyed OCSP service.

Why presign batches rather than individual responses?  Because for a 
large PKI the response pre-production time can exceed the CRL update 
frequency.

-- Tim

---

From: Russ Housley <[email-masked]>
Date: Tue, 30 Dec 2008 17:12:02 -0500

>This is a different claim than "CAs should stop issuing certs with 
>MD5 signatures", which is what I as an amateur take away from a 
>quick scan of the material.  Obviously MD5 is suspect in various 
>ways, but does this new work lead to the conclusion that MD5-signed 
>roots are untrustworthy today?

We recommended a migration (walk, don't run) away from MD2, MD4, and 
SHA-1 toward SHA-256 a few years ago.  MD2 and MD4 generate 128 bit 
hash values; even without the attacks, these are getting to be too 
small.  SHA-1 has been shown to be weaker than its design goal, and 
the 160 bit hash value will be getting too short in a couple of 
years.  We recommended SHA-256 while fully recognizing that NIST was 
starting a hash competition, and that we might recommend the winner 
of that competition as the successor to SHA-256.

I still strongly encourage the migration to SHA-256.

The use of the random bits in the serial number are insurance against 
similar problems being found in other hash functions.  This insurance 
will hopefully provide time to migrate to another hash function when 
cryptanalysis begins to show flaws in any future hash function.

Russ

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 30 Dec 2008 14:34:59 -0800

At Tue, 30 Dec 2008 16:05:56 -0600,
Timothy J. Miller wrote:
> 
> [1  <text/plain; ISO-8859-1 (7bit)>]
> Eric Rescorla wrote:

I'm not sure I understand the issue here, but 
they don't actually have to be totally randomized. You could use a
PRF so they were predictable to the CA.

-Ekr

---

From: "Blake Ramsdell" <[email-masked]>
Date: Tue, 30 Dec 2008 14:23:42 -0800

> particularly those that use presigned responses in order to optimize

It seems that the disruption caused by modifying serial number
generation for existing CAs is pretty high. Would an easier solution
be to either a) make the validity period vary slightly (in the
documented attack, the notBefore was always a fixed interval from the
submission time, and making this vary in a period of just a few
minutes would have thwarted it, if I'm understanding correctly), or b)
the CA sticks some random junk in the subject DN (not an MPEG of a
cat, but maybe OU=sf9fj3 [some base64 PRNG data]).

Blake
-- 
Blake Ramsdell | http://www.blakeramsdell.com

---

From: Scott Rea <[email-masked]>
Date: Tue, 30 Dec 2008 17:30:14 -0500

Russ Housley wrote:
>> MD5 signatures", which is what I as an amateur take away from a quick 
>> scan of the material.  Obviously MD5 is suspect in various ways, but 
>> does this new work lead to the conclusion that MD5-signed roots are 
>> untrustworthy today?
>
> starting a hash competition, and that we might recommend the winner of 
> that competition as the successor to SHA-256.
>

But one of the things that has kept the brakes on migration has been 
support in clients for SHA256 - the largest vendor of client machines 
only just recently added SHA256 to its XP platform (if you upgrade to 
SP3). I keep running into folks using OpenSSL as their crypto base and 
they haven't updated to a distribution that supports SHA256. I think it 
will take a little more time before it becomes the default...

-- 
Scott Rea

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 30 Dec 2008 14:54:53 -0800

Here's Tim Callan from VEriSign posting about this:

https://blogs.verisign.com/ssl-blog/2008/12/on_md5_vulnerabilities_and_mit.php

-Ekr
y

---

From: Yoav Nir <[email-masked]>
Date: Wed, 31 Dec 2008 00:02:07 +0200

> Replacing a root is a much bigger deal then changing signing  

CAs should have stopped issuing certs with MD5 signatures 4 years ago,  
when the first practical attacks on MD5 were published.

Now it would be more correct to say that "relying parties should treat  
as invalid any certificate chain that contains an MD5 (or MD2, MD4)  
signature"

Since in the HTTPS context the relying parties are the browsers, it  
falls to the vendors (if Microsoft leads, everyone will follow) to, as  
Paul said, yank the trust anchors.

It should be noted, though, that yanking the trust anchors is not  
enough. You really should change the relying party to not recognize  
this algorithm. Otherwise, it's perfectly valid for a CA whose  
certificate is signed with SHA1 to sign an intermediate CA certificate  
with MD5 (although they usually don't do that, I hope)

Email secured by Check Point

---

From: Nicolas Williams <[email-masked]>
Date: Tue, 30 Dec 2008 16:36:12 -0600

> to choose between seriously compromising either security or 

+1

But note that in the case of the SSH CBC mode ciphers the vulnerable
ciphers had only the cipher mode in common.  The SSH vulnerability, in
any case, doesn't stem from the use of CBC, but is more general, and
well could have been worse, but let's ignore that for this argument.

So in the SSH case one would have liked to have seen two or more
REQUIRED to implement ciphers with very distinct properties.  Say
3DES in CBC mode, AES in counter mode, and arcfour.

Applying a principle of redundancy in RTI algorithms to symmetric key
protocols is fairly simple.  Applying such a principle to PKI seems
rather more difficult -- it's not just hash algorithms, but pk
algorithms too.  Your example was to require not just the implementation
of multiple hash (but not pk) algorithms, but to require the *use* of
those.  That makes sense to me, but it's not quite the same principle
being applied to PKI as to SSH.

Nico
--

---

From: Russ Housley <[email-masked]>
Date: Tue, 30 Dec 2008 17:23:33 -0500

>PRF so they were predictable to the CA.

That works.  This works too: the serial number could be composed of 
two parts, where the most significant bits are a counter and the 
least significant bits are randomly generated.

Russ

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 30 Dec 2008 18:26:04 -0500

As mentioned, self-signed roots have their own problems and hash is not
one of them.  They need other means to protect since signatures on them
are useless.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]

This is a different claim than "CAs should stop issuing certs with MD5 
signatures", which is what I as an amateur take away from a quick scan
of 
the material.  Obviously MD5 is suspect in various ways, but does this
new 
work lead to the conclusion that MD5-signed roots are untrustworthy
today?
Replacing a root is a much bigger deal then changing signing practices.

  - RL "Bob"

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 30 Dec 2008 18:28:07 -0500

Peter,

Roots need not be replaced since they need protected migration and
storage.

Since the attack is computing pre-image, I suspect that past MD5
certificates are safe until the attack was devised.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of Peter Hesse
Sent: Tuesday, December 30, 2008 4:40 PM
To: 'RL 'Bob' Morgan'; 'Paul Hoffman'
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: RE: [saag] Further MD5 breaks: Creating a rogue CA certificate

Ceasing the issuance of certificates with MD5 used in the signature
doesn't
solve the problem of the certificates that have already been issued and
are
still out there, any number of which may be rogue.

Replacing, or marking as untrusted all root certificates which have any
current valid (i.e. non-expired, non-revoked) certificates with MD5 used
in
the signature could have tremendous undesirable impact and be an
untenable
solution.

The right tool for the job is a client-side solution to fail validation
of
any signature which uses MD5, especially certificate signatures.  I will
not
hold my breath for such a solution.

--Peter 

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]
On Behalf Of RL 'Bob' Morgan
Sent: Tuesday, December 30, 2008 4:18 PM
To: Paul Hoffman
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: [saag] Further MD5 breaks: Creating a rogue CA certificate

  - RL "Bob"

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 30 Dec 2008 18:30:13 -0500

Let us leave the trust anchors alone.  Your challenge of protecting
trust anchors does not change even if you use SHA 512 or next generation
hash function yet to be determined.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Yoav Nir
Sent: Tuesday, December 30, 2008 5:02 PM
To: RL 'Bob' Morgan
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: [saag] Further MD5 breaks: Creating a rogue CA certificate

Email secured by Check Point
_______________________________________________
saag mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/saag

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 30 Dec 2008 18:14:55 -0500

> being applied to PKI as to SSH.

Correct.  I'm suggesting that in the case of PKI, merely having two RTI 
algorithms wouldn't be sufficient; at least for long-term certificates you 
need to actually sign using two algorithms in order to get the 
interoperability benefit.  Validating using both isn't necessary, though it 
does have a benefit, in that no code or configuration changes are required 
to continue to be safe as long as at least one is good enough.

IMHO, one of the biggest problems in the current PKI standards is that 
there is no ability to future-proof certificates by generating signatures 
with multiple algorithms.  The result is that you can't start signing with 
a new algorithm until everyone understands it, and you can't stop accepting 
an old algorithm without either reissuing lots of certificates with a new 
one or waiting for them to expire.  This means movement is very slow and we 
are unable to abandon a broken algorithm in a hurry.  The former is poor; 
the latter is a disaster waiting to happen.

-- Jeff

---

From: "Santosh Chokhani" <[email-masked]>
Date: Tue, 30 Dec 2008 18:23:15 -0500

Paul,

I disagree in the matter of trust anchors, assuming you mean self-signed
ones.

Signatures on Trust anchors are inherently useless from security
viewpoint.  Thus, they could be signed using even MD4.

Their security relies on protecting them from unauthorized modification.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Paul Hoffman
Sent: Tuesday, December 30, 2008 3:53 PM
To: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cfrg] [saag] Further MD5 breaks: Creating a rogue
CAcertificate

>This is a practical application of an approach that I remember being
brought up during discussions about MD5 at a saag meeting some time ago.
I also recall someone mentioning at the time that many/most CA's were
already issuing certificates with random rather than sequential serial
numbers, which would have thwarted this particular attack.

Your recollection may be off. I believe I was the person who brought up
the serial number hack at the mic, and I'm pretty sure I said "some",
not "many" (and certainly not "most"!). When I looked at a handful of
popular CAs earlier this week, I only found a few who are using
randomization in their serial numbers.

For one, it is only needed in signatures that use known-attackable hash
functions. A "best practice" in that case is to use a better hash
function in the signature. Also, it relies on the ability of the
software using the random number to be sure that the result is a
positive integer in ASN.1, which seems overly optimistic.

If the IETF feels that adding randomization to signatures is important,
we should define randomized signature functions. We could start with
NIST Draft SP 800-106
(<http://csrc.nist.gov/publications/drafts/800-106/2nd-Draft_SP800-106_J
uly2008.pdf>). However, I think that doing so is sending the wrong
message: we should instead be encouraging the use of non-broken hash
functions.

--Paul Hoffman, Director
--VPN Consortium
_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Hugo Krawczyk" <[email-masked]>
Date: Tue, 30 Dec 2008 18:40:36 -0500

Paul, Eric and everyone else,

Paul said

    > (<
http://csrc.nist.gov/publications/drafts/800-106/2nd-Draft_SP800-106_July2008.pdf>).
However,
    > instead be encouraging the use of non-broken hash functions.

and Eric responded

   >  compatible insurance against the fact that that's going to take a long
time.

I believe that the best answer to the above arguments regarding the use of
randomized hashing vs. the "patch" of using random SNs is given by Sotirov
et
al, the cryptanalysts that carried out the remarkable MD5-certificate attack
(see their website). They say:

  *We do note however that this use of randomness in the serial number is a
  workaround, made possible by lucky choices in the X.509 standard. It is
not a
  bad idea in general to add randomness to a hash input when a possible
attacker
  is able to choose the input. A much more reliable, since designed,
solution is
  to use randomized hashing, see [HK]. Such a solution introduces
randomization
  as a "mode of operation" for hash functions, which is a much more
fundamental
  approach to the problem than relying on features that happen to be present
in
  existing standards for non-security reasons, or for no reason at all.*

> instead be encouraging the use of non-broken hash functions.

The two things are not exclusive. We should do BOTH:
Adopt a randomized hashing technique (as a mode of operation for hash
functions) and continue our quest for better hash functions.

We must aim at the best possible hash function, but we cannot guarantee its
security in the long term. As stated in the above text by Sotirov et al,
randomized hashing is a more fundamental (I would call it "infrastructural")
approach. It strengthens digital signatures with any hash function and for
any
digital signature application, not just certificates.

Let's take the example of HMAC: Its development in mid-90's was motivated to
a
large extent by the weaknesses found in MD5 by Dobbertin and others.
If we took the approach of "let's use a better hash function" we should have
adopted the key-append method
  MAC(K,X) = SHA1(X||K)
which used SHA1 for which there was ample belief that it was a very good
collision resistant hash function.  However, had we done that, we would now
have a broken MAC since the above design breaks with collisions on the
underlying hash function.

I believe that the responsible course of action for the IETF and
particularly
SAAG is to adopt the standardization process started by NIST with
http://csrc.nist.gov/publications/drafts/800-106/2nd-Draft_SP800-106_July2008.pdf
and create a deployment path that could accommodate a randomized hashing
approach as a mode of operation. This includes the consideration of
randomized
hashing in protocol changes and new protocol design that support algorithm
agility.

No one in the world will think that by doing that we should keep using MD5,
or not pay attention to NIST's hash competition, or should stop from moving
to
SHA2.

The just-published attack indicates that it is time that we take seriously
our
digital signatures, and randomized hashing is the best long-term insurance
we know against future collision vulnerabilities.

You can find more details on the specific randomized hashing approach behind
NIST's document in http://www.ee.technion.ac.il/~hugo/rhash/
In particular, some of the documents in that site provide some guidance
regarding implementation and deployment issues (it also includes a
now-expired
internet draft).

Hugo

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 30 Dec 2008 18:45:45 -0500

> certificates are safe until the attack was devised.

The attack does _not_ involve computing a preimage; it involves computing a 
colliding pair one of which has a prefix which is predictable but not 
controllable, followed by a controllable component consisting of some 
minimum number of bits followed by at least three aligned message blocks. 
What makes existing certificates safe is that there are no known preimage 
attacks against MD5, couple with limitations of the technique used to 
construct the colliding pair.

However, there is a limit to how "safe" existing certificates are, because 
the attack does not require anything that was not known 3-4 years ago.  The 
only change is that with the latest techniques for computing collisions, it 
is possible to do so in a short enough time to be able to predict the 
validity and serial number that will be used by the issuer with fairly high 
probability.

-- Jeff

---

From: [email-masked] (Peter Gutmann)
Date: Wed, 31 Dec 2008 14:20:39 +1300

>the signature could have tremendous undesirable impact and be an untenable

I hate to be the one to point to the elephant in the room (well OK, I don't
hate it, it's rather fun actually) but you need to keep this in perspective:
one in ten AuthentiCode-signed Windows binaries is malware, and cybercrooks
have no problems at all obtaining certs from commercial CAs using stolen
identities and credentials for pretty much any use they want.  The current MD5
attack is very cool but there's no need to worry about bad guys doing much
with it because it's much, much easier to get legitimate CA-issued certs the
normal way, you buy them just like everyone else does (except that you use
someone else's credit card and identity, obviously).

In other words, if this problem is fixed, would anyone other than security
geeks even notice?  I doubt the crooks will.

Peter.

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 31 Dec 2008 03:07:26 -0500

One would think we want to start using SHA-1 or even SHA256 (assuming
client vendors implement SHA256 ASAP) and ask the CAs emanating from
commercial roots to perform responsible I&A before issuing certificates.

It will also help if the client side certificate policy processing
became more of a norm.

But, all of this is probably expecting too much.  My fear is that
expecting any of this is also too much.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Peter Gutmann
Sent: Tuesday, December 30, 2008 8:21 PM
To: [email-masked]; [email-masked];
[email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cfrg] [saag] Further MD5 breaks: Creating a rogue
CAcertificate

doesn't
are
untenable
>solution.

I hate to be the one to point to the elephant in the room (well OK, I
don't
hate it, it's rather fun actually) but you need to keep this in
perspective:
one in ten AuthentiCode-signed Windows binaries is malware, and
cybercrooks
have no problems at all obtaining certs from commercial CAs using stolen
identities and credentials for pretty much any use they want.  The
current MD5
attack is very cool but there's no need to worry about bad guys doing
much
with it because it's much, much easier to get legitimate CA-issued certs
the
normal way, you buy them just like everyone else does (except that you
use
someone else's credit card and identity, obviously).

In other words, if this problem is fixed, would anyone other than
security
geeks even notice?  I doubt the crooks will.

Peter.

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 31 Dec 2008 07:05:05 -0800

At Wed, 31 Dec 2008 14:20:39 +1300,
> geeks even notice?  I doubt the crooks will.

Well, if we're going to be pointing ot the obvious, then code signing actually
seems kind of off-point as well. > 50% of IE users are not running up-to-date
copies of their browser.[0] In many cases this means that the browsers have
remote exploits. Why worry about AuthentiCode?

-Ekr

[0] http://www.techzoom.net/publications/insecurity-iceberg/index.en

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 31 Dec 2008 10:04:40 -0500

Mini CRL are not a standard.

That said, using implementators agreement (based on whether high order
to low order bits are true serial number) one bit per certificate can be
assigned and the random prefix or appendage to the serial number
ignored.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of Timothy J. Miller
Sent: Wednesday, December 31, 2008 9:43 AM
To: Russ Housley
Cc: Eric Rescorla; [email-masked]; [email-masked]; [email-masked];
[email-masked]
Subject: Re: Further MD5 breaks: Creating a rogue CA certificate

> least significant bits are randomly generated.

How would Corestreet's miniCRL format fare under this?

-- Tim

---

From: "Timothy J. Miller" <[email-masked]>
Date: Wed, 31 Dec 2008 09:18:00 -0600

> commercial roots to perform responsible I&A before issuing certificates.

Speaking of I&A, I found it interesting to note that the CA/Browser 
forum guidelines for EV certs allows (but recommends against) MD5 until 
2010.

The spot check of EV issuers I did yesterday didn't turn up anyone 
actually using MD5, but I didn't have all of 'em available.

-- Tim

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 31 Dec 2008 10:21:12 -0500

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.

-----Original Message-----
From: Timothy J. Miller [mailto:[email-masked]] 
Sent: Wednesday, December 31, 2008 10:18 AM
To: Santosh Chokhani
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cfrg] [saag] Further MD5 breaks: Creating a rogue
CAcertificate

-- Tim

---

From: "Timothy J. Miller" <[email-masked]>
Date: Wed, 31 Dec 2008 08:42:56 -0600

-- Tim

---

From: "Tim Moses" <[email-masked]>
Date: Wed, 31 Dec 2008 10:36:56 -0500

Colleagues - It has been confirmed that no EV issuer is signing certificates with MD5.  Also, EV certificates cannot be issued by an automated process, putting another obstacle in the path of an attacker.  All the best.  Tim.

Tim Moses
+1 613 270 3183

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Timothy J. Miller
Sent: Wednesday, December 31, 2008 10:18 AM
To: Santosh Chokhani
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cfrg] [saag] Further MD5 breaks: Creating a rogue CAcertificate

> commercial roots to perform responsible I&A before issuing certificates.

Speaking of I&A, I found it interesting to note that the CA/Browser forum guidelines for EV certs allows (but recommends against) MD5 until 2010.

The spot check of EV issuers I did yesterday didn't turn up anyone actually using MD5, but I didn't have all of 'em available.

-- Tim

---

From: Mike <[email-masked]>
Date: Wed, 31 Dec 2008 09:03:37 -0800

> 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.

Mike

---

From: Mike <[email-masked]>
Date: Wed, 31 Dec 2008 09:49:45 -0800

I sent my last message a bit too hastily.  Other ideas that I was
contemplating should have been mentioned including:

   - remove any unrecognized extensions
   - remove tumors

Those could potentially cause problems if for some reason they were
actually needed.  This one, though, shouldn't cause trouble:

   - add a private EKU with a random number (or two) in the OID

That would not mess up the serial number scheme in use or modify the
subject name as has been suggested.

Mike

---

From: Dr Stephen Henson <[email-masked]>
Date: Wed, 31 Dec 2008 18:11:35 +0000

> subject name as has been suggested.

Or add a non-critical extension with some randomness in it...

Steve.
-- 
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.co.uk/
Email: [email-masked], PGP key: via homepage.

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 31 Dec 2008 13:03:13 -0500

Private EKU could cause problems if EKU is not otherwise present in the
certificate.

The certificate may not be usable for intended purpose.  Not all clients
may recognize "any key purpose" as intended by 5280.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of Mike
Sent: Wednesday, December 31, 2008 12:50 PM
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cfrg] [saag] Further MD5 breaks: Creating a rogue
CAcertificate

Mike

---

From: "Timothy J. Miller" <[email-masked]>
Date: Wed, 31 Dec 2008 12:30:13 -0600

> Or add a non-critical extension with some randomness in it...

Do you want to propose id-ce-magicCookie OBJECT IDENTIFIER  ::=  {id-ce 
55} or should I?  :)

-- Tim

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 31 Dec 2008 13:23:49 -0500

I am a bit concerned about random goo when random goo is one of the
things the attacker uses to cause collision.  This may limit human or
machine's ability to discern mischief.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of Dr Stephen Henson
Sent: Wednesday, December 31, 2008 1:12 PM
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cfrg] [saag] Further MD5 breaks: Creating a rogue
CAcertificate

Steve.

---

From: "Timothy J. Miller" <[email-masked]>
Date: Wed, 31 Dec 2008 12:23:50 -0600

How about adding an otherName to the SAN?  You'd need an OID for random 
data though.

Or the CA could insert a method 4 UUID as a URI in the SAN.  That's 
intentionally random.  This might upset anyone wanting to use UUIDs as 
unique names, though (and these people do exist :).

Just thinking out loud.

-- Tim

---

From: "Timothy J. Miller" <[email-masked]>
Date: Wed, 31 Dec 2008 12:35:09 -0600

> machine's ability to discern mischief.

I don't see how, if the random goo is added by the CA.  It defeats 
chosen prefix attacks as a class.

-- Tim

---

From: "Timothy J. Miller" <[email-masked]>
Date: Wed, 31 Dec 2008 12:34:04 -0600

> Do you want to propose id-ce-magicCookie OBJECT IDENTIFIER  ::=  {id-ce 

draft-01 already:  Make that id-ce-magicNumber instead.  :)

-- Tim

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 31 Dec 2008 13:56:27 -0500

You have some time there and work with client vendors to implement
SHA-256 and next generation SHA.

I would support a random value extension if clients checked for it.

-----Original Message-----
From: Timothy J. Miller [mailto:[email-masked]] 
Sent: Wednesday, December 31, 2008 1:54 PM
To: Santosh Chokhani
Cc: Dr Stephen Henson; [email-masked]; [email-masked];
[email-masked]; [email-masked]
Subject: Re: [Cfrg] [saag] Further MD5 breaks: Creating a rogue
CAcertificate

Santosh Chokhani wrote:

> So, if you are relying on CAs, why not ask them to switch to SHA-1 as
> opposed to adding more software to the CA.  SHA-1 is purely a
> configuration item for the CA deployments.

Because someday SHA-1 (and SHA-2, or any hash algorithm) may be subject 
to a similar collision generation attack, and the presence of 
unpredictable data in the cert will defeat it as well.

Just trying to be proactive here.

-- Tim

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 31 Dec 2008 13:50:13 -0500

These things need to be thought through.

If all the CAs did this, it might work.  But, what if the client side
was looking for junk in the certificate as evidence of collision?

Also, client will not enforce this.

I just find that all three mail lists are getting work out and real
message and analysis is getting lost.

For example, folks are still posting misinformation that self-signed
roots have a hash problem.  Signatures on self-signed roots are
gratuitous from security viewpoint.  So, we do not want to cry wolf and
undertaken replacing roots which will be a humongous waste to time and
money.  Signatures and hence hash used to sign these do not matter.  

-----Original Message-----
From: Timothy J. Miller [mailto:[email-masked]] 
Sent: Wednesday, December 31, 2008 1:35 PM
To: Santosh Chokhani
Cc: Dr Stephen Henson; [email-masked]; [email-masked];

-- Tim

---

From: "Timothy J. Miller" <[email-masked]>
Date: Wed, 31 Dec 2008 12:53:59 -0600

-- Tim

---

From: "Kemp, David P." <[email-masked]>
Date: Wed, 31 Dec 2008 14:20:23 -0500

Just to be precise, past MD5 certificates should be safe as long as
there
are no second-preimage attacks.  I have no idea* whether there are any
computational shortcuts to finding a second preimage (where both the
hashed data and its digest value are known) relative to finding a
preimage
(where only the digest value is known), but in principle second-preimage
attacks might be feasible sooner.

Dave

* for example, http://www.springerlink.com/content/yut517362112765h/
indicates
that 1 in 2^56 messages may be "weak" against a specified attack on MD4.
What is needed is an attack on MD5 where many or all messages are
"weak".

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of Jeffrey Hutzelman
Sent: Tuesday, December 30, 2008 6:46 PM
To: Santosh Chokhani; Peter Hesse; RL 'Bob' Morgan; Paul Hoffman
Cc: [email-masked]; [email-masked]; [email-masked]; [email-masked];
[email-masked]
Subject: Re: [saag] Further MD5 breaks: Creating a rogue CA certificate

> certificates are safe until the attack was devised.

The attack does _not_ involve computing a preimage; it involves
computing a 
colliding pair one of which has a prefix which is predictable but not 
controllable, followed by a controllable component consisting of some 
minimum number of bits followed by at least three aligned message
blocks. 
What makes existing certificates safe is that there are no known
preimage 
attacks against MD5, couple with limitations of the technique used to 
construct the colliding pair.

However, there is a limit to how "safe" existing certificates are,
because 
the attack does not require anything that was not known 3-4 years ago.
The 
only change is that with the latest techniques for computing collisions,
it 
is possible to do so in a short enough time to be able to predict the 
validity and serial number that will be used by the issuer with fairly
high 
probability.

-- Jeff