OCSP Responders Are An Attack Vector For SHA-1 Collisions

[Andrew Ayer]

As we all know, the Baseline Requirements forbid signing certificates
with SHA-1 after January 1, 2016. However, both the BRs and Mozilla
policy are silent on the topic of OCSP response signatures[1].
Theoretically, CAs could continue to sign OCSP responses with SHA-1
indefinitely. Indeed, among the 869 distinct OCSP responder URLs
referenced in CT logs, 351 sign responses with SHA-1 (as of
March 5, 2016).

([1] The BRs forbid SHA-1 for signing "certificates to verify OCSP
responses" after January 1, 2017, but I take that to mean the signature
on the OCSP responder's certificate, not the OCSP responses themselves.)

Of those 351 responders, 209 will include an attacker-controlled nonce
of arbitrary length in the signed response (I tested with up to 1kb
nonces). This creates a condition *extremely* favorable for a
chosen-prefix attack. The first ~200 bytes of the hash input are
trivially predictable (the only variable parts are the "Produced At",
"This Update", and "Next Update" fields, which are all based on the
current time). This prefix is followed by the entirely
attacker-controlled nonce. An attacker can predict the prefix and
stash the collision bits in the nonce to create a collision with
another preimage, such as a certificate.

Fortunately, the majority of those responders sign responses using a
certificate that is restricted by ExtendedKeyUsage to OCSP signing, so
the worst that an attacker could do is forge OCSP responses. However,
I found two responders that sign responses using CA:TRUE certificates
that are trusted for server auth in NSS:

1. http://ocsp.buypass.no/ocsp/BPClass2CA1 signs responses with a root
certificate ("Buypass Class 2 CA 1") trusted for server auth in NSS.
There is no path length constraint.

Raw request: https://www.agwa.name/misc/ocsp_collisions/sha1/buypass-response.ocsp
Request text: https://www.agwa.name/misc/ocsp_collisions/sha1/buypass-response.txt
Raw responder cert: https://www.agwa.name/misc/ocsp_collisions/sha1/buypass-response.crt
Responder cert text: https://crt.sh/?q=0f4e9cdd264b025550d170806340214fe94434c9b02f697ec710fc5feafb5e38

2. http://ocsp.acedicom.edicomgroup.com/servidores signs responses with
an intermediate cert which chains up to "ACEDICOM Root". There are no
path length constraints in the chain.

Raw request: https://www.agwa.name/misc/ocsp_collisions/sha1/acedicom-response.ocsp
Request text: https://www.agwa.name/misc/ocsp_collisions/sha1/acedicom-response.txt
Raw responder cert: https://www.agwa.name/misc/ocsp_collisions/sha1/acedicom-response.crt
Responder cert text: https://crt.sh/?q=071fa8b9e12a9632cfcb5c7e2b96ab318ccb40591713d5f914834b682d481b45

Once a chosen-prefix attack on SHA-1 becomes viable, it will be possible
to forge a trusted CA:TRUE certificate by creating a collision with
an OCSP response from one of these two responders. This attack can be
performed without a CA having to issue a SHA-1 certificate, or do
anything that currently violates the BRs or Mozilla policy. In fact,
exploiting a collision against an OCSP responder is much easier than
exploiting a collision against the certificate issuance process. You
can exploit it completely anonymously, you don't have to predict the
serial number, and you have plenty of room for collision bits instead
of having to smuggle them in the CSR's public key. The OCSP response
is so predictable that an attacker could predict it months in advance,
allowing plenty of time to compute the collision. In contrast, it took
Stevens et al four attempts to predict even a sequential serial number
when they forged their MD5 cert in 2008, and they spent hundreds of
dollars on certs in the process.

As a proof of concept, I have created an OCSP response and a CA:TRUE
certificate which share the same MD5 signature:

OCSP response: https://www.agwa.name/misc/ocsp_collisions/md5/poc-response.ocsp
OCSP response text: https://www.agwa.name/misc/ocsp_collisions/md5/poc-response.txt
Rogue certificate: https://www.agwa.name/misc/ocsp_collisions/md5/poc-rogue.crt
Rogue certificate text: https://www.agwa.name/misc/ocsp_collisions/md5/poc-rogue.txt
Root cert: https://www.agwa.name/misc/ocsp_collisions/md5/poc-root.crt

Although this uses MD5 and my own root CA, it demonstrates that the
OCSP format is amenable to chosen-prefix attacks, particularly with the
attacker-controlled nonce and the very predictable prefix. We should
therefore be concerned about the risk of OCSP responders which use
SHA-1 and support nonces.

I have thought of a few ways to address the risk:

1. Forbid the use of SHA-1 to sign OCSP responses, effective as soon
as possible (consider that signing certificates with SHA-1 has been
forbidden since January 1, 2016).

2. Forbid OCSP nonces. OCSP nonces are optional in practice and it's
always risky to sign arbitrary attacker-controlled data. Or, limit
nonces to 32 bytes, which is long enough for an anti-replay nonce
but probably too short to exploit a chosen-prefix attack.

3. Require the use of a technically-constrained OCSP responder
certificate when doing online signing of OCSP responses. This seems
like a good security practice anyways, and most CAs are already doing
this. However, OCSP responses could still be forged.

What do others think?

Regards,
Andrew


P.S. This underscores a point which I have made several times on this
list in the last month: with a chosen-prefix attack, the forged
certificate need not look anything like the data which the CA signs. As
I've demonstrated here, a CA can sign an OCSP response that can be
turned into a certificate. This is why various proposals like revoking
certificates, embedding a poison extension, or blacklisting based on
the notBefore date do absolutely nothing to address the risk of SHA-1:
a forged certificate--the certificate that clients need to
reject--won't have any of the markings (serial number, poison
extension, notBefore date) that the CA placed in the "legitimate" SHA-1
certificate. It's also why it's so important that *anything* signed by
a CA that is trusted for server auth be in-scope for the BRs and
Mozilla Policy, as Ryan, Rob, and I have said[2].

([2] https://www.mail-archive.com/dev-security-policy%40lists.mozilla.org/msg02994.html)

[Richard Barnes]

First, thanks for the excellent write-up. The MD5 collisions are a nice
touch :)

I would note that we could also combine these responses. For example, we
might require that CAs retire SHA-1 for OCSP with a long-ish horizon, but
require them to use constrained OCSP certs basically ASAP.

Of course, if we could just turn off SHA-1 for OCSP, that would be
fantastic. Do any CAs on the list know of blockers on making this switch
basically now? E.g., are there client stacks that support SHA-2 for
verification, but not for OCSP? (Firefox is obviously fine for both.)

--Richard

>
> Regards,
> Andrew
>
>
> P.S. This underscores a point which I have made several times on this
> list in the last month: with a chosen-prefix attack, the forged
> certificate need not look anything like the data which the CA signs. As
> I've demonstrated here, a CA can sign an OCSP response that can be
> turned into a certificate. This is why various proposals like revoking
> certificates, embedding a poison extension, or blacklisting based on
> the notBefore date do absolutely nothing to address the risk of SHA-1:
> a forged certificate--the certificate that clients need to
> reject--won't have any of the markings (serial number, poison
> extension, notBefore date) that the CA placed in the "legitimate" SHA-1
> certificate. It's also why it's so important that *anything* signed by
> a CA that is trusted for server auth be in-scope for the BRs and
> Mozilla Policy, as Ryan, Rob, and I have said[2].
>
> ([2]
> https://www.mail-archive.com/dev-security-policy%40lists.mozilla.org/msg02994.html
> )

> _______________________________________________
> dev-security-policy mailing list
> dev-secur...@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-security-policy
>

[Mads Egil Henriksveen]

Hi Andrew

Thank you for making us aware of this issue with our OCSP responder.

We did make a major change in our CAs some years ago where we among other things established a new OCSP responder for all Buypass CAs used for SSL/TLS-certificates (including Buypass Class 2 CA 1). However, the original OCSP responder for Buypass Class 2 CA 1 is still active, even though it is not referenced for use in SSL/TLS-certificates today.

We will do some investigation in order to identify any potentially problematic consequences of disabling this OCSP responder before we can decide to do so. However, as a short term measure we have reconfigured the OCSP responder to use SHA256 instead of SHA-1.


Regards
Mads

[Rick Andrews]

> I would note that we could also combine these responses. For example, we
> might require that CAs retire SHA-1 for OCSP with a long-ish horizon, but
> require them to use constrained OCSP certs basically ASAP.
>
> Of course, if we could just turn off SHA-1 for OCSP, that would be
> fantastic. Do any CAs on the list know of blockers on making this switch
> basically now? E.g., are there client stacks that support SHA-2 for
> verification, but not for OCSP? (Firefox is obviously fine for both.)
>
> --Richard

I know of one blocker: Microsoft. Their TechNet article at aka.ms/sha1 says that CAs are allowed to use SHA-1 and SHA-2 for OCSP signing certs and OCSP responses, to allow continued support for XP SP1 and 2, and Server 2003. Using SHA-2 only for OCSP signing certs and OCSP responses will break those platforms.

The TechNet article is about Authenticode code signing and timestamping, but I think most CAs use the same roots (but different intermediates) to issue TLS and Code Signing certs. The current discussion in the CABF public list about what's in scope and what's not in scope is relevant here. If the BRs are scoped to include everything signed under certain roots, that may pull in code signing certs, timestamping certs, and CRLs and OCSP responses for code signing certs.

[Yuhong Bao]

> I know of one blocker: Microsoft. Their TechNet article at aka.ms/sha1 says that CAs are allowed to use SHA-1 and SHA-2 for OCSP signing certs and OCSP responses, to allow continued support for XP SP1 and 2, and Server 2003. Using SHA-2 only for OCSP signing certs and OCSP responses will break those platforms.

I don't think XP supports OCSP at all.

[Rob Stradling]

On 09/03/16 19:03, Yuhong Bao wrote:
>> I know of one blocker: Microsoft. Their TechNet article at aka.ms/sha1 says that CAs are allowed to use SHA-1 and SHA-2 for OCSP signing certs and OCSP responses, to allow continued support for XP SP1 and 2, and Server 2003. Using SHA-2 only for OCSP signing certs and OCSP responses will break those platforms.
>
> I don't think XP supports OCSP at all.

XP doesn't support OCSP out of the box, but CryptoAPI does support
third-party revocation providers (some of which use OCSP and perhaps
don't support SHA-2). I'd like to think that the number of users of
such revocation providers is statistically insignificant by now though.

--
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

[Jakob Bohm]

On 09/03/2016 20:03, Yuhong Bao wrote:
>> I know of one blocker: Microsoft. Their TechNet article at aka.ms/sha1 says that CAs are allowed to use SHA-1 and SHA-2 for OCSP signing certs and OCSP responses, to allow continued support for XP SP1 and 2, and Server 2003. Using SHA-2 only for OCSP signing certs and OCSP responses will break those platforms.
> I don't think XP supports OCSP at all.
>

It does.

And XP is not the only old system that needs to be serviced. Many
embedded or semi-embedded systems had a permanent code freeze (read:
ROM manufactured, source code now lost) in the past. In fact we have
have had to stop using SSL/TLS to communicate with some such systems
because of the modern ban on algorithms those systems understand.

The more fundamental point is this:

An OCSP response for existing certificate X is pretty must guaranteed
to have been requested by something that understands the algorithms
(such as SHA-1 and RSA) in certificate X. It is much less likely that
a legitimate requester understands any other algorithm.

Therefore OCSP responders should sign requests related to existing
certificates with the same algorithms that were used for those
certificates, even if those algorithms are no longer used for new
certificates.

If the query is for a non-existing (never issued) certificate, the
response needs to use the algorithms that were used to issue or
self-sign the alleged issuing certificate (which must be known to the
OCSP responder if it is to have an opinion at all).

Furthermore, the use of securely timestamped signatures means that OCSP
responders need to keep responding about certificates for a significant
period (years) after those certificates expire. This is to service
clients that validate existing signatures on existing data (such as
documents or code).

So in practice, only the following can be done to secure OCSP
responders for CAs that used now obsolete algorithms to issue
certificates in the past:

1. Use a non-CA OCSP certificate if the relevant clients are known to
support this aspect of the OCSP protocol (I don't know if any OCSP
clients, historic or otherwise, lack this ability). Such an OCSP
certificate needs to be issued using the historic (and obsolete!)
algorithms that were used for the certificates the OCSP is responding
about, even though this technically violates fanatical readings of
modern algorithm bans.

2. Find a way to add OCSP responder chosen random data in each OCSP
response. And preferably lots of bits, e.g. 256 or more bits with
current technology. This does not preclude the use of precomputed
pre-signed responses for each known single certificate query, as
the random value only needs to change when the rest of the response
changes, so a pre-computed response would contain a pre-computed
random value.




Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S. https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark. Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

[Peter Gutmann]

Jakob Bohm <jb-mo...@wisemo.com> writes:

>2. Find a way to add OCSP responder chosen random data in each OCSP
> response.

Responder or requester? You've got the OCSP nonce, although since every
(public) CA has disabled it that probably won't help much. OTOH since clients
won't be checking the nonce because of this, you might be able to insert a
dummy one that'll be ignored by the client.

Peter.

[Peter Bowen]

On Wed, Mar 9, 2016 at 12:40 PM, Jakob Bohm <jb-mo...@wisemo.com> wrote:
> 1. Use a non-CA OCSP certificate if the relevant clients are known to
> support this aspect of the OCSP protocol (I don't know if any OCSP
> clients, historic or otherwise, lack this ability). Such an OCSP
> certificate needs to be issued using the historic (and obsolete!)
> algorithms that were used for the certificates the OCSP is responding
> about, even though this technically violates fanatical readings of
> modern algorithm bans.
>

> 2. Find a way to add OCSP responder chosen random data in each OCSP

> response. And preferably lots of bits, e.g. 256 or more bits with
> current technology. This does not preclude the use of precomputed
> pre-signed responses for each known single certificate query, as
> the random value only needs to change when the rest of the response
> changes, so a pre-computed response would contain a pre-computed
> random value.

The OCSP spec has tons of places where extensions are supported. For
example nonces are not part of the core message but are a type of
extension. If OCSP clients properly ignore unknown extensions then
random data could be included in a newly defined extension.
Additionally the response is technically a sequence of
SingleResponses. RFC 6960 says:

"The response SHOULD NOT include any additional
SingleResponse elements, but, for example, OCSP responders that
pre-generate status responses might include additional SingleResponse
elements if necessary to improve response pre-generation performance
or cache efficiency (according to [RFC5019], Section 2.2.1)."

This suggests another solution would be add a random SingleResponse as
the first responses member. SingleResponse has plenty of room for
random bytes while still ending up with a syntactically valid
structure.

[Jakob Bohm]

Obviously the responder, so it can protect its private key against
chosen values and hence collision attacks.

And since requesters that don't send a nonce might check that they
don't get one back, a more practical approach would be to put the
random responder-nonce in a different singleExtension, either one
borrowed from some other PKIX context or a new one. Note that it should
go in singleExtensions and have an OID that sorts earlier than
id-pkix-ocsp-nonce, in order to prevent putting prefix attack data in
the requester nonce if responders were to reenable that extension to
protect against some future attack.

If a new extension is needed, it could be given the (currently unused)
object identifier "{ id-pkix-ocsp 0 }" = 1.3.6.1.5.5.7.48.1.0

I would also like to point out that I consider the wording in RFC6960
section 5.1.1 naive in the context of archival applications accessed by
archived clients. The "solution" given there works only for new
clients checking old signatures, not for old systems continuing to do
the only thing they know how to do. If a new client checking old data
is capable of understanding a modern signing algorithm for the OCSP
response, it can state that explicitly via the
PreferredSignatureAlgorithms request extension, while an old client
cannot change the form of its request to indicate that it has not been
changed.

[Andrew Ayer]

On Tue, 8 Mar 2016 13:58:21 -0800
Andrew Ayer <ag...@andrewayer.name> wrote:

> 2. Forbid OCSP nonces. OCSP nonces are optional in practice and it's
> always risky to sign arbitrary attacker-controlled data. Or, limit
> nonces to 32 bytes, which is long enough for an anti-replay nonce
> but probably too short to exploit a chosen-prefix attack.

Addendum: I just noticed that some responders will echo back
attacker-controlled serial numbers of arbitrary length (with a
certificate status of "unknown"), which provides another vector for a
chosen-prefix attack even if nonces are restricted.

To plug this hole, responders could return an unsigned "unauthorized"
response for unknown certificates, as permitted by RFC5019.

Regards,
Andrew

[Andrew Ayer]

On Wed, 9 Mar 2016 21:40:32 +0100

Jakob Bohm <jb-mo...@wisemo.com> wrote:

> 1. Use a non-CA OCSP certificate if the relevant clients are known to
> support this aspect of the OCSP protocol (I don't know if any OCSP
> clients, historic or otherwise, lack this ability).

Using a dedicated OCSP responder certificate is a common practice (518
of the responders I probed use one; only 52 do not), and was part of
the original RFC, so hopefully support for this is widespread among
OCSP clients.

> Such an OCSP certificate needs to be issued using the historic (and obsolete!)
> algorithms that were used for the certificates the OCSP is
> responding about, even though this technically violates fanatical
> readings of modern algorithm bans.

The BRs explicitly permit signing OCSP responder certificates with SHA-1
until January 1, 2017, so bringing a new SHA-1 OCSP responder certificate
online before then would not violate any reading of the BRs.

> 2. Find a way to add OCSP responder chosen random data in each OCSP

> response. And preferably lots of bits, e.g. 256 or more bits with
> current technology. This does not preclude the use of precomputed
> pre-signed responses for each known single certificate query, as
> the random value only needs to change when the rest of the response
> changes, so a pre-computed response would contain a pre-computed
> random value.

Pre-signed responses do not need any random data since they don't contain
any attacker-controlled input.

Just using pre-signed responses (equivalently, preventing any attacker
control over the response) is a much simpler fix than trying to stuff
entropy into the OCSP response. Are there clients that will choke if
they receive a response without the expected nonce?

Regards,
Andrew

[Peter Gutmann]

Andrew Ayer [ag...@andrewayer.name] writes:

>Are there clients that will choke if they receive a response without the
>expected nonce?

See my previous message, since no public CAs honour nonces [0] I don't think
there'd be any problem.

Peter.

[0] At least as of the last check a few years ago.

[Andrew Ayer]

On Thu, 10 Mar 2016 00:58:07 +0000
Peter Gutmann <pgu...@cs.auckland.ac.nz> wrote:

> Andrew Ayer [ag...@andrewayer.name] writes:
>
> >Are there clients that will choke if they receive a response without
> >the expected nonce?
>
> See my previous message, since no public CAs honour nonces [0] I
> don't think there'd be any problem.

As I explained in my original post, I found 209 responders for public
CAs that return nonces (and that's just among the responders which use
SHA-1 signatures).

Regards,
Andrew

[Erwann Abalea]

First case is worrying, in that it means the root private key isn't offline or air-gaped.

[Mads Egil Henriksveen]

Hi

Some additional information regarding Buypass Class 2 CA 1. The Buypass Class 2 CA 1 is a part of the first generation of Buypass CA infrastructure and this CA was originally both an issuing and a root CA. We established a new generation of CA infrastructure separating the root CAs and issuing CAs back some years ago and have performed a migration from the old infrastructure to the new infrastructure to fulfill the requirements within this area.

We did stop issuing certificates in the old infrastructure years ago, but it was difficult to switch off the validation operations due to important end clients and relaying parties (e.g. governmental entities) depending on this services in the old infrastructure.

The last step in our migration plan has been to remove the support for validation services in the old infrastructure. This has taken some time since it must be performed in a controlled manner and we have used a staged approach to reduce the consequences for our clients.

However, we have now been able to complete this last step and disabled the Buypass Class 2 CA 1 as an OCSP responder. All validation operations are now being taken care of in the new infrastructure.

Once a chosen-prefix attack on SHA-1 becomes viable, it will be possible to forge a trusted CA:TRUE certificate by creating a collision with an OCSP response from one of these two responders. This attack can be performed without a CA having to issue a SHA-1 certificate, or do anything that currently violates the BRs or Mozilla policy. In fact, exploiting a collision against an OCSP responder is much easier than exploiting a collision against the certificate issuance process. You can exploit it completely anonymously, you don't have to predict the serial number, and you have plenty of room for collision bits instead of having to smuggle them in the CSR's public key. The OCSP response is so predictable that an attacker could predict it months in advance, allowing plenty of time to compute the collision. In contrast, it took Stevens et al four attempts to predict even a sequential serial number when they forged their MD5 cert in 2008, and they spent hundreds of dollars on c erts in the process.

As a proof of concept, I have created an OCSP response and a CA:TRUE certificate which share the same MD5 signature:

OCSP response: https://www.agwa.name/misc/ocsp_collisions/md5/poc-response.ocsp
OCSP response text: https://www.agwa.name/misc/ocsp_collisions/md5/poc-response.txt
Rogue certificate: https://www.agwa.name/misc/ocsp_collisions/md5/poc-rogue.crt
Rogue certificate text: https://www.agwa.name/misc/ocsp_collisions/md5/poc-rogue.txt
Root cert: https://www.agwa.name/misc/ocsp_collisions/md5/poc-root.crt

Although this uses MD5 and my own root CA, it demonstrates that the OCSP format is amenable to chosen-prefix attacks, particularly with the attacker-controlled nonce and the very predictable prefix. We should therefore be concerned about the risk of OCSP responders which use
SHA-1 and support nonces.

I have thought of a few ways to address the risk:

1. Forbid the use of SHA-1 to sign OCSP responses, effective as soon as possible (consider that signing certificates with SHA-1 has been forbidden since January 1, 2016).

2. Forbid OCSP nonces. OCSP nonces are optional in practice and it's always risky to sign arbitrary attacker-controlled data. Or, limit nonces to 32 bytes, which is long enough for an anti-replay nonce but probably too short to exploit a chosen-prefix attack.

[tomass...@gmail.com]

Good read. Thanks for an interesting post.

Since it's trivial to limit size of Nonces that are acceptable we decided to do that in EJBCA [1]. Returning a malformed request error in case of larges Nonce [2].

Of course, I have read the rest of the thread and there are probably other attack vectors, like serialNumber as you point out. Trivial hardening should still be implemented.

Cheers,
Tomas

[1]: https://www.ejbca.org/
[2]: https://jira.primekey.se/browse/ECA-4906