Half a year ago I finally achieved my master’s degree in computing science. Now I am pursuing a PhD at the Radboud University in the field of cryptography. Among other things, I have been looking at elliptic curves and implementation and application of a couple of post-quantum KEMs.

As I understand it, the point of a PhD—really—is to try and find some overarching theme (one could say “thesis”) by which to conduct your research. One direction that I am currently exploring, is to see if we can add proper support in mainstream compilers for the secure implementation of cryptographic software. That’s what this entry is about.

Compilers and side-channel resistance 

Normal programmers write their code mostly in an interpreted (Python), or a compiled language (like C, C++, Rust, etc). Using the compiler, you translate the programming language into machine code that can be natively run on any platform. No matter which platform is targeted in the end—X86, ARM, AVR—the compiler will deal with that for you.

From this perspective it is surprising that cryptographic engineers still often prefer to write their code in plain assembly language. There are two main reasons for this though:

  1. Cryptographic engineers like speed, and like to go to ridiculous length to achieve the ultimate performance.
  2. Compilers are known to break the constant-time property that is needed to keep cryptographic implementations secure against timing attacks.

I personally think that both of these problems are completely fixable. First, compilers are getting better by the year, so the performance issue will become less and less over time.

The second problem is a little more involved, and requires an example.

How LLVM introduces branches in your code 

Here is an example of how a cryptographic engineer would implement a scanning table lookup operation.

1
2
3
4
5
6
7
8
9
10
11
12
13

// Select an element from an array in constant time
uint64_t
constant_time_lookup(const size_t secret_idx,
                     const uint64_t table[16]) {
    uint64_t result = 0;

    for (size_t i = 0; i < 8; i++) {
        const bool cond = i == secret_idx;
        const uint64_t mask = (-(int64_t)cond);
        result |= table[i] & mask;
    }
    return result;
}

view in Godbolt

The table lookup function selects a value from table. To guarantee that it executes in constant time/memory, we touch every element from the lookup table. Then we use a bitwise operation with a mask value to select the value at secret_idx.

The most important part is that the code does not contain an if-statement that depends on the secret_idx. Using this branch, an attacker could use timing attacks to learn the secret value in secret_idx. If (for example) this value contains a password, or a cryptographic key, we could be in deep trouble.

There is a problem, though: the Clang compiler is smart. It knows that only the value at i == secret_idx is used. See how it eliminates these loads operations using normal branches:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

constant_time_lookup:
        xor     eax, eax
        xor     ecx, ecx
        cmp     rdi, rcx    ; Contents of rdi are secret.
        jne     .LBB0_2     ; Dangerous branch added here!
.LBB0_3:
        mov     rdx, qword ptr [rsi + 8*rcx]
.LBB0_4:
        or      rax, rdx
        add     rcx, 1
        cmp     rcx, 8
        je      .LBB0_5
        cmp     rdi, rcx    ; Contents of rdi are secret.
        je      .LBB0_3     ; Dangerous branch added here!
.LBB0_2:
        xor     edx, edx
        jmp     .LBB0_4
.LBB0_5:
        ret

view in Godbolt

In the machine code, the compiler has added a new branch operation that completely breaks the side-channel resistance that was desired.

How could this happen? 

The culprit seems to be the x86-cmov-conversion pass in the X86-backend of the LLVM library. In this pass, all conditional move instructions that load from memory are converted, such that they may skip the load altogether.

Indeed, if we disable the x86-cmov-conversion pass, we see that side-channel resistance is maintained:

1
2
3
4
5
6
7
8
9
10
11
12
13

constant_time_lookup:
        xor     r8d, r8d
        xor     eax, eax
        xor     edx, edx
.LBB0_1:
        cmp     rdi, rdx    ; Contents of rdi are secret.
        mov     rcx, qword ptr [rsi + 8*rdx]
        cmovne  rcx, r8     ; No branch added here! :)
        or      rax, rcx
        add     rdx, 1
        cmp     rdx, 8
        jne     .LBB0_1
        ret

view in Godbolt

The secret keyword 

There are multiple ways we could try and solve this. Of course, the easiest way to avoid this problem is to avoid using the compiler at all, which is what most cryptographic engineers do.

Some others write their own compilers. They can be useful, but in my experience they are solutions built by cryptographers, for cryptographers. That is, I think they are often limited, hard to use, and still require in-depth knowledge about the underlying architecture. For example, qhasm is—in a way—just a register allocator with syntactic sugar, and jasmin does not support any architectures except for x86_64.

It would be better instead to have support for side-channel resistant code in actual mainstream compilers. This way, side-channel resistance is not reserved for only the experts. If there would be a general and easy method to mark code as timing-channel sensitive in our programming languages, then every programmer can secure their code against attacks, without needing to have an in-depth knowledge about these attacks and the platform. Writing secure code should be easy, and not implemented using hacks.

Rust example 

As an example, let us look at how that could look in a regular programming language. I really like the Rust language, so let’s use that language for now. You can put your own favorite language here, if you so desire.

Consider we had a secret keyword in Rust, then we could write our code like this:

/// Select an element from an array in constant time
pub fn constant_time_lookup(secret_idx: secret usize,
                            table: [secret u64; 16]) -> secret u64 {
    let mut result: secret u64 = 0;

    for (idx, value) in table.iter().enumerate() {
        let cond = idx == secret_idx;
        let mask = -(cond as secret i64) as secret u64;
        result |= value & mask;
    }
    result
}

The rustc compiler could tell the LLVM backend that all these values are secret, and LLVM should ensure that no branches are emitted that depend on these values.

The compiler can easily check if the compilation is possible. For example, this code is insecure:

/// Select an element from an array in constant time
pub fn constant_time_select(cond: secret bool, a: u64, b: u64) -> u64 {
    if cond {
        b
    } else {
        a
    }
}

Because of the if-else structure, the programmer illegally adds a branch that depends on the secret value in cond. In this case, the compiler should emit some kind of error:

error: cannot branch on secret value in `cond`
 --> :2:46
  |
3 | if cond {
  | ^^ `cond` contains a secret value, so this branch is unsafe

Next steps 

The current main obstacle to getting something like this implemented seems to be that x86-cmov-conversion pass. The pass exists in the X86 backed of LLVM, so it deals with machine code, instead of LLVM intermediate representation. In this stage, there is virtually no meta-information left about the code; all of it is lost in the instruction selection phase. That will make it impossible to differentiate between code that contains secrets, and code that is inherently safe.

A first step could be to move the x86-cmov-conversion pass to earlier in the compilation process. This could even lead to better optimizations, because in the current state this pass is only be able to optimize on boolean conditions.

After moving this pass to a spot where we have still access to LLVM metadata, we can look into introducing a metadata type signalling that an operation should not be optimized in a way that would lead to insecure code.

From there on, the path is fuzzy to me.

Conclusion 

This could be the start of a large project allowing the world to write code that is side-channel resistant by just using the programming language, and its compiler.

Though it is an endeavor that I am not able to carry out alone. With this post I hope I can spark some interest in people, to look into exploring this issue together. :)

I hope that—in a couple of years—if a programmer wants to write code that is secure against timing attacks, that they don’t need to be an expert anymore.