2024.07 Vol.2

I am working on a patch to bring some of the lower level cryptography from BIP324 into the rust-bitcoin repository. Specifically, the ChaCha20 stream cipher and the Poly1305 authenticator which are often paired together to form a ChaCha20Poly1305 “Authenticated Encryption with Associated Data” (AEAD) scheme. In the short term, it would be nice to harden these implementations and make more of the Bitcoin ecosystem “dark” using BIP324. In the long term, I think there are a lot of higher level application communication channels in the ecosystem which could use this AEAD outside of just BIP324. It would be great to make them accessible here on the “ground floor” of rust-bitcoin.

Not surprisingly, this code needs to be solid. Cryptographic code generally has a much higher bar since there are so many ways to accidentally “leak” information. This is a nice little intro blog on a subset of the things you have to now be looking out for writing cryptographic code. One gets the impression that it is almost impossible to protect against every type of attack, there is no exhaustive static analyzer to check everything. So your best weapon might just be keeping the code as clear and concise as possible, which I believe is achievable in this case. Here are some improvements I made to secret handling, performance, and the public interface of the library.

Secret Handling

Instead of hanging on to the secret values as just byte arrays, wrap them up in newtypes. This is a Rust pattern which purposefully limits a type’s interface. If a developer wants to expose some functionality of the wrapped typed, they need to explicitly wire it up with some glue code. This is perfect for secret values where we want every type of access to be extremely auditable to make sure no information is being leaked.

/// A 256 bit secret session key shared by the parties communicating.
#[derive(Clone, Copy, Debug)]
pub struct SessionKey([u8; 32]);

impl SessionKey {
    /// Create a new session key.
    pub fn new(key: [u8; 32]) -> Self {
        SessionKey(key)
    }
}
 

Wrap the 32-byte session key in a new type SessionKey.

Performance

Based on some feedback from Matt Corallo, looked into seeing if some tweaks in the cipher code could influence the Rust compiler to output more performant code. The Godbolt tool (fun fact, the creator just has a really cool last name) is great for analyzing the generated assembly. To minimize variables, I just looked at Rust version 1.56, the MSRV of rust-bitcoin, with an optimization level of 3. Although it was interesting seeing how lowering the optimization level or bumping the Rust version influenced the output as expected.

Matt was specifically concerned with the Rust compiler generating SSE (Streaming SIMD Extensions) instructions, which are a type of SIMD (Single Instruction Multiple Data) operations supported by modern CPUs. SIMD is parallelism at the register level, and it isn’t too hard to think of modern scenarios where you know you are going to be performing the same instruction on different sets of data at the same time. Graphics are a clear use case…and so is cryptography, where algorithms usually involve “rounds” of instructions and “words” of data. The idea of SIMD has been around since the 60s, while SSE was introduced in ‘99 by Intel and adopted by other manufactures like AMD. The “Streaming” part of the name appears to mostly be marketing jumbo, I don’t know why these instructions won out over others though, maybe just Intel forcing it?

Anyways, the idea is pretty simple, but how does a programmer use these special instructions over normal ones? Well, ideally the compiler (in my case, rustc) recognizes code which would benefit from the SIMD instructions and outputs assembly for the CPU which uses them instead. If the compiler isn’t able to pick up on a use case, one can always build the assembly by hand. That seems like a very daunting task to me, in just about every way, so I would like to avoid if at all possible. Theoretically Rust is all about the programming giving the compiler as much information as possible to work with (e.g. lifetimes). And luckily, analyzing the initial version of the patch with Godbolt show that it is already leveraging some SIMD instructions (probably due to using Rust 1.56 and not the older versions Matt was using back when he wrote the LDK version).

ITERATION             LINES

Original              1111
With Secret newtype   1228
With State newtype    1282

Results on Rust 1.56 with optimization level 3.

And going just off the number of lines of assembly, it appears I lost ground adding in some newtypes. I don’t have great intuition on how important that number is though, but my gut says the clarity of the newtypes is worth it. For now, I am going to hold off on attempting to squeeze any more juice out of these instructions.

Public Interface

The module introduced in the patch consists of three parts: the ChaCha20 stream cipher, the Poly1305 MAC, and those two combined to form the AEAD. The AEAD interface is very small for now, perhaps too specific to the BIP324 use case. The same can be said for ChaCha20 stream cipher. These are new cryptographic primitives for the Bitcoin ecosystem so there is not a lot of prior interfaces to influence them. The same cannot be said for the Poly1305 MAC which opened up some interesting questions.

Poly1305 is a hash function, and there exists a handful of these in the Bitcoin ecosystem such as RIPEMD160 or SHA256. Unsurprisingly, rust-bitcoin created an abstraction across these hash implementations, so they are more “plug and play” friendly in higher level schemes like HMACs. Ideally, the Poly1305 implementation can be tweaked to satisfy this existing hash interface. I noticed that Poly1305 is very similar to the existing Sip Hash 2-4, and figured I could use it as a reference (the big difference between the two is Poly1305 is less performant, but is cryptographically secure, so better for some scenarios). Poly1305 and SipHash are both keyed hash functions, as opposed to the rest of the hash functions in the ecosystem which are un-keyed. An un-keyed function only takes the data to be hashed and spits out a hash. A keyed function can be viewed as a family of hash functions, each key corresponding to a function, so before you can hash some data you first need to choose a function. This extra key requirement doesn’t actually play to nice with rust-bitcoin’s current hash interface, and the callout on this distinction lead @Kixunil to a possible vulnerability in rust-bitcoin’s SipHash. So before landing the AEAD patch, I first need to clean up this un-keyed vs. keyed hash interface in rust-bitcoin.