Replace built-in hashlib with verified implementations from HACL*

[msprotz]

Feature or enhancement

We propose to replace the non-OpenSSL cryptographic primitives in hashlib with high-assurance, verified versions from the HACL* project.

Pitch

As evidenced by the recent SHA3 buffer overflow, cryptographic primitives are tricky to implement correctly. There might be issues with memory management, exceeding lengths, incorrect buffer management, or worse, incorrect implementations in corner cases.

The HACL* project https://github.com/hacl-star/hacl-star provides verified implementations of cryptographic primitives. These implementations are mathematically shown to be:

• memory safe (no buffer overflows, no use-after-free)
• functionally correct (they always compute the right result)
• side-channel resistant (the most egregious variants of side-channels, such as memory and timing leaks, are ruled out by construction).

See https://hacl-star.github.io/Overview.html#what-is-verified-software for a longer description of how formal methods can help write high-assurance software and rule out entire classes of bugs.

The performance of HACL* is competitive with, and sometimes exceeds, that of OpenSSL. HACL* is distributed as pure C, and therefore is portable. Parts of HACL* have been adopted in Mozilla, Linux, the Tezos blockchain, and many more, thereby demonstrating that formally verified code is ready for production-time.

Previous discussion

Tagging @alex with whom I've informally discussed this.

• PR: gh-99108: Import SHA2-224 and SHA2-256 from HACL* #99109

• PR: gh-99108: Import SHA2-384/512 from HACL* #101707

• PR: gh-99108: Build the hashlib HACL* code as a static library. (fix wasm builds) #101917

• PR: gh-99108: Refactor _sha256 & _sha512 into _sha2. #101924

• PR: gh-99108: Import MD5 and SHA1 from HACL* #102089

• PR: gh-99108: Followup fix for Modules/Setup #102183

• PR: gh-99108: Add missing md5/sha1 defines to Modules/Setup #102308

• PR: gh-99108: Initial import of HACL-SHA3 into Python #103597

• PR: gh-99108: fix typo in Modules/Setup #104293

• PR: gh-99108: Refresh HACL* from upstream #104401

• PR: gh-99108: Release the GIL around hashlib built-in computation #104675

• PR: [3.12] gh-99108: Release the GIL around hashlib built-in computation (GH-104675) #104776

• PR: gh-99108: Refresh HACL* #104808

• PR: [3.12] gh-99108: Refresh HACL* (GH-104808) #104893

• PR: gh-99108: Mention HACL\* in the hashlib docs. #105634

• PR: [3.12] gh-99108: Mention HACL\* in the hashlib docs. (GH-105634) #105635

• PR: gh-99108: Refresh HACL*; update modules accordingly; fix namespacing #117237

• PR: [3.12] gh-99108: Refresh HACL*; update modules accordingly; fix namespacing (GH-117237) #117243

• PR: gh-99108: Update and check HACL* version information #117295

• PR: [3.12] gh-99108: Update and check HACL* version information (GH-117295) #117302

• PR: gh-99108: Add HACL* Blake2 implementation to hashlib #119316

• PR: gh-99108: Inform HACL when explicit_bzero is unavailable #123027

• PR: GH-99108: Fix Setup in addition to Setup.stdlib.in #123146

• PR: gh-99108: Disable HACL SIMD code on older versions of Android #124304

• PR: GH-99108: Make vectorized versions of Blake2 available on x86, too #125244

• PR: gh-99108: Cleanup references to inexisting Modules/_blake2. #126270

[gpshead]

(missing context: there was a private email thread cc'ing ~7 of us including myself, @tiran, @alex, @msprotz & others that led to this issue and PR) in response to #98517 CVE happening with our old XKCP sha3 vendored code.

One reason I might support this work across all of our required always supported hashes is that if these perform well, I'd be happy to see the _hashlib module wrapping OpenSSL deprecated entirely. (Others probably disagree with that, so we may never get there). One less thing depending on OpenSSL sounds nice - but the OpenSSL EVP interface and these algorithms are far less likely to be where OpenSSL CVE bugs lurk (famous last words). BUT... if the vendored third party code we use as a fallback for hash algorithms can be replaced with something nearly guaranteed not to be the next CVE as the hack-star project appears to aim to be (I cannot actually be the judge of that), and be high performance... Why should we bother involving OpenSSL for these at all?

If this sounds like the opposite of my statements over buried in the blake3 rejection thread - it's because I did not seek an alternative to the variety of vendored fallback hash algorithm implementations we carry there. So the goal in those statements was to lean towards simplicity instead of complexity. (which has already paid off via our XKCP removal in favor of tiny_sha3 by not having Python 3.11+ suffer from the sha3 XKCP CVE that the larger complex third party code in 3.6-3.10 did)

We provide and ship native implementations for the hash algorithms anyways as we support builds without OpenSSL present, and support building on systems with libssl versions or variants that do not provide everything.

Q: Would adopting this code increase our maintenance burden?

A: Probably, yes. We'd presumably want to update it with more recent versions from hacl-star from time to time. Though the theory is that there should never be a security need to do so? In the past we've been asked to update vendored hash algorithm code from time to time but have hesitated due to the complexity and perceived risk, and assumed lack of reward given people who care about performance would presumably have a modern OpenSSL to get that from. Though if we did get rid of the OpenSSL wrapper code that'd also be a reduced burden.

Q: What about performance?

A: Good question. That needs continual measuring on our Tiered supported platforms. Don't focus solely on thruput. OpenSSL's EVP APIs are known to have silly-slow setup time. So something hashing a pile of 234 byte objects may be slow no matter how good OpenSSL's bulk data thruput is. Benchmark small message thruput as well as bulk data thruput.

Parting thought: There is a broader desire to wean us off of our OpenSSL dependency. I realize that's a hard thing so long as the _ssl module exists, but it is a long term desire of many. This kind of change would be one necessary step, regardless of when it is taken.

[msprotz]

Thanks for your comment, Greg. Some related thoughts.

• We have support for all of the algorithms in hashlib (md5, sha1, sha2, sha3, blake2). So there is a clear pathway to consolidating those implementations together into a single vendored library that is side-channel resistant, and that has proofs of correctness.
• Getting rid of OpenSSL is feasible, but not today (as you accurately pointed out on gh-99108: Import SHA2-224 and SHA2-256 from HACL* #99109). For now, we are proposing pure C that is easy to compile, portable, fast, and secure. We have a technology for mixing ASM and C, or even using C compiler intrinsics -- that's what we used to beat OpenSSL in a 2020 paper, on one specific algorithm. But then there are numerous drawbacks:
  • your build becomes more complicated: you need to probe the current toolchain and make sure it even knows about e.g. that fancy AVX512 intrinsic you're about to use; or that it can use inline ASM; etc.
  • your runtime becomes more complicated: once the compiled binary is copied to another computer, you need to perform run-time CPU detection, so that in the event that you did manage to compile that AVX512 version, then you do use it if the processor you're running on happens to have those fancy instructions
  • your maintenance burden becomes greater, and you need to decide how many ASM versions you want to support, for which architecture families, etc.

None of this is infeasible -- it's just a matter of deciding what is good for a Python-in-the-future where hashlib no longer depends on OpenSSL. For instance, you might say "let's maintain a portable C version, and one single ASM version that uses SHAEXT when available (fastest)", and this is something we could make happen within HACL*.

Just to give you a sense of what we have right now, allow me to go into greater detail:

• MD5, SHA1: legacy broken algorithms, no particular performance optimizations have been performed
• SHA2: on-par with OpenSSL noasm+nohw, option to use SHAEXT when available but currently not part of gh-99108: Import SHA2-224 and SHA2-256 from HACL* #99109 -- happy to do that in a followup PR
• SHA3: a few low-hanging fruits on our side to make performance better, happy to work on that if this is what it takes for Python to integrate it
• Blake2: regular portable C, AVX and AVX2 versions, just like the reference implementation; same as SHA3, probably needs a few performance tweaks before integrating.

Hope this helps. As you said, this kind of change is a first step in the right direction.

[gpshead]

Alright, the first PR is in. Checkbox time:

• 2a) The initial HACL* SHA2 sha256 and sha224 implementation PR has been merged.
• 2b) SHA384 & SHA512 support
• 3) SHA3 support
• SHA1 and MD5
• HMAC for the above
• is Blake2b competitive? It'll need a performance comparison as we currently ship blake2 code that from upstream blake2 that includes at least amd64 sse4.1 asm optimizations.

[msprotz]

Great! sha384/sha512 is a no-brainer and I'll send a followup PR very soon. We have SHA3 as well, so I can send that in, too, with the caveat that we have a few performance optimizations for sha3 in the works, so we can either wait for those to land in HACL* then submit the Python PR, or first land SHA3 in Python, then send a followup PR to refresh the HACL* code once the performance tweaks have landed. Happy to hear your thoughts on this.

[gpshead]

Given that the SHA3 implementation we currently ship is a tiny poor performing one, no need to wait. I expect we'll pull in updates to the HACL* implementations as needed in the future when there is a motivating reason.

[msprotz]

@gpshead I'll let you check MD5/SHA1 in the checklist above... quick question: what is the timeline for landing sha3? it requires a little bit of work on my side and I'll be traveling all March, so ideally I would submit the SHA3 PR in April. But if it's a dealbreaker because of e.g. the Python release schedule, I can scramble to try to submit it before then. Let me know.

[gpshead]

So long as we can get it committed before 3.12beta1 at the beginning of May (see https://peps.python.org/pep-0693/) we're good. So April for that is fine by me. No need to scramble.

[encukou]

CPython now fails to build on x86 Debian, see: https://buildbot.python.org/#/builders/1244/builds/3176

[msprotz]

Ok, I'm surprised this wasn't caught earlier. Thanks for reporting.

We could either disable vectorized versions on x86 builds (i.e. edit autoconf), or fix the vectorized headers so that they also work for an x86 toolchain (i.e. relax this ifdef to also work on x86: https://github.com/python/cpython/blob/main/Modules/_hacl/libintvector.h#L22)

Maybe you could try the latter and see if that would fix the Debian build? (I don't have a Debian x86 handy.) Thanks.

[encukou]

I don't have it handy either, but if you make a PR, I can ask Buildbot to test it.

[gpshead]

Not sure how we missed this before; I believe 32-bit x86 should have access to at least SSE4.2. I've never looked to see if more recent additions like AVX2 or SHA NI are available in 32-bit mode or not. Test changing that build conditional in a PR and we'll find out.

It is a legacy platform so if we wind up just leaving the accelerated instructions turned off there, no big deal.

[picnixz]

FYI: I'm currently working on adding HACL* HMAC implementation for the known hash functions (SHA1/2 + blake2b/2s). There are certain limitations on the input data (the length of the inputs is expected to fit on uint32_t values but any object supporting the buffer protocol stores its length as ssize_t values, which may be much larger).

The portage is quite straightforward since everything operates on uint8_t arrays and I can just pass the underlying buffer as is (modulo some pre-processing and post-processing). I'm planning to benchmark the results to see whether we lose performances or not. Should I proceed further or should I wait for HACL to add support for other hash functions?

[gpshead]

I'd say go ahead and do it, no need to wait for others.

[msprotz]

Also there's a macro we added for the discrepancy between uint32_t and ssize_t so you might be able to reuse that.

Which hash algorithms are you missing? CC @R1kM

[picnixz]

I expected SHA-3 to be supported as well since we have a sha3 module (md5 could have been supported but I don't think it's worth it).

[msprotz]

Which variants do you need? Is there a link towards the expected API?

[picnixz]

Python's HMAC expects any algorithm that can be passed to hashlib.new (see https://docs.python.org/3/library/hmac.html#hmac.new). So:

• md5 (not supported)
• sha1 (ok)
• sha224 (not supported)
• sha{256,384,512} (ok)
• sha3_{224,256,384,512} (not supported)

I'm using the Hacl_HMAC_compute_* functions in https://github.com/hacl-star/hacl-star/blob/main/dist/portable-gcc-compatible/Hacl_HMAC.h. Should I use another API?

---

Technically, all the names that are in hashlib.algorithms_available should be available. But it's not really pressing as gp said. If HACL does not support a specific algorithm yet, we'll just fallback to the one that we already used.

[gpshead]

It's perfectly fine for Python to fall back to the existing implementation when accelerated HMAC does not exist. It's a nice to have for the most widely used variants.

[picnixz]

Great! I'll probably have something by the end of next week (I don't have much time in the next few days).

[msprotz]

This was fairly easy to add and @R1kM and I just have a PR (see above) that adds all of the required algorithms. We'll merge as soon as the CI comes back green and then you'll be able to pull from that directly.

Could you confirm this completely eliminates the need for fallback implementations? Thanks!

[picnixz]

Could you confirm this completely eliminates the need for fallback implementations

I think it should completely eliminates those needs. I can confirm it tomorrow or when I'll submit the PR but I think this should be good. Thank you for your quick reply!

[picnixz]

FTR: As mentioned in #72570, not supporting HMAC+SHAKE was deliberate but we'll probably need to improve the docs for that as well (since it only says "any name accepted by hashlib.new()"). (well, the current implementation works for sha3 family although keccak-based hash functions are already protected against LE-attacks).