Whacking the Bitcoin Piñata

Page content

@yomimono or @hannesm surely know if people have tried crowbar on the BTC Piñata. – @kensan@mastodon.social

tl;dr - yes, and it seems that ocaml-x509 is not trivially easy to trick.

Background

The Bitcoin Piñata

In 2015 David Kaloper-Mersinjak and Hannes Mehnert released ocaml-tls, an implementation of TLS (formerly known as SSL) written fully in OCaml. A full writeup of the stack is available in their Usenix Security 2015 paper, and as a series of blog posts on mirage.io. To accompany the release they also deployed a fully-automated bug bounty for the security stack – the bitcoin piñata.

The piñata will establish TLS connections only with endpoints presenting a certificate signed by its own, undisclosed certificate authority, but allows an attacker to easily listen to the encrypted traffic. The piñata always sends the same plaintext in such a connection: the private key to a wallet containing approximately 10 bitcoin. If the attacker can decrypt the ciphertext, or trick the piñata into negotiating a TLS connection with another host and disclosing the key, the information (and therefore the money) is theirs.

Crowbar

Crowbar is a library for writing tests. It combines a property-based API (like QuickCheck) with a coverage-driven generator of test cases (like the fuzzer American Fuzzy Lop). Crowbar tries to find counterexamples to stated properties by prioritizing the generation of test cases which touch more code. It is very good at finding counterexamples.

Testing ocaml-x509

TLS connections are usually authenticated via X509 certificates. ocaml-tls uses ocaml-x509 for this purpose, which is written as a standalone library. There is a clear separation of concerns between ocaml-x509 and ocaml-tls, and a straightforward API for certificate operations in ocaml-x509; both features help tremendously in writing tests for certificate handling.

Stating Tests

Of the possible operations in X509, the most interesting in the context of the BTC piñata are those related to certificate validation. We expect the piñata to check whether a certificate provided by the attacker has a trust chain to any CA it is aware of. This suggests a property we might want to find a counterexample to:

  • certificates signed by CA m will not be judged valid unless CA m is provided as a trust anchor.

If we can find a counterexample, we’re well on the way to getting the piñata to negotiate a TLS connection with an endpoint presenting a certificate not signed by the CA it generated at boot time.

Generating Certificates

In order to test this property, we need to be able to call X509.Validation.verify_chain_of_trust with something of type X509.CA.t (representing the certificate authority; for the piñata, this is a known and trusted value) and something of type X509.t (representing the certificate; for the piñata, this is presented by the remote host of the TLS connection).

For our tests, we’ll allow Crowbar’s random generators to specify most parts of the certificate, with the important exception of the key material – generating this randomly will cause the execution of each test to be very slow, and it’s not the goal of this testing to try to brute-force the key of our test CA.

The generators for certificates are largely automatically created by ppx_deriving_crowbar, although some manual help is needed to include generators for data types in dependencies used by X509 (and generators for their dependencies and dependencies’ dependencies). A maximalist interpretation can be seen in this iteration of the tests, which uses ppx_deriving to automatically generate equality tests and pretty-printers as well as generators for many of the relevant types.

Increasing Stability

Since we want all randomness in the test execution to be driven by the fuzzer, it’s important to remove other sources of entropy in the code execution. Luckily, ocaml-x509 and the cryptography library underneath it, nocrypto, were written considerately, and there is a facility for providing a constant seed to the pseudorandom number generator. Using the same seed across all test runs removes noise from the measurement of coverage between different test runs.

Running Tests

Tests built with the Crowbar library need to be run via afl-fuzz. To automatically launch afl-fuzz in a manner that uses all available computing resources and reports failures as quickly as possible, we used ocaml-bun. You can see the results of such a test run in Travis CI here.

The number of executions per second is appallingly low for OCaml native code running in afl-fuzz (cryptography is hard!); to compensate I ran this code over a weekend locally instead of briefly on whatever free resources Travis would give me.

Results

Many certificates with silly sets of extensions were generated:

`Priv_key_period (`Not_after (0066-02-08 09:28:58 +00:00))
`Subject_alt_name ([`EDI_party (((Some "mmmmmmmmmxmmmmmmmmmmmmmrs\146n\020sh&&&&&&&&&&.&&&'&&t\014the&w[rn Bx WrV"),
                                 "c\130 s'\186\186\186\186\186\186\186Te@rica tbiitx WrVc\127 s', or soTe@wos\127\141\018o\139\255repeeseb u"));
                                                      `Other ((0.32, "t \228ay of\015t"))])
                                                      `Priv_key_period (`Not_after (1088-06-01 06:08:11 +00:00))

`CRL_distribution_points ([((Some `Relative ([`Generation ("EEElE$EE \127\255E'EEElEEEYE$EE\151ai4RgEbEE\151a\214\214\214\235\214\214\214\214bnt\225")
                                               ])),
                            None,
                            (Some [`Surname ("~~~~~~~~~~EEEYE$EEB\127\255E'EEElEEEYE$EE\151a\214\214\214\235\214\214\214\214\214\214\214\214\214\214\214\214\198\214\214\214\215\214\214\214\214 \214")
                                    ]))
                            ])

`Certificate_issuer ([])
`Policies ([`Something (0.36.3703494230495416691)])`Certificate_issuer (
[])
`Subject_alt_name ([`Other ((2.2839008736452811263, "\140abbi\131\129\b',"));
                     `URI ("'[cay@")])

As we hoped, a certificate signed by the wrong CA with these sets of extensions don’t validate. ocaml-x509 isn’t tricked by arbitrarily ridiculous sets of extensions in a signed certificate, and I didn’t manage to steal any bitcoin.

None of this work targets ocaml-tls or any of the more general parts of the stack run by the piñata. Notably, neither tcpip which provides the TCP, IPv4, and Ethernet implementations, nor any of the hypervisor-specific virtual network devices, are examined by this work. (This includes mirage-net-xen, the originator of the only MirageOS security advisory to date.) With releases of all tooling used to test ocaml-x509 available via opam, this is easier to rectify than it previously was!

Acknowledgements

Thanks to OCaml Labs for funding this work, IPredator for stuffing the piñata, and robur.io for future and continuing work in building resilient systems.