riscv-crypto-scalar-zkt.adoc

Data Independent Execution Latency Subset: Zkt

The Zkt extension attests that the machine has data-independent execution time for a safe subset of instructions. This property is commonly called "constant-time" although should not be taken with that literal meaning.

All currently proposed cryptographic instructions (scalar K extension) are on this list, together with a set of relevant supporting instructions from I, M, C, and B extensions.

SH	Note to software developers Failure to prevent leakage of sensitive parameters via the direct timing channel is considered a serious security vulnerability and will typically result in a CERT CVE security advisory.

Scope and Goal

An "ISA contract" is made between a programmer and the RISC-V implementation that Zkt instructions do not leak information about processed secret data (plaintext, keying information, or other "sensitive security parameters" — FIPS 140-3 term) through differences in execution latency. Zkt does not define a set of instructions available in the core; it just restricts the behaviour of certain instructions if those are implemented.

Currently, the scope of this document is within scalar RV32/RV64 processors. Vector cryptography instructions (and appropriate vector support instructions) will be added later, as will other security-related functions that wish to assert leakage-free execution latency properties.

Loads, stores, conditional branches are excluded, along with a set of instructions that are rarely necessary to process secret data. Also excluded are instructions for which workarounds exist in standard cryptographic middleware due to the limitations of other ISA processors.

The stated goal is that OpenSSL, BoringSSL (Android), the Linux Kernel, and similar trusted software will not have directly observable timing side channels when compiled and running on a Zkt-enabled RISC-V target. The Zkt extension explicitly states many of the common latency assumptions made by cryptography developers.

Vendors do not have to implement all of the list’s instructions to be Zkt compliant; however, if they claim to have Zkt and implement any of the listed instructions, it must have data-independent latency.

For example, many simple RV32I and RV64I cores (without Multiply, Compressed, Bitmanip, or Cryptographic extensions) are technically compliant with Zkt. A constant-time AES can be implemented on them using "bit-slice" techniques, but it will be excruciatingly slow when compared to implementation with AES instructions. There are no guarantees that even a bit-sliced cipher implementation (largely based on boolean logic instructions) is secure on a core without Zkt attestation.

Out-of-order implementations adhering to Zkt are still free to fuse, crack, change or even ignore sequences of instructions, so long as the optimisations are applied deterministically, and not based on operand data. The guiding principle should be that no information about the data being operated on should be leaked based on the execution latency.

Note	It is left to future extensions or other techniques to tackle the problem of data-independent execution in implementations which advanced out-of-order capabilities which use value prediction, or which are otherwise data-dependent.

SH

Note to software developers Programming techniques can only mitigate leakage directly caused by arithmetic, caches, and branches. Other ISAs have had micro-architectural issues such as Spectre, Meltdown, Speculative Store Bypass, Rogue System Register Read, Lazy FP State Restore, Bounds Check Bypass Store, TLBleed, and L1TF/Foreshadow, etc. See e.g. NSA Hardware and Firmware Security Guidance It is not within the remit of this proposal to mitigate these micro-architectural leakages.

Background

• Timing attacks are much more powerful than was realised before the 2010s, which has led to a significant mitigation effort in current cryptographic code-bases.

• Cryptography developers use static and dynamic security testing tools to trace the handling of secret information and detect occasions where it influences a branch or is used for a table lookup.

• Architectural testing for Zkt can be pragmatic and semi-formal; security by design against basic timing attacks can usually be achieved via conscious implementation (of relevant iterative multi-cycle instructions or instructions composed of micro-ops) in way that avoids data-dependent latency.

• Laboratory testing may utilize statistical timing attack leakage analysis techniques such as those described in ISO/IEC 17825 cite:[IS16].

• Binary executables should not contain secrets in the instruction encodings (Kerckhoffs’s principle), so instruction timing may leak information about immediates, ordering of input registers, etc. There may be an exception to this in systems where a binary loader modifies the executable for purposes of relocation — and it is desirable to keep the execution location (PC) secret. This is why instructions such as LUI, AUIPC, and ADDI are on the list.

• The rules used by audit tools are relatively simple to understand. Very briefly; we call the plaintext, secret keys, expanded keys, nonces, and other such variables "secrets". A secret variable (arithmetically) modifying any other variable/register turns that into a secret too. If a secret ends up in address calculation affecting a load or store, that is a violation. If a secret affects a branch’s condition, that is also a violation. A secret variable location or register becomes a non-secret via specific zeroization/sanitisation or by being declared ciphertext (or otherwise no-longer-secret information). In essence, secrets can only "touch" instructions on the Zkt list while they are secrets.

Specific Instruction Rationale

• HINT instruction forms (typically encodings with rd=x0) are excluded from the data-independent time requirement.

• Floating point (F, D, Q, L extensions) are currently excluded from the constant-time requirement as they have very few applications in standardised cryptography. We may consider adding floating point add, sub, multiply as a constant time requirement for some floating point extension in case a specific algorithm (such as the PQC Signature algorithm Falcon) becomes critical.

• Cryptographers typically assume division to be variable-time (while multiplication is constant time) and implement their Montgomery reduction routines with that assumption.

• Zicsr, Zifencei are excluded.

• Some instructions are on the list simply because we see no harm in including them in testing scope.

Programming Information

For background information on secure programming "models", see:

• Thomas Pornin: "Why Constant-Time Crypto?" (A great introduction to timing assumptions.) https://www.bearssl.org/constanttime.html

• Jean-Philippe Aumasson: "Guidelines for low-level cryptography software." (A list of recommendations.) https://github.com/veorq/cryptocoding

• Peter Schwabe: "Timing Attacks and Countermeasures." (Lecture slides — nice references.) https://summerschool-croatia.cs.ru.nl/2016/slides/PeterSchwabe.pdf

• Adam Langley: "ctgrind." (This is from 2010 but is still relevant.) https://www.imperialviolet.org/2010/04/01/ctgrind.html

• Kris Kwiatkowski: "Constant-time code verification with Memory Sanitizer." https://www.amongbytes.com/post/20210709-testing-constant-time/

• For early examples of timing attack vulnerabilities, see https://www.kb.cert.org/vuls/id/997481 and related academic papers.

Zkt listings

The following instructions are included in the Zkt subset They are listed here grouped by their original parent extension.

SH	Note to implementers You do not need to implement all of these instructions to implement Zkt. Rather, every one of these instructions that the core does implement must adhere to the requirements of Zkt.

RVI (Base Instruction Set)

Only basic arithmetic and slt* (for carry computations) are included. The data-independent timing requirement does not apply to HINT instruction encoding forms of these instructions.

RV32	RV64	Mnemonic	Instruction
✓	✓	lui rd, imm	[insns-lui]
✓	✓	auipc rd, imm	[insns-auipc]
✓	✓	addi rd, rs1, imm	[insns-addi]
✓	✓	slti rd, rs1, imm	[insns-slti]
✓	✓	sltiu rd, rs1, imm	[insns-sltiu]
✓	✓	xori rd, rs1, imm	[insns-xori]
✓	✓	ori rd, rs1, imm	[insns-ori]
✓	✓	andi rd, rs1, imm	[insns-andi]
✓	✓	slli rd, rs1, imm	[insns-slli]
✓	✓	srli rd, rs1, imm	[insns-srli]
✓	✓	srai rd, rs1, imm	[insns-srai]
✓	✓	add rd, rs1, rs2	[insns-add]
✓	✓	sub rd, rs1, rs2	[insns-sub]
✓	✓	sll rd, rs1, rs2	[insns-sll]
✓	✓	slt rd, rs1, rs2	[insns-slt]
✓	✓	sltu rd, rs1, rs2	[insns-sltu]
✓	✓	xor rd, rs1, rs2	[insns-xor]
✓	✓	srl rd, rs1, rs2	[insns-srl]
✓	✓	sra rd, rs1, rs2	[insns-sra]
✓	✓	or rd, rs1, rs2	[insns-or]
✓	✓	and rd, rs1, rs2	[insns-and]
	✓	addiw rd, rs1, imm	[insns-addiw]
	✓	slliw rd, rs1, imm	[insns-slliw]
	✓	srliw rd, rs1, imm	[insns-srliw]
	✓	sraiw rd, rs1, imm	[insns-sraiw]
	✓	addw rd, rs1, rs2	[insns-addw]
	✓	subw rd, rs1, rs2	[insns-subw]
	✓	sllw rd, rs1, rs2	[insns-sllw]
	✓	srlw rd, rs1, rs2	[insns-srlw]
	✓	sraw rd, rs1, rs2	[insns-sraw]

RVM (Multiply)

Multiplication is included; division and remaindering excluded.

RV32	RV64	Mnemonic	Instruction
✓	✓	mul rd, rs1, rs2	[insns-mul]
✓	✓	mulh rd, rs1, rs2	[insns-mulh]
✓	✓	mulhsu rd, rs1, rs2	[insns-mulhsu]
✓	✓	mulhu rd, rs1, rs2	[insns-mulhu]
	✓	mulw rd, rs1, rs2	[insns-mulw]

RVC (Compressed)

Same criteria as in RVI. Organised by quadrants.

RV32	RV64	Mnemonic	Instruction
✓	✓	c.nop	[insns-c_nop]
✓	✓	c.addi	[insns-c_addi]
✓	✓	c.addiw	[insns-c_addiw]
✓	✓	c.lui	[insns-c_lui]
✓	✓	c.srli	[insns-c_srli]
✓	✓	c.srai	[insns-c_srai]
✓	✓	c.andi	[insns-c_andi]
✓	✓	c.sub	[insns-c_sub]
✓	✓	c.xor	[insns-c_xor]
✓	✓	c.or	[insns-c_or]
✓	✓	c.and	[insns-c_and]
✓	✓	c.subw	[insns-c_subw]
✓	✓	c.addw	[insns-c_addw]
✓	✓	c.slli	[insns-c_slli]
✓	✓	c.mv	[insns-c_mv]
✓	✓	c.add	[insns-c_add]

RVK (Scalar Cryptography)

All K-specific instructions are included. Additionally, seed CSR latency should be independent of ES16 state output entropy bits, as that is a sensitive security parameter. See [crypto_scalar_appx_es_access].

RV32	RV64	Mnemonic	Instruction
✓		aes32dsi	[insns-aes32dsi]
✓		aes32dsmi	[insns-aes32dsmi]
✓		aes32esi	[insns-aes32esi]
✓		aes32esmi	[insns-aes32esmi]
	✓	aes64ds	[insns-aes64ds]
	✓	aes64dsm	[insns-aes64dsm]
	✓	aes64es	[insns-aes64es]
	✓	aes64esm	[insns-aes64esm]
	✓	aes64im	[insns-aes64im]
	✓	aes64ks1i	[insns-aes64ks1i]
	✓	aes64ks2	[insns-aes64ks2]
✓	✓	sha256sig0	[insns-sha256sig0]
✓	✓	sha256sig1	[insns-sha256sig1]
✓	✓	sha256sum0	[insns-sha256sum0]
✓	✓	sha256sum1	[insns-sha256sum1]
✓		sha512sig0h	[insns-sha512sig0h]
✓		sha512sig0l	[insns-sha512sig0l]
✓		sha512sig1h	[insns-sha512sig1h]
✓		sha512sig1l	[insns-sha512sig1l]
✓		sha512sum0r	[insns-sha512sum0r]
✓		sha512sum1r	[insns-sha512sum1r]
	✓	sha512sig0	[insns-sha512sig0]
	✓	sha512sig1	[insns-sha512sig1]
	✓	sha512sum0	[insns-sha512sum0]
	✓	sha512sum1	[insns-sha512sum1]
✓	✓	sm3p0	[insns-sm3p0]
✓	✓	sm3p1	[insns-sm3p1]
✓	✓	sm4ed	[insns-sm4ed]
✓	✓	sm4ks	[insns-sm4ks]

RVB (Bitmanip)

The [zbkb], [zbkx] and [zbkx] extensions are included in their entirety.

SH	Note to implementers Recall that rev, zip and unzip are pseudo-instructions representing specific instances of grevi, shfli and unshfli respectively.

RV32	RV64	Mnemonic	Instruction
✓	✓	clmul	[insns-clmul]
✓	✓	clmulh	[insns-clmulh]
✓	✓	xperm4	[insns-xperm4]
✓	✓	xperm8	[insns-xperm8]
✓	✓	ror	[insns-ror]
✓	✓	rol	[insns-rol]
✓	✓	rori	[insns-rori]
	✓	roriw	[insns-roriw]
✓	✓	andn	[insns-andn]
✓	✓	orn	[insns-orn]
✓	✓	xnor	[insns-xnor]
✓	✓	pack	[insns-pack]
✓	✓	packh	[insns-packh]
	✓	packw	[insns-packw]
✓	✓	brev8	[insns-brev8]
✓	✓	rev8	[insns-rev8]
✓		zip	[insns-zip]
✓		unzip	[insns-unzip]