Constant-time code and data-independent timing

A tag check that returns at the first wrong byte ran 7 instructions when byte 0 was wrong and 97 when only byte 15 was, in the run recorded below. Anyone who can time many such checks learns how many leading bytes of a guess were right, which turns one hopeless guess at 16 bytes into sixteen small ones.

Constant-time code closes that gap for keys, password hashes and authentication tags: the instructions it runs and the addresses it reads depend only on public values such as a length. This page finds the leak, writes the fix and checks it with a count that fails on the weak version.

A secret leaks through what the code does with it

A side channelside channel: A way to learn a secret not from the data itself but from a measurable effect of handling it, such as how long an operation took or whether a cache line was loaded. More in “Branch prediction and speculative execution” is anything measurable about how a computation ran, apart from its result. For code that holds a secret value, the one that matters most is time, and a secret reaches the time by two routes.

A branch whose condition depends on a secret runs different instructions for different values, so the step count moves with it. An address computed from a secret, such as table[key], runs the same instructions but reads a different place in memory, and what the cache holds afterwards depends on that value: a cache-timingcache-timing leak: A side channel in which a secret picks which memory a program reads, so what the cache holds afterwards, and how fast later reads are, depends on that secret even though the same instructions ran. leak. Constant-time codeconstant-time code: Code whose instructions and memory addresses depend only on public values, such as a length, so its running time reveals nothing about the secrets it handles beyond what its result already says. keeps secrets out of both, letting them flow only through data operations such as XOR, AND, OR and masks.

An early exit tells the timing how many bytes matched

compare.c checks one 16-byte tag three ways; count_steps.py adds an LLDB command that counts the instructions of one call.

/* Three ways to compare a received 16-byte tag with the expected one. All three return the same answers; they differ
   in how much work they do, and so in how long they take, depending on where the first difference is. */
#include <stdio.h>
#include <string.h>

#define TAG 16

/* Weak: returns at the first difference, so its running time says how many leading bytes matched. */
__attribute__((noinline)) int tag_eq_early(const unsigned char *a, const unsigned char *b, size_t n) {
    for (size_t i = 0; i < n; i++) {
        if (a[i] != b[i]) {
            return 0;
        }
    }
    return 1;
}

/* Looks branch-free, but && stops evaluating once eq is 0, and the compiler may branch on that. */
__attribute__((noinline)) int tag_eq_andand(const unsigned char *a, const unsigned char *b, size_t n) {
    int eq = 1;
    for (size_t i = 0; i < n; i++) {
        eq = eq && (a[i] == b[i]);
    }
    return eq;
}

/* Fixed: every byte is read and combined with OR, and the only branch is the loop's own test on n. */
__attribute__((noinline)) int tag_eq_ct(const unsigned char *a, const unsigned char *b, size_t n) {
    unsigned char diff = 0;
    for (size_t i = 0; i < n; i++) {
        diff |= (unsigned char)(a[i] ^ b[i]);
    }
    return diff == 0;
}

typedef int (*compare_fn)(const unsigned char *, const unsigned char *, size_t);

/* Runs one comparison on the three inputs in a fixed order: equal tags, a difference at byte 0, one at byte 15. */
static void show(const char *name, compare_fn eq, const unsigned char *expected, const unsigned char *first,
                 const unsigned char *last) {
    int same = eq(expected, expected, TAG);
    int at0 = eq(expected, first, TAG);
    int at15 = eq(expected, last, TAG);
    printf("%s: %d %d %d\n", name, same, at0, at15);
}

int main(void) {
    unsigned char expected[TAG], first[TAG], last[TAG];
    memset(expected, 0x5a, TAG);
    memcpy(first, expected, TAG);
    memcpy(last, expected, TAG);
    first[0] ^= 1;          /* differs at byte 0 */
    last[TAG - 1] ^= 1;     /* differs at byte 15 */
    show("early exit", tag_eq_early, expected, first, last);
    show("&& form   ", tag_eq_andand, expected, first, last);
    show("OR form   ", tag_eq_ct, expected, first, last);
    return 0;
}

# An LLDB command, `count`, that steps the stopped function one instruction at a time until it returns to its caller,
# and prints how many instructions ran. A constant-time function runs the same number of instructions for every input
# of the same length; a function with a branch on the data does not.
#
# Use: lldb -b -o 'command script import count_steps.py' -o 'breakpoint set -n f' -o run -o count -o continue ...
import lldb


def count(debugger, command, result, internal_dict):
    thread = debugger.GetSelectedTarget().GetProcess().GetSelectedThread()
    name = thread.GetFrameAtIndex(0).GetFunctionName()
    depth = thread.GetNumFrames()
    steps = 0
    while thread.GetNumFrames() >= depth and steps < 100000:
        thread.StepInstruction(True)
        steps += 1
    result.AppendMessage(f"{name}: {steps} instructions")


def __lldb_init_module(debugger, internal_dict):
    debugger.HandleCommand("command script add -f count_steps.count count")

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

session.run("""
# Build the comparisons and check that they agree: equal tags, a difference at byte 0, a difference at byte 15
clang -O2 -o compare compare.c
./compare
""")

session.run("""
# The early exit's listing: b.ne straight after cmp w8, w9 is a branch on the bytes themselves
otool -tv compare | awk '/^_tag_eq_early:/,/^_tag_eq_andand:/' | grep -v '^_tag_eq_andand:'
""")

session.run("""
# The check: count the instructions each call runs. Same tag length, three inputs, so the counts should not differ
lldb -b -o 'command script import count_steps.py' -o 'breakpoint set -n tag_eq_early' -o run -o count -o continue -o count -o continue -o count -o continue ./compare 2>&1 | grep instructions
lldb -b -o 'command script import count_steps.py' -o 'breakpoint set -n tag_eq_ct' -o run -o count -o continue -o count -o continue -o count -o continue ./compare 2>&1 | grep instructions
""")

# Build the comparisons and check that they agree: equal tags, a difference at byte 0, a difference at byte 15
$ clang -O2 -o compare compare.c
$ ./compare
early exit: 1 0 0
&& form   : 1 0 0
OR form   : 1 0 0
# The early exit's listing: b.ne straight after cmp w8, w9 is a branch on the bytes themselves
$ otool -tv compare | awk '/^_tag_eq_early:/,/^_tag_eq_andand:/' | grep -v '^_tag_eq_andand:'
_tag_eq_early:
0000000100000460	cbz	x2, 0x10000047c
0000000100000464	ldrb	w8, [x0], #0x1
0000000100000468	ldrb	w9, [x1], #0x1
000000010000046c	cmp	w8, w9
0000000100000470	b.ne	0x100000484
0000000100000474	subs	x2, x2, #0x1
0000000100000478	b.ne	0x100000464
000000010000047c	mov	w0, #0x1
0000000100000480	ret
0000000100000484	mov	w0, #0x0
0000000100000488	ret
# The check: count the instructions each call runs. Same tag length, three inputs, so the counts should not differ
$ lldb -b -o 'command script import count_steps.py' -o 'breakpoint set -n tag_eq_early' -o run -o count -o continue -o count -o continue -o count -o continue ./compare 2>&1 | grep instructions
tag_eq_early: 99 instructions
tag_eq_early: 7 instructions
tag_eq_early: 97 instructions
$ lldb -b -o 'command script import count_steps.py' -o 'breakpoint set -n tag_eq_ct' -o run -o count -o continue -o count -o continue -o count -o continue ./compare 2>&1 | grep instructions
tag_eq_ct: 37 instructions
tag_eq_ct: 37 instructions
tag_eq_ct: 37 instructions

In the listing, cmp w8, w9 compares one pair of bytes and the next instruction, b.ne, leaves the loop on a difference, so the bytes decide how long the loop runs. The count shows it: 7 instructions when byte 0 differed, 97 when only byte 15 did, 99 for equal tags. Two of those calls return the same 0, yet their times differ, and the time is what leaks. The shape to look for in any listing is the same: a conditional branch inside the loop whose flags come from the loaded bytes, not from the counter.

The fixed compare reads every byte and decides once

tag_eq_ct reads every pair, folds each difference into one byte with XOR and OR, and tests that byte once, after the loop. Its branches test only the length, which is public, and it ran 37 instructions for all three inputs. That is the check: one function, one length, several inputs and a count that must not move; it fails on the early exit and passes on the fix.

import pathlib
import sys

sys.path.insert(0, str(pathlib.Path(__file__).parent / "sessions"))
import session

session.run(r"""
# The two comparisons on x86-64 and RISC-V. Vectorising and unrolling are off so that each loop is one pass per byte
clang-23 --target=x86_64-linux-gnu -O2 -fno-vectorize -fno-unroll-loops -S -o - compare_portable.c | sed 's/[[:space:]]*#.*//' | grep -E '^[.A-Za-z_][.A-Za-z0-9_]*:|^[[:space:]]+[a-z]'
clang-23 --target=riscv64-linux-gnu -O2 -fno-vectorize -fno-unroll-loops -S -o - compare_portable.c | sed 's/[[:space:]]*#.*//' | grep -E '^[.A-Za-z_][.A-Za-z0-9_]*:|^[[:space:]]+[a-z]'
""", max_lines=80)

# The two comparisons on x86-64 and RISC-V. Vectorising and unrolling are off so that each loop is one pass per byte
$ clang-23 --target=x86_64-linux-gnu -O2 -fno-vectorize -fno-unroll-loops -S -o - compare_portable.c | sed 's/[[:space:]]*#.*//' | grep -E '^[.A-Za-z_][.A-Za-z0-9_]*:|^[[:space:]]+[a-z]'
tag_eq_early:
	movl	$1, %eax
	testq	%rdx, %rdx
	je	.LBB0_5
	xorl	%ecx, %ecx
.LBB0_3:
	movzbl	(%rdi,%rcx), %r8d
	cmpb	(%rsi,%rcx), %r8b
	jne	.LBB0_4
	incq	%rcx
	cmpq	%rcx, %rdx
	jne	.LBB0_3
.LBB0_5:
	retq
.LBB0_4:
	xorl	%eax, %eax
	retq
.Lfunc_end0:
tag_eq_ct:
	testq	%rdx, %rdx
	je	.LBB1_1
	xorl	%ecx, %ecx
	xorl	%eax, %eax
.LBB1_5:
	movzbl	(%rsi,%rax), %r8d
	xorb	(%rdi,%rax), %r8b
	movzbl	%r8b, %r8d
	orl	%r8d, %ecx
	incq	%rax
	cmpq	%rax, %rdx
	jne	.LBB1_5
	xorl	%eax, %eax
	testl	%ecx, %ecx
	sete	%al
	retq
.LBB1_1:
	movl	$1, %eax
	retq
.Lfunc_end1:
$ clang-23 --target=riscv64-linux-gnu -O2 -fno-vectorize -fno-unroll-loops -S -o - compare_portable.c | sed 's/[[:space:]]*#.*//' | grep -E '^[.A-Za-z_][.A-Za-z0-9_]*:|^[[:space:]]+[a-z]'
tag_eq_early:
	mv	a3, a0
	li	a0, 1
	beqz	a2, .LBB0_3
.LBB0_1:
	lbu	a4, 0(a3)
	lbu	a5, 0(a1)
	bne	a4, a5, .LBB0_4
	addi	a2, a2, -1
	addi	a1, a1, 1
	addi	a3, a3, 1
	bnez	a2, .LBB0_1
.LBB0_3:
	ret
.LBB0_4:
	li	a0, 0
	ret
.Lfunc_end0:
tag_eq_ct:
	beqz	a2, .LBB1_4
	li	a3, 0
	add	a2, a2, a1
.LBB1_2:
	lbu	a4, 0(a0)
	lbu	a5, 0(a1)
	xor	a4, a4, a5
	addi	a1, a1, 1
	or	a3, a3, a4
	addi	a0, a0, 1
	bne	a1, a2, .LBB1_2
	seqz	a0, a3
	ret
.LBB1_4:
	li	a0, 1
	ret
.Lfunc_end1:

On x86-64 and RISC-V the early exit also branches straight after the byte comparison, jne after cmpb and bne a4, a5, while the fixed loop branches only on its counter. Where a library offers a routine, prefer it: OpenSSL’s CRYPTO_memcmp, OpenBSD’s timingsafe_bcmp and libsodium’s sodium_memcmp are each documented to take a time set by the length alone.

Two cautions remain. The compiler chooses the instructions, so it can put a branch back into C that has none. And Apple silicon offers data-independent timingdata-independent timing: A processor setting, called DIT on Arm, under which a listed set of instructions takes the same time whatever values it processes. It does not change which branches a program takes or which addresses it reads., DIT, a setting under which a listed set of instructions takes the same time whatever values it processes. Data-independent timing leaves the branches taken and the addresses read unchanged, so it adds to constant-time code rather than replacing it.

Practise

Copy the page’s files first; setting up the toolchain covers other machines.

1. Move the difference in last from byte 15 to byte 8, predict the early exit’s count for that call, then run the counter.
2. Set TAG to 32 and count again: the fixed compare’s count changes, by the same amount for all three inputs.
3. Fold with subtraction instead, diff |= (unsigned char)(a[i] - b[i]), and confirm that the answers and the equal counts stay.
4. Build compare_portable.c for RISC-V with the listing command and name the instruction of tag_eq_early whose outcome the bytes decide.

A measured timing gap, and a branch the compiler adds to branch-free C Pro: opens with a Pro, Premium or Ultimate pass

DIT on Apple silicon, and a table lookup it does not fix Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

A warm-up for freshers: why is memcmp the wrong way to check a received authentication tag?

Because it may stop at the first byte that differs, so its time says how many leading bytes of the received tag were right. Use a comparison whose time depends only on the length: a library routine documented as constant time, such as CRYPTO_memcmp or sodium_memcmp, or a loop that reads every byte, folds the differences with XOR and OR and tests the total once. Either way, check the compiled code, because the compiler decides the branches.

Three harder questions follow: fixing a teammate’s comparison, keeping it constant-time across compilers, and placing DIT.

Key takeaways

• A secret leaks through timing when it decides a branch or an address, even when every result is correct.
• A constant-time comparison reads every byte, folds the differences and tests the total once, so its count is the same for every input of one length.
• The evidence is the compiled code: count instructions on several inputs of one length, and treat any difference as a failure.
• DIT fixes the timing of listed instructions on Apple silicon, not the branches a program takes or the addresses it reads.