Zig: use case: constant time operations for crypto

[andrewrk]

Here's a simple example of this problem:

Let's say you're writing a password checker. Your algorithm looks like:

// vulnerable function
fn checkPass(hashed_password: []const u8, guessed_password: []const u8) bool {
    // assume hashed_password.len == guessed_password.len for sake of example
    for (hashed_password) |byte, i| {
        if (guessed_password[i] != byte) return false;
    }
    return true;
}

This is vulnerable to a timing attack. The early return in the for loop allows the attacker to measure the statistical difference in duration for various passwords, and eventually guess every byte of the hashed password.

This is just one example; timing attacks are a fundamental challenge when writing robust cryptographic algorithms.

The reason that this is a special use case is that it breaks from a foundational premise in the rest of Zig: that the goal of the compiler is to interpret the semantic meaning and then emit whatever machine code it can to make it go fast. Here the goal is different: make it go the same amount of time regardless of the input.

Typically crypto implementations resort to using hand-written, hand-verified assembly code for this, because the optimizer cannot be trusted given that it does not share the premise of constant time code.

So I'd like to research what it would look like to support this use case at the language level in Zig. My first thought is to have something like this:

timeconst {
    // in this block all math operations become constant time
    // and it is a compile error to call non timeconst functions
}

This block would guarantee that all code inside it completes in the same amount of time regardless of the inputs to the block. If this guarantee could not be satisfied then there would be a compile error.

We would probably need some builtin primitives such as @timeConstMemCompare, as calling std.mem.eql would cause a compile error, since that function does not have the timeconst property.

One thing that a comprehensive proposal should do before getting accepted is look at a real world project, such as BoringSSL, and port the constant time parts of it to the proposal's semantics, to prove that the semantics would be applicable and useful.

[komuw]

This[1] Golang proposal and the ensuing discussion has a lot of good points that maybe of benefit to this zig issue.

1. https://github.com/golang/go/issues/20654

[bzzoop]

BearSSL has some good information on constant time operations for various cpus: https://bearssl.org/ctmul.html
https://bearssl.org/constanttime.html

[marler8997]

I could imagine that the compiler could make sure that the same number of instructions are always executed within a timeconst block regardless of input, however, modern processors are very complex. Often the biggest factor in performance depends on the predictability of the code based on the inputs and the number of cache hits and misses you have. In fact I know that some exploits use the timing of the processor cache to infer the values of arbitrary memory locations, and that cache timing in some cases will be solely dependent on the inputs rather than the instructions being executed. I'm not sure how Zig could even start to solve problems like this...am I missing something?

[shawnl]

Timing attacks are far more complicated than just doing things in constant time. There are many types of timing attacks.

[JesseRMeyer]

Is the following trivial transformation not the common solution for making comparison functions take 'constant time'? Or is the issue that Zig will rewrite this expression as the 'fast' version above, so the timeconst {} block tells Zig to limit its set of optimizations on the code block? Are scope level optimization settings too coarse to address this?

fn checkPass(hashed_password: []const u8, guessed_password: []const u8) bool {
    // assume hashed_password.len == guessed_password.len for sake of example
    var result = true;
    for (hashed_password) |byte, i| {
        if (guessed_password[i] != byte) result = false;
    }
    return result;
}

[anon17]

If you know the array size in advance, say, 16 bytes, you can load 64-bit integers from it then xor and or them.

[anon17]

Traditional generalized byte-wise xor loop is okayish, but when loop vectorization is enabled and the compiler sees such overly general code, it can assume that the array can be big, so vectorization will help to speed up it, but it must also assume that the array is not evenly sized and adds branched logic to process the tail, it shouldn't normally be used, but you get the idea.