Bug: ModSqrt entered infinite loop with p == 1

cronokirby · ericcornelissen · cronokirby · commit d39f5a274f7c · 2021-09-08T11:00:22.000+02:00
Thanks to Eric Cornelissen for discovering and responsibly reporting
this vulnerability.

The problem was that our tonelliShanks algorithm needed to calculate the
number of least significant zeros in p - 1. This was done by shifting
right until the LSB becomes 1. With p == 1, this process never ends,
because p - 1 == 0, sending us into an infinite loop.

This could be a potential vulnerability, because if a modulus can be
controlled by an adversary, they can cause a process to deadlock.

The fix is to simply check if p == 1, and return 0 in that case, which
makes perfect sense mathematically.

Checking the value of the modulus is also fine from a leakage
perspective, because ModSqrt is explicitly allowed to leak the value of
the modulus.

Co-authored-by: Eric Cornelissen &lt;ericornelissen@gmail.com&gt;
diff --git a/num.go b/num.go
@@ -1868,6 +1868,13 @@ func (z *Nat) tonelliShanks(x *Nat, p *Modulus) *Nat {
 	one := new(Nat).SetUint64(1)
 	trailingZeros := 1
 	reducedPminusOne := new(Nat).Sub(&p.nat, one, p.BitLen())
+	// In this case, p must have been 1, so sqrt(x) mod p is 0. Explicitly checking
+	// this avoids an infinite loop when trying to remove the least significant zeros.
+	// Checking this value is fine, since ModSqrt is explicitly allowed to branch
+	// on the value of the modulus.
+	if reducedPminusOne.EqZero() == 1 {
+		return z.SetUint64(0)
+	}
 	shrVU(reducedPminusOne.limbs, reducedPminusOne.limbs, 1)
 
 	nonSquare := new(Nat).SetUint64(2)
diff --git a/num_test.go b/num_test.go
@@ -1075,6 +1075,12 @@ func TestModSqrtExamples(t *testing.T) {
 	if x.Eq(z) != 1 {
 		t.Errorf("%+v != %+v", x, z)
 	}
+	m = ModulusFromUint64(1)
+	x.SetUint64(13)
+	x.ModSqrt(x, m)
+	if x.EqZero() != 1 {
+		t.Errorf("%+v != 0", x)
+	}
 }
 
 func TestBigExamples(t *testing.T) {

Original file line number	Diff line number	Diff line change
`@@ -1075,6 +1075,12 @@ func TestModSqrtExamples(t *testing.T) {`
`1075`	`1075`	`if x.Eq(z) != 1 {`
`1076`	`1076`	`t.Errorf("%+v != %+v", x, z)`
`1077`	`1077`	`}`
	`1078`	`+ m = ModulusFromUint64(1)`
	`1079`	`+ x.SetUint64(13)`
	`1080`	`+ x.ModSqrt(x, m)`
	`1081`	`+ if x.EqZero() != 1 {`
	`1082`	`+ t.Errorf("%+v != 0", x)`
	`1083`	`+ }`
`1078`	`1084`	`}`
`1079`	`1085`
`1080`	`1086`	`func TestBigExamples(t *testing.T) {`