ABSTRACT HACL * is a verified portable C cryptographic library that implements modern cryptographic primitives such as the ChaCha20 and Salsa20 encryption algorithms, Poly1305 and HMAC message authentication, SHA-256 and SHA-512 hash functions, the Curve25519 elliptic curve, and Ed25519 signatures. HACL * is written in the F * programming language and then compiled to readable C code. The F * source code for each cryptographic primitive is verified for memory safety, mitigations against timing side-channels, and functional correctness with respect to a succinct high-level specification of the primitive derived from its published standard. The translation from F * to C preserves these properties and the generated C code can itself be compiled via the CompCert verified C compiler or mainstream compilers like GCC or CLANG. When compiled with GCC on 64-bit platforms, our primitives are as fast as the fastest pure C implementations in OpenSSL and Libsodium, significantly faster than the reference C code in TweetNaCl, and between 1.1x-5.7x slower than the fastest hand-optimized vectorized assembly code in SUPERCOP. HACL * implements the NaCl cryptographic API and can be used as a drop-in replacement for NaCl libraries like Libsodium and TweetNaCl. HACL * provides the cryptographic components for a new mandatory ciphersuite in TLS 1.3 and is being developed as the main cryptographic provider for the miTLS verified implementation. Primitives from HACL * are also being integrated within Mozilla's NSS cryptographic library. Our results show that writing fast, verified, and usable C cryptographic libraries is now practical. Cryptographic libraries lie at the heart of the trusted computing base of the Internet, and consequently, they are held to a higher standard of correctness, robustness, and security than other distributed applications. Even minor bugs in cryptographic code typically result in CVEs and software updates. For instance, since 2016, OpenSSL has issued 11 CVEs 1 for bugs in its core cryptographic primitives, including 6 memory safety errors, 3 timing side-channel leaks, and 2 incorrect bignum computations. Such flaws may seem difficult to exploit at first, but as Brumley et al. [24] demonstrated, even an innocuous looking arithmetic bug hiding deep inside an elliptic 1 https://www.openssl.org/news/vulnerabilities.html Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). CCS '17, October 30-November 3, 2017, Dallas, TX, USA © 2017 Copyright held by the owner/author(s). ACM ISBN 978-1-4503-4946-8/17/10. https://doi.org/10.1145/3133956.3134043 curve implementation may allow an attacker to efficiently retrieve a victim's long-term private key, leading to a critical vulnerability. Bugs in cryptographic code have historically been found by a combination of manual inspection, testing, and fuzzing, on a besteffort basis. Rather than finding and fixing bugs one-by-one, we join Brumley et al. and a number of recent works [8, 12, 25, 29, 37] in advocating the use of formal verification to mathematically prove the absence of entire classes of potential bugs. In this paper, we will show how to implement a cryptographic library and prove that it is memory safe and functionally correct with respect to its published standard specification. Our goal is to write verified code that is as fast as state-of-the-art C implementations, while implementing standard countermeasures to timing side-channel attacks.
Zinzindohoue et al. REF develop HACL*, a portable C library that implements many modern cryptographic primitives.
HACL*: A Verified Modern Cryptographic Library
CCS '17
Computer Science