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. 

Re: OCSP Responders Are An Attack Vector For SHA-1 Collisions

[Richard Barnes]

On Tue, Mar 8, 2016 at 4:58 PM, Andrew Ayer  wrote:

> 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