run.sh

#!/bin/sh
# Does the code that handles a secret run in time independent of it?
#
# memcheck already follows undefined bytes through arithmetic and reports the
# moment one decides a branch or an address.  That is the same question, so
# each driver declares its secret undefined and runs under valgrind: every
# report names a place where the secret reached a branch or an index.
# The technique is Adam Langley's ctgrind.
#
# Without valgrind the drivers are still built and run, which says only that
# the plumbing is right -- it checks nothing about timing, and says so.
#
# Usage: cbits/tests/ct/run.sh [build-dir]
set -eu

root=$(CDPATH= cd -- "$(dirname -- "$0")/../../.." && pwd)
out=${1:-$(mktemp -d)}
cc=${CC:-cc}
mkdir -p "$out"
cd "$root"

D=cbits/decaf
decaf_src="$D/ed448goldilocks/decaf_all.c $D/ed448goldilocks/eddsa.c
           $D/ed448goldilocks/scalar.c $D/p448/f_arithmetic.c
           $D/p448/f_generic.c $D/utils.c $D/p448/arch_ref64/f_impl.c
           cbits/crypton_sha3.c"
decaf_inc="-DCRYPTON_DECAF_WORD_BITS=64 -I$D/include -I$D/p448
           -I$D/include/arch_ref64 -I$D/p448/arch_ref64"

# The portable C, not whatever the machine happens to offer, and the BearSSL
# it is written on.  All three builds below have to be silent, so what tells
# them apart is which implementation each one's dispatch chose -- which the
# driver prints and run_one checks, since otherwise a build that quietly took
# the wrong path would pass by saying nothing.
aes_src="cbits/crypton_aes.c cbits/aes/generic.c cbits/aes/gf.c
         cbits/bearssl/aes_ct64.c cbits/bearssl/aes_ct64_enc.c
         cbits/bearssl/aes_ct64_dec.c cbits/bearssl/ghash_ctmul64.c
         cbits/bearssl/dec32le.c"

# The same driver again against the instructions, on each architecture that
# has them.
armv8_src="$aes_src cbits/aes/armv8.c cbits/crypton_cpu.c"
armv8_inc="-DWITH_ARMV8_CRYPTO -march=armv8-a+crypto -Icbits/aes"

x86ni_src="$aes_src cbits/aes/x86ni.c cbits/crypton_cpu.c
           cbits/aes/gcm_vaes_x86.c cbits/aes/gcm_vaes512_x86.c"
x86ni_inc="-DWITH_AESNI -DWITH_PCLMUL -maes -mpclmul -mssse3 -msse4.1 -Icbits/aes"

status=0
have_valgrind=no
ct_define=
if command -v valgrind > /dev/null 2>&1; then
	have_valgrind=yes
	ct_define=-DCRYPTON_CT_VALGRIND
fi

# MLK_CONFIG_CT_TESTING_ENABLED turns on mlkem-native's own secret and
# declassify annotations, which are in the source at the points the algorithm
# says a value becomes public.  The important one is the public seed: it is
# derived from the key generation seed, so it starts out secret, and the
# matrix it then seeds is generated by rejection sampling, which branches on
# the bytes it draws.  Upstream declassifies the seed first -- rho travels in
# the encapsulation key and is not secret -- and without that the driver
# reports a leak that is not one.  Those points are maintained by the people
# whose proofs cover this code, so they are a better answer than marking by
# hand from outside.
#
# Only with valgrind, since the macros include valgrind/memcheck.h.
mlkem_src="cbits/mlkem/crypton_mlkem.c"
mlkem_inc="-Icbits/mlkem${ct_define:+ -DMLK_CONFIG_CT_TESTING_ENABLED}"
# And the hand-written backend, where the architecture has one.  Both builds
# have to be silent: unlike the AES pair below there is no variable-time
# implementation here for one of them to expose.
mlkem_native_src="$mlkem_src cbits/mlkem/crypton_mlkem_asm.S"
mlkem_native_inc="$mlkem_inc -DCRYPTON_MLKEM_NATIVE_BACKEND"


# Does this processor have AES instructions at all?
#
# Asked of the system rather than of crypton, because the question being
# settled is whether crypton found what is there -- and a witness that comes
# from the code under test cannot answer that.  "Cannot tell" counts as
# having them, so an unfamiliar system turns into a loud failure rather than
# a silent skip.
#
# CRYPTON_CT_CPUINFO is for testing this function itself; nothing else sets
# it.
machine_has_aes() {
	cpuinfo=${CRYPTON_CT_CPUINFO:-/proc/cpuinfo}
	if [ -r "$cpuinfo" ]; then
		# "aes" in Features on ARM, in flags on x86; -w so that a model
		# name containing the letters does not answer for the flags
		grep -qw aes "$cpuinfo"
		return
	fi
	if [ "$(uname -s)" = Darwin ]; then
		[ "$(sysctl -n hw.optional.arm.FEAT_AES 2>/dev/null)" = 1 ] && return 0
		[ "$(sysctl -n hw.optional.aes 2>/dev/null)" = 1 ] && return 0
		return 1
	fi
	return 0
}

# run_one <name> <sources> <includes> [driver]
#
# The driver defaults to ct_<name>.c.  It is given separately where one
# driver is built twice -- the same question asked of the portable C and of
# the hand-written backend -- rather than copying the file to a second name.
run_one() {
	name=$1; srcs=$2; inc=$3; drv=${4:-$1}
	# shellcheck disable=SC2086
	$cc -O2 -g $ct_define -Icbits -Icbits/include64 $inc \
		-o "$out/$name" "cbits/tests/ct/ct_$drv.c" $srcs 2> "$out/$name.cc" || {
		echo "FAIL $name did not build"; sed -n '1,12p' "$out/$name.cc"; status=1; return
	}
	# Which implementation did this build's dispatch actually take?  The
	# driver says, and the three AES builds want different answers.  This
	# used to be inferred: the portable build was required to report,
	# because the tables leaked, and silence meant it had taken an
	# accelerated path instead.  The tables are gone and all three are
	# silent now, so the question is asked outright rather than read off a
	# leak that no longer happens.
	case $name in
	aes | aes_armv8 | aes_x86ni)
		want=0
		[ "$name" = aes ] || want=1
		got=$("$out/$name" 2>/dev/null | sed -n 's/^dispatch aes=\([01]\).*/\1/p')
		if [ "$got" != "$want" ]; then
			# A processor with no AES instructions is not a failure of
			# this driver; there is simply nothing here to measure, and
			# the portable one above has already measured what does run.
			# Boards in this position are common -- the Raspberry Pi 2,
			# 3 and 4 among them, on either word size.
			if [ "$want" = 1 ] && [ "$got" = 0 ] && ! machine_has_aes; then
				echo "skip $name: this processor has no AES instructions,"
				echo "     so there is nothing here to measure"
				return
			fi
			echo "FAIL $name: dispatch took aes=$got, wanted aes=$want --"
			echo "     this build is not running the implementation it is named for"
			status=1
			return
		fi
		;;
	esac
	if [ "$have_valgrind" = no ]; then
		"$out/$name" > /dev/null 2>&1 && echo "built $name (no valgrind here; nothing checked)" \
			|| { echo "FAIL $name did not run"; status=1; }
		return
	fi
	valgrind --error-exitcode=0 --track-origins=yes --num-callers=20 \
		--log-file="$out/$name.log" "$out/$name" > /dev/null 2>&1 || true
	n=$(grep -c "^==[0-9]*== \(Conditional jump\|Use of uninitialised\)" "$out/$name.log" || true)
	# Which places did it name?  Only the frame the report is against -- the
	# first "at" line under the complaint -- is the place; the "by" lines
	# below it are how the code got there and are not themselves branching
	# on anything.  Nor is the "at" line under "Uninitialised value was
	# created by", which --track-origins prints to say where the value came
	# from: that frame is a stack allocation, not a branch, and taking it
	# for one put a function's opening brace on the list.  A site is
	# "file:line", and the ones listed in known.txt are understood.
	sites=$(awk '
		/^==[0-9]*== (Conditional jump|Use of uninitialised)/ { want = 1; next }
		want && /^==[0-9]*==    at 0x/ { print; want = 0 }
	' "$out/$name.log" |
		sed -n 's/^==[0-9]*==    at 0x[0-9A-Fa-f]*: [A-Za-z_0-9]* (\([^)]*\))$/\1/p' |
		grep -v '^ct_' | sort -u)
	unknown=
	for site in $sites; do
		file=${site%%:*}
		if grep -q "^$site[[:space:]]" cbits/tests/ct/known.txt ||
		   grep -q "^$file[[:space:]]" cbits/tests/ct/known.txt; then
			continue
		fi
		unknown="$unknown $site"
	done

	case $name in
	canary)
		# the calibration: silence here would mean the marking never reached
		# the code, and every other zero in this run would be worthless
		if [ "$n" -eq 0 ]; then
			echo "FAIL canary: the deliberately leaky driver reported nothing,"
			echo "     so the marking is not reaching the code and nothing below counts"
			status=1
		else
			echo "ok   canary: reported $n, so the marking works"
		fi
		;;
	aes | aes_armv8 | aes_x86ni)
		# Nothing here looks anything up: the portable AES and GHASH are
		# bitsliced, and the two instruction sets branch on nothing.  So
		# anything at all is a finding and known.txt does not apply --
		# until the tables went this entry read the other way round, with
		# the portable build required to report.
		if [ "$n" -eq 0 ]; then
			echo "ok   $name: the secret decided nothing"
		else
			echo "FAIL $name: $n report(s) from AES or GHASH,"
			echo "     which should branch on nothing:"
			for site in $sites; do echo "         $site"; done
			sed -n '/Conditional jump\|Use of uninitialised/,/^==[0-9]*== $/p' \
				"$out/$name.log" | head -30 | sed 's/^/    /'
			status=1
		fi
		;;
	*)
		if [ "$n" -eq 0 ]; then
			echo "ok   $name: the secret decided nothing"
		elif [ -z "$unknown" ]; then
			echo "ok   $name: $n report(s), all known -- $(echo "$sites" | tr '\n' ' ')"
		else
			echo "REPORT $name: the secret decided a branch or an address"
			echo "       somewhere not listed in cbits/tests/ct/known.txt:"
			for site in $unknown; do echo "         $site"; done
			sed -n '/Conditional jump\|Use of uninitialised/,/^==[0-9]*== $/p' \
				"$out/$name.log" | head -30 | sed 's/^/    /'
			status=1
		fi
		;;
	esac
}

# The calibration first: it must report, or nothing below means anything.
run_one canary  "" ""

run_one powm    "cbits/crypton_powm.c" ""
run_one p256    "cbits/p256/p256.c cbits/p256/p256_ec.c" ""
run_one x25519  "cbits/curve25519/curve25519-donna-c64.c" ""
run_one ed25519 "cbits/ed25519/ed25519.c cbits/crypton_sha512.c" "-Icbits/ed25519"
run_one decaf   "$decaf_src" "$decaf_inc"
run_one chapoly "cbits/crypton_chacha.c cbits/crypton_poly1305.c" ""
run_one mlkem   "$mlkem_src" "$mlkem_inc"
run_one aes     "$aes_src" ""

# Only where the instructions exist.  Elsewhere there is nothing to measure
# and the build would not even compile.
case $(uname -m) in
aarch64 | arm64)
	run_one aes_armv8 "$armv8_src" "$armv8_inc" aes
	;;
x86_64 | amd64)
	run_one aes_x86ni "$x86ni_src" "$x86ni_inc" aes
	;;
esac

# The ML-KEM backend, on both architectures that have one.  x86-64 wants the
# flags its own build system passes, or the AVX2 sources do not assemble.
case $(uname -m) in
aarch64 | arm64)
	run_one mlkem_native "$mlkem_native_src" "$mlkem_native_inc" mlkem
	;;
x86_64 | amd64)
	run_one mlkem_native "$mlkem_native_src" "$mlkem_native_inc -mavx2 -mbmi2" mlkem
	;;
esac

if [ "$have_valgrind" = no ]; then
	echo "skip no valgrind here, so none of the above was checked"
	exit 0
fi
exit $status