Forem: CipherStash

Fixing a 1-in-256 bug in CLWW order-preserving encryption

Dan Draper — Sat, 25 Apr 2026 04:32:10 +0000

Many databases let you sort and range-query encrypted data using order-preserving encryption (OPE): a scheme where ciphertext bytes compare in the same order as their plaintexts, so standard B-tree indexes and ORDER BY clauses Just Work. A well-known construction is Chenette-Lewi-Weis-Wu (CLWW) from 2015 — small, fast, and widely deployed. The paper gives an order-revealing scheme with a custom comparator, and notes in passing that the same ciphertext bytes can be compared lexicographically to yield an order-preserving scheme as a side benefit.

But that reinterpretation is only almost right. Roughly 1 in 256 comparisons disagrees with the true plaintext order. In this post I'll walk through why, with a worked example, and show how two small changes to the encoding eliminate the residual — at the cost of one extra byte per ciphertext and a single arithmetic pass.

This post walks through the construction and the intuition. If you want the full derivation — triangular probability distributions, the signal/noise argument, empirical verification, and a discussion of what the scheme leaks — head over to the companion engineering note: Exact OPE from CLWW ORE via Backward Carry + MSB-Bit Placement.

Why order-preserving encryption?

When you encrypt a column in a database with a standard symmetric cipher — AES-GCM, ChaCha20, pick your favourite — you get great confidentiality. You also lose every other useful property of the column. The ciphertext byte order has nothing to do with the plaintext order, so your B-tree index, your ORDER BY clauses, and your range queries (WHERE price BETWEEN 100 AND 500) stop working entirely.

Order-preserving encryption fixes this, at a cost. In an OPE scheme, if plaintext x < y, then enc(x) < enc(y) under the standard comparison your database already understands — usually byte-lexicographic compare, i.e. memcmp. Drop these ciphertexts into any off-the-shelf sorted index and range scans work out of the box. No custom comparator. No query-rewriting middleware.

To make that concrete, here's a handful of 8-bit integer plaintexts alongside illustrative ciphertexts — the bytes are made up rather than produced by running the scheme, but they follow its rules (9 bytes each, reserved leading byte, shared prefix where the high-order plaintext bits agree, first differing byte offset by ~128). Only the first 6 of 9 bytes are shown:

Plaintext	Ciphertext (hex)
`7`	`00 5e 38 12 9a 2c …`
`42`	`00 5e 38 92 3f c4 …`
`100`	`00 5e b8 4c 92 3f …`
`200`	`00 de 7a 23 51 8c …`
`250`	`00 de 7a a3 ff 22 …`

Plaintexts in ascending order produce ciphertexts in ascending byte-lexicographic order: memcmp over any two rows returns the same verdict as comparing the plaintexts directly. Drop these into a B-tree index and ORDER BY / range queries work out of the box. You can also see the scheme's leakage profile hiding in plain sight — the closer two plaintexts' high-order bits are, the more leading bytes their ciphertexts share. More on that in a minute.

The cost is leakage. A scheme that preserves order also leaks order (tautologically), and typically a bit more — usually some information about the common prefix of two plaintexts. For many workloads that tradeoff is acceptable; for others you'd reach for a construction with a tighter leakage profile, like the Lewi–Wu Block ORE scheme — which is what CipherStash uses for most production paths, exposed to Postgres through EQL. Block ORE needs a custom comparator, which in Postgres means registering a custom operator class via CREATE OPERATOR CLASS / CREATE OPERATOR FAMILY. Some managed platforms permit those statements without superuser (AWS RDS does, which is why EQL runs there today); others don't (Supabase, as of writing). When you're on a platform in the latter category, CLWW OPE is the next best thing — standard lex-compare on the ciphertext works with any stock B-tree index, no custom operator class required. I'll touch on what CLWW specifically leaks toward the end.

CLWW in 60 seconds

CLWW is a bit-by-bit ORE scheme. For an n-bit plaintext p = b₀ b₁ … bₙ₋₁ (MSB-first), it produces an n-byte ciphertext. The construction feeds the plaintext bits through a keyed hash function one bit at a time — we'll model that keyed hash as a pseudorandom function (PRF), a function whose output is indistinguishable from uniform random bytes to anyone who doesn't have the key. In practice that's HMAC-SHA256, BLAKE3 in keyed mode, or similar; our implementation uses BLAKE3. At each step we pull one PRF byte and add the plaintext bit to it:

The arrows between the PRF boxes are the important part. PRFᵢ depends on all the plaintext bits b₀ … bᵢ₋₁ that came before it. So for two plaintexts X and Y that first differ at bit k:

At positions 0 through k, the PRF inputs are identical in both plaintexts, so PRFᵢ^X = PRFᵢ^Y.
At positions k+1 onward, the chain has diverged (one side saw bₖ = 0, the other saw bₖ = 1), so the PRFs look independent-random.

At the first differing byte itself, then, the ciphertexts differ by exactly b_k^Y − b_k^X, which is +1 or −1. The native CLWW comparator exploits this: find the first differing byte, check whether c_Y ≡ c_X + 1 (mod 256). If yes, X < Y; otherwise Y < X. Note the mod 256 in that check — we'll come back to it.

The paper's OPE reinterpretation — and the 1/256 bug

Section 3.2 of the CLWW paper observes that the ciphertext bytes agree up to the first differing byte, and at that byte one side is exactly one more than the other. So if you forget about the custom comparator and just sort the ciphertexts lexicographically, you'll usually get the right answer.

"Usually" is doing a lot of work there.

Consider X = 0 and Y = 1 as 8-bit plaintexts. Bits of X are 0000 0000; bits of Y are 0000 0001. The PRF chain for Y sees only zeros up to bit 6, so PRF₀ … PRF₇ are identical in both plaintexts. Every ciphertext byte agrees, except byte 7 — which encodes the one differing bit.

Now imagine PRF₇ = 0xFF. A 1-in-256 event.

Byte	PRF	X's bit	Y's bit	`c^X`	`c^Y`
0–6	`PRFᵢ`	0	0	`PRFᵢ`	`PRFᵢ`
7	`0xFF`	0	1	`0xFF`	`(0xFF + 1) mod 256 = 0x00`

Lex compare: bytes 0 through 6 agree, byte 7 has 0x00 on the Y side and 0xFF on the X side. The comparator says Y < X. The plaintext says Y > X. Wrong answer.

The CLWW comparator handles this case because its check is c_Y ≡ c_X + 1 (mod 256), which is true for (0xFF, 0x00) as well as for (0x42, 0x43). Lex compare doesn't have the mod-256 awareness — when the byte wraps around, the ordering flips.

Per-comparison error rate: 1/256 ≈ 3.9 × 10⁻³. For a range scan touching a few thousand ciphertexts, that's multiple mis-orderings per query. Unacceptable.

First fix: backward carry

Here's the key reframe: instead of thinking of the ciphertext as a byte stream, think of it as a big-endian integer. When PRFₖ + bₖ wraps past 256, we don't lose the +1 — we propagate it as an arithmetic carry to the byte on the left, exactly like schoolbook long addition. We reserve a leading byte at the top of the ciphertext to absorb any carry that makes it all the way up.

fn encrypt_ope_v1(K, p):
    hasher = keyed_hasher(K)

    # Pass 1: generate PRF bytes, record the plaintext bits.
    prfs = []; bits = []
    for bit in bits_msb_first(p):
        prfs.push(hasher.next_byte())
        bits.push(bit)
        hasher.update(bit)

    # Pass 2: compute P + B as an (n+1)-byte big-endian integer,
    # with a reserved leading byte that absorbs the final carry.
    out = [0] + prfs
    carry = 0
    for i in reversed(0..n):
        total      = out[i + 1] + bits[i] + carry
        out[i + 1] = total mod 256
        carry      = total >> 8       # always 0 or 1
    out[0] = carry
    return out

Comparison is plain byte-lex compare — no custom comparator required.

Let's replay the failing case. X = 0, Y = 1, PRF₇ = 0xFF. The ciphertext is now 9 bytes (one reserved + eight content).

X (all bits zero): pass 2 adds nothing and no carry propagates. c^X = [0, PRF₀, …, PRF₆, 0xFF].
Y (bit 7 = 1): at byte 8 we compute 0xFF + 1 + 0 = 0x100 → byte 8 becomes 0x00, carry out = 1. At byte 7 we compute PRF₆ + 0 + 1 = PRF₆ + 1, carry out = 0. Other bytes unchanged. c^Y = [0, PRF₀, …, PRF₅, PRF₆ + 1, 0x00].

Lex compare: c^X and c^Y agree through byte 6. At byte 7, c^X has PRF₆ and c^Y has PRF₆ + 1. Y is bigger — correctly. ✓

The +1 didn't disappear when the byte wrapped; it just moved one position to the left, where it reappears at the byte the lex comparator hits first.

But wait — this isn't exact

A big improvement, but it turns out this scheme is only almost right. The per-comparison error rate drops from ~1/256 to around 7.7 × 10⁻⁶ — about 500× better — but it's still not zero.

The residual is a signal/noise mismatch. At the first differing byte, the plaintext injects a +1 signal — but the backward carry coming up from the byte to its right can also swing the result by ±1. Signal and noise are the same order of magnitude, so in rare PRF configurations they cancel exactly and the two ciphertexts tie where the plaintexts don't. The full derivation — triangular distributions, tail probabilities, the small correction for the m = 2 case — lives in the engineering note.

The question is: can we kill the residual without making the ciphertext larger?

Second fix: place the bit at the MSB

The signal-vs-noise framing suggests the obvious move: make the signal bigger. We can't shrink the noise — ±1 per byte is intrinsic to how the carry works — but we can inject the plaintext bit at a higher-weight position within its byte.

Concretely: instead of adding +bit (which puts the signal at bit 0 of the byte, weight 1), add +bit · 128 (which puts it at bit 7, weight 128). Same ciphertext size. Same PRF chain. One line of code:

-    total = out[i + 1] + bits[i]       + carry
+    total = out[i + 1] + bits[i] * 128 + carry

The signal is now +128 at the first differing byte. The carry noise is still ±1. They can't cancel — lex compare resolves at the first differing byte by a margin of at least 127 (or, if that byte happens to wrap and the carry propagates one position left, at the byte before it, which sits at 256× the integer weight and so dominates anyway). The engineering note has the full case analysis.

Exact OPE. Verified empirically: 1 310 700 adjacent u16 pairs under 20 randomly sampled keys, zero ordering errors.

Wrap-up

Two small changes — a backward carry pass with a reserved byte, and placing the plaintext bit at the top bit of its byte rather than the bottom — turn CLWW's paper-suggested OPE reinterpretation from a ~1/256-wrong scheme into an exact one. Same number of PRF evaluations, one extra ciphertext byte, no custom comparator needed.

What this gives you: drop-in ciphertexts for any ordered index or sort operation, with ordering that matches plaintext ordering exactly.

What it doesn't give you: strict-ORE-level leakage hiding (the scheme leaks first-differing-bit position, same as CLWW ORE), and no decryption — for round-trip you pair the OPE ciphertext with an authenticated symmetric cipher like AES-GCM.

The implementation lives in our cllw-ore crate on crates.io, with a fuller derivation of the error rate and the exactness argument in the engineering note.

If you've got a production encrypted-database use case that needs order-preserving indexes — or you just enjoy small clean cryptographic primitives — I'd love to hear what you think.

Show Dev: Introducing Protect.js

Dan Draper — Fri, 14 Mar 2025 00:59:31 +0000

Protecting data that’s sensitive — such as personal health or financial information — is crucial to building applications that users trust. But getting access control right is a tricky business. Complex requirements and a plethora of tools, as well as performance considerations, can kill dev team productivity.

This is why we created Protect.js.

Protect turns data access control on its head by protecting data directly. Unlike complex, application-specific frameworks or hand-rolled tools, Protect.js makes building secure, data-driven applications simple so you can deliver services that users trust without slowing down delivery.

We rolled the crypto so you don’t have to

Security experts say you shouldn't roll your own crypto but it's ok, we've done the hard work for you.

Protect’s power comes from the strongest form of access control: encryption. Encryption is rarely considered for the fine-grained protection of data because it's hard to implement, slow, and doesn’t play nicely with other tools in the stack like identity providers or the database. That is, until today.

Based on the CipherStash encryption SDK and using our revolutionary key management service, ZeroKMS, Protect.js unlocks the power of encryption but without the hassle. Protect.js:

Works with any Node.js framework or ORM (like Next.js + Drizzle)
Is based on AES-256 encryption and uses formally-verified cryptography
Uses ZeroKMS key management that’s up to 14x faster than AWS KMS
Supports queries and sorting over encrypted data
Is so easy to use you can get started in ~under 15-minutes~

Encryption in use

You’ve probably heard of encryption at rest or in transit but these approaches are only part of the story when it comes to effective data protection.

At-rest and in-transit encryption leave critical gaps in your data’s defenses which can lead to vulnerabilities or accidental leaks and make it harder to reason about whether data is secure, especially when trying to convince customers or an auditor.

Protect.js uses encryption in use to protect data.
Sensitive data items, like individual email addresses remain protected right up until an authorized end-user needs to read them.
This limits the “surface area” of a potential attack and reduces risk as well as making it easier to demonstrate that data is secure.

To protect a sensitive database field with Protect.js, you do so via a protected schema definition. To specify that the email column of the users table should be encrypted:

// src/protect/schema.ts
import { csTable, csColumn } from '@cipherstash/protect'

export const users = csTable('users', {
  email: csColumn('email'),
})

Then, to encrypt a value, pass any schemas you've defined to protect and call encrypt:

// src/protect/client.ts
import { protect } from '@cipherstash/protect'
import { users } from './schema'

// Do this once when your app starts
export const protectClient = await protect(users)

// Encrypt an email address for a configured column and table
const encryptResult = await protectClient.encrypt(
  'secret@squirrel.example', {
  column: users.email,
  table: users,
})

Check out the Protect.js getting started guide if you want to jump right into the code. Or read on to learn about some of Protect.js's other capabilities!

Key management

Encryption in use is similar to the idea of "field" or "row-level" encryption. One of the main differences is in how keys are managed: Encryption in use ensures each value is encrypted by a unique data key.

I spoke about why this is a good thing at BSides SF in 2024.

Even the best encryption tech is useless without good key management.
When using traditional field-level encryption in a web-based application you have 2 options available:

A local key (fast but less secure)
A cloud-based key-management service (secure but slow)

A local key is a secret encryption key (usually stored as an environment variable). This approach uses the same key to encrypt all data in the application and comes with some nasty security problems. For starters, if an adversary obtains the key, they can use it to access all of the data in your system.

If you need to update ("rotate") the key you'll need to re-encrypt everything. More subtle problems can arise too. AES keys are vulnerable to key wear out which means that if a single key is used to encrypt more than about 4GB, previously encrypted values can be used to recover the key itself.

Key Management Services (KMS) like AWS KMS or Azure KeyVault mitigate these problems with a technique called envelope encryption. Instead of storing an encryption key in an application environment variable, a root_key is stored within the cloud provider's infrastructure inside a device called a Hardware Security Module (HSM).

To perform an encryption operation, clients must make a request to the key service which returns a randomly generated data key along with a copy that has itself been encrypted using the root key (called a wrapped data key). The data key is used to encrypt the target value (such as an email address) and discarded with the result stored in the database with the wrapped data key.

Envelope encryption is a big security improvement over a local key but has a major drawback. Because each data key requires a separate HTTP request, performance can be abysmal. To get around this, cloud providers added support for data key caching.

However, when caching data-keys many of the same problems as using a local-key can arise. Use a single data key to encrypt too much data and you can run into wear-out issues. A compromise of the cache used to store data-keys could lead to a pretty significant data breach.

Data key caching also means that there is no-longer a 1-to-1 mapping between a data-key and the specific value it was used to encrypt which means we miss out on powerful access-control and auditing capabilities. We'll cover these in a moment!

Security or performance: why not both?

To address these problems, Protect.js uses ZeroKMS, which eliminates the performance-security tradeoffs common with traditional KMS. Instead of a single root key, ZeroKMS uses composable pairs of keys to generate data keys. One half of the pair, the client key is stored by your application and the other, stored by ZeroKMS.

This technique has a number of security benefits, but most relevant to this discussion is that it now makes it safe to do bulk requests for data keys. ZeroKMS can generate up to 10,000 data keys in a single operation.

To demonstrate the impact on performance of this approach, we've shared some benchmarks below of Protect.js running in a Next.js application with Postgres and Drizzle. Each request fetches 10 user records from a table that have 2 fields encrypted (email and address).

The first report shows AWS KMS performance without data-key caching.
It managed an average of 27 and a peak of 44 requests per second.

ZeroKMS managed 7 times the average and 14 times the peak performance of AWS KMS, with a peak rate of 615 requests/second.

The Apdex scores are particularly telling:

In a future post, we'll do a deep dive on how we ran these benchmarks as well as some surprising results.

Rust you can trust

Under the hood, Protect.js is written in Rust.
We chose Rust because it's incredibly fast, memory efficient, and has some unique security properties, particularly when it comes to cryptography. Rust is the only mainstream compiled language that is also memory safe without the need for a garbage collector.
This eliminates the most common type of security vulnerabilities: memory bugs.

Computerphile has a great video about Rust and memory safety if you'd like to learn more.

Quantum resistant, verified cryptography

The low-level cryptographic components of Protect.js use aws-lc-rs, Amazon’s formally verified cryptography library. Used to mathematically prove the correctness of software, formal verification is the gold-standard in high-assurance, secure-by-design systems. Protect.js is also designed to be resistant to attacks by a quantum computer should such devices ever become practical.

Vitamins for your crypto

At CipherStash, we’re also working on formal verification for other parts of our stack and have created an open source framework, called Vitamin C. Vitamin C is like vitamins for cryptography. It simplifies the writing of high-assurance software by providing secure, highly-scrutinised and tested reusable building blocks.

SOC 2 compliant

CipherStash, including the ZeroKMS key service is SOC 2 compliant.
You can learn more in our trust centre.

What’s coming next?

We've barely scratched the surface in this post but over the coming weeks we'll share more about what Protect.js can do to make effective data protection easy.

Granular control with identity-based context locking
Searchable encryption with Protect.js and when to use it
Deep dives on the internals of Protect.js and ZeroKMS
More benchmarks, code samples, and tutorials for specific use-cases

Protect sensitive data in just 15 minutes

All there is to do now is give Protect.js a try!
Don't forget to star us on Github, too :)

Verifying Rust Zeroize with Assembly...including portable SIMD

Dan Draper — Wed, 10 Jan 2024 12:31:13 +0000

When writing code that deals with sensitive information like passwords or payment data, it's important to zeroize memory when you're done with it. Failing to do so can leave sensitive data in memory even after the program is terminated and even end up on disk when the computer uses swap.

In this post, I'll explain what zeroizing is, why and when you should use it and how to implement it correctly.

What is Zeroizing?

When a sensitive value, say an encryption key, is used in a program it must be stored in memory: either on the stack or in the heap. In either case, even after memory is dropped (or freed, garbage collected etc), the contents may still lurk in the computer - even beyond the life of the program. It is therefore important that such data be cleared before the memory is dropped so that secrets are not leaked to unexpected places.

Why is Zeroizing important?

The code below demonstrates that even after it has been dropped, data stored in a given memory location can still be read.

use std::mem;
use std::ptr;

struct SensitiveData {
    data: [u8; 16],  // Representing sensitive data
}

fn main() {
    // Some mock sensitive data
    let sensitive = SensitiveData { data: [42; 16] };

    let data_location = &sensitive.data as *const u8;
    mem::drop(sensitive);

    // Attempt to read the data back
    // after it has been dropped
    let mut recovered_data = [0u8; 16];
    unsafe {
        ptr::copy_nonoverlapping(
          data_location,
          recovered_data.as_mut_ptr(),
          16
        );
    }

    println!("Recovered data: {:?}", recovered_data);
}

The code calls creates a mock SensitiveData value and then calls mem::drop directly instead of letting Rust do it when the value goes out of scope. Before doing so, it stores the location of the memory that was used for the data as a raw pointer and then uses that location to read back the original contents of the memory.

While this is a very simple example, it illustrates that just because memory is dropped, data still exists in the system even if the program doesn't care about it anymore.

How to Zeroize

Zeroizing memory is surprisingly very tricky. Even Rust, famous for memory safety has no formal built-in way to do this. The main challenge is stopping the compiler from optimizing away code that it thinks is not necessary.

Let's look at an example.

// lib.rs (simd_zeroize)
pub struct SafeArray([u32; 4]);

impl SafeArray {
    pub fn consume_and_sum(self) -> u32 {
        // Careful! This could overflow!
        self.0.into_iter().sum()
    }
}

In this code, I have a type called SafeArray which just wraps a 4-element array of u32. I've created my own type so that I can implement the Drop trait in a moment.

My type has a single function which consumes self and sums all elements as a u32. Because self is consumed but not returned it will be dropped. (Be aware that this code could easily cause an addition overflow but I'm intentionally keeping it very simple to limit how much assembly code is generated).

Inspecting the compiled code

To really understand what's going on here we can look at the compiled assembly code. I'm working on a Mac and can do this using the objdump tool. Compiler Explorer is also a handy tool but doesn't seem to support Arm assembly which is what Rust will use when compiling on Apple Silicon.

Before looking at the assembly, the code must be compiled in release mode as this will ensure that all of the compiler's target optimizations are applied.

cargo build --release

Then I'll use objdump to disassemble the machine code into Arm64 ASM:

objdump -d target/debug/libsimd_zeroize.rlib > assembly.s

Here's the assembly.s file:

0000000000000000 <ltmp0>:
       0: 00 00 c0 3d   ldr q0, [x0]
       4: 00 b8 b1 4e   addv.4s s0, v0
       8: 00 00 26 1e   fmov    w0, s0
       c: c0 03 5f d6   ret

Don't worry if you don't know or understand assembly code, we'll focus just on specific instructions for this exercise.

The line starting with 0000000000000000 is the label Rust has given to the consume_and_sum method and the actual machine instructions are contained below it. These steps load the values from a memory address stored in x0 into a register called q0, add all 4 values in one step (using the vectorized addv.4s instruction), move the result into an output register and return.

Registers are what the CPU uses to perform most operations so this code loads data from memory into the register to that an operation can be performed.

Implementing Drop

Let's see what happens when we try to implement zeroization when our SafeArray is dropped.

impl Drop for SafeArray {
    fn drop(&mut self) {
        // Demonstration only: Don't do this
        self.0 = [0; 4];
    }
}

This is the ASM for the whole program:

0000000000000000 <ltmp0>:
       0: 00 00 c0 3d   ldr q0, [x0]
       4: 00 b8 b1 4e   addv.4s s0, v0
       8: 01 00 26 1e   fmov    w1, s0
       c: 1f 7c 00 a9   stp xzr, xzr, [x0]
      10: e0 03 01 aa   mov x0, x1
      14: c0 03 5f d6   ret

The important line is shown below. It uses stp which stores a pair of registers, in this case the special zero register, xzr in the memory pointed to by x0. In other words, the memory was zeroed! It worked!

       c: 1f 7c 00 a9   stp xzr, xzr, [x0]

But let's not get too excited, yet. We should check that it still works for other types. Changing the code to use u8 instead of u32 (and leaving the drop implementation the same), we have:

// Changed to u8
pub struct SafeArray([u8; 4]);

impl SafeArray {
    pub fn consume_and_sum(self) -> u8 {
        // Careful! This could overflow!
        self.0.into_iter().sum()
    }
}

Compiles to the following:

0000000000000000 <ltmp0>:
       0: 08 20 40 0b   add w8, w0, w0, lsr #8
       4: 08 41 40 0b   add w8, w8, w0, lsr #16
       8: 00 61 40 0b   add w0, w8, w0, lsr #24
       c: c0 03 5f d6   ret

It looks quite different from the earlier version! The compiler is using a totally different approach. This code is doing is a series of additions involving the original value in w0 and its progressively right-shifted versions. After each shift, the shifted value is added to an accumulating sum. The shifts are by 8, 16, and then 24 bits, effectively breaking w0 into four bytes, adding these bytes together, and storing the final sum back into w0.

But where is the zeroizing code!? For some reason the compiler decided that our code to zeroize was irrelevant and optimized it away.

Avoiding unsafe compiler operations

Compilers are complicated pieces of software and are designed to generate code that is optimal for the target architecture. This means their behaviour can sometimes be hard to reason about and, like in the case above, remove code that is important to security in the interests of performance.

We need a different approach to ensure our attempts to zeroize data don't get optimized away.

Thankfully, there is already a crate to do this: Zeroize!

I'll add it to my Cargo.toml with the derive feature enabled as we'll use that in a moment. I've also added #[no_mangle] to the drop which retains symbol names in the generated assembly code and will make things a bit easier to read.

# Cargo.toml

[dependencies]
zeroize = { version = "1.7.0", features = ["derive"] }

Now we can derive Zeroize for SafeArray and call zeroize in the Drop implementation:

use zeroize::Zeroize;

#[derive(Zeroize)]
pub struct SafeArray(pub [u8; 4]);

impl Drop for SafeArray {
    #[no_mangle]
    fn drop(&mut self) {
        self.0.zeroize();
    }
}

The compiled assembly is as follows:

0000000000000000 <ltmp0>:
       0: ff 43 00 d1   sub sp, sp, #16
       4: 08 7c 08 53   lsr w8, w0, #8
       8: e8 2f 00 39   strb    w8, [sp, #11]
       c: 09 7c 10 53   lsr w9, w0, #16
      10: e9 2b 00 39   strb    w9, [sp, #10]
      14: 0a 7c 18 53   lsr w10, w0, #24
      18: ea 27 00 39   strb    w10, [sp, #9]
      1c: 08 01 00 0b   add w8, w8, w0
      20: 29 01 0a 0b   add w9, w9, w10
      24: 00 01 09 0b   add w0, w8, w9
      28: ff 33 00 39   strb    wzr, [sp, #12]
      2c: ff 2f 00 39   strb    wzr, [sp, #11]
      30: ff 2b 00 39   strb    wzr, [sp, #10]
      34: ff 27 00 39   strb    wzr, [sp, #9]
      38: ff 43 00 91   add sp, sp, #16
      3c: c0 03 5f d6   ret

0000000000000040 <_drop>:
      40: 1f 00 00 39   strb    wzr, [x0]
      44: 1f 04 00 39   strb    wzr, [x0, #1]
      48: 1f 08 00 39   strb    wzr, [x0, #2]
      4c: 1f 0c 00 39   strb    wzr, [x0, #3]
      50: c0 03 5f d6   ret

There is a lot more code now but for the most part it is doing the same thing as before (the addition is done over several instructions this time though).

The important part is that we have a Drop implementation that is correctly zeroizing memory 🎉. As you can see, there is the implementation of the Drop trait, conveniently labeled <_drop> (thanks to #[no_mangle]) but that the zeroizing code has also been included (via inlining) in the summation code above. In this case, the compiler has used the strb instruction to store the zero register (wzr) into each element of our array.

Using `ZeroizeOnDrop`

The Zeroize crate comes with a marker trait called ZeroizeOnDrop which works for any Zeroize type and means I don't have to implement Drop every time. I can derive ZeroizeOnDrop instead of using my own Drop implementation.

use zeroize::{Zeroize, ZeroizeOnDrop};

#[derive(Zeroize, ZeroizeOnDrop)]
pub struct SafeArray(pub [u8; 4]);

Caution!

Implementing Zeroize alone won't automatically zeroize memory on drop. Zeroize just implements the zeroize method to clear memory. The ZeroizeOnDrop trait must be implemented as well to automatically zeroize when the value is dropped.

But...what about Portable SIMD?

But you may also be asking, what is SIMD!?

...um, what is SIMD?

Single Instruction, Multiple Data (SIMD) is a parallel processing paradigm used in computer architecture to enhance performance by executing the same operation simultaneously on multiple data points. This approach is especially effective for tasks that require the same computation to be repeated over a large data set, such as in digital signal processing, image and video processing, and scientific simulations. In my case, I'm using SIMD for high-performance cryptography implementations.

SIMD architectures achieve this by employing vector processors or SIMD extensions in CPUs, where a single instruction directs the simultaneous execution of operations on multiple data elements within wider registers. For instance, a SIMD instruction could add or multiply pairs of numbers in a single operation, significantly speeding up computations compared to processing each pair sequentially. This method leverages data-level parallelism, different from the traditional sequential execution model, and is a key feature in modern processors to boost computational efficiency and performance.

For example, with SIMD I can sum 8 arrays of 4 integers in parallel.

#![feature(portable_simd)]
use core::simd::prelude::Simd;

let x: [Simd<u32, 8>; 4] = [
    Simd::from_array([1, 1, 1, 1, 1, 1, 1, 1]),
    Simd::from_array([2, 2, 2, 2, 2, 2, 2, 2]),
    Simd::from_array([1, 2, 3, 4, 5, 6, 7, 8]),
    Simd::from_array([0, 0, 0, 0, 0, 0, 0, 0]),
];

let sums = x.into_iter().reduce(|sum, x| sum + x);
dbg!(sums);

This code outputs:

Some(
    [
        4,  // 1 + 2 + 1 + 0
        5,  // 1 + 2 + 2 + 0
        6,  // etc
        7,
        8,
        9,
        10,
        11,
    ],
)

Neat, huh?!

OK, back to Zeroize for SIMD

While the Zeroize crate is awesome, and you should absolutely use it, it doesn't currently have implementations for the forthcoming portable SIMD modules for Rust. Unlike working with SIMD directly, which requires knowledge of the specific CPU architecture you're building for, Portable SIMD abstracts common CPU vectorizations into a universal interface that works on most architectures.

I've created a type which wraps Simd<u16, 8>, a vector of 8 u16 values and a simple method that adds 2 values, consuming both.

pub struct MySimd(Simd<u16, 8>);

impl MySimd {
    #[no_mangle]
    pub fn consume_and_add(self, other: Self) -> Self {
        Self(self.0 + other.0)
    }
}

The generated assembly is as follows:

0000000000000000 <ltmp0>:
       0: 00 00 c0 3d   ldr q0, [x0]
       4: 21 00 c0 3d   ldr q1, [x1]
       8: 20 84 60 4e   add.8h  v0, v1, v0
       c: 00 01 80 3d   str q0, [x8]
      10: c0 03 5f d6   ret

We just added 8 pairs of numbers in only 5 instructions! Let's try adding a Drop implementation.

impl Drop for MySimd {
    fn drop(&mut self) {
        // splat is roughly equivalent to `[0u16; 8]
        self.0 &= Simd::splat(0);
    }
}

But oh no! The generated assembly is identical! My drop code was completely ignored 😫.

0000000000000000 <ltmp0>:
       0: 00 00 c0 3d   ldr q0, [x0]
       4: 21 00 c0 3d   ldr q1, [x1]
       8: 20 84 60 4e   add.8h  v0, v1, v0
       c: 00 01 80 3d   str q0, [x8]
      10: c0 03 5f d6   ret

Using `unsafe` to be safe!?

Ironically, the only way we can make this code safely and correctly zero memory that may contain sensitive data is to use some unsafe operations. The Zeroize crate itself uses two approaches to avoid compiler optimizations removing zeroizing code. I'll use them both here:

use core::{ptr, sync::atomic};

impl Drop for MySimd {
    fn drop(&mut self) {
        unsafe {
          ptr::write_volatile(self, core::mem::zeroed())
        };
        atomic::compiler_fence(atomic::Ordering::SeqCst);
    }
}

Before explaining what's going on, let's first see if it works.

0000000000000000 <ltmp0>:
       0: 00 e4 00 6f   movi.2d v0, #0000000000000000
       4: 00 00 80 3d   str q0, [x0]
       8: c0 03 5f d6   ret

000000000000000c <_consume_and_add>:
       c: 00 00 c0 3d   ldr q0, [x0]
      10: 21 00 c0 3d   ldr q1, [x1]
      14: 20 84 60 4e   add.8h  v0, v1, v0
      18: 00 01 80 3d   str q0, [x8]
      1c: 00 e4 00 6f   movi.2d v0, #0000000000000000
      20: 20 00 80 3d   str q0, [x1]
      24: 00 00 80 3d   str q0, [x0]
      28: c0 03 5f d6   ret

The two functions represent the consume_and_add method on MySimd and the drop method in the Drop trait. The top function confusingly denoted by ltmp0 (I'm still not sure why) is the Drop code and it contains:

       0: 00 e4 00 6f   movi.2d v0, #0000000000000000

This moves the special zero value into the vector v0 which was dropped. Because the consume_and_add method returns a vector, only one of the 2 arguments is actually dropped. You can also see that the same code has been inlined into the consume_and_add function.

So, what's going on here?

Firstly, we're using write_volatile to reliably zero the target memory. The Rust compiler guarantees not to mess with it! Unfortunately, the method is unsafe but its the only way to safely zero the data.

Secondly, we're using what's called an atomic compiler fence which tells the compiler it is not allowed to reorganize the memory in question. It doesn't prevent the CPU from doing so in hardware though that is a post for another day.

Implementing Zeroize

Instead of implementing Drop I can use my custom Zeroize implementation and then just implement ZeroizeOnDrop like we did earlier.

impl Zeroize for MySimd {
    fn zeroize(&mut self) {
        unsafe {
          ptr::write_volatile(self, core::mem::zeroed())
        };
        atomic::compiler_fence(atomic::Ordering::SeqCst);
    }
}

impl ZeroizeOnDrop for MySimd {}

Better, safer code

While you may not have this exact problem in your day-to-day code, understanding what's happening under the hood can be instructive. And hopefully lead to better and safer code.

:wq

Encrypt(Syd) MeetUp

Tia — Tue, 02 Aug 2022 05:55:46 +0000

We'd love it if you were able to join our community_Encrypt(Syd)_and hope to see you at a meetup soon!

We've got some great talks this month, join online or come say hi IRL - https://www.meetup.com/en-AU/encrypt-syd/events/dwnrssydclbpb/