crypto/internal/constanttime: expose intrinsics to the FIPS 140-3 packages

Intrinsifying things inside the module (crypto/internal/fips140/subtle)
is asking for trouble, as the import paths are rewritten by the
GOFIPS140 mechanism, and we might have to support multiple modules
in the future.

Importing crypto/subtle from inside a FIPS 140-3 module is not allowed,
and is basically asking for circular dependencies.

Instead, break off the intrinsics into their own package
(crypto/internal/constanttime), and keep the byte slice operations
in crypto/internal/fips140/subtle. crypto/subtle then becomes a thin
dispatch layer.

Change-Id: I6a6a6964cd5cb5ad06e9d1679201447f5a811da4
Reviewed-on: https://go-review.googlesource.com/c/go/+/716120
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Filippo Valsorda <filippo@golang.org>
Reviewed-by: Jorropo <jorropo.pgm@gmail.com>

11 files changed, 82 insertions, 75 deletions

diff --git a/src/crypto/internal/constanttime/constant_time.go b/src/crypto/internal/constanttime/constant_time.go
new file mode 100644
index 0000000000..5525307195
--- /dev/null
+++ b/src/crypto/internal/constanttime/constant_time.go
@@ -0,0 +1,42 @@
+// Copyright 2025 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package constanttime
+
+// The functions in this package are compiler intrinsics for constant-time
+// operations. They are exposed by crypto/subtle and used directly by the
+// FIPS 140-3 module.
+
+// Select returns x if v == 1 and y if v == 0.
+// Its behavior is undefined if v takes any other value.
+func Select(v, x, y int) int {
+	// This is intrinsicified on arches with CMOV.
+	// It implements the following superset behavior:
+	// ConstantTimeSelect returns x if v != 0 and y if v == 0.
+	// Do the same here to avoid non portable UB.
+	v = int(boolToUint8(v != 0))
+	return ^(v-1)&x | (v-1)&y
+}
+
+// ByteEq returns 1 if x == y and 0 otherwise.
+func ByteEq(x, y uint8) int {
+	return int(boolToUint8(x == y))
+}
+
+// Eq returns 1 if x == y and 0 otherwise.
+func Eq(x, y int32) int {
+	return int(boolToUint8(x == y))
+}
+
+// LessOrEq returns 1 if x <= y and 0 otherwise.
+// Its behavior is undefined if x or y are negative or > 2**31 - 1.
+func LessOrEq(x, y int) int {
+	return int(boolToUint8(x <= y))
+}
+
+// boolToUint8 is a compiler intrinsic.
+// It returns 1 for true and 0 for false.
+func boolToUint8(b bool) uint8 {
+	panic("unreachable; must be intrinsicified")
+}
diff --git a/src/crypto/internal/fips140/edwards25519/tables.go b/src/crypto/internal/fips140/edwards25519/tables.go
index 801b76771d..7da3f7b15b 100644
--- a/src/crypto/internal/fips140/edwards25519/tables.go
+++ b/src/crypto/internal/fips140/edwards25519/tables.go
@@ -4,9 +4,7 @@
 
 package edwards25519
 
-import (
-	"crypto/internal/fips140/subtle"
-)
+import "crypto/internal/constanttime"
 
 // A dynamic lookup table for variable-base, constant-time scalar muls.
 type projLookupTable struct {
@@ -95,7 +93,7 @@ func (v *projLookupTable) SelectInto(dest *projCached, x int8) {
 	dest.Zero()
 	for j := 1; j <= 8; j++ {
 		// Set dest = j*Q if |x| = j
-		cond := subtle.ConstantTimeByteEq(xabs, uint8(j))
+		cond := constanttime.ByteEq(xabs, uint8(j))
 		dest.Select(&v.points[j-1], dest, cond)
 	}
 	// Now dest = |x|*Q, conditionally negate to get x*Q
@@ -111,7 +109,7 @@ func (v *affineLookupTable) SelectInto(dest *affineCached, x int8) {
 	dest.Zero()
 	for j := 1; j <= 8; j++ {
 		// Set dest = j*Q if |x| = j
-		cond := subtle.ConstantTimeByteEq(xabs, uint8(j))
+		cond := constanttime.ByteEq(xabs, uint8(j))
 		dest.Select(&v.points[j-1], dest, cond)
 	}
 	// Now dest = |x|*Q, conditionally negate to get x*Q
diff --git a/src/crypto/internal/fips140/nistec/generate.go b/src/crypto/internal/fips140/nistec/generate.go
index 7786dc556f..75b1ac60f0 100644
--- a/src/crypto/internal/fips140/nistec/generate.go
+++ b/src/crypto/internal/fips140/nistec/generate.go
@@ -140,8 +140,8 @@ const tmplNISTEC = `// Copyright 2022 The Go Authors. All rights reserved.
 package nistec
 
 import (
+	"crypto/internal/constanttime"
 	"crypto/internal/fips140/nistec/fiat"
-	"crypto/internal/fips140/subtle"
 	"errors"
 	"sync"
 )
@@ -467,7 +467,7 @@ func (table *{{.p}}Table) Select(p *{{.P}}Point, n uint8) {
 	}
 	p.Set(New{{.P}}Point())
 	for i := uint8(1); i < 16; i++ {
-		cond := subtle.ConstantTimeByteEq(i, n)
+		cond := constanttime.ByteEq(i, n)
 		p.Select(table[i-1], p, cond)
 	}
 }
diff --git a/src/crypto/internal/fips140/nistec/p224.go b/src/crypto/internal/fips140/nistec/p224.go
index 82bced251f..7965b18689 100644
--- a/src/crypto/internal/fips140/nistec/p224.go
+++ b/src/crypto/internal/fips140/nistec/p224.go
@@ -7,8 +7,8 @@
 package nistec
 
 import (
+	"crypto/internal/constanttime"
 	"crypto/internal/fips140/nistec/fiat"
-	"crypto/internal/fips140/subtle"
 	"errors"
 	"sync"
 )
@@ -333,7 +333,7 @@ func (table *p224Table) Select(p *P224Point, n uint8) {
 	}
 	p.Set(NewP224Point())
 	for i := uint8(1); i < 16; i++ {
-		cond := subtle.ConstantTimeByteEq(i, n)
+		cond := constanttime.ByteEq(i, n)
 		p.Select(table[i-1], p, cond)
 	}
 }
diff --git a/src/crypto/internal/fips140/nistec/p256.go b/src/crypto/internal/fips140/nistec/p256.go
index c957c54247..650bde4e73 100644
--- a/src/crypto/internal/fips140/nistec/p256.go
+++ b/src/crypto/internal/fips140/nistec/p256.go
@@ -7,8 +7,8 @@
 package nistec
 
 import (
+	"crypto/internal/constanttime"
 	"crypto/internal/fips140/nistec/fiat"
-	"crypto/internal/fips140/subtle"
 	"crypto/internal/fips140deps/byteorder"
 	"crypto/internal/fips140deps/cpu"
 	"errors"
@@ -458,7 +458,7 @@ func (table *p256Table) Select(p *P256Point, n uint8) {
 	}
 	p.Set(NewP256Point())
 	for i := uint8(1); i <= 16; i++ {
-		cond := subtle.ConstantTimeByteEq(i, n)
+		cond := constanttime.ByteEq(i, n)
 		p.Select(&table[i-1], p, cond)
 	}
 }
@@ -553,7 +553,7 @@ func (table *p256AffineTable) Select(p *p256AffinePoint, n uint8) {
 		panic("nistec: internal error: p256AffineTable.Select called with out-of-bounds value")
 	}
 	for i := uint8(1); i <= 32; i++ {
-		cond := subtle.ConstantTimeByteEq(i, n)
+		cond := constanttime.ByteEq(i, n)
 		p.x.Select(&table[i-1].x, &p.x, cond)
 		p.y.Select(&table[i-1].y, &p.y, cond)
 	}
@@ -618,7 +618,7 @@ func (p *P256Point) ScalarBaseMult(scalar []byte) (*P256Point, error) {
 	// the point at infinity (because infinity can't be represented in affine
 	// coordinates). Here we conditionally set p to the infinity if sel is zero.
 	// In the loop, that's handled by AddAffine.
-	selIsZero := subtle.ConstantTimeByteEq(sel, 0)
+	selIsZero := constanttime.ByteEq(sel, 0)
 	p.Select(NewP256Point(), t.Projective(), selIsZero)
 
 	for index >= 5 {
@@ -636,7 +636,7 @@ func (p *P256Point) ScalarBaseMult(scalar []byte) (*P256Point, error) {
 		table := &p256GeneratorTables[(index+1)/6]
 		table.Select(t, sel)
 		t.Negate(sign)
-		selIsZero := subtle.ConstantTimeByteEq(sel, 0)
+		selIsZero := constanttime.ByteEq(sel, 0)
 		p.AddAffine(p, t, selIsZero)
 	}
 
diff --git a/src/crypto/internal/fips140/nistec/p384.go b/src/crypto/internal/fips140/nistec/p384.go
index 318c08a979..352f1a806e 100644
--- a/src/crypto/internal/fips140/nistec/p384.go
+++ b/src/crypto/internal/fips140/nistec/p384.go
@@ -7,8 +7,8 @@
 package nistec
 
 import (
+	"crypto/internal/constanttime"
 	"crypto/internal/fips140/nistec/fiat"
-	"crypto/internal/fips140/subtle"
 	"errors"
 	"sync"
 )
@@ -333,7 +333,7 @@ func (table *p384Table) Select(p *P384Point, n uint8) {
 	}
 	p.Set(NewP384Point())
 	for i := uint8(1); i < 16; i++ {
-		cond := subtle.ConstantTimeByteEq(i, n)
+		cond := constanttime.ByteEq(i, n)
 		p.Select(table[i-1], p, cond)
 	}
 }
diff --git a/src/crypto/internal/fips140/nistec/p521.go b/src/crypto/internal/fips140/nistec/p521.go
index 8ade8a3304..429f637993 100644
--- a/src/crypto/internal/fips140/nistec/p521.go
+++ b/src/crypto/internal/fips140/nistec/p521.go
@@ -7,8 +7,8 @@
 package nistec
 
 import (
+	"crypto/internal/constanttime"
 	"crypto/internal/fips140/nistec/fiat"
-	"crypto/internal/fips140/subtle"
 	"errors"
 	"sync"
 )
@@ -333,7 +333,7 @@ func (table *p521Table) Select(p *P521Point, n uint8) {
 	}
 	p.Set(NewP521Point())
 	for i := uint8(1); i < 16; i++ {
-		cond := subtle.ConstantTimeByteEq(i, n)
+		cond := constanttime.ByteEq(i, n)
 		p.Select(table[i-1], p, cond)
 	}
 }
diff --git a/src/crypto/internal/fips140/rsa/pkcs1v22.go b/src/crypto/internal/fips140/rsa/pkcs1v22.go
index 94e7345996..29c47069a3 100644
--- a/src/crypto/internal/fips140/rsa/pkcs1v22.go
+++ b/src/crypto/internal/fips140/rsa/pkcs1v22.go
@@ -9,6 +9,7 @@ package rsa
 
 import (
 	"bytes"
+	"crypto/internal/constanttime"
 	"crypto/internal/fips140"
 	"crypto/internal/fips140/drbg"
 	"crypto/internal/fips140/sha256"
@@ -432,7 +433,7 @@ func DecryptOAEP(hash, mgfHash hash.Hash, priv *PrivateKey, ciphertext []byte, l
 	hash.Write(label)
 	lHash := hash.Sum(nil)
 
-	firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
+	firstByteIsZero := constanttime.ByteEq(em[0], 0)
 
 	seed := em[1 : hash.Size()+1]
 	db := em[hash.Size()+1:]
@@ -458,11 +459,11 @@ func DecryptOAEP(hash, mgfHash hash.Hash, priv *PrivateKey, ciphertext []byte, l
 	rest := db[hash.Size():]
 
 	for i := 0; i < len(rest); i++ {
-		equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
-		equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
-		index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
-		lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
-		invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
+		equals0 := constanttime.ByteEq(rest[i], 0)
+		equals1 := constanttime.ByteEq(rest[i], 1)
+		index = constanttime.Select(lookingForIndex&equals1, i, index)
+		lookingForIndex = constanttime.Select(equals1, 0, lookingForIndex)
+		invalid = constanttime.Select(lookingForIndex&^equals0, 1, invalid)
 	}
 
 	if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
diff --git a/src/crypto/internal/fips140/subtle/constant_time.go b/src/crypto/internal/fips140/subtle/constant_time.go
index fa7a002d3f..fc1e307985 100644
--- a/src/crypto/internal/fips140/subtle/constant_time.go
+++ b/src/crypto/internal/fips140/subtle/constant_time.go
@@ -5,6 +5,7 @@
 package subtle
 
 import (
+	"crypto/internal/constanttime"
 	"crypto/internal/fips140deps/byteorder"
 	"math/bits"
 )
@@ -24,7 +25,7 @@ func ConstantTimeCompare(x, y []byte) int {
 		v |= x[i] ^ y[i]
 	}
 
-	return ConstantTimeByteEq(v, 0)
+	return constanttime.ByteEq(v, 0)
 }
 
 // ConstantTimeLessOrEqBytes returns 1 if x <= y and 0 otherwise. The comparison
@@ -58,20 +59,6 @@ func ConstantTimeLessOrEqBytes(x, y []byte) int {
 	return int(b ^ 1)
 }
 
-// ConstantTimeSelect returns x if v == 1 and y if v == 0.
-// Its behavior is undefined if v takes any other value.
-func ConstantTimeSelect(v, x, y int) int { return ^(v-1)&x | (v-1)&y }
-
-// ConstantTimeByteEq returns 1 if x == y and 0 otherwise.
-func ConstantTimeByteEq(x, y uint8) int {
-	return int((uint32(x^y) - 1) >> 31)
-}
-
-// ConstantTimeEq returns 1 if x == y and 0 otherwise.
-func ConstantTimeEq(x, y int32) int {
-	return int((uint64(uint32(x^y)) - 1) >> 63)
-}
-
 // ConstantTimeCopy copies the contents of y into x (a slice of equal length)
 // if v == 1. If v == 0, x is left unchanged. Its behavior is undefined if v
 // takes any other value.
@@ -86,11 +73,3 @@ func ConstantTimeCopy(v int, x, y []byte) {
 		x[i] = x[i]&xmask | y[i]&ymask
 	}
 }
-
-// ConstantTimeLessOrEq returns 1 if x <= y and 0 otherwise.
-// Its behavior is undefined if x or y are negative or > 2**31 - 1.
-func ConstantTimeLessOrEq(x, y int) int {
-	x32 := int32(x)
-	y32 := int32(y)
-	return int(((x32 - y32 - 1) >> 31) & 1)
-}
diff --git a/src/crypto/internal/fips140deps/fipsdeps_test.go b/src/crypto/internal/fips140deps/fipsdeps_test.go
index 3eaae1830d..29a56047c3 100644
--- a/src/crypto/internal/fips140deps/fipsdeps_test.go
+++ b/src/crypto/internal/fips140deps/fipsdeps_test.go
@@ -28,6 +28,9 @@ var AllowedInternalPackages = map[string]bool{
 
 	// randutil.MaybeReadByte is used in non-FIPS mode by GenerateKey functions.
 	"crypto/internal/randutil": true,
+
+	// constanttime are the constant-time intrinsics.
+	"crypto/internal/constanttime": true,
 }
 
 func TestImports(t *testing.T) {
diff --git a/src/crypto/subtle/constant_time.go b/src/crypto/subtle/constant_time.go
index 8eeff3b629..14c911101b 100644
--- a/src/crypto/subtle/constant_time.go
+++ b/src/crypto/subtle/constant_time.go
@@ -6,63 +6,47 @@
 // code but require careful thought to use correctly.
 package subtle
 
-import "crypto/internal/fips140/subtle"
+import (
+	"crypto/internal/constanttime"
+	"crypto/internal/fips140/subtle"
+)
+
+// These functions are forwarded to crypto/internal/constanttime for intrinsified
+// operations, and to crypto/internal/fips140/subtle for byte slice operations.
 
 // ConstantTimeCompare returns 1 if the two slices, x and y, have equal contents
 // and 0 otherwise. The time taken is a function of the length of the slices and
 // is independent of the contents. If the lengths of x and y do not match it
 // returns 0 immediately.
 func ConstantTimeCompare(x, y []byte) int {
-	if len(x) != len(y) {
-		return 0
-	}
-
-	var v byte
-
-	for i := 0; i < len(x); i++ {
-		v |= x[i] ^ y[i]
-	}
-
-	return ConstantTimeByteEq(v, 0)
+	return subtle.ConstantTimeCompare(x, y)
 }
 
 // ConstantTimeSelect returns x if v == 1 and y if v == 0.
 // Its behavior is undefined if v takes any other value.
 func ConstantTimeSelect(v, x, y int) int {
-	// This is intrinsicified on arches with CMOV.
-	// It implements the following superset behavior:
-	// ConstantTimeSelect returns x if v != 0 and y if v == 0.
-	// Do the same here to avoid non portable UB.
-	v = int(constantTimeBoolToUint8(v != 0))
-	return ^(v-1)&x | (v-1)&y
+	return constanttime.Select(v, x, y)
 }
 
 // ConstantTimeByteEq returns 1 if x == y and 0 otherwise.
 func ConstantTimeByteEq(x, y uint8) int {
-	return int(constantTimeBoolToUint8(x == y))
+	return constanttime.ByteEq(x, y)
 }
 
 // ConstantTimeEq returns 1 if x == y and 0 otherwise.
 func ConstantTimeEq(x, y int32) int {
-	return int(constantTimeBoolToUint8(x == y))
+	return constanttime.Eq(x, y)
 }
 
 // ConstantTimeCopy copies the contents of y into x (a slice of equal length)
 // if v == 1. If v == 0, x is left unchanged. Its behavior is undefined if v
 // takes any other value.
 func ConstantTimeCopy(v int, x, y []byte) {
-	// Forward this one since it gains nothing from compiler intrinsics.
 	subtle.ConstantTimeCopy(v, x, y)
 }
 
 // ConstantTimeLessOrEq returns 1 if x <= y and 0 otherwise.
 // Its behavior is undefined if x or y are negative or > 2**31 - 1.
 func ConstantTimeLessOrEq(x, y int) int {
-	return int(constantTimeBoolToUint8(x <= y))
-}
-
-// constantTimeBoolToUint8 is a compiler intrinsic.
-// It returns 1 for true and 0 for false.
-func constantTimeBoolToUint8(b bool) uint8 {
-	panic("unreachable; must be intrinsicified")
+	return constanttime.LessOrEq(x, y)
 }