Variable-time multiplication by nonce in adaptor signatures, EOTSs, ECDSA, and Schnorr signatures
Description
All of Babylon's implementations of Secp256k1-based signature schemes use a variable-time implementation of scalar multiplication, which gives a timing side channel that leaks information about their nonces, potentially allowing key recovery.
The adaptor signature module's encSign↗ and the EOTS module's signHash↗ functions use btcd's ScalarBaseMultNonConst with the nonce when computing signatures, and the ecdsa module's Sign↗ function uses btcd's SignCompact↗, which uses dcrd's SignCompact↗, which also uses ScalarBaseMultNonConst↗ with the nonce. The btcstaking module uses btcd's Sign↗, which is likewise affected.
The btcd library's implementation of ScalarBaseMultNonConst↗ uses dcrd's implementation of ScalarBaseMultNonConst↗, which takes a variable amount of time in the length of the scalar, which is a timing side channel.
The following benchmark demonstrates that the timing of ScalarBaseMultNonConst is approximately linear in the length of the scalar:
func benchScalarBaseMultNonConst(b *testing.B, kStr string) {
k := hexToModNScalar(kStr)
b.ReportAllocs()
b.ResetTimer()
var result JacobianPoint
for i := 0; i < b.N; i++ {
ScalarBaseMultNonConst(k, &result)
}
}
func BenchmarkTimingScalarBaseMult0(b *testing.B) {
benchScalarBaseMultNonConst(b, "0000000000000000000000000000000000000000000000000000000000000000")
}
func BenchmarkTimingScalarBaseMult1(b *testing.B) {
benchScalarBaseMultNonConst(b, "0000000000000000000000000000000000000000000000000000000000000001")
}
func BenchmarkTimingScalarBaseMult2_8(b *testing.B) {
benchScalarBaseMultNonConst(b, "000000000000000000000000000000000000000000000000000000000000000ff")
}
func BenchmarkTimingScalarBaseMult2_16(b *testing.B) {
benchScalarBaseMultNonConst(b, "0000000000000000000000000000000000000000000000000000000000000ffff")
}
func BenchmarkTimingScalarBaseMult2_32(b *testing.B) {
benchScalarBaseMultNonConst(b, "000000000000000000000000000000000000000000000000000000000ffffffff")
}
func BenchmarkTimingScalarBaseMult2_64(b *testing.B) {
benchScalarBaseMultNonConst(b, "000000000000000000000000000000000000000000000000ffffffffffffffff")
}
func BenchmarkTimingScalarBaseMult2_96(b *testing.B) {
benchScalarBaseMultNonConst(b, "0000000000000000000000000000000000000000ffffffffffffffffffffffff")
}
func BenchmarkTimingScalarBaseMult2_128(b *testing.B) {
benchScalarBaseMultNonConst(b, "00000000000000000000000000000000ffffffffffffffffffffffffffffffff")
}
func BenchmarkTimingScalarBaseMult2_160(b *testing.B) {
benchScalarBaseMultNonConst(b, "000000000000000000000000ffffffffffffffffffffffffffffffffffffffff")
}
func BenchmarkTimingScalarBaseMult2_192(b *testing.B) {
benchScalarBaseMultNonConst(b, "0000000000000000ffffffffffffffffffffffffffffffffffffffffffffffff")
}
func BenchmarkTimingScalarBaseMult2_255(b *testing.B) {
benchScalarBaseMultNonConst(b, "efffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff")
}
func BenchmarkTimingScalarBaseMultOrder(b *testing.B) {
benchScalarBaseMultNonConst(b, "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140")
}% go test -bench BenchmarkTimingScalarBase
goos: darwin
goarch: arm64
pkg: github.com/decred/dcrd/dcrec/secp256k1/v4
BenchmarkTimingScalarBaseMult0-12 8715968 137.7 ns/op 0 B/op 0 allocs/op
BenchmarkTimingScalarBaseMult1-12 8713813 138.2 ns/op 0 B/op 0 allocs/op
BenchmarkTimingScalarBaseMult2_8-12 8705205 137.7 ns/op 0 B/op 0 allocs/op
BenchmarkTimingScalarBaseMult2_16-12 8716395 137.7 ns/op 0 B/op 0 allocs/op
BenchmarkTimingScalarBaseMult2_32-12 1000000 1036 ns/op 0 B/op 0 allocs/op
BenchmarkTimingScalarBaseMult2_64-12 312010 3860 ns/op 0 B/op 0 allocs/op
BenchmarkTimingScalarBaseMult2_96-12 195265 6102 ns/op 0 B/op 0 allocs/op
BenchmarkTimingScalarBaseMult2_128-12 143324 8348 ns/op 0 B/op 0 allocs/op
BenchmarkTimingScalarBaseMult2_160-12 113204 10596 ns/op 0 B/op 0 allocs/op
BenchmarkTimingScalarBaseMult2_192-12 93406 12844 ns/op 0 B/op 0 allocs/op
BenchmarkTimingScalarBaseMult2_255-12 68043 17330 ns/op 0 B/op 0 allocs/op
BenchmarkTimingScalarBaseMultOrder-12 69144 17344 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/decred/dcrd/dcrec/secp256k1/v4 16.046sImpact
The Minerva↗ attack recovers signing keys from samples of signatures of different messages with different nonces, given timing information that correlates with the nonces' bit lengths. While the paper's noisiest data set contains measurements of a hardware device on the same network as the computer performing the timing (requiring a few thousand samples), the attack applies in principle to the timing data over a remote network, with an increase in the number of samples required to offset the increased variance.
Additionally, if signing is performed on a cloud host, other virtual machines on the same server or other servers in the same data center may be able to get low-variance timing samples. The LadderLeak↗ attack is able to handle a larger number of samples and may also be applicable.
Recommendations
As a short-term mitigation, for each scalar multiplication by a secret value k, generate a uniformly random blinding factor r and compute (k+r)G - rG instead of computing kG to mask the timing information.
As a longer-term fix, use a constant-time implementation of scalar multiplication for signature generation, such as Bitcoin's libsecp256k1↗, which is also used by Cosmos SDK↗.
Remediation
This issue has been acknowledged by Babylon Labs, and the mitigation of using a blinding factor was implemented in the following commits: