Sled: Use SHA3-256 for checksum

[ckaran]

As of release 0.31.0, sled is using the CRC32 checksum for the checksum value. This is quite weak. Would you consider upgrading the SHA3 family of functions? I'd suggest either (SHA3-256)[https://docs.rs/sha3/0.8.2/sha3/struct.Sha3_256.html] or (SHA3-512)[https://docs.rs/sha3/0.8.2/sha3/struct.Sha3_512.html].

[spacejam]

@ckaran the purpose of the crc32 is to check corruption on each message in the log, without adding unnecessary space or computational burdens. How does the best pure-rust sha3-32 compare to crc32fast in terms of throughput and error checking?

[ckaran]

How does the best pure-rust sha3-32 compare to crc32fast in terms of throughput and error checking?

I don't know how fast it will be, but it should be fast enough that disk I/O should be the bottleneck in all cases. For databases that fit completely within memory and are never written to disk crc32fast should be faster. However, you really need to do profiling to really decide; I believe that the speed difference will be minuscule, and that repeated runs will show that the variance between runs for all tasks exceeds the costs of SHA3-256.

As for error checking, it is well suited for it. SHA3 is the latest in the SHA family of cryptographic hash algorithms. Put simply, cryptographic hash functions are designed to detect not only random mutations like corruptions, but also deliberate attempts at surreptitiously modifying what they are hashing. Used properly, it means that a person can share a sled database on the internet along with the SHA hash, which will allow others to detect if the database was modified somewhere along the way.

If you're worried about speed though, you could change the API to something like the following:

#[non_exhaustive]
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub enum ChecksumType {
    CRC32,
    SHA3_256
}

pub fn checksum(&self, checksum_type: ChecksumType) -> Result<Vec<u8>>;

That will let the end user decide what they want to do. Alternatively, you could do something like this:

use std::sync::{Mutex, Arc};

// This comes from the [digest](https://crates.io/crates/digest) crate
use digest::DynDigest;

pub fn checksum(&self, hasher: Arc<Mutex<dyn DynDigest>>) -> Result<Vec<u8>>;

This lets the end user decide what sort of checksum they want to use, offloading the trade-offs between speed and security to them. It also means that you don't have to keep up with what the latest and greatest hash functions are, leaving you to concentrate on the core of sled (which AFAIK is not to be doing checksums or maintaining a cryptographic hash library).

[Licenser]

I don't know how fast it will be, but it should be fast enough that disk I/O should be the bottleneck in all cases. For databases that fit completely within memory and are never written to disk crc32fast should be faster. However, you really need to do profiling to really decide; I believe that the speed difference will be minuscule, and that repeated runs will show that the variance between runs for all tasks exceeds the costs of SHA3-256.

ZFS uses sha256 as a checksumming mechanism and I've observed multiple occasions where this lead to the CPU turning into the bottleneck and more where CPU usage raised to a significant degree - which at least to me is not a desirable situation.

The goals of cryptographic hashes and checksums are quite different too, while a cryptographic algorithm does cover the requirements for a checksum it also isn't designed to be fast - at times even the opposite to make brute force attacks harder. It's also not a concern for a checksum if it is possible to obtain information about the inputs from its output.

Last but not least with sled also aiming for mobile systems it's worth considering that no optimized versions of any sha algorithm will exist for a while, rust has no (or only extremely limited) support for NEON so any kind of vectorization can't be taken advantage of (this applies to crc32fast as well).

I'm curious what's the desired guarantee that crc32 doesn't offer?

[spacejam]

I would consider changing to some other algo if it improves error detection capabilities in a way that seems to be worth the throughput impacts.

I saw that some sha3 people recommend the kangaroo 12 algorithm, although I don't know how this implementation varies compared to others.

diff --git a/Cargo.toml b/Cargo.toml
index 6b95aa70..1cb4d7dd 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -49,6 +49,7 @@ log = "0.4.8"
 parking_lot = "0.10.0"
 color-backtrace = {version = "0.3.0", optional = true }
 rio = { version = "0.9.2", optional = true }
+tiny-keccak = { version = "2.0.0", features = ["sha3", "k12"] }

 [target.'cfg(any(target_os = "linux", target_os = "macos", target_os="windows"))'.dependencies]
 fs2 = "0.4.3"
diff --git a/src/lib.rs b/src/lib.rs
index 72cbdbbe..065c30ea 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -302,10 +302,16 @@ fn crc32(buf: &[u8]) -> u32 {
 }

 fn calculate_message_crc32(header: &[u8], body: &[u8]) -> u32 {
+    /*
     let mut hasher = crc32fast::Hasher::new();
+    */
+    use tiny_keccak::Hasher;
+    let mut hasher = tiny_keccak::KangarooTwelve::new("");
     hasher.update(body);
     hasher.update(&header[4..]);
-    let crc32 = hasher.finalize();
+    let mut output = [0; 4]; // (woohoo sponge algorithms let you choose the output size)
+    hasher.finalize(&mut output);
+    let crc32 = u32::from_le_bytes(output);
     crc32 ^ 0xFFFF_FFFF
 }

run from the benchmarks/stress2 directory:
rm -rf default.sled; cargo flamegraph --features=no_metrics -- --total-ops=100000000 --entries=10240 --set-prop=1000000000 --threads=12 --key-len=4 --val-len=0

initial glance at throughput impact:

• crc32fast (without the above patch) writes 100m keys (overwriting the same 10240 keys over and over again) in 45 seconds, writing about 2.2 million items per second on 12 cores on my laptop.
• kagaroo12 via the tiny-keccak crate version 2.0.1 (with the above patch applied) completes the same workload in 53 seconds, writing about 1.9 million items per second on 12 cores on my laptop.

I ran the workloads 3 times and it seems consistent across runs.

Notes on workload characteristics:

• sled crc32's every message written. a message gets written to the log every time any tree node changes in any way. usually it writes a small node delta, like (key xxx added to node 2112 with value yyyy, or deleted key z from node 43242432) and every 10 writes for a node it will replace the fragments with a larger rewrite, which also gets the crc32
• a new hasher is created for every message, rather than hashing entire 8mb segments. this allows the system to detect runtime errors when reading data that was paged out of cache earlier and corrupted at some point since then.
• lots of new hashers, generally small buffers being hashed (depends largely on the size of the keys and values being written into the system)

I'm happy to answer any questions about the writepath or readpath if it helps us to find a specific error detection algorithm that is more effective for this system's constraints.

Personal experience: benchmarking rocksdb often shows big bottlenecks in their crc checking code, usually caused by failing to compile the system with SIMD support, which is a fairly common situation due to the build system complexity. One thing I like about crc32fast is that it seems pretty good at runtime feature detection, to reduce the chances of someone accidentally disabling SIMD by not having some random preexisting library installed on their system etc...

So, the first thing to consider is that this is not 0 impact. Does this improve the error detection rate by a proportional amount? I don't know much about information theory, but I'm happy to learn if you can point to some good concise summaries of findings to try to actually evaluate what the benefits or downsides are. However, without some evidence that sha3 significantly improves error detection capabilities, I am inclined to turn it down due to the throughput loss for the system.

[spacejam]

@tarcieri what is your opinion on this? I'm definitely not qualified to evaluate the strength of sha3 as a checksum vs crc32fast.

[tarcieri]

Absent an attacker, CRC is a better choice than a cryptographic hash function, because it will be considerably faster and is also guaranteed to detect bit flips 100% of the time. CRC with a proper polynomial can even always reliably detect 2-bit flips (or more).

The reason you'd want to use a cryptographic hash function is if you have a threat model that involves an attacker either attempting to preimage messages from their checksums, or collide checksums deliberately. If you don't and merely want to detect bitrot, CRC is the better choice, namely for performance reasons, but also because cryptographic hash functions are random oracles which by design must have some (vanishingly small) probability of failing to detect bitflips in order to produce uniformly random outputs.

Regarding SHA3-256, it's so slow even the Keccak team that developed it doesn't recommend it (due to overspecified NIST SHA-3 competition security margins). They would instead recommend you use SHAKE128 for this purpose.

[spacejam]

Thanks for the perspective, Tony!

The same workload, using tiny_keccak::Shake::v128 instead of KangarooTwelve, takes 52 seconds and hits 1.92 million writes/second.

So, it seems as though the error detection may actually be worse, and the performance is worse. I'd be interested in verifying the properties of crc32fast to see if the polynomial in use can detect 2, but that's out of scope.

I'm going to close this issue for now, but in general I'm quite interested in changing the approach used in sled if we can improve the error detection rate in a way that has an improvement that is worth any performance impact (ideally better in both before we hit 1.0, when this will become more expensive to change).

Thanks for starting this conversation, @ckaran :)

[tarcieri]

@spacejam you might check out these CRC polynomial tables which are based on this paper if you'd like to fine-tune your usage of CRC (e.g. to guarantee errors are detected for a given hamming distance).

[divergentdave]

It looks like crc32fast uses the polynomial 0xedb88320, which is the same as in Ethernet and a variety of other applications. The CRC Zoo says this polynomial is optimal for Hamming distances of 3 and has "good performance" for Hamming distances of 2.

[ckaran]

@tarcieri said:

The reason you'd want to use a cryptographic hash function is if you have a threat model that involves an attacker either attempting to preimage messages from their checksums, or collide checksums deliberately.

Actually, deliberate collisions was the model I had in mind! However, if this isn't what everyone is concerned with, then CRC32 is good enough.

@spacejam said:

• a new hasher is created for every message, rather than hashing entire 8mb segments. this allows the system to detect runtime errors when reading data that was paged out of cache earlier and corrupted at some point since then.
• lots of new hashers, generally small buffers being hashed (depends largely on the size of the keys and values being written into the system)

If this is typical of how the hashers will be used, then even my thought of:

use std::sync::{Mutex, Arc};

// This comes from the [digest](https://crates.io/crates/digest) crate
use digest::DynDigest;

pub fn checksum(&self, hasher: Arc<Mutex<dyn DynDigest>>) -> Result<Vec<u8>>;

could be horribly slow because of all the churn in creating/destroying hashers (again, the only way to know for certain would be to profile it).

So the real question is 'why do I want this?' It was for precisely the reason that @tarcieri mentioned earlier; I'm concerned about outside attackers trying to mutate my database without me knowing about it. If I understand how sled works correctly, trying to use an external tool to hash it won't work because the garbage collection thread could be running and mutating a database, even if I have the database open in read-only mode. That makes detection more difficult.

[Licenser]

So the real question is 'why do I want this?' It was for precisely the reason that @tarcieri mentioned earlier; I'm concerned about outside attackers trying to mutate my database without me knowing about it.

Given that they are stored in the same file and do not include a secret would a cryptographic hash function even affect the attack vector? If an attack can modify the file, they can modify the hash. If that's your concern I would think you need a full signature with an external secret at least.

[spacejam]

Thanks for looking into that, @divergentdave!

@ckaran the way sled calculates this is pretty simple. You may be able to achieve what you want with code like this:

let mut hasher = tiny_keccak::Shake::v128();
let tree_names = db.tree_names()?;
for tree_name in tree_names {
  hasher.update(&tree_name);
  let tree = db.open(&tree_name)?;
  let mut iter = tree.iter();
  while let Some(Ok((key, value))) = iter.next() {
    hasher.update(key);
    hasher.update(value);
  }
}
let mut output = [0; 16];
hasher.finalize(&mut output);
let hash = u128::from_le_bytes(output);

@Licenser yeah, it would need to be stored OOB.

[ckaran]

@Licenser wrote:

Given that they are stored in the same file and do not include a secret would a cryptographic hash function even affect the attack vector?

I'm afraid that there may have been a miscommunication; I would not be storing the checksum in the database itself. As far as I know, the only way to do that would involve cryptographically signing the checksum, and then storing that in the database, similar to what digital signatures normally do. This requires some kind of public key infrastructure so that anyone that wants to verify the signature is able to download the keys securely, which may or may not be possible (@tarcieri is this all correct?). I was going for the really simply approach, like what some websites do now (e.g. ubuntu mate lists a bunch of SHA-256 checksums for their products). That is, you get a cert for your server, ensure you're using https with the latest and greatest security protocols, and trust that will be enough for anyone that wants to verify that they are getting the database's real digest. That will allow people to torrent the database (or get it in some other fast, but possible insecure manner), while ensuring that they can verify that the database hasn't been tampered with.

@spacejam wrote:

let mut hasher = tiny_keccak::Shake::v128();
let tree_names = db.tree_names()?;
for tree_name in tree_names {
 hasher.update(&tree_name);
 let tree = db.open(&tree_name)?;
 let mut iter = tree.iter();
 while let Some(Ok((key, value))) = iter.next() {
   hasher.update(key);
   hasher.update(value);
 }
}
let mut output = [0; 16];
hasher.finalize(&mut output);
let hash = u128::from_le_bytes(output);

Works for me! Thanks!

Hmmm... do you have a place where you keep snippets of code like this around? So that others are able to see ways of solving their problems? This would be a good little snippet to put into there...

[spacejam]

@ckaran I've been thinking about writing a little "sled cookbook" that talks about patterns for using sled. It's probably time to create a "recipes" section on sled.rs

[ckaran]

@spacejam That would be fantastic! I've been thinking about interesting patterns that can be done using sled, and (assuming you're willing to accept PRs for it), I'd like to contribute some to the cookbook (pending my employer's approval).